Another way in which the memory manager enhances the ability of the operating system to support multiple process running simultaneously is by the use of virtual memory. According the Nutt [1997], "virtual memory strategies allow a process to use the CPU when only part of its address space is loaded in the primary memory. In this approach, each process's address space is partitioned into parts that can be loaded into primary memory when they are needed and written back to secondary memory otherwise." Another consequence of this approach is that the system can run programs which are actually larger than the primary memory of the system, hence the idea of "virtual memory." Brookshear [1997] explains how this is accomplished:

"Suppose, for example, that a main memory of 64 megabytes is required but only 32 megabytes is actually available. To create the illusion of the larger memory space, the memory manager would divide the required space into units called pages and store the contents of these pages in mass storage. A typical page size is no more than four kilobytes. As different pages are actually required in main memory, the memory manager would exchange them for pages that are no longer required, and thus the other software units could execute as though there were actually 64 megabytes of main memory in the machine."

In order for this system to work, the memory manager must keep track of all the pages that are currently loaded into the primary memory. This information is stored in a page table maintained by the memory manager. A page fault occurs whenever a process requests a page that is not currently loaded into primary memory. To handle page faults, the memory manager takes the following steps:

  1. The memory manager locates the missing page in secondary memory.
  2. The page is loaded into primary memory, usually causing another page to be unloaded.
  3. The page table in the memory manager is adjusted to reflect the new state of the memory.
  4. The processor reexecutes the instructions which caused the page fault.

The applet below shows a simplified simulation of virtual memory paging. The applet starts off with 8 processes that take turns referencing memory locations. Dark blue indicates the process is the running one, and light blue indicates the process is ready to run but is waiting for its turn. There are 16 virtual memory pages and 8 page frames in primary memory. Initially the page frames are white indicating that the frame is empty. As the simulation progress, the running process randomly chooses a page. If a page fault occurs, the process changes color to red, and the requested page is brought into primary memory. All "new" pages in the page table are colored green. If a process writes to the page, then the page changes color to yellow indicating that its contents have changed and it should be copied back to disk before being replaced by another page. [Coutinho 1996].

Virtual Memory Simulation
Courtesy of Murilo Coutinho, USC Information Sciences Institute

Whenever a page fault occurs and all the page frames in primary memory have been loaded with a page from virtual memory, the memory manager must decided which page to swap out of primary memory in order to load the requested page. Various different algorithms known as replacement polices are employed to determine the best page to replace. Several of these polices are described below.

Random Replacement

In the Random Replacement policy, the replaced page is chosen at random from all the pages currently in primary memory. In general, random replacement does not perform well.

First In First Out

In the First In First Out (FIFO) policy, "the operating system maintains a list of all pages currently in memory, with the page at the head of the list the oldest one and the page at the tail the most recent arrival. On a page fault, the page at the head is removed and the new page added to the tail of the list" [Tanenbaum and Woodhull 1997]. Thus, the oldest page is always replaced. One problem here is that the age of the page does not necessarily imply that the page is not being used. Some pages may be heavily accessed for quite some time. Replacing these pages would be a poor choice.

Second Chance

The Second Chance (SC) policy is a slight modification of FIFO in order to avoid the problem of replacing a heavily used page. In this policy, a reference bit R is used to keep track of pages that have been recently referenced. This bit is set to 1 each time the page is referenced. Periodically, all the reference bits are set to 0 by the operating system to distinguish pages that have not been reference recently from those that have been. Using this bit, the operating system can determine whether old pages are still being used (i.e., R = 1). If so, the page is moved to the end of the list of pages, and its load time is updated as though it had just arrived in memory. Then the search continues. Thus heavily accessed pages are given a "second chance" [Tanenbaum and Woodhull 1997].

Least Recently Used

The Least Recently Used (LRU) policy takes advantage of the heuristic that pages which have been accessed recently are more likely to be accessed again. Thus, this policy always replaces the page which has been in primary memory the longest without being accessed. One example of why this policy is effective is that "programs are written to contain loops, which cause the main line of the code to execute repeatedly, with special case code rarely being executed." [Nutt 1997]. The pages which contain the code for the loop are likely to be accessed repeatedly.

Least Frequently Used

The Least Frequently Used (LFU) replacement policy selects a page for replacement if the page had not been used often in the past. This policy keeps count of the number of times that page is accessed. Pages with the lowest counts are replaced while pages with higher counts remain in primary memory [Nutt 1997].

The applet below simulates the behavior of each of the five page replacement polices. Set the number of page frames to "8" and the Page Reference Generate Method to "Random Generate." Press "Start" to begin the simulation. This configuration simulates a virtual memory of 16 pages and a primary memory of 8 pages.

Simulation of Page Replacement Algorithms
Courtesy of Qi Song, New York Institute of Technology

Now try running the simulation with a custom string of page references. Copy the string below into the box labeled "Sample String." Each number is an integer representing the requested page, and each integer is separated by a space similar to the example string below. You will also need to change the Page Reference Generate Method to "Sample String."

Example String: 0 0 1 2 0 1 2 1 2 2 0 3 4 5 4 5 6 5 6 6 5 5 4 4 5 6 5 6 5 7 6 7 7 7 6 6 7 6 7 7 6 5 3 3 4 3 4 3 4 2 3 3 4 3 7 6 6 7

References