LRU replacement
= LRU replacement
{c}
= Least recently used replacement
{synonym}
= LRU
{c}
{synonym}
Evict the least recently accessed eligible item. Exact recency tracking on every <memory reference> can be expensive, whereas accesses to a <buffer cache> already pass through software. Recency captures <temporal locality> but a long scan can evict frequently reused items before their next use.
For <page replacement>, update recency on hits as well as misses; evict only when a miss requires a <page frame> and all eligible <page frames> are occupied. The four-page cycle in <memory thrashing> shows how exact <LRU replacement> behaves at capacities three and four.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others/Beyond Physical Memory: Policies>[Chapter 22, section 22.5, pp. 7–8: least-recently-used eviction; section 22.7, p. 11: update recency on every access]{ref}
The <LRU stack property> compares different capacities on one fixed <page-reference trace>; it does not say that <LRU replacement> always beats <FIFO page replacement>. On the displayed <sequence>, three-<page frame> <LRU replacement> has ten misses, versus nine for <FIFO page replacement>, while four-<page frame> <LRU replacement> has only eight.