4.3 PAGE MANAGEMENT ALGORITHMS

The memory management subsystem is the second part of the OpenVMS operating system kernel. It is composed of the page fault handler, page management, the SWAPPER, and a memory status database.

To control the working set size for each process, the memory management subsystem determines which pages in the current working set have become inactive so that, when a demand for a new page is made, it replaces the old, inactive page with the newly faulted one. Put another way, the system must determine which page of the working set to remove to make room for a new one because the maximum working set size is limited.

There are several page replacement algorithms, and this section introduces two of the most common ones; the others are variations of these two. The simplest algorithm is a FIFO scheme. A list is maintained to record the order that frames were added to the working set, and a maximum list size is defined for the process. Then, when the list is full, the first frame is released and the newest one takes its place. This scheme appears to work because, on the basis of the principle of locality, the older the frame is, the less likely it is to be used again.

Extending the philosophy of FIFO page replacement is an algorithm called LRU (Least Recently Used). Intuitively, LRU selects a replacement page that has not been used in a long time; this is not necessarily the page least...