Memory is full; a new page arrives; one resident page must be evicted. Which one? The choice is a policy, and the policy is runnable: feed the same reference string to FIFO, LRU and OPT and count the faults each takes. One of them — OPT, evict the page used furthest in the future — is a proven lower bound no online policy can beat. Down the center, data flows: the reference string goes in, the pager fills its frames, the fault count comes out. The blue team builds and defends it; the red team tries to break it.
source L. A. Belady, A Study of Replacement Algorithms for a Virtual-Storage Computer, IBM Systems Journal 5(2):78–101 (1966) — doi:10.1147/sj.52.0078. Rendered, not quoted.
A fault is a reference to a page not resident in the k frames. When frames are full, the policy names the victim:
FIFO evict the page loaded earliest — order of arrival, ignores use. LRU evict the least-recently-used — a bet that the recent past predicts the near future. OPT (Belady) evict the page whose next use is furthest ahead — needs the whole future, so it is unrealizable, but it is the exact minimum.
Faults on the current string / k, computed live:
| policy | faults | vs OPT |
|---|
Belady 1966 asked one question — which page to evict — and answered it three times. OPT is the unreachable ideal (a lower bound). LRU is the practical stand-in that keeps recency. the-clock-algorithm is the cheap hardware approximation of LRU (a reference bit and a sweeping hand).
And FIFO, the simplest, is the source of the-belady-anomaly: give FIFO more frames and it can fault more. Each sphere is the next one's premise.
The blue team's live check: recompute all three fault counts and prove OPT equals the brute-force minimum and no policy beats it. If red tampers — claiming FIFO is optimal — this badge is where it shows.
The input is a reference string — the sequence of pages a program touches — plus k, the number of physical frames. The default string touches page 1 again and again between one-shot visitors:
Page 1 is hot. A policy that notices — LRU, OPT — keeps it; a policy that only remembers arrival — FIFO — keeps evicting it and paying for it. That difference is what you feed the panel below.
Change policy, k, or the string — every frame and every fault is simulated on the spot, never looked up.
What the machine produces, proven: for the default string at k=3, FIFO 8, LRU 7, OPT 6 — and OPT's 6 is the exact minimum, matched by exhaustive brute force over every possible eviction choice. No policy, online or offline, faults fewer than OPT. LRU beats FIFO here; OPT beats both.
The blue team's witness (left) confirms OPT is minimal live; the red team (right) tries to crown FIFO instead.
LRU is realizable but expensive: exact LRU needs a timestamp or move-to-front on every access — too costly in hardware, so systems ship approximations (clock, aging, second-chance). And FIFO carries the Belady anomaly: adding frames can add faults, so "more memory is always better" is simply false. "Valid" here is always relative to a cost you are willing to pay.
"LRU is the best you can do." Cut. OPT faults ≤ LRU on every string — LRU is the best online policy of its class, not the minimum. Both are counted in the machine.
"More frames never hurt." Cut. Under FIFO, more frames can raise the fault count — the Belady anomaly. OPT and LRU are anomaly-free (stack algorithms).
"FIFO is simplest, so it is fine." Kept, corrected. FIFO is cheapest to build, but on hot-page workloads it pays the most faults — simplicity is a cost, not a free lunch.
The red team's move: declare FIFO the optimal policy — wire OPT's eviction to FIFO's rule and claim its count is the minimum. The blue team's witness (window 7) is watching.
Wire OPT to evict by arrival like FIFO and its count jumps from 6 to 8 — above the true minimum of 6. The witness recomputes, sees OPT no longer equals the brute-force optimum, and turns red. Nothing is faked; the attack is real and it is caught.