Paging & LRU

Your computer keeps a small, fast cache in front of slow memory. It holds only k pages, but the program keeps asking for more pages than fit. Each request is either a hit (the page is already cached — instant) or a miss (fetch it from slow memory, and if the cache is full, evict something to make room).

The whole game is the eviction choice. Throw out a page the program never touches again and you lose nothing. Throw out the page it asks for next and you pay another expensive miss. The catch: you must decide now, with no idea what the program will request next.

That last word — next — is the heart of it. The clairvoyant who can see the future plays this perfectly. You cannot see the future. The surprising part is exactly how much that blindness costs you, and that it can be pinned down to the dot.

Here is a cache that holds just k = 3 pages and a stream of requests. Step through it and watch two policies side by side: LRU, which evicts the page unused for the longest, and OPT, Belady's clairvoyant policy, which evicts the page whose next use is furthest in the future.

<p class="hint">{{hint}}</p>
<div class="streams" id="streams"></div>
<div class="tape" id="tape"></div>
<div class="panes">
  <div class="pane"><div class="phead">LRU <span class="sub">{{lru_sub}}</span></div>
    <div class="slots" id="lruSlots"></div><div class="faults" id="lruF">{{faults_zero}}</div></div>
  <div class="pane"><div class="phead">OPT <span class="sub">{{opt_sub}}</span></div>
    <div class="slots" id="optSlots"></div><div class="faults" id="optF">{{faults_zero}}</div></div>
</div>
<div class="ratio" id="ratio"></div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="play" type="button">{{btn_autoplay}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.streams { display: flex; gap: .4rem; margin-bottom: .6rem; flex-wrap: wrap; }
.streams button { font: 600 13px system-ui; padding: .3rem .7rem; border: 1px solid #adb1b8;
  background: #fff; color: #1d3557; border-radius: 999px; cursor: pointer; }
.streams button.active { background: #1d3557; color: #fff; border-color: #1d3557; }
.tape { display: flex; gap: 4px; flex-wrap: wrap; margin: .3rem 0 .8rem; }
.req { width: 30px; height: 30px; display: flex; align-items: center; justify-content: center;
  font: 700 14px ui-monospace, monospace; border-radius: 6px; background: #e8eef3;
  color: #1d3557; border: 1px solid #cdd9e3; }
.req.cur { background: #ffd166; border-color: #e0ad33; }
.req.done { opacity: .45; }
.panes { display: flex; gap: 1rem; flex-wrap: wrap; }
.pane { flex: 1 1 200px; }
.phead { font: 700 15px system-ui; color: #1d3557; margin-bottom: .35rem; }
.phead .sub { font: 400 11px system-ui; color: #777; }
.slots { display: flex; gap: 6px; }
.slot { width: 46px; height: 46px; display: flex; align-items: center; justify-content: center;
  font: 700 18px ui-monospace, monospace; border-radius: 8px; background: #f4f6f8;
  border: 2px dashed #cdd9e3; color: #1d3557; transition: all .15s; }
.slot.full { background: #d7e3ec; border-style: solid; border-color: #9fb2c8; }
.slot.hit { background: #b7e4c7; border-color: #0a7d33; }
.slot.miss { background: #f6c6cb; border-color: #c92f3c; }
.faults { margin-top: .4rem; font: 600 14px system-ui; color: #444; }
.ratio { margin: .7rem 0 .3rem; font: 600 14px system-ui; min-height: 1.3em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .4rem; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
  background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. OPT is allowed to cheat — it reads the entire future before deciding. LRU only knows the past. Step through and count the faults: OPT is unbeatable but unbuildable, while LRU, knowing nothing of what comes next, still keeps pace within a fixed factor. Try the adversary stream, which is designed to make any online policy stumble.

How good can an online cache be? This is solved, and the answer is sharp.

• OPT is offline and easy. If you know the whole request sequence in advance, Belady's rule — evict the page used furthest in the future — provably minimizes misses. It is the gold standard, but it needs the future.
• Competitive analysis measures an online policy by its worst-case ratio to OPT. A policy is c-competitive if it never makes more than $c \times (OPT's misses) + constant$, on any input.
• LRU is exactly k-competitive. In 1985 Daniel Sleator and Robert Tarjan proved that LRU (and FIFO) never exceeds k times OPT's misses, where k is the cache size — and that this bound is tight.
• No deterministic policy beats k. They also proved a matching lower bound: for every deterministic online policy an adversary can build a stream forcing a factor of k. So LRU is not just good — it is optimal among deterministic policies.
• Randomization helps. Allowing coin flips, the randomized marking algorithm achieves an expected ratio of $O(\log k)$ against an oblivious adversary, and that is optimal too.

That is the punchline: the cost of not seeing the future is not vague hand-waving. It is a clean factor of k, proven both ways. This is the friendly cousin of the worst-case reasoning behind P vs NP — here the limit isn't time, it's information.

"The buffer is full and a new thing arrived — what do I drop?" is one of the most-asked questions in all of computing, and LRU is its workhorse answer:

• CPU and memory caches: hardware approximates LRU to decide which cache line to evict on every miss.
• Databases: the buffer pool of every serious database (PostgreSQL, MySQL, Oracle) is an LRU-style cache over disk pages.
• Web caches and CDNs: browsers, proxies and content-delivery networks evict the least-recently-used objects to fit a fixed budget.
• Operating systems: virtual-memory page replacement is literally this problem — which RAM page gets written back to disk.
• Judging online decisions: competitive analysis, born here, now grades online problems everywhere — from scheduling jobs to renting-vs-buying.

Understand why LRU is k-competitive and you understand the limit of every system that must decide without knowing what comes next.

Paging hides a tidy theorem. A clairvoyant policy that sees the whole future plays the cache perfectly — but no real system can. Strip away the future and the cost is measurable: LRU never does worse than k times optimal, and Sleator and Tarjan proved that no deterministic policy can promise less.

So the next time a cache misses and you wonder whether a cleverer rule would have saved it, take comfort. LRU isn't a lazy heuristic — it is, provably, the best you can do without a crystal ball. Like P vs NP, it marks a hard edge: not what we can't compute, but what we can't know in time.