# Page Replacement Algorithms

- Feb 8, 2002

- 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

## The Least Recently Used (LRU) Page Replacement Algorithm

A good approximation to the optimal algorithm is based on the
observation that pages that have been heavily used in the last few instructions
will probably be heavily used again in the next few. Conversely, pages that have
not been used for ages will probably remain unused for a long time. This idea
suggests a realizable algorithm: when a page fault occurs, throw out the page
that has been unused for the longest time. This strategy is called **LRU
**(**Least Recently Used**) paging.

Although LRU is theoretically realizable, it is not cheap. To fully implement LRU, it is necessary 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).

However, there are other ways to implement LRU with special hardware.
Let us consider the simplest way first. This method requires equipping the
hardware with a 64-bit counter, *C*, that is automatically incremented
after each instruction. Furthermore, 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 occurs, the operating system examines all the
counters in the page table to find the lowest one. That page is the least
recently used.

Now let us look at a second hardware LRU algorithm. For a machine
with *n *page frames, the LRU hardware can maintain a matrix of *n
*´ *n *bits, initially 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, 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 Fig. 4-3 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 Fig. 4-3(a). After page 1 is reference, we have the situation of Fig. 4-3(b), and so forth.

**Figure 4-3. LRU using a matrix when pages are referenced in the order 0,
1, 2, 3, 2, 1, 0, 3, 2, 3.**