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

• LRU: the block unused for the longest time (largest gap since its last access).
• LFU: the block with the smallest access-count (least frequently used so far).
• FIFO: the block that entered the cache earliest, no matter how recently it was used.
• Random: a uniformly random block — every resident block equally likely.

Why these four and not one universal rule? Each is a different guess about the unknowable future. There's no free lunch: the only policy that is provably best is Belady's OPT, and it needs future knowledge, so it can't be built.

This single table is the seed of every "LRU vs FIFO" trap below: the difference lives on hits, not misses.

Write the cache MRU→LRU (left = most-recently-used, right = least-recently-used, as defined above). A hit moves the block to the left end (MRU); a miss on a full cache evicts the rightmost (LRU) block.

Hits = 1 (only step 4). Misses = 7.

Look at step 5: A was touched at step 4, so it sits ahead (nearer the MRU/left end) of C; B had not been touched since step 2, so B is at the LRU/right end and is the victim. That's the whole rule in action.

Queue shown oldest→newest (left = oldest by insertion, right = newest). Note this is a different order from LRU's recency order — FIFO ranks by when a block arrived, and hits do not reorder anything.

Hits = 2 (steps 4 and 6). Misses = 6.

Contrast with LRU: at step 5 LRU kept A (just used) and evicted B, but FIFO evicted A because insertion order never noticed the step-4 hit. Yet FIFO got lucky at step 6 (B was still queued), so FIFO ends with more hits here — a reminder that "smarter" LRU is not guaranteed to win on every trace.

Track a counter per resident block (counter = number of accesses while resident; a fresh load starts at 1).

Hits = 2 (steps 4 and 8). Misses = 6.

Notice A survives everything: its count climbs (2, then 3) so it is never the minimum. That's LFU's whole personality — it protects the popular block.

3 frames (queue oldest→newest):

3 frames → 9 misses.

4 frames:

4 frames → 10 misses. More frames, more misses — that's Belady's anomaly, and only FIFO-like policies can show it.

What the figure below shows: two bars, the left (blue) for a 3-frame FIFO cache at height 9, the right (red) for a 4-frame cache at height 10. The vertical axis is the FIFO miss count for the trace printed in green underneath. The yellow arrow points upward from the 3-frame bar to the taller 4-frame bar, labelled "+1 miss (should DROP!)" — driving home that giving FIFO more room here made things worse, the exact signature of the anomaly.

Read it as a warning label: for FIFO, the miss-vs-size curve is not guaranteed to slope downward.

The stack property says: for the same trace, the contents of a size-$n$ LRU cache are always a subset of the size-$(n+1)$ cache, written $C_n\subseteq C_{n+1}$.

Why LRU has it: LRU ranks blocks by a single recency order that does not depend on cache size. A size-$n$ cache keeps the top-$n$ most-recent blocks; a size-$(n+1)$ cache keeps the top-$(n+1)$. The top-$n$ set is a subset of the top-$(n+1)$ set by construction.

The consequence: if a block is a hit in the smaller cache, it is present in the larger cache too (subset ⇒ present), so it is also a hit there. Hence misses can only stay the same or drop as size grows — never rise. FIFO fails this because its "which block leaves" depends on a queue whose evictions differ with size, breaking the subset relation. This is also why pseudo-LRU is worth approximating: it inherits most of LRU's good behaviour cheaply.

Use the boxed formula: $\text{AMAT}=T_{hit}+m\cdot T_{penalty}$

• P1: ${\text{AMAT}}_1=2+0.08\times 120=2+9.6=11.6$ ns.
• P2: ${\text{AMAT}}_2=2+0.05\times 120=2+6.0=8.0$ ns.
• Improvement: $\frac{11.6-8.0}{11.6}=\frac{3.6}{11.6}\approx 0.3103$, i.e. about $31.0\%$ faster average access.

Why the small miss-rate change yields a big time change: the penalty ($120$ ns) dwarfs the hit time ($2$ ns), so the term $m\cdot T_{penalty}$ dominates AMAT. Cutting $m$ from $0.08$ to $0.05$ is leverage.

Penalty contribution $=m_1\cdot T_{penalty}=0.08\times 120=9.6$ ns out of $11.6$ ns. $\frac{9.6}{11.6}\approx 0.8276\Rightarrow \text{82.8\%}.$ Over four-fifths of average access time is "waiting for memory." That is why replacement quality matters at all — it's the only knob that touches the dominant term.

Sequence: $A,B,C,A,D,A$. Capacity 3.

LRU (MRU→LRU):

LRU hits = 2.

FIFO (oldest→newest):

FIFO hits = 1.

The mechanism: at step 4 both hit on A, but only LRU promoted A. When D arrives at step 5, FIFO evicts A (oldest in queue) while LRU keeps A (freshly used). So step 6's re-access to A is an LRU hit but a FIFO miss. LRU 2 hits, FIFO 1 hit — strict win. This is the minimal witness of "the difference lives on hits."

After warm-up: cache $=\{X:5\}$ plus two empty slots.

Loop misses = 6 out of 6 — a 0% hit rate on the working set!

Why $X$ is immortal: its count $5$ is always strictly above the working-set blocks' count $1$, so $X$ is never the minimum and is never evicted. It squats one slot forever even though it's dead. This is cache pollution / stale popularity. Fix in real LFU: periodically age (decay) the counters so old fame fades. Compare with LRU, which would happily evict $X$ once it goes untouched.

LRU-vs-FIFO diverge on ::: a hit (LRU promotes, FIFO doesn't). Belady's anomaly can appear under ::: FIFO (not LRU/LFU, which are stack algorithms). AMAT keeps $T_{hit}$ on a miss because ::: the cache is probed first, then memory. LFU's failure mode is ::: stale popularity / cache pollution, fixed by aging.