The Least Recently Used (LRU) Page Replacement Algorithm

The Least Recently Used (LRU) Page Replacement Algorithm

A good estimation to the best algorithm is based on the observation that pages that have been heavily used in the last few instructions will possibly be heavily used again in the next few. On the other hand, pages that have not been used for ages will possibly remain unused for a long time. This idea suggests a realizable algorithm: when a page fault takes place, throw out the page that has been unused for the longest time. This strategy is called LRU (Least Recently Used) paging.

Though LRU is theoretically realizable, it is not cheap. To fully implement LRU, it is essential to maintain a linked list of all pages in memory, with the most recently used page at the front and the least recently used page at the rear. The difficulty is that the list must be updated on every memory reference. Finding a page in the list, deleting it, and then moving it to the front is a very time consuming operation, even in hardware (assuming that such hardware could be built).

On the other hand, there are other ways to implement LRU with special hardware. Let us examine the simplest way first. This method requires equipping the hardware with a 64-bit counter, C, that is automatically increased after each instruction. Moreover, each page table entry must also have a field large enough to contain the counter. After each memory reference, the current value of C is stored in the page table entry for the page just referenced. When a page fault takes place, the operating system observes all the counters in the page table to find the lowest one. That page is the least recently used.

Now let us consider a second hardware LRU algorithm. For a machine with n page frames, the LRU hardware can maintain a matrix of n X n bits, at first all zero. Whenever page frame k is referenced, the hardware first sets all the bits of row k to 1, then sets all the bits of column k to 0. At any instant of time, the row whose binary value is lowest is the least recently used, the row whose value is next lowest is next least recently used, and so forth. The workings of this algorithm are given in Figure 1 for four page frames and page references in the order

0 1 2 3 2 1 0 3 2 3

After page 0 is referenced, we have the situation of Figure 1(a). After page 1 is referenced, we have the situation of Figure 1(b), and so forth.

LRU using a matrix when pages are referenced


Tags

algorithm, lru paging, memory, operating system