Worked examples — Replacement policies (LRU, FIFO, random)

This page is the "throw everything at it" drill for Replacement policies. We will not just re-run one nice sequence — we will hunt down every kind of situation a replacement policy can meet, and work each one to the end.

Before we start, three plain-word reminders so no symbol arrives naked:

If any of those feels shaky, the parent note builds them from zero — come back here after.

---

The scenario matrix

Every replacement question is one of these case classes. Our examples below are labelled with the cell they hit, and together they cover all of them.

#	Case class	What makes it tricky	Covered by
C1	Cold cache / empty ways	No eviction yet — where do blocks land?	Ex 1
C2	Hit vs miss divergence	LRU and FIFO agree until a hit happens on an old block	Ex 2
C3	All three policies on one trace	Same input, three different victims	Ex 3
C4	Degenerate: 1-way (direct mapped)	Policy becomes irrelevant	Ex 4
C5	Limiting: fully associative / repeated block	No misses after warm-up	Ex 5
C6	Belady's anomaly (FIFO)	Bigger cache → more misses	Ex 6
C7	Random: expected miss count	Answer is a probability, not a fixed number	Ex 7
C8	Real-world word problem (AMAT)	Turn a miss-rate difference into nanoseconds	Ex 8
C9	Exam twist: pseudo-LRU disagrees with true LRU	The cheap approximation picks a different victim	Ex 9

---

Example 1 — Cold cache, no eviction (C1)

Forecast: guess the number of evictions before reading on.

1. Access P → miss, empty ways exist. Why this step? Replacement policy only fires when the set is full. With free ways we just fill the lowest empty one. P → way 0.
2. Access Q → miss, way 1 free. Q → way 1.
3. Access R → miss, way 2 free. R → way 2.

Answer: 3 misses, 0 evictions, way 3 still empty.

Verify: ways used = 3, set size = 4, so $3\le 4$ ⇒ no eviction needed. ✓

---

Example 2 — The hit that splits LRU from FIFO (C2)

Forecast: do both evict the same block? Guess.

Look at the figure — the top track is LRU (reorders on the hit), the bottom is FIFO (frozen order).

1. Load A, load B — both policies now hold $\{A,B\}$, and A is the older one. Why? First two accesses fill the empty ways; nothing to decide yet.
2. Access A (hit). Why this is the pivot: LRU moves A to most-recently-used (MRU), so B becomes the coldest. FIFO ignores hits, so A is still the oldest by insertion.
3. Access C (miss → evict):
   • LRU throws out B (coldest by recency).
   • FIFO throws out A (oldest by arrival), even though A was just used.

Answer: LRU evicts B, FIFO evicts A.

Verify: After the trace, LRU set = $\{A,C\}$, FIFO set = $\{B,C\}$ — different, confirming the hit is exactly where the policies diverge. ✓

---

Example 3 — All three policies, one trace (C3)

Forecast: which block is safest under LRU? Which under FIFO?

1. LRU victim. Why: evict the coldest by use. That is D (least recently used).
2. FIFO victim. Why: evict the earliest inserted. Here A was inserted first, so FIFO evicts A — the one LRU considers safest.
3. Random victim. Why: uniform over 4 ways, so any of A, B, C, D with probability $\frac{1}{4}$ each.

Answer: LRU → D, FIFO → A, Random → any of the four ($p=0.25$ each).

Verify: LRU and FIFO pick opposite ends of the same 4-block set (D vs A), which is the sharpest possible disagreement — sanity confirmed. ✓

---

Example 4 — Degenerate: 1-way (direct mapped) (C4)

Forecast: can any policy help here?

1. Access X → miss, load into the single slot.
2. Access Y → miss, must evict — but there is only one block, X. Why: with $n=1$, "which of the full slots?" has exactly one answer. Evict X.
3. Access X → miss (X was just evicted), evict Y.
4. Access Y → miss, evict X.

Answer: 4 misses for both LRU and FIFO — identical.

Recall Why is policy choice meaningless at n=1?

Question: With one way, why do LRU, FIFO, and Random all behave the same? ::: There is only one full slot to choose from, so every policy's "pick a victim" step returns that same block. See cache organization for how set size $n$ is chosen.

Verify: $n=1\Rightarrow$ victim set has size 1 $\Rightarrow$ all policies deterministic and equal. Miss count = 4. ✓

---

Example 5 — Limiting case: repeated block / fits entirely (C5)

Forecast: after warm-up, how many misses per pass?

1. First pass: 4 compulsory misses (cold slots fill).
2. Second pass onward: the whole working set $\{A,B,C,D\}$ fits in 4 ways. Why misses stop: no access ever needs a fifth block, so no eviction is ever triggered — no policy is invoked.

Answer: miss rate $\to 0$ as passes $\to \infty$; exactly 4 total misses forever.

Verify: working set size $=4=$ ways, so the working set fits; steady-state miss rate $=4/(\text{passes}\times 4)\to 0$. ✓

---

Example 6 — Belady's Anomaly under FIFO (C6)

Forecast: which cache size gives fewer misses? (The "obvious" answer is wrong.)

The figure runs both side by side; each column is one access, ✗ marks a miss.

In the tables below, ✗ = miss (block was not present, an eviction may fire) and ✓ = hit (block was already in the cache, nothing changes).

3-frame FIFO trace (frames listed oldest→newest):

Access	1	2	3	4	1	2	5	1	2	3	4	5
Hit/Miss	✗	✗	✗	✗	✗	✗	✗	✓	✓	✗	✗	✓

Count: 9 misses (3 hits).

4-frame FIFO trace:

Access	1	2	3	4	1	2	5	1	2	3	4	5
Hit/Miss	✗	✗	✗	✗	✓	✓	✗	✗	✗	✗	✗	✗

Count: 10 misses (2 hits).

Reading the 4-frame row: accesses 1 and 2 (5th and 6th columns) are hits because 1, 2, 3, 4 all still fit in 4 frames. But then 5 evicts 1, and from that point every one of 1, 2, 3, 4, 5 arrives just after it was thrown out — so the final 5 is also a miss. That last column is the extra miss the 3-frame cache did not suffer.

1. Why does the 4-frame version do worse? Why this step: FIFO evicts by arrival age, not usefulness. The larger cache keeps 1 and 2 alive longer, but this shifts the phase of the circular queue so that blocks (1, 2) get evicted right before they are reused.
2. Fix: LRU is a "stack algorithm" and cannot show this anomaly — its miss count never rises with size.

Answer: 3 frames → 9 misses, 4 frames → 10 misses. Anomaly confirmed.

Verify: the =VERIFY= block simulates both FIFO caches on this exact trace and checks $9$ and $10$. ✓

---

Example 7 — Random replacement: expected misses (C7)

Forecast: is the second access (A) always a hit?

1. Access C → miss (C not present), evict a uniformly random block: A or B, each with $p=\frac{1}{2}$. Why: Random ignores history; the victim is a fair coin flip.
2. Access A → depends on step 1:
   • If C evicted A (prob $\frac{1}{2}$): set is $\{C,B\}$, so A is a miss.
   • If C evicted B (prob $\frac{1}{2}$): set is $\{C,A\}$, so A is a hit.
3. Expected misses $=\underset{\text{C always misses}}{\underbrace{1}}+\underset{\text{A}}{\underbrace{\frac{1}{2}\cdot 1+\frac{1}{2}\cdot 0}}=1+\frac{1}{2}=\frac{3}{2}$.

Answer: expected misses $=\frac{3}{2}=1.5$.

Verify: $1+\frac{1}{2}(1)+\frac{1}{2}(0)=1.5$. ✓

---

Example 8 — Word problem: turning miss rate into time (C8)

Forecast: a 1-point miss-rate gap — big deal or not?

Recall the formula from the parent: $\text{AMAT}=\text{Hit Time}+\text{Miss Rate}\times \text{Miss Penalty}$

1. LRU: ${\text{AMAT}}_{\text{LRU}}=1+0.04\times 100=1+4=5\text{ ns}$. Why: plug miss rate $=0.04$ directly; the $\times 100$ turns each miss into its 100 ns cost.
2. FIFO: ${\text{AMAT}}_{\text{FIFO}}=1+0.05\times 100=1+5=6\text{ ns}$.
3. Speedup of LRU $=\frac{6-5}{6}=\frac{1}{6}\approx 16.7\%$. Why divide by the slower one: percent improvement is measured against the baseline you are replacing (FIFO).

Answer: ${\text{AMAT}}_{\text{LRU}}=5$ ns, ${\text{AMAT}}_{\text{FIFO}}=6$ ns, LRU is $\approx 16.7\%$ faster.

Verify: units: $\text{ns}+(\text{unitless})\times \text{ns}=\text{ns}$ ✓. Numeric check in =VERIFY=. ✓

---

Example 9 — Exam twist: pseudo-LRU disagrees with true LRU (C9)

Forecast: will the 3-bit approximation match true LRU?

The figure shows the tree: each bit is an arrow pointing to the recently-used side; the victim is found by following the opposite arrows from the root.

1. True LRU victim. Why: evict the least-recent access. Order is $w_2>w_0>w_3>w_1$, so the coldest is $w_1$.
2. Reconstruct the pseudo-LRU bits from the access order.
   • Root bit: last access to the left pair $\{w_0,w_1\}$ was $w_0$ (2nd overall); last to right pair $\{w_2,w_3\}$ was $w_3$ (3rd overall). The right pair was touched more recently ⇒ root points right. So the victim search goes left.
   • Left-pair bit: within $\{w_0,w_1\}$, $w_0$ was touched (position 2), $w_1$ never re-touched after — so the pair bit points to $w_0$ ⇒ victim is the other one, $w_1$.
3. Compare. Here pseudo-LRU also lands on $w_1$.

Answer: both true-LRU and pseudo-LRU evict $w_1$ this time — but pseudo-LRU only tracks per-pair recency, so with a different access order (e.g. $w_0,w_2,w_1,w_3$) it can miss the true coldest block. It is an approximation, cheaper (3 bits vs 8 bits) but not exact.

Recall Cost comparison

Question: For a 4-way set, how many bits does exact LRU vs pseudo-LRU need? ::: Exact LRU: 4 counters × 2 bits = 8 bits. Pseudo-LRU: 3 bits (n−1). Same victim often, but not always.

Verify: bit counts $4\times 2=8$ and $4-1=3$; both methods agree on $w_1$ for this trace. ✓

---

Recap clozes

• The only case where LRU, FIFO and Random all behave identically is a 1-way (direct-mapped) cache.
• FIFO can suffer Belady's anomaly, where a larger cache gives more misses.
• Expected misses under Random need a probability calculation, not a fixed count.