LRU Replacement Policy

The Least Recently Used replacement policy chooses to replace the page which has not been referenced for the longest time. This policy assumes the recent past will approximate the immediate future. The operating system keeps track of when each page was referenced by recording the time of reference or by maintaining a stack of references.

The Least Recently Used diagram above illustrates the LRU algorithm. The reference string used here is a part of the reference string for column matrix multiplication found in the reference string demonstration. Notice that the most recently accessed page is now represented by the top page rectangle. The rectangles do not represent specific page frames as they did in the FIFO diagram. Thus, each reference necessitating a page fault (shown in red) is now on the top row.

Further inspection will show that as more pages are allotted to the program the page references in each row do not change. Only the number of page faults changes. The set of pages in memory for n pages is thus a subset of the set of pages for n + 1 page frames. In fact, the diagram could be considered a STACK data structure with the depth of the stack representing the number of page frames. If a page is not on the stack (i.e. is found a depth greater than the number of page frames) then a page fault occurs. LRU and other page replacement policies that may be represented by a stack data structure are known as stack algorithms. [T1] [S1]

The notion that the LRU replacement policy can be represented as a stack leads the concept of the swapping function.

---