Page Replacement Algorithms: FIFO, LRU
Operating Systems Lab Class 9
In the previous Lab we have seen that every process in a computer system needs some storage in primary memory (RAM) in order to be eligible to execute on the CPU. In a non-demand paging system, it is assumed that all the pages of a process’ logical address space are kept in physical memory’s frames. Each process has a page table (PT) and lets the OS/CPU translate virtual addresses of locations in a desired page into physical addresses in the frames that hold the desired pages.
In a demand paging system, only some of the pages are kept in physical memory. The remainder are kept in swap space set aside on the hard drive for processes in the system. As in non-demand paging, a PT helps the OS/CPU translate virtual memory addresses into physical memory ad- dresses, but now it also keeps track of whether the desired page is in fact currently in physical memory. If a process refers to a virtual address of a page that is in memory, translate proceeds as for non-demand paging. However, if the desired page is not resident in some frame in physical memory, then a page fault occurs. This means that the desired page must be loaded from swap space into some frame in physical memory.
In Lab 8 we assumed that physical memory is the same size as the virtual address space. In practice, physical memory is typically much smaller than a virtual address space. A required modification is to use a smaller physical address space. This change will require modifying your program so that it keeps track of free page frames as well as implementing a page-replacement policy using: 1. First-In-First-Out (FIFO) and 2. Least Recently Used (LRU).
The following figure describes the address translation task as discussed above.
In this lab session you will write a program that implements the FIFO and LRU page-replacement algorithms. We aim to extend the virtual memory manager that has been implemented in Lab 8.
1 Getting Started
1. Download the os-lab9.zip archive from Canvas and unzip into your workspace.
2. Start NetBeans and open the project. The project should contain six files in the src directory: PageReplacement.java (contains the main method), TLB.java, PageTable.java, ReplacementAlgorithm.java, FIFO.java and LRU.java.
3. Before you begin, read through the code and then compile it before making any modifications. This should work without problems.
1
2 Implementation
1. Design and implement the two classes: LRU and FIFO, that extend the abstract class ReplacementAlgorithm. Each of these classes will implement the updatePageTable() method, one class using the LRU page-replacement algorithm and the other using the FIFO algorithm.
2. Once you have implemented the FIFO and LRU algorithms, experiment with a different number of pages for a given logical addresses and record the number of page faults.
The program will work as follows. Running
java PageReplacement 1234 1 4 3 1 FIFO 1 3 15 4 7 5 15 2 0 7
• args[0]=1234: seed 1234 to randomly initialise the page table (not used! Why?) • args[1]=1: 21 TLB entries
• args[2]=4: 24 = 16 logical addresses
• args[3]=3: 23 = 8 physical addresses
• args[4]=1: 21 = 2B = page size = frame size
• args[5]=FIFO (or LRU): page replacement algoritm
• and the sequence of logical addresses to be translated 1, 3, 15, 4, 7, 5, 15, 2, 0, 7.
Based on the above inputs, method printMemoryDetails() prints the following:
*************************************************
[Virtual Memory]:
Page size: 2
4-bit logical addresses
then Logical Address Space = 16
1-bit offset , and 3-bit page
pages = 8
[Physical Memory]:
Frame size: 2
3-bit physical addresses
then Physical Address Space = 8
1-bit offset, and 2-bit frame
frames = 4
[TLB]:
TLB size = 2 entries
*************************************************
as shown in the following figure.
Logical CPU address
page offset
page offset
011
1
(7)
Physical address
frame offset
(1)
000
1
Logical Addresses
Page Table
TLB
Page 0 0 Page 1 2
000 0 1 000 1
Physical Addresses
Frame 0 0 1
Frame 1 2 3
Frame 2 4 5
Frame 3 6 7
frame offset
000 001 010 011 100 101
11 0 11 1
page
frame
3
0
…
1
…
2
…
3
001 0 3 001 1
Page 2 4 Page 3 6
010 0 5 010 1
011 0 7 011 1
Page 4 8 Page 5 10
100 0 9 100 1
101 0 11 101 1
Physical Memory
page
frame
3
0
…
…
Page 6 12 Page 7 14
110 0 13 110 1
111 0 15 111 1
Virtual Memory
The full output of running this example can be found in the Appendix section. The follow- ing two tables visualise the allocation to frames based on FIFO and LRU, note that frames are initially empty.
FIFO:
Logical Address
1
3
15
4
7
5
15
2
0
7
Page
0
1
7
2
3
2
7
1
0
3
frame 0
0
0
0
0
3
3
3
3
3
3
frame 1
1
1
1
1
1
1
1
0
0
frame 2
7
7
7
7
7
7
7
7
frame 3
2
2
2
2
2
2
2
Page faults
PF
PF
PF
PF
PF
PF
LRU:
Logical Address
1
3
15
4
7
5
15
2
0
7
Page
0
1
7
2
3
2
7
1
0
3
frame 0
0
0
0
0
3
3
3
3
0
0
frame 1
1
1
1
1
1
1
1
1
1
frame 2
7
7
7
7
7
7
7
7
frame 3
2
2
2
2
2
2
3
Page faults
PF
PF
PF
PF
PF
PF
PF
4. You have to fill in gaps in five files.
3
•
•
• • •
PageReplacement.java contains the main method, which parses the command line pa- rameters allocates a PageTable, a TLB and FIFO or LRU and then performs translation of logical addresses passed to the program on the command line into physical addresses in the translate() method. You have to implement the parsing of command line arguments and the translate() method. The implementation of the latter will require the use of bitwise operators (see Section 4 of Lab Sheet 8). You are provided with a method toBinary() for printing integers as binary Strings.
PageTable.java has a find() method for returning the frame number corresponding to a given page number. The constructor of PageTable initialises the page table such that frames are initially empty. The frames will be occupied by the incoming pages and when the physical memory will be fully occupied, any new incoming page will be translated based on FIFO or LRU algorithm. The only part that you have to complete is the allocation of a page table of correct size.
TLB.java implements a translation look-aside buffer as a direct-mapped cache, associat- ing the least significant bits with a cache slot. We assume this implementation has been completed at Lab 8.
FIFO.java has a updatePageTable() method which replaces the oldest page number in the page table by a new incoming page. If the page already exists in the page table then there is nothing to do.
LRU.java has a updatePageTable() method which replaces the least recently used page in the page table by a new incoming page. If the page already exists in the page table then there is nothing to do.
Reflection
5. Try to translate different sequences of logical addresses and compare the page faults, does one algorithm perform better than the other?
6. Extra question 1: Consider the following page reference string:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
How many page faults would occur for the FIFO and LRU page replacement algorithms, assuming one, two, three, four, five, six, or seven frames? Remember all frames are initially empty, so your first unique pages will all cost one fault each. Run your program to check for your answers.
7. Extra question 2: What are the following values on your machine,
Total physical memory:
……………..
Total paging file size:
……………..
Cached:
……………..
Total virtual memory:
……………..
Available:
……………..
Committed Memory:
……………..
Free/In Use: :
……………..
Hard(Page) Faults/sec:
……………..
Page Table size:
……………..
Processes/Threads:
……………..
4 References
https://goo.gl/lPstQr
Appendix
Runningjava PageReplacement 1234 1 4 3 1 FIFO 1 3 15 4 7 5 15 2 0 7gives:
Incoming Logical Addresses: 1 3 15 4 7 5 15 2 0 7
Initially:
==============
| Page table:|
==============
p: f
-1: 0
-1: 1
-1: 2 -1: 3
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
—–
| TLB:|
—–
p:f x:x x:x
FIFO
=============================================================
New incoming address:
Logical address: (1) 0001
Update table: incoming pagenumber = 0
==============
| Page table:|
==============
p: f
0: 0
-1: 1
-1: 2
-1: 3
-1 0
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1-1-1-1-1-1-1-1-1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Lookup page number (0) 000
TLB Miss!
Found frame number (0) 00
001 –> 001
1 –> 1
—–
| TLB:|
—–
p:f 0:0 x:x
=============================================================
New incoming address:
Logical address: (3) 0011
Update table: incoming pagenumber = 1
==============
| Page table:|
==============
p: f
0: 0
1: 1
-1: 2
-1: 3
0 -1 -1 -1 -1 -1 -1 -1 -1
1 -1 -1 -1 -1 -1 -1 -1 -1
-1 0
-1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Lookup page number (1) 001
TLB Miss!
Found frame number (1) 01
011 –> 011
3 –> 3 —–
| TLB:| —–
p:f 0:0 1:1
=============================================================
New incoming address:
Logical address: (15) 1111
Update table: incoming pagenumber = 7
==============
| Page table:|
==============
p: f
0: 0 1: 1 7: 2
-1: 3
0-1-1-1-1-1-1-1 1-1-1-1-1-1-1-1 7-1-1-1-1-1-1-1
-1 0 0
-1 -1 1
-1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Lookup page number (7) 111
TLB Miss!
Found frame number (2) 10
111 –> 101
15 –> 5 —–
| TLB:| —–
p:f 0:0 7:2
=============================================================
New incoming address:
Logical address: (4) 0100
Update table: incoming pagenumber = 2
==============
| Page table:|
==============
p: f
0: 0
1: 1
7: 2
2: 3
-10 0
-1 -1 1
-1 -1 -1
-1 -1 -1 -1
Lookup page number (2) 010
TLB Miss!
Found frame number (3) 11
100 –> 110
4 –> 6 —–
| TLB:| —–
p:f 2:3 7:2
0 0-1-1-1-1-1-1 1 1-1-1-1-1-1-1 7 7-1-1-1-1-1-1
2 -1 -1 -1 -1 -1 -1
=============================================================
New incoming address:
Logical address: (7) 0111
Update table: incoming pagenumber = 3
==============
| Page table:|
==============
p: f
3: 0
1: 1
7: 2
2: 3
-10 -1 -1 -1 -1 -1 -1
0 0 0
1 1 1
-1 7 7
-1 -1 2
3-1-1-1-1-1 1-1-1-1-1-1 7-1-1-1-1-1 2-1-1-1-1-1
Lookup page number (3) 011
TLB Miss!
Found frame number (0) 00
111 –> 001
7 –> 1 —–
| TLB:| —–
p:f 2:3 3:0
=============================================================
New incoming address:
Logical address: (5) 0101
Update table: incoming pagenumber = 2
==============
| Page table:|
==============
p: f
3: 0
1: 1
7: 2
2: 3
-1 0 0 0 0 3 3 -1 -1 -1 -1
-1 -1 1 1 1 1
-1 -1 -1 7 7 7
-1 -1 -1 -1 2 2
Lookup page number (2) 010
TLB hit!
Found frame number (3) 11
101 –> 111
5 –> 7 —–
| TLB:| —–
p:f 2:3 3:0
1 -1 -1 -1 -1
7 -1 -1 -1 -1
2 -1 -1 -1 -1
=============================================================
New incoming address:
Logical address: (15) 1111
Update table: incoming pagenumber = 7
==============
| Page table:|
==============
p: f
3: 0
1: 1
7: 2
2: 3
-1 0 0 0 0 3 3 3 -1 -1 -1
-1 -1 1 1 1 1 1 1 -1 -1 -1
-1 -1 -1 7 7
-1 -1 -1 -1 2
Lookup page number (7) 111
TLB Miss!
Found frame number (2) 10
111 –> 101
15 –> 5
—–
| TLB:|
—–
p:f 2:3 7:2
7 7 2 2
7-1-1-1 2-1-1-1
=============================================================
New incoming address:
Logical address: (2) 0010
Update table: incoming pagenumber = 1
==============
| Page table:|
==============
p: f
3: 0
1: 1
7: 2
2: 3
-1 0 0 0 0 3 3 3 3 -1 -1
-1 -1 1 1 1 1 1 1 1 -1 -1
-1 -1 -1 7 7 7 7 7 7 -1 -1
-1 -1 -1 -1 2 2 2
Lookup page number (1) 001
TLB Miss!
Found frame number (1) 01
010 –> 010
2 –> 2
—–
| TLB:|
—–
p:f 2:3 1:1
22-1-1
=============================================================
New incoming address:
Logical address: (0) 0000
Update table: incoming pagenumber = 0
==============
| Page table:|
==============
p: f
3: 0
0: 1
7: 2
2: 3
-1 0 0 0 0 3 3 3 3 3 -1
-1 -1 1 1 1 1 1 1 1 0 -1
-1 -1 -1 7 7 7 7 7 7 7 -1
-1 -1 -1 -1 2 2 2 2 2 2 -1
Lookup page number (0) 000
TLB Miss!
Found frame number (1) 01
000 –> 010
0 –> 2 —–
| TLB:| —–
p:f 0:1 1:1
=============================================================
New incoming address:
Logical address: (7) 0111
Update table: incoming pagenumber = 3
==============
| Page table:|
==============
p: f
3: 0
0: 1
7: 2
2: 3
-1 0 0 0 0 3 3 3 3 3 3
-1 -1 1 1 1 1 1 1 1 0 0
-1 -1 -1 7 7 7 7 7 7 7 7
-1 -1 -1 -1 2 2 2 2 2 2 2
Lookup page number (3) 011
TLB Miss!
Found frame number (0) 00
111 –> 001
7 –> 1 —–
| TLB:| —–
p:f 0:1 3:0
Page Faults: 6
TLB hit rate: 0.1
The effective memory-access time: 190.0