Replacement policies — LRU, LFU, FIFO, Random: Visual walkthrough

Step 0 — What is a cache, drawn as boxes

WHY start here? Every policy below is just a rule for which box to empty when all three are full and a new block knocks. If you can picture three boxes, you can picture the whole topic.

PICTURE. Three empty boxes waiting for blocks. The "door" on the left is where new blocks enter.

Figure — Replacement policies — LRU, LFU, FIFO, Random

Throughout we use one fixed access sequence — the list of blocks the program asks for, in order: $A, B, C, A, D, B$

Step 1 — Fill the empty boxes (no choice yet)

WHAT. We process the first three accesses $A, B, C$ . Every one is a miss (the boxes start empty), but nobody gets evicted — there is always a spare box.

WHY show this? To make the point that a replacement policy does nothing until the cache is full. Steps 1–3 are identical for LRU, FIFO, LFU, Random. The policies only diverge later.

PICTURE. Watch the boxes fill left-to-right. After $C$ the cache is full — the interesting part begins.

Recall Why no eviction here?

Eviction only happens on a miss when the cache is full ::: With a spare box, a miss just uses the empty box — no victim needed.

Step 2 — A hit arrives: this is where LRU and FIFO split

Access #4 is $A$ . $A$ is already in a box → hit. No fetch, no eviction. But something invisible happens that decides the future.

WHAT the two policies record after the hit on $A$ :

LRU re-stamps $A$ as most recently used. New recency order (most-recent → least-recent): $A, C, B$ .
FIFO does nothing. Its queue is still, by insertion order: $A, B, C$ (A entered first).

WHY this matters. The very next miss will read these two different memories and evict two different blocks. The hit is the fork in the road.

PICTURE. Left panel = LRU's stamps after touching $A$ ( $A$ jumps to front). Right panel = FIFO's queue, unchanged. Same cache contents, different bookkeeping.

Step 3 — The decisive miss: $D$ needs a box

Access #5 is $D$ . $D$ is in no box → miss. Cache is full → we must evict. Now the two memories from Step 2 give different answers.

WHAT each policy evicts:

Policy	Reads	Victim	Cache after
LRU	recency stamps $t (A) = 4, t (C) = 3, t (B) = 2$	== $B$ == (smallest stamp)	$A, C, D$
FIFO	insertion queue $A, B, C$	== $A$ == (entered first)	$B, C, D$

WHY they disagree. LRU just saw $A$ used at step 4, so it protects $A$ and dumps the long-untouched $B$ . FIFO doesn't care that $A$ was just used — $A$ has simply been in the cache longest, so out it goes. This single disagreement is the entire LRU-vs-FIFO story.

PICTURE. Two side-by-side cache strips. Red arrow points at the box each policy empties: LRU stabs $B$ , FIFO stabs the freshly-used $A$ .

Step 4 — Finish the trace and count the damage

Access #6 is $B$ . Check each cache from Step 3:

LRU cache was $A, C, D$ → $B$ absent → miss, evict LRU block. Stamps: $t (A) = 4, t (C) = 3, t (D) = 5$ ; smallest is $C$ → evict $C$ . Cache: $B, D, A$ .
FIFO cache was $B, C, D$ → $B$ present → hit! Queue unchanged.

WHAT the full scoreboard looks like over all 6 accesses:

Access	LRU result	FIFO result
A	miss	miss
B	miss	miss
C	miss	miss
A	hit	hit
D	miss	miss
B	miss	hit

WHY the ending differs. On this trace FIFO accidentally keeps $B$ (it never evicted $B$ because $A$ was the oldest), so FIFO wins the last access. This shows the winner is trace-dependent — no policy is universally best, which is exactly why four of them exist.

PICTURE. A timeline ribbon: green tick = hit, coral tick = miss, one row per policy. You can eyeball who scored where.

Recall Miss count on this trace

LRU misses vs FIFO misses ::: LRU = 5 misses (only step-4 hit); FIFO = 4 misses (steps 4 and 6 both hit) — FIFO wins this particular trace.

Step 5 — The stack property: why LRU can't be "surprised"

WHAT this buys us. If the big cache contains everything the small one does, the big cache can only hit more often, never less. So misses go down (or stay flat) as you add boxes — the intuitive, sane behaviour.

WHY LRU qualifies. LRU evicts purely by recency order, and that order is the same list whether the cache is size 3 or 4 — the size-4 cache just keeps one extra block off the end of the same ordered list. Nesting is automatic.

PICTURE. Two concentric rounded rectangles: inner = size-3 contents, outer = size-4 contents. The inner set sits fully inside the outer set — that is $C_{3} \subseteq C_{4}$ made visible.

Step 6 — The degenerate case: FIFO breaks the "bigger is better" rule

FIFO is not a stack algorithm, because its victim depends on a queue that reshuffles when you change the cache size. So $C_{3} \subseteq C_{4}$ can fail — and when it fails, adding a box can add misses. This is Belady's anomaly (see Belady's Optimal Algorithm).

WHAT the classic trace does — sequence $1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5$ under FIFO:

3 frames → 9 misses
4 frames → 10 misses ← more misses with more memory!

WHY it happens. With 4 frames, a block you'll soon reuse gets shoved out at just the wrong moment because it happened to be oldest in the 4-frame queue, whereas the 3-frame queue evicted a different, less-useful block. The queues are not nested, so the guarantee is gone.

PICTURE. A bar chart: two bars, "3 frames = 9" and "4 frames = 10". The taller bar sits on the right — the visual shock of the anomaly.

Step 7 — Why any of this pays off: the AMAT lever

We measured misses. Now turn misses into time, so we can feel the payoff.

See AMAT and Memory Hierarchy for the multi-level version.

The one-picture summary

Everything above, compressed: the fork at the hit (Step 2), the divergent evictions (Step 3), the nested-vs-broken guarantee (Steps 5–6), and the AMAT payoff (Step 7) — one diagram.

Recall Feynman retelling — the whole walkthrough in plain words

You have three boxes. You fill them with books $A, B, C$ — no decisions yet, there was always a spare box. Then you re-open book $A$ . Here's the secret fork: LRU writes down "I just touched $A$ ", but FIFO shrugs — it only remembers who was packed first. Now book $D$ shows up and a box must be emptied. LRU protects the just-touched $A$ and dumps sleepy $B$ ; FIFO dumps $A$ anyway because $A$ was packed first. Same three books in the boxes, different victim — that single disagreement IS the whole LRU-vs-FIFO difference. Next, ask "does a bigger backpack always mean fewer trips to the library?" For LRU yes, because a bigger LRU cache literally contains everything a smaller one keeps (that's the stack property — nested boxes). For FIFO no: its packing queue reshuffles when you add a box, so a 4-box FIFO can miss more than a 3-box one — Belady's spooky anomaly. Finally, why care about counting misses at all? Because time $= T_{hi t} + (miss rate) \times T_{p e na l t y}$ , and that penalty is a hundred times bigger than a hit — so shaving the miss rate is a giant lever on speed. Four policies, one decision — which box do I empty? — and now you can see each one choose.

Related: Cache Memory Fundamentals · Set-Associative Mapping · Pseudo-LRU and Tree-PLRU · Temporal and Spatial Locality · Page Replacement (OS).