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


  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?

  2. 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.

  3. 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?

  4. 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?