Read Chapter 9 – Virtual Memory
Write a program to simulate the Least-Recently-Used (LRU) Page Replacement Algorithm that appears on page 440 of the textbook. In particular, the simulator should accept the following input from standard input (stdin):
Number of Virtual Pages
Number of Page Frames Available (not used by page table)
Number of References
Page Referenced Read or Write (0 or 1, respectively) duration
Page Referenced Read or Write (0 or 1, respectively) duration
: :
For example:
5
3
2
0 0 2
1 1 1
3 0 1
is valid input. There are 5 virtual pages (numbered 0, 1, ... 4), 3 page frames (numbered 0, 1, 2) in memory, 3 references listed: page 0 is read from for 2 clock ticks, page 1 is written to for 1 clock tick, and page 3 is read from for 1 clock tick.
Maintain a page table as an array. Use page number as an index to the array. The array should include an R-bit, an M-bit, and a Present/Absent bit, as well as the frame currently mapped.
R-bit = 1 if page has been referenced recently (read/write)
M-bit = 1 if page has been modified (needs to be written to disk)
Corresponding to the previous example, the page table could look like this way:
1 0 1 0
1 1 1 1
0 0 0 0
1 0 1 2
0 0 0 0
The first row indicates the virtual page 0 is mapped to the physical page 0. The page has been referenced and is present in the physical memory.
Assume that the R-bit is reset to 0 after a set of 6 pages have been referenced. This is to simulate a reset after each clock interrupt.
The output from the simulator should indicate whenever a fault occurs, and which page has been evicted (if one is evicted). Always select the smallest numbered page in a class to be evicted. In addition, the output should include the total number of faults that occurred.
The possible output would look something like:
: :
Fault: no page evicted, page 0 brought in to memory.
Fault: page 2 evicted, page 3 brought in to memory.
: :
Total number of faults is 23.
What to Hand In:
Email your source code files to barbara.hecker@csueastbay.edu with the subject line of [your last name] + “Prog7”
Use a stack implementation of an array in C. Then pull from the bottom of the stack for the least recently used, and the top of the stack for the most recently used.
