5.4.5 · D5Memory Hierarchy & Caches
Question bank — Replacement policies (LRU, FIFO, random)
This page is a workout for your intuition, not your arithmetic. Every item below targets a place where students of replacement policies usually slip — a hidden assumption, a boundary case, or a "sounds true but isn't" claim. Cover the answer, commit to a guess, then reveal.
Before we start, a quick vocabulary anchor so nothing below is a symbol you haven't earned:
The single idea that generates half the traps below:
True or false — justify
Give a reason, never a bare yes/no.
TF1. "LRU and FIFO always evict the same block."
False. They only agree when no hits occur between insertions; a hit re-orders LRU's recency list but leaves FIFO's insertion queue untouched, so after a hit they can point at different victims.
TF2. "On a cache hit, FIFO must update its queue pointer."
False. FIFO ignores hits entirely — the pointer only advances on an eviction. That obliviousness is exactly why FIFO is cheap and why it can evict a freshly-used block.
TF3. "A larger cache can never increase the miss rate."
False for FIFO. This is Belady's Anomaly: FIFO can miss more with a bigger cache because extra capacity shifts the phase of its circular queue relative to the access pattern. It IS true for LRU, which is a stack algorithm.
TF4. "Random replacement has no hardware to track history, so it needs no state at all."
Mostly true, with a caveat. It stores no per-block recency or insertion info, but it does need a small pseudorandom source (e.g. a linear-feedback shift register) shared across sets to pick a victim.
TF5. "Exact LRU in a 4-way set needs only 3 bits."
False — that's pseudo-LRU. Exact LRU needs to order 4 blocks, roughly bits (or bits with the naive counter method). The 3-bit () figure is the tree-based approximation.
TF6. "In a direct-mapped cache the replacement policy still matters."
False. A direct-mapped cache is 1-way: each address has exactly one possible slot, so there is only ever one candidate to evict. LRU, FIFO, and Random all reduce to the same forced eviction.
TF7. "LRU always beats FIFO on miss rate."
False. LRU usually wins, but for some access patterns FIFO ties or even edges ahead; LRU's advantage is typical-case and its guarantee of no Belady's Anomaly, not a universal miss-rate dominance.
TF8. "Replacement policy affects the hit time term of AMAT."
False (essentially). The policy changes the miss rate, and , so it moves the middle term. Hit time is set by array/tag lookup, not by which block you'd evict.
TF9. "LRU is a good idea because it predicts the future."
Half-true. LRU doesn't predict — it bets on the past repeating, exploiting temporal locality. When locality is absent (e.g. a streaming scan bigger than the cache), that bet loses badly.
Spot the error
Each statement contains one concrete mistake. Name it.
SE1. "For access sequence A, B, A, C in a 2-way set, FIFO evicts B."
Wrong victim. FIFO evicts the earliest inserted block, which is A — the hit on A does not save it. LRU would evict B; the student swapped the two policies.
SE2. "Pseudo-LRU tracks the exact same victim as true LRU, just with fewer bits."
'Exact same' is wrong. Tree-based pseudo-LRU is an approximation; it can occasionally pick a different (not truly oldest) block. It's "close enough," not identical.
SE3. "FIFO needs one counter per block to remember insertion order."
Over-built. FIFO needs one small -bit pointer per set, not per block — the pointer alone identifies the next victim as it cycles through the ways.
SE4. "With Random replacement, the miss rate is unpredictable and therefore useless for real chips."
Wrong conclusion. Random's per-run victim is unpredictable, but its average miss rate is stable and often within a few percent of LRU — hence its use in real high-associativity caches where LRU is too expensive.
SE5. "LRU's recency counter for the just-accessed block should be set to ."
Backwards. The just-accessed block is most recently used, so its recency resets to ; the victim is the block whose recency equals .
SE6. "Belady's Anomaly proves LRU can also get worse with more capacity."
Misattributed. The anomaly is a property of FIFO (and non-stack policies). LRU is a stack algorithm and is guaranteed monotone — more capacity never raises its miss count.
SE7. "On a write, LRU doesn't update recency because writes aren't reads."
False distinction. LRU updates recency on any access, read or write. This interacts with write policies but the recency touch happens regardless.
Why questions
WHY1. Why does FIFO stay oblivious to hits while LRU reacts to them?
Because they answer different questions: FIFO tracks arrival time (fixed once a block enters), so a hit changes nothing; LRU tracks last-use time, and a hit is a use, so it must move the block to "most recent."
WHY2. Why is exact LRU rarely used in caches with high associativity (say 16-way)?
The bookkeeping cost grows fast (roughly bits per set) and every access must reorder the whole set. At high this is expensive in area and latency, so designers switch to pseudo-LRU or Random.
WHY3. Why does a 1% change in miss rate cause a much larger performance change?
Because a miss costs a huge miss penalty relative to hit time; in the AMAT formula the miss-rate term is multiplied by that big penalty, so small miss-rate swings dominate memory-bound runtime (often 10–20%).
WHY4. Why does LRU exploit temporal locality but not spatial locality directly?
LRU decides which block to keep, and temporal locality says recently-touched blocks recur — that's the recency signal LRU reads. Spatial locality is captured by block size (loading neighbors together), a separate design lever.
WHY5. Why can Random be good enough despite ignoring all history?
In a large associative set, the odds of randomly evicting a block that's about to be reused are low, and the working set usually survives in the remaining ways — so average miss rate lands close to LRU without any tracking hardware.
WHY6. Why does FIFO's pointer use modulo- arithmetic?
The pointer cycles through ways and must wrap back to after the last way — implements a circular queue, matching FIFO's "next-oldest becomes the victim" behavior.
WHY7. Why do replacement policies operate within a set, not across the whole cache?
An address can only map to one specific set (its index bits fix that), so eviction candidates are exactly the ways of that set — the policy never needs to consider blocks in other sets.
Edge cases
EC1. Cache not yet full — which block does LRU evict?
None yet. While an empty way exists, every policy loads the new block into the free slot; eviction logic only fires once all ways of the set are occupied.
EC2. (direct-mapped) — what do LRU, FIFO, and Random do?
They all collapse to the identical behavior: the single resident block is the only candidate, so it's always the victim. Policy choice is moot.
EC3. The exact same block is accessed repeatedly (A, A, A, ...) — how does each policy behave?
After the first load it's all hits: LRU keeps re-marking A as most-recent (no eviction), FIFO leaves its queue frozen (no eviction), Random is never invoked. No policy differences appear.
EC4. Access sequence larger than the set and with no reuse (pure streaming scan) — how do the policies compare?
Every access is a compulsory/capacity miss for all of them; LRU's cleverness gains nothing because the past never repeats. Here even Random matches LRU — locality is what LRU needs, and there is none.
EC5. Two blocks in a set have equal recency under LRU — who wins?
This can't happen in true LRU, since each access gives a distinct last-use time. It only arises in approximations (pseudo-LRU), where a fixed tie-break rule chooses; the point is that exact LRU keeps a strict total order.
EC6. A write-allocate miss under write-back — does replacement change?
The victim choice is unchanged (same policy), but evicting a dirty victim forces a write-back to memory first, raising that particular eviction's cost even though the policy logic is identical.
EC7. How does replacement policy interact with a TLB or page replacement?
The same LRU/FIFO/Random ideas reappear one level up for page frames — and Belady's Anomaly was originally described there. The concepts transfer; the hardware and time scales differ.
Recall Self-test before you leave
- Which policy reacts to hits, and which one ignores them? ::: LRU reacts (updates recency); FIFO ignores hits.
- Which policy can suffer Belady's Anomaly? ::: FIFO (and other non-stack policies), never LRU.
- What does the recency value mark? ::: The least-recently-used block — the LRU victim.
- When do all three policies behave identically? ::: In a direct-mapped () cache, or on a pure no-reuse streaming scan.
Related depth: Cache-conscious-programming shows how programmers shape access patterns so whichever policy the hardware uses actually keeps the working set; 5.4.06-Cache-coherence-protocols adds eviction's role in multi-core sharing.