LRU replacement

Since we cannot see the future the way optimal does, the next best thing is to bet that the future looks like the recent past. If a page has not been touched for a long while, it is probably out of the program's current focus and will likely stay unused; the page you used a moment ago, you will probably use again soon. LRU replacement makes exactly this bet: when it must evict, it removes the page that was least recently used — the one that has gone longest without a reference.

Think of LRU as optimal looking backwards instead of forwards. Optimal evicts the page used farthest in the future; LRU evicts the page used farthest in the past. To do this it must remember the order in which pages were last accessed. Two textbook ways: a counter — stamp each page with a logical clock on every access and evict the smallest stamp; or a stack — on every access move the page to the top of a doubly linked list, so the bottom is always the LRU victim. Because programs really do exhibit locality of reference, this past-as-prologue bet works very well in practice and LRU comes close to optimal on typical workloads.

Why it matters and its honest catch: LRU is a stack algorithm, so unlike FIFO it never suffers Belady's anomaly — more frames never make it worse. But exact LRU is expensive: it would need the hardware to update a timestamp or reorder a list on every single memory reference, which is far too costly to do for real. So actual systems do not run true LRU; they run cheap approximations of it — the reference-bit aging scheme and the second-chance (clock) algorithm — that capture most of LRU's benefit at a fraction of the cost.