Least Recently Used

An alternative scheme is to replace Least recently Used pages. It replaces the page that has not been used for the longest period of time.

To see how this works we use the same string 7 0 1 2 0 3 0 4 as before.

Assume that page 4 is requested. At this stage, pages 0,2,3 are in memory. By scanning backwards, we see that of the three frames in memory page 2 is the least recently used.

The frame holding this page is the one that will be sacrificed to make way for page 4.

By the principle of locality the LRU policy should and does work well. However it is difficult to implement. Each page would need a tag with the time it was last referenced and even if the hardware supported such a scheme the overheads would be tremendous.

Not Recently Used (NRU)is an approximation of LRU. With this policy each page table entry contains a modified bit and a reference bit as shown above. When a page is loaded, the operating system sets the reference bit to 1. Periodically the operating system will reset the reference bit to 0. When a page is accessed the bit is set to 1. When selecting a page for replacement the system will use two criteria: the first priority is to select a page with a reference bit of 0, which indicates that it has not been accessed within a period of time, the second priority is to select a page whose modified bit is 0 (indicating that it has not been modified while in memory).

Another approximation of LRU is called aging. Aging is achieved by a adding an extra byte to a page table entry. When a page is accessed, the hardware sets the most significant bit in the reference byte. Periodically, as with NRU above, the contents of this byte is adjusted by shifting all the bits right. A page with the lowest value in its reference byte is selected for removal. As with NRU, the operating system may pick any page from among all the pages with the lowest value.

Over the years designers have tried to implement algorithms that approximate to the performance of LRU but without the overheads. Many of these are referred to as the clock policy.

The simplest form of clock policy requires the association of an additional bit with each frame, referred to as the reference bit. When a page is first loaded into a frame in memory, the reference bit for that frame is set to 1. When the page is subsequently referenced (after the reference that generated the page fault), its reference bit is set to 1. For 1 the page replacement algorithm, the set of frames that are candidates for replacement is considered to be a circular buffer, with which a pointer is associated. When a page is replaced, the pointer is set to indicate the next frame in the buffer. When it comes time to replace a page, the operating system scans the buffer to find a frame with a use bit set to zero. Each time it encounters a frame with a use bit of 1, it resets that bit to zero. If any of the frames in the buffer have a use bit of zero at the beginning of this process, the first such frame encountered is chosen for replacement. If all of the frames have a use bit of 1, then the pointer will make one complete cycle through the buffer, set ting all the use bits to zero, and stop at its original position, replacing the page in that frame. We can see that this policy is similar to FIFO, except that, in the clock policy, any frame with a use bit of 1 is passed over by the algorithm. The policy is referred to as a clock policy because we can visualize the page frames as laid out in a circle. A number of operating systems have employed some variation of this simple clock policy (for example, Multics).

The figure below provides an example of the simple clock policy mechanism. A circular buffer of n- 1 main memory frames is available for page replacement. Just prior to the replacement of a page from the buffer with incoming page 727, the next frame pointer points at frame 2, which

contains page 45. The clock policy is now executed. Because the use bit for page 45 in frame 2 is equal to 1, this page is not replaced. Instead, the use bit is set to zero and the pointer advances. Similarly, page 191 in frame 3 is not replaced; its use bit is set to zero and the pointer advances. In the next frame, frame 4, the use bit is set to O. Therefore, page 556 is replaced with page 727. The use bit is set to 1 for this frame and the pointer advances to frame 5, completing the page replacement procedure.