The Not Recently Used Page Replacement Algorithm

The Not Recently Used Page Replacement Algorithm

In order to allow the operating system to collect useful page usage statistics, 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, as illustrated in "Page Tables" Figure 1. It is important to realize that these bits must be updated on every memory reference, so it is necessary that they be set by the hardware. Once a bit has been set to 1, it stays 1 until the operating system resets it.

If the hardware does not have these bits, they can be reproduced 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 happen. 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 modified, another page fault will happen, 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 differentiate pages that have not been referenced recently from those that have been.

When a page fault happens, the operating system inspects all the pages and divides them into 4 categories based on the current values of their R and M bits:

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 happen 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 required 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 class4. Implicit in this algorithm is the idea that it is better to remove a modified page that has not been referenced in at least one clock tick (usually about 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 sufficient.

The First-In, First-Out (FIFO) Page Replacement Algorithm

Another low-overhead paging algorithm is the FIFO (First-In, First-Out) algorithm. To show how this works, consider a supermarket that has enough shelves to display exactly k different products. One day, some company introduces a new convenience food - instant, freeze-dried, organic yogurt that can be reconstituted in a microwave oven. It is an immediate success, so our finite supermarket has to get rid of one old product in order to stock it.

One possibility is to find the product that the supermarket has been stocking the longest (i.e., something it began selling 120 years ago) and get rid of it on the grounds that no one is interested any more. In effect, the supermarket maintains a linked list of all the products it currently sells in the order they were introduced. The new one goes on the back of the list; the one at the front of the list is dropped.

As a page replacement algorithm, the same idea is applicable. The operating system maintains a list of all pages currently in memory, with the most recent arrival at the tail and the least recent arrival at the head. On a page fault, the page at the head is removed and the new page added to the tail of the list. When applied to stores, FIFO might remove mustache wax, but it might also remove flour, salt, or butter. When applied to computers the same problem arises. For this reason, FIFO in its pure form is seldom used.

The Second-Chance Page Replacement Algorithm

A simple alteration to FIFO that avoids the problem of throwing out a heavily used page is to inspect the R bit of the oldest page. If it is 0, the page is both old and unused, so it is replaced immediately. If the R bit is 1, the bit is cleared, the page is put onto 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.

The operation of this algorithm, called second chance, is shown in Figure 1. In Figure 1(a) we see pages A through H kept on a linked list and sorted by the time they arrived in memory.

Operation of second chance

Assume that a page fault happens at time 20. The oldest page is A, which arrived at time 0, when the process started. If A has the R bit cleared, it is removed from memory, either by being written to the disk (if it is dirty), or just abandoned (if it is clean). On the other hand, if the R bit is set, A is put onto the end of the list and its "load time" is reset to the current time (20). The R bit is also cleared. The search for a appropriate page continues with B.

What second chance is looking for is an old page that has not been referenced in the most recent clock interval. If all the pages have been referenced, second chance degenerates into pure FIFO. Particularly, imagine that all the pages in Figure 1(a) have their R bits set. One by one, the operating system moves the pages to the end of the list, clearing the R bit each time it appends a page to the end of the list. Ultimately, it comes back to page A, which now has its R bit cleared. At this point A is removed. In this way the algorithm always ends.

The Clock Page Replacement Algorithm

Although second chance is a reasonable algorithm, it is unnecessarily inefficient because it is continually moving pages around on its list. A better approach is to keep all the page frames on a circular list in the form of a clock, as shown in Figure 2. The hand points to the oldest page.

When a page fault happens, the page being pointed to by the hand is inspected. If its R bit is 0, the page is removed, the new page is inserted into the clock in its place, and the hand is advanced one position. If R is 1, it is cleared and the hand is advanced to the next page. This process is repeated until a page is found with R = 0. Not surprisingly, this algorithm is called clock.

The clock page replacement algorithm


Tags

virtual memory, algorithm, clock, fifo, operating system