CSC 539: Operating Systems Structure and Design
Fall 2002
HW5: Virtual Memory
The following questions concern a simple virtual memory simulator,
defined by the following files:
vm.cpp,
PageTable.h, and
PageTable.cpp.
The simulator first prompts the user for the number of pages in logical
memory and the number of frames in physical memory (page and
frame numbers are assumed to start at 0). It then reads a succession of page
numbers representing virtual memory accesses and carries out those
accesses, swapping pages into physical memory when page faults occur.
The results of each memory access, whether the page was found in memory
or else swapped in, is displayed after each access. The simulator
currently uses a FIFO page replacement algorithm. For example:
Enter number of pages in logical memory:
4
Enter number of frames in physical memory:
2
0 1 2 1 3 1 3 2 1 3 1
0: PAGE FAULT -- added at frame 0
1: PAGE FAULT -- added at frame 1
2: PAGE FAULT -- replaces page 0 at frame 0
1: found at frame 1
3: PAGE FAULT -- replaces page 1 at frame 1
1: PAGE FAULT -- replaces page 2 at frame 0
3: found at frame 1
2: PAGE FAULT -- replaces page 3 at frame 1
1: found at frame 0
3: PAGE FAULT -- replaces page 1 at frame 0
1: PAGE FAULT -- replaces page 2 at frame 1
|
- Build a C++ project and execute the simulator for the page-reference
string
0 1 2 1 2 0 1 2 1 0 1
assuming 1, 2, 3, and 4 physical frames, respectively. Provide printouts
of the simulation in each case (by redirecting output to a file and
printing the file). How many page faults occurred in each case?
- Consider the following page-reference string:
3 2 1 0 3 2 4 3 2 1 0 4 2 3 2 1 0 4
Does this string demonstrate Belady's anomaly using FIFO? That is, is it
ever the case that increasing the size of physical memory increases the
number of page faults? Document your answer.
- Modify the virtual memory simulator so that the Least Recently Used
(LRU) page replacement algorithm is used. This should only require
minimal changes to the PageTable code. Execute your modified simulator on the
page-reference string from Question 1 assuming 1, 2, 3, and 4 physical
frames, respectively. Provide printouts of the simulation in each case.
How many page faults occurred in each case?
- For each of the cases in the previous exercise, how close was LRU to
optimal? That is, given a number of physical frames, how did the number
of page faults using LRU compare to the number of faults that would occur
using the OPTIMAL strategy?
- Execute your modified simulator on the following page-reference
string, assuming 8 physical frames:
0 1 2 3 4 8 9 10 11 12 5 6 7 8 2 3 4 8 9 10 11 0 1 2
5 6 5 6 5 6 13 14 15 0 1 2 3 4 8 9 10 11 12 13 14 15
Provide a printout of the simulation. How many page faults occurred?