Worked examples — Replacement policies — LRU, LFU, FIFO, Random

Before we start, one word we lean on constantly. A frame (or slot / way) is one storage box in the cache that can hold exactly one block. If a cache has capacity 3, it has 3 frames. When all frames are occupied and a new block arrives, one resident must leave — that leaving is the eviction, and the block chosen is the victim.

We use two events throughout:

• Hit — the requested block is already sitting in a frame. Fast, no eviction.
• Miss — the block is absent. We must fetch it; if the cache is full we evict a victim first.

Two more words we will paint on every figure. When a cache orders its blocks by how recently they were used, the block used most recently sits at the "hot" end — we call it the ==MRU (Most-Recently-Used)== block. The block used longest ago sits at the "cold" end — the ==LRU (Least-Recently-Used)== block, which is exactly the victim the LRU policy evicts. So in every filmstrip tower below, top = MRU, bottom = LRU.

Prerequisites worth a glance: Cache Memory Fundamentals, Set-Associative Mapping, Temporal and Spatial Locality.

---

The scenario matrix

Every replacement puzzle is really one (or a blend) of the cells below. Each worked example is tagged with the cell(s) it covers.

#	Case class	What makes it tricky	Covered by
C1	Cold cache (empty frames)	No eviction yet — just compulsory misses	Ex 1
C2	Full cache, plain eviction	The core decision rule fires	Ex 1, Ex 2
C3	Hit that changes the future (LRU vs FIFO on a hit)	A hit reorders LRU but not FIFO	Ex 2
C4	Tie-breaking (two equally-bad victims)	Policy underspecified → need a rule	Ex 3
C5	Frequency ties & stale popularity (LFU)	Old counts vs recent counts	Ex 4
C6	Belady's anomaly (more frames, more misses)	Non-stack behaviour of FIFO	Ex 5
C7	Degenerate: capacity 1 (incl. Random)	Every miss evicts; all policies collapse together	Ex 6
C8	Degenerate: working set ≤ capacity	After warm-up, zero misses forever	Ex 7
C9	Real-world word problem (AMAT payoff)	Turn a miss rate into nanoseconds	Ex 8
C10	Exam twist: OPT vs LRU on same trace	Show LRU losing to the impossible ideal	Ex 9

We reuse a short "master trace" wherever it helps so you can compare policies side by side.

---

Ex 1 — Cold cache to first eviction (C1, C2)

Steps.

1. A → miss, cache [A]. Why this step? Cache is empty — this is a compulsory miss (cell C1): A has never been seen, so nothing to evict.
2. B → miss, cache [B, A]. Why? Still a free frame; another first-touch compulsory miss, load without eviction.
3. C → miss, cache [C, B, A]. Why? Third frame fills. Now the cache is full — the next miss must evict (we enter C2).
4. A → hit, cache [A, C, B]. Why? A is present. LRU updates recency: A jumps to most-recent, so the order becomes A (newest) … B (oldest).
5. D → miss, cache [D, A, C], evict B. Why? Cache full, D absent. LRU evicts the least-recently-used = the block at the tail = B. (B is oldest by use because A was touched at step 4.)

The figure below is a filmstrip of these five snapshots, left to right. Read it as a comic strip: in each little tower the top box is most-recent (MRU) and the bottom box is least-recent (LRU). Watch A (burnt orange) climb back to the top at step 4 when it is hit, and watch B (teal) sink to the bottom and then vanish at step 5 — the orange arrow at the bottom points exactly at that eviction. That downward slide of B is the LRU rule made visible.

Figure 1 — LRU filmstrip: MRU on top, B drifts to the LRU tail and is evicted when D arrives.

Verify. Misses = steps 1,2,3,5 = 4 misses, 1 hit (step 4). Final resident set = $\{D,A,C\}$; B is gone. Sanity check: 5 accesses = 4 misses + 1 hit ✓. B was untouched since step 2 while A (step 4) and C (step 3) were newer — correct victim ✓.

---

Ex 2 — The hit that changes the future: LRU vs FIFO (C2, C3)

Steps.

1–3. A, B, C → three misses. FIFO queue (oldest→newest): A, B, C. Identical to LRU so far. Why? On misses everyone inserts at the "newest" end; the policies only diverge on hits/evictions. 4. A → hit, queue unchanged A, B, C. Why this step? This is the crux of cell C3. FIFO tracks age since insertion, not since last use. A hit does not reorder the queue — so A stays "oldest". 5. D → miss, evict A, queue B, C, D. Why? Cache full; FIFO removes the front (oldest inserted) = A, even though A was just used at step 4.

The figure puts the two policies side by side at the moment of decision (step 5). The left tower is LRU, the right tower is FIFO; in each, the top is the position that just got touched and the bottom is the eviction candidate. Notice A (burnt orange) sits on top of the LRU tower (safe, because the step-4 hit lifted it) but sits at the front of the FIFO tower (doomed, because FIFO never noticed the hit). The double-headed arrow labelled "hit reorders? yes / no" is the whole lesson: same trace, same fullness, opposite victims — because the state each policy keeps is different.

Figure 2 — Step-5 face-off: LRU keeps A (top), FIFO evicts A (front); the hit reordered one and not the other.

Verify. FIFO evicts A; LRU (Ex 1) evicted B. Different victim — and this is exactly the disagreement that makes FIFO able to throw away hot data. Cross-check with the parent's rule: "did a hit change who gets evicted?" Under LRU yes, under FIFO no ✓. See Pseudo-LRU and Tree-PLRU for how hardware approximates the LRU behaviour cheaply.

---

Ex 3 — Tie-breaking when two victims look equal (C4)

Steps.

1. A → miss, queue A.
2. B → miss, queue A, B (full).
3. A → hit. FIFO does not reorder → queue still A, B. Why? Cell C3 again: hits are invisible to FIFO. This is what creates the apparent tie.
4. C → miss, evict A, queue B, C. Why this step? There is no tie for FIFO: insertion order is a total order (A inserted before B). The victim is unambiguously the front, A.

Verify. Evicted = A; final cache $\{B,C\}$. Under LRU the same trace would evict B at step 4 (because A was used at step 3, making B least-recently-used) — a clean demonstration that the "tie" was policy-dependent, not real ✓.

---

Ex 4 — LFU: frequency ties and stale popularity (C4, C5)

Steps.

1. A, A, A → A missed once then hit twice. Counts: A=3. Cache {A}. Why? First A is a compulsory miss; the next two are hits that bump A's counter.
2. B → miss, cache {A:3, B:1}.
3. C → miss, cache {A:3, B:1, C:1} (full).
4. D → miss, cache full. Evict the smallest count. B and C tie at 1 (cell C4 for LFU). Why this step? Two blocks share the minimum. Apply the secondary rule (LRU): B was used before C, so evict B. Cache {A:3, C:1, D:1}.
5. E → miss, evict smallest count. C and D tie at 1; C is older → evict C. Cache {A:3, D:1, E:1}.

The bar chart shows every block's access count as a tower. One tower dwarfs the rest: A stands at 3 (burnt orange) while B, C, D, E each sit at only 1. The teal arrow points at the short towers — those are the eviction candidates, and among ties the older one goes first. The orange arrow flags the villain of the story: A's tall tower never shrinks, so A is un-evictable no matter how stale it becomes. Reading the picture, you can literally see why the least-frequent (shortest) blocks are the ones that keep getting thrown out.

Figure 3 — LFU counts as bar heights: A's tall count (3) shields it forever while the count-1 blocks churn.

Verify. A survives the whole trace even though it was last touched at step 3 and hasn't been used since. That is cache pollution / stale popularity (cell C5): A's count 3 shields it forever. Cross-check the parent's fix: real LFU adds aging to decay A's count over time ✓. Evictions were B then C, both at count 1 ✓.

Recall Why LFU needs aging

Without decay, a block popular long ago keeps a high count and becomes un-evictable. Aging periodically halves (or decrements) counters so recent behaviour wins.

---

Ex 5 — Belady's anomaly: more frames, more misses (C6)

Walk-through, 3 frames. Queue shown oldest→newest. FIFO evicts the front whenever a miss hits a full queue.

1. 1 → miss, queue 1.
2. 2 → miss, queue 1,2.
3. 3 → miss, queue 1,2,3 (full).
4. 4 → miss, evict front 1, queue 2,3,4.
5. 1 → miss (1 was just evicted!), evict 2, queue 3,4,1.
6. 2 → miss (2 was evicted at step 5), evict 3, queue 4,1,2.
7. 5 → miss, evict 4, queue 1,2,5.
8. 1 → hit (1 is still resident), queue unchanged 1,2,5.
9. 2 → hit, queue unchanged 1,2,5.
10. 3 → miss, evict front 1, queue 2,5,3.
11. 4 → miss, evict 2, queue 5,3,4.
12. 5 → hit (5 is still resident — the queue is 5,3,4), queue unchanged 5,3,4.

Count the misses. Hits occur at steps 8, 9, and 12 (three hits); the other 9 steps are misses. So 3 frames → 9 misses.

Walk-through, 4 frames. Now the queue holds four blocks before it must evict.

1–4. 1,2,3,4 → four misses, queue 1,2,3,4 (full). 5. 1 → hit (1 still resident — this is the block the 3-frame run had just lost!), queue unchanged. 6. 2 → hit, queue unchanged. 7. 5 → miss, evict front 1, queue 2,3,4,5. 8. 1 → miss (1 evicted at step 7), evict 2, queue 3,4,5,1. 9. 2 → miss (2 evicted at step 8), evict 3, queue 4,5,1,2. 10. 3 → miss, evict 4, queue 5,1,2,3. 11. 4 → miss, evict 5, queue 1,2,3,4. 12. 5 → miss, evict 1, queue 2,3,4,5.

Count the misses. Hits occur only at steps 5 and 6 (two hits); the other 10 steps are misses. So 4 frames → 10 misses.

Notice the twist the walk-throughs expose: with 3 frames, blocks 1 and 5 survived long enough to give three hits (steps 8, 9, 12); with 4 frames, the extra slot let more early blocks linger, which pushed 1 and 2 out right before they were needed again, wrecking their reuse. More space rearranged the queue for the worse. The bar chart contrasts the two totals so the anomaly is unmissable.

Figure 4 — Two bars: 3 frames → 9 misses (teal), 4 frames → 10 misses (orange). The taller bar is the bigger cache — that is the anomaly.

Verify. 3 frames → 9 misses; 4 frames → 10 misses — the bigger cache is worse. That is Belady's anomaly (cell C6) ✓. It happens because FIFO's resident set at size 3 is not a subset of the size-4 set, so the stack property fails. Under LRU on the same trace the larger cache never does worse ✓.

---

Ex 6 — Degenerate capacity 1: LRU, FIFO, Random all coincide (C7)

Steps (identical for all three policies).

1. A → miss, cache [A]. Why this step? Cold cache, compulsory miss; nothing to evict.
2. B → miss, evict A, cache [B]. Why? With one frame the cache is full and there is exactly one victim candidate (A). "Least recently used" (LRU), "first in" (FIFO), and "pick one uniformly at random" (Random) all point at the same single block — even Random's coin flip has only one outcome. This is where cell C7 collapses the policies together.
3. A → miss, evict B, cache [A]. Why? B is now the sole resident; again all three policies must choose it.
4. B → miss, evict A, cache [B]. Why? Same reasoning — a working set of size 2 "ping-pongs" through a size-1 cache.

Verify. All 4 accesses miss (a "ping-pong" of a working set of size 2 into a size-1 cache). Every policy produced the identical sequence of evictions $A,B,A$ (cell C7): the decision rule is trivial when the candidate set has one element ✓. Miss count = 4 for LRU, FIFO, and Random alike ✓.

---

Ex 7 — Working set fits: warm-up then zero misses (C8)

Steps.

1–3. A, B, C → three compulsory misses; cache now holds $\{A,B,C\}$ = the entire working set. Why? The working set (distinct blocks ever accessed) has size 3 = capacity, so it fits with nothing left over. 4–9. A, B, C, A, B, C → every access is a hit; each hit just reshuffles recency but never evicts, because nothing new arrives. Why this step? No miss ⇒ no eviction ⇒ the resident set is stable forever (cell C8).

Verify. Total misses = 3 (only the first pass); all remaining 6 accesses are hits. Miss rate = $3/9=1/3\approx 0.333$. After warm-up, steady-state miss rate = 0 ✓. This is the payoff of temporal locality meeting sufficient capacity.

---

Ex 8 — Word problem: turn a policy win into nanoseconds (C9)

Steps.

1. Recall the formula defined above. $\text{AMAT}=T_{\text{hit}}+m\times T_{\text{penalty}}$. Why this step? Because a miss still probes the cache first (pay $T_{\text{hit}}$), then adds the penalty — so $T_{\text{hit}}$ appears once, unconditionally.
2. FIFO: ${\text{AMAT}}_1=2+0.08\times 120=2+9.6=11.6$ ns.
3. LRU: ${\text{AMAT}}_2=2+0.05\times 120=2+6.0=8.0$ ns.
4. Improvement $=11.6-8.0=3.6$ ns. Percentage $=3.6/11.6\approx 0.3103=31.0\%$. Why? The penalty term dominates, so shaving 3 percentage points off the miss rate is worth $0.03\times 120=3.6$ ns.

Verify. Units: ns + (dimensionless)·ns = ns ✓. ${\text{AMAT}}_1=11.6$ ns, ${\text{AMAT}}_2=8.0$ ns, saving $3.6$ ns ($\approx 31\%$) ✓. Forecast check: FIFO's 11.6 ns is close to 12 ns, matching the penalty-dominated intuition ✓.

---

Ex 9 — Exam twist: OPT beats LRU on the same trace (C10)

Step-4 decision (the headline).

1. Fill: A, B, C (3 misses), cache $\{A,B,C\}$.
2. D (step 4) → miss, cache full → evict.
3. LRU choice: least recently used = A (touched at step 1, oldest). Evict A. Why? LRU only sees the past.
4. OPT choice: look at future uses after step 4. Next use of A = step 5, B = step 6, C = step 10. Farthest future = C. Evict C. Why this step? OPT sees the future: A and B come back very soon (steps 5, 6), so keeping them and dumping C is smarter.

Full LRU walk (cache shown MRU→LRU; ✗ = miss, ✓ = hit).

Step	Access	Action	Cache after	✗/✓
1	A	load	A	✗
2	B	load	B,A	✗
3	C	load	C,B,A	✗
4	D	evict A	D,C,B	✗
5	A	evict B	A,D,C	✗
6	B	evict C	B,A,D	✗
7	E	evict D	E,B,A	✗
8	A	hit	A,E,B	✓
9	B	hit	B,A,E	✓
10	C	evict E	C,B,A	✗
11	D	evict A	D,C,B	✗
12	E	evict B	E,D,C	✗

LRU misses = every step except 8 and 9 = 10 misses.

Full OPT walk (evict the resident whose next use is farthest ahead).

Step	Access	Action	Cache after	✗/✓
1	A	load	A	✗
2	B	load	A,B	✗
3	C	load	A,B,C	✗
4	D	evict C (next use step 10)	A,B,D	✗
5	A	hit	A,B,D	✓
6	B	hit	A,B,D	✓
7	E	evict D (next use step 11)	A,B,E	✗
8	A	hit	A,B,E	✓
9	B	hit	A,B,E	✓
10	C	evict E (no future use)	A,B,C	✗
11	D	evict C (no future use)	A,B,D	✗
12	E	evict D (no future use)	A,B,E	✗

OPT misses = steps 1,2,3,4,7,10,11,12 = 7 misses (hits at 5,6,8,9).

Verify. At step 4 LRU evicts A (needed immediately at step 5 → forced re-miss) while OPT evicts C (not needed until step 10). Different victims (cell C10) ✓. Over the full trace LRU = 10 misses, OPT = 7 misses; OPT wins because it never throws out a soon-needed block ✓. This is why OPT is the unbeatable baseline that all real policies chase.

---

Putting the cells together

Recall One-line summary of every cell

C1 cold → compulsory misses, no eviction. ::: Ex 1 C2 full → the core rule fires. ::: Ex 1, 2 C3 hit reorders LRU not FIFO. ::: Ex 2, 3 C4 ties → FIFO/LRU can't tie, LFU can (needs secondary rule). ::: Ex 3, 4 C5 stale popularity pollutes LFU → needs aging. ::: Ex 4 C6 FIFO Belady's anomaly: more frames, more misses. ::: Ex 5 C7 capacity 1 → all policies (incl. Random) coincide. ::: Ex 6 C8 working set ≤ capacity → zero steady-state misses. ::: Ex 7 C9 AMAT converts miss-rate wins to ns. ::: Ex 8 C10 OPT can beat LRU on the same trace. ::: Ex 9

Back to the parent topic.