CSC 539: Operating Systems Structure and Design
Fall 2003
HW4: Memory Management
Exercises from the text: 9.5, 9.8, 10.2, 10.5, 10.11.
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 3 0 1 2 0 1 0 2 3
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?
- 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?