Belady

Two caches, side by side, fed the same stream of page requests. The left one has k frames, the right one has k + 1. Everything else — the policy, the string, the order — is identical. The only question the piece asks is whether the right-hand cache faults fewer times than the left, and the answer under FIFO is: not always.

The default string is the one from Bélády, Nelson and Shedler’s 1969 paper — 1 2 3 4 1 2 5 1 2 3 4 5 — and under FIFO it takes 9 faults in three frames and 10 in four. Adding memory made it worse. That is Bélády’s anomaly, and the reason it is worth a picture rather than a sentence is that the sentence sounds like a typo.

What each band is

Everything that is a function of the step shares one x-axis, so a column is the same request whichever band you read it in.

• The tape is the reference string. Each cell carries two result bars, the small cache’s outcome over the big one’s. Where the upper bar is green and the lower one orange, the extra frame just cost you a fault; those cells are outlined in red.
• The two columns are the caches. Slots are positional, so the box that changes colour is the box that was evicted rather than the whole column resorting. Each slot carries the number its policy judges it by — insertion age under FIFO, idle time under LRU, distance to the next use under OPT — and the amber arrow marks the slot that number condemns, one step before it goes.
• The containment strip is contents(k) ⊆ contents(k+1), checked at every step.
• The curves are the cumulative fault counts, with the gap between them filled: red where the bigger cache is behind, green where it is ahead. Nine faults against ten is a hair’s width on a shared axis, so the sign of the gap is coloured rather than left to be squinted at.

The mechanism, which is the containment strip

The anomaly looks like a paradox until you watch the strip. Switch the policy to LRU and it stays solid green for the whole run: whatever three frames are holding, four frames are holding too. That is the inclusion property, and a policy that has it is called a stack algorithm. It makes the anomaly impossible for the boring reason — the bigger cache can only fault on a page the smaller one also lacks, so its fault set is a subset, request by request. LRU has it. OPT has it. FIFO does not, and the strip goes red the moment FIFO’s four-frame cache drops a page its three-frame cache is still holding.

That is the whole mechanism: the extra frame does not just add space, it changes the arrival order, and FIFO evicts on arrival order. A page that would have been evicted early in the small cache survives long enough in the big one to become the oldest thing there at exactly the wrong moment.

The strip also makes the weaker half of the claim visible, which most treatments skip. Run FIFO on a random string and you will often see the strip break with no anomaly in the totals at all — the story panel says so when it happens. Losing inclusion is necessary for the anomaly, not sufficient. It unlocks the door; it does not walk through it.

Is the classic string cherry-picked?

That is what the find an anomaly button answers, and the number it reports is the point. It searches uniform-random reference strings at your chosen capacity and stops at the first one where k + 1 frames faults more than k. Measured over 40 runs per capacity:

So: roughly one random string in a thousand at three against four, and closer to one in two hundred by six against seven. Rare enough that you will never trip over one while checking your own work; common enough that a fresh example is a few hundred tries away. Not cherry-picked — just not what anybody writes down.

The empty row is the other half of the answer. At two frames against three the search comes back empty every single time, at every seed, having burned the whole 80,000-string budget. The smallest counterexample anyone writes down is the 3-against-4 classic, and the search agrees with that.

The other streams

• Looping scan walks 1..k+1 on repeat, and is the cliff rather than the anomaly: three frames against a four-page loop faults on every single request, 20 for 20, because FIFO and LRU both evict the page that is about to be needed. One more frame takes it to 4. Switch to OPT on the same string and the cliff is gone — the cliff belongs to the policy, not to the arithmetic.
• Working set is the control: a stream with real locality, where more memory does the obvious thing and the strip stays green.
• Random is the hunting ground.

Reuse

src/belady.js is a framework-free ES module with no canvas and no timers:

• simulate(refs, capacity, policy) — one frame per request plus a frame 0 for the empty cache, each carrying the slot contents, the slot touched, what was evicted, the per-slot eviction keys and the running fault count. policy is 'fifo' | 'lru' | 'opt'.
• compare(small, big) — the step-by-step relationship between two runs over one string: the contained array, the anomalies list (requests where the big cache faults and the small one hits), the crossing step and firstBreak.
• faultCount(refs, capacity, policy) — the same eviction rule with no trace kept, for searches. simulate allocates a frame, a Set and a key array per request and OPT’s keys rescan the future per slot; fine to animate, far too heavy for 80,000 strings.
• findAnomaly({ capA, policy, pages, length, rand, tries }), CLASSIC, loopRefs, randomRefs, localityRefs, rng(seed).

Same trace-per-tick shape as collapse, rho, sift and window: the module produces frames, the demo draws them.

Gotchas

• The eviction key is not the eviction order for FIFO on a hit. A FIFO slot’s age keeps counting through hits — that is precisely what separates it from LRU — so a page can sit at the top of the column with a large age badge and be next out despite having just been served. It looks wrong. It is FIFO.
• CLASSIC is a fixed 3-vs-4 artifact, so the capacity slider keeps it as-is rather than regenerating it; every other stream is generated against the capacity and rebuilds with it.
• OPT is a stack algorithm, so it can never show the anomaly either. It is on the dial as the floor — the fewest faults any policy could have taken on this string — not as a candidate.
• The anomaly needs the totals to cross, which is a stronger condition than a single anomalous request. Strings with one or two red-outlined tape cells and no crossing are common; the story panel distinguishes them.
• The demo bundles its own copy of belady.js (self-contained by contract); re-copy after editing src/.