Exercises — Replacement policies (LRU, FIFO, random)

• LRU: evict the block not accessed for the longest time (oldest use).
• FIFO: evict the block loaded earliest (oldest insertion), ignoring how recently it was used.
• Random: evict a uniformly random block, tracking no history at all.

• LRU — updates: the hit block becomes most recently used (reordered to the front).
• FIFO — does nothing: insertion order is unchanged by hits.
• Random — does nothing: there is no history to update.

This one line is the whole difference between LRU and FIFO. LRU reacts to access; FIFO only reacts to insertion.

• Exact LRU: one 2-bit counter per way $\Rightarrow 4\times 2=8$ bits.
• Tree pseudo-LRU: $n-1=4-1=3$ bits.

FIFO for the same set needs only $\lceil {\log }_{2}4\rceil =2$ bits (one pointer for the whole set).

Why $n-1$ bits for the tree? Picture the $n=4$ ways as the four leaves of a small binary tree. To pick a single leaf you walk down from the root making one left/right choice at each internal node: first choice picks the left pair or the right pair, second choice picks one way inside that pair. A binary tree with $n$ leaves has exactly $n-1$ internal nodes, and each internal node stores one bit ("which child was touched more recently — go the other way to evict"). So $4$ leaves $\to 3$ internal nodes $\to 3$ bits. On every access you flip the bits along the root-to-leaf path to point away from the block just used; on eviction you follow the bits to reach the pseudo-oldest leaf. That is why $n-1$ bits suffice instead of the $n{\log }_{2}n$ bits exact LRU needs.

Recency shown as [MRU → LRU] (freshest → eviction candidate).

Misses = 4 (only the second A is a hit). Final contents: {C, B}. Note the C step: B was LRU (A had just been re-hit), so B is evicted — not A.

Queue shown [Head(oldest) → Tail(newest)]. Hits leave the queue untouched.

Misses = 3. Final contents: {C, B}. The C step evicts A — the oldest insertion — even though A was just hit. That saved B, so the final B is a hit. Here FIFO beats LRU (3 vs 4 misses) purely by luck of pattern.

AMAT stands for Average Memory Access Time — the average number of time units one memory access costs, blending fast hits and slow misses.

Why the formula decomposes this way. Every access first tries the cache, so it always pays the Hit Time. A fraction of accesses (the Miss Rate) additionally miss and must fetch from the slower level, paying the Miss Penalty on top. Averaging over all accesses, the expected extra cost is (fraction that miss) $\times$ (cost of a miss) $=$ Miss Rate $\times$ Miss Penalty. Add the guaranteed hit cost and you get: $\text{AMAT}=\text{Hit Time}+\text{Miss Rate}\times \text{Miss Penalty}$ This is just an expected value: base cost everyone pays, plus a penalty weighted by how often it strikes.

Plugging in: ${\text{AMAT}}_{4\%}=2+0.04\times 100=2+4=6\text{ns}$ ${\text{AMAT}}_{3\%}=2+0.03\times 100=2+3=5\text{ns}$ Improvement $=\frac{6-5}{6}=0.1\overline{6}\approx 16.7\%$ faster average access. A "mere" 1-percentage-point drop in miss rate cut average access time by one-sixth — exactly why replacement policy matters. See 5.4.01-Cache-organizationand-addressing for where Hit Time comes from.

Recency [MRU→LRU]. Full set = 3 blocks.

Misses = 6. Final set: {B, E, A}. Watch the D step: LRU order was [B,A,C], so C (LRU) dies. Then E kicks A (A had aged to LRU). Then A returns as a miss — LRU discarded it one step too early here.

Queue [Head→Tail], hits frozen.

*At the B step the queue head is C, so C is evicted, B loaded into that slot. Misses = 7. Final set: {E, B, A}. Comparison: LRU = 6 misses, FIFO = 7. Here LRU wins because it exploited that A and B were reused (temporal locality — see Temporal-and-spatial-locality), while FIFO evicted A blindly by insertion order.

LRU is a stack algorithm: at any moment, the set of blocks a cache of size $k$ holds is always a subset of what a cache of size $k+1$ would hold on the same trace. Formally, order all blocks by recency in one big stack; a size-$k$ cache holds exactly the top $k$ of that stack. Growing the cache to $k+1$ just adds the next block down — it never removes anything the smaller cache kept. So any block that was a hit with $k$ frames is still a hit with $k+1$ frames. Hits can only be added, never lost ⇒ misses are monotonically non-increasing in capacity. FIFO lacks this property because its "stack" (insertion order) does not nest as capacity grows.

Queue [Head→Tail]. ✘ = miss.

3-frame misses = 9.

4-frame misses = 10.

Result: 9 misses with 3 frames vs 10 misses with 4 frames — more cache, more misses. This is Belady's Anomaly. The figure below plots both curves so you can see the crossover.

Recency [MRU→LRU]. Full set = 3 blocks.

Count the ✘ rows: refs 1,2,3,4 (4 misses), then 1,2,5 (3 more = 7), then 3,4 (2 more = 9). The final 5 is a hit. LRU 3-frame misses = 9. The three ✔ rows are the mid-sequence hits on blocks 1 and 2 (steps 8, 9) and the final hit on 5 (step 12).

Count the ✘ rows: 1,2,3,4 (4) then 5 (5) then 3,4,5 (3 more = 8). LRU 4-frame misses = 8.

Check: 3-frame LRU = 9 misses, 4-frame LRU = 8 misses. Since $8\le 9$, misses did not increase with capacity — the stack property holds, exactly as Exercise 3.3 predicts. Contrast the FIFO anomaly (9 → 10) with LRU's clean 9 → 8.

With 1 slot, A and B conflict on every access: loading A evicts B, loading B evicts A. Since consecutive accesses always differ (A, B, A, B…), every access is a miss. $\text{Miss rate}=100\%=1.0$ Policy is irrelevant: with only one candidate to evict, LRU, FIFO and Random all evict the same (only) block. Miss rate is $1$ for all three. Lesson: replacement policy only matters when there is a choice of victim, i.e. associativity $\ge 2$. A pathological conflict (working set > ways) defeats every policy — see Working-set-model and Cache-conscious-programming for how software avoids this.

Random picks each of the 4 ways with equal probability, so $P_{\text{Random}}(\text{evict }{B}_1)=\frac{1}{4}=\mathrm{0.25.}$ Random makes the wrong choice $25\%$ of the time here.

Ideal LRU: we are told $B_1$ is the most-recently-used block. LRU always evicts the least-recently-used block, which is one of $B_2,B_3,B_4$ — never the MRU block. Therefore $P_{\text{LRU}}(\text{evict }{B}_1)=0.$

Comparison: Random has a $0.25$ chance of throwing away the hot block; LRU has a $0$ chance. That gap — $25\%$ vs $0\%$ of self-inflicted extra misses — is exactly the payoff of tracking history. LRU spends hardware bits to buy this protection, and it pays off whenever temporal locality holds (the just-used block really is likely to be needed again).

Recommended: tree pseudo-LRU (or plain FIFO if bits are truly scarce).

• Bit budget: exact LRU needs $4\times 2=8$ bits/set; tree pseudo-LRU needs $3$ bits/set; FIFO needs $2$ bits/set. Pseudo-LRU nearly matches exact-LRU miss rate at $3$ bits — a strong bits-vs-performance point.
• Real-time latency: all three (LRU counter update, FIFO pointer, pseudo-LRU bit-flip) are O(1) constant-time in hardware — no policy stalls the pipeline, so the fixed-cycle requirement is met by any of them.
• Miss rate: on locality-rich embedded workloads pseudo-LRU beats FIFO (which risks Belady-style bad phases) and beats Random's $\sim 25\%$ mis-evictions.
• When FIFO wins: if silicon area is the dominant constraint and workloads are streaming (little reuse, so LRU's history buys nothing), FIFO's 2-bit cost is optimal. Verdict: choose tree pseudo-LRU — 3 bits, constant-time, near-LRU miss rate, no anomaly worries. Relate to write-behavior sizing in 5.4.03-Write-policies-(write-through,-write-back) and multi-core effects in 5.4.06-Cache-coherence-protocols.