- The Optimal Page Replacement Algorithm
- The Not Recently Used Page Replacement Algorithm
- The First-In, First-Out (FIFO) Page Replacement Algorithm
- The Second Chance Page Replacement Algorithm
- The Clock Page Replacement Algorithm
- The Least Recently Used (LRU) Page Replacement Algorithm
- Simulating LRU in Software
- The Working Set Page Replacement Algorithm
- The WSClock Page Replacement Algorithm
- Summary of Page Replacement Algorithms
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
The Not Recently Used Page Replacement Algorithm
In order to allow the operating system to collect useful statistics about which pages are being used and which ones are not, most computers with virtual memory have two status bits associated with each page. R is set whenever the page is referenced (read or written). M is set when the page is written to (i.e., modified). The bits are contained in each page table entry. It is important to realize that these bits must be updated on every memory reference, so it is essential that they be set by the hardware. Once a bit has been set to 1, it stays 1 until the operating system resets it to 0 in software.
If the hardware does not have these bits, they can be simulated as follows. When a process is started up, all of its page table entries are marked as not in memory. As soon as any page is referenced, a page fault will occur. The operating system then sets the R bit (in its internal tables), changes the page table entry to point to the correct page, with mode READ ONLY, and restarts the instruction. If the page is subsequently written on, another page fault will occur, allowing the operating system to set the M bit and change the page's mode to READ/WRITE.
The R and M bits can be used to build a simple paging algorithm as follows. When a process is started up, both page bits for all its pages are set to 0 by the operating system. Periodically (e.g., on each clock interrupt), the R bit is cleared, to distinguish pages that have not been referenced recently from those that have been.
When a page fault occurs, the operating system inspects all the pages and divides them into four categories based on the current values of their R and M Class 0: not referenced, not modified. Class 1: not referenced, modified. Class 2: referenced, not modified. Class 3: referenced, modified.
Although class 1 pages seem, at first glance, impossible, they occur when a class 3 page has its R bit cleared by a clock interrupt. Clock interrupts do not clear the M bit because this information is needed to know whether the page has to be rewritten to disk or not. Clearing R but not M leads to a class 1 page.
The NRU (Not Recently Used) algorithm removes a page at random from the lowest numbered nonempty class. Implicit in this algorithm is that it is better to remove a modified page that has not been referenced in at least one clock tick (typically 20 msec) than a clean page that is in heavy use. The main attraction of NRU is that it is easy to understand, moderately efficient to implement, and gives a performance that, while certainly not optimal, may be adequate.