LRU — Page Replacement

Overview

What this concept solves

LRU — Least Recently Used — bets that the recent past predicts the near future. The page you haven't touched in the longest time is the one you're least likely to need soon, so evict that one. It's the practical workhorse of replacement policies and usually the first thing anyone reaches for.

The bet rests on locality of reference: real programs reuse the same pages over short windows — a loop's data, the current function's stack, the hot rows of a table. If a page hasn't been used in a while, the program has probably moved on. Recency is a cheap, surprisingly accurate stand-in for the future that Optimal needs.

Where FIFO orders pages by arrival and ignores use, LRU orders them by last use. That single change turns a weak baseline into a policy that often lands close to Optimal — and, unlike FIFO, never suffers Belady's anomaly.

Mechanics

How it works

The rule, step by step

Page already in a frame? Hit. Move it to the most-recently-used end — it just proved it's still wanted.
Not in memory, free frame available? Load it at the most-recently-used end.
Not in memory, all frames full? Evict the page at the least-recently-used end, then load the new page at the most-recent end.

Implementing it is the hard part

The rule is simple; tracking it efficiently is not. Exact LRU needs to know the recency order at all times. Two classic approaches: (1) a doubly-linked list + hash map — O(1) to move a node to the front on every access, but a pointer update on every memory reference is expensive; (2) a timestamp or counter per page, updated on each access and scanned on eviction. Both add real cost to the hot path. That overhead is exactly why Clock, Aging, and friends exist — they approximate LRU for a fraction of the price.

LRU is a stack algorithm: the set of pages it keeps with N frames is always a subset of what it keeps with N+1. So adding memory can only help — no Belady's anomaly. Compare the Sequential thrash preset against the same string in the FIFO prototype to see the difference recency makes.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › LRU

About this simulation

Frames are kept sorted by recency — least-recently-used on the left (next to be evicted), most-recently-used on the right. Every hit slides its page to the right end; every fault loads at the right end and, if full, drops the left end. Step through and watch a reused page repeatedly rescue itself by jumping to the most-recent end.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Watch a hit rescue a page

Load the Hot page preset and step through. The frequently-referenced page keeps getting hit, and each hit slides it to the 'most recent' end — so it's never the leftmost (LRU) frame when an eviction happens. Contrast this with FIFO, which would evict it on schedule regardless.

try 02

See recency beat arrival order

Run the Sequential thrash preset (1 2 3 4 repeating, 3 frames) in this prototype, then run the identical string in the FIFO prototype. Compare the page-fault totals. Then try Working set fit, where the reused set fits in memory and the fault rate drops sharply — locality rewarded.

try 03

Read the 'used @ step' labels

Step through any preset and watch the small 'used @ step N' note under each frame. The leftmost frame always has the smallest step number — it's the least recently used, and it's the next to go. This is the single fact that defines LRU.

In practice

When to use it — and what you give up

When LRU shines (and when it doesn't)

Workloads with temporal locality — loops, working sets, recently-accessed data that's likely to be accessed again. This is most real software, which is why LRU is the default mental model.
When you can afford the bookkeeping — application-level caches (an in-memory key/value cache) can maintain an exact LRU list cheaply; that's harder at the OS/hardware level.
As the quality target — even when you ship an approximation (Clock), you design and measure it against LRU.
Beware sequential scans — one big linear pass over data you'll never revisit floods the cache and evicts your hot pages. This 'scan resistance' problem is what ARC, 2Q, and LIRS (see the Cache Eviction topic) were built to fix.

Where you'll see it

Application and database caches lean on LRU and its variants constantly: Redis offers an allkeys-lru eviction policy (an approximate LRU that samples a few keys rather than maintaining a global order), and most database buffer managers use an LRU-flavored policy. At the OS and CPU-cache level, true LRU is too costly, so you'll find Clock and pseudo-LRU approximations instead.

Pros

Strong fault rates — exploits locality, often near Optimal on real workloads.
No Belady's anomaly — it's a stack algorithm; more memory never hurts.
Intuitive and predictable — easy to reason about what's in the cache and why.
Well-studied — decades of variants (2Q, ARC, LIRS) build on it for tricky workloads.

Cons

Expensive to track exactly — a metadata update on every single access (list move or timestamp write).
Not scan-resistant — a one-time linear scan can evict the entire hot set.
Recency ≠ frequency — a page hit a hundred times then idle briefly can lose to a page touched once recently.
Approximations usually win in practice — Clock gets most of LRU's quality for far less cost, so exact LRU is often not worth it at the OS level.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

lru.ts

// Exact LRU with a Map (insertion order = recency order in JS Maps).
class LRU {
  private frames: number;
  private cache = new Map<number, true>(); // oldest entry first
  faults = 0;
  hits = 0;

  constructor(frames: number) { this.frames = frames; }

  access(page: number): "hit" | "fault" {
    if (this.cache.has(page)) {
      this.cache.delete(page);
      this.cache.set(page, true);          // re-insert => now most recent
      this.hits++;
      return "hit";
    }
    this.faults++;
    if (this.cache.size >= this.frames) {
      const lru = this.cache.keys().next().value!; // first key = least recent
      this.cache.delete(lru);                       // evict it
    }
    this.cache.set(page, true);            // load as most recent
    return "fault";
  }
}

References & further reading

5 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

What signal does LRU use to choose a victim?

question 02 / 03

Why do real operating systems usually approximate LRU instead of implementing it exactly?

question 03 / 03

Which workload is LRU notably bad at?

0/3 answered