CSC 539: Operating Systems Structure and Design
Spring 2005

HW4: Memory Management


Exercises from the Text

(8.3) Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)? Which algorithm makes the most efficient use of memory?
(8.9) Consider a paging system with the page table stored in memory.
  1. If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?
  2. If we add associative registers, and 75 percent of all page-table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.)
(8.10) Why are segmentation andpaging sometimes combined into one scheme?
(9.5) Assume we have a demand-paged memory. The page table is held in registers. It takes 8 milliseconds to service a page fault if an empty page is available or the replaced page is not modified, and 20 milliseconds if the replaced page is modified. Memory access time is 100 nanoseconds. Assume that the page to be replaced is modified 70 percent of the time. What is the maximum acceptable page-fault rate for an effective access time of no more than 200 nanoseconds?
(9.7) Discuss situations under which the least frequently used page-replacement algorithm generates fewer page faults than the least recently used page replacement algorithm. Also discuss under what circumstance does the opposite holds.
(9.15) What is the cause of thrashing? How does the system detect thrashing? Once it detects thrashing, what can the system do to eliminate this problem?

Virtual Memory Simulator

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 Enter the page-reference string: 0 1 2 1 3 1 3 2 1 3 1 -1 0: PAGE FAULT -- inserting page 0 into frame 0 0: page found at frame 0 1: PAGE FAULT -- inserting page 1 into frame 1 1: page found at frame 1 2: PAGE FAULT -- swapping page 2 into frame 0 2: page found at frame 0 1: page found at frame 1 3: PAGE FAULT -- swapping page 3 into frame 1 3: page found at frame 1 1: PAGE FAULT -- swapping page 1 into frame 0 1: page found at frame 0 3: page found at frame 1 2: PAGE FAULT -- swapping page 2 into frame 1 2: page found at frame 1 1: page found at frame 0 3: PAGE FAULT -- swapping page 3 into frame 0 3: page found at frame 0 1: PAGE FAULT -- swapping page 1 into frame 1 1: page found 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?