A program accesses memory blocks in a strict cyclic pattern: A, B, C, D, E, A, B, C, D, E, ... and the cache holds 4 blocks. LRU is used. What happens?
ALRU performs well because it keeps the most recently used blocks ready
BLRU suffers near-constant misses because it evicts the block that will be needed next in the cycle
CLRU and FIFO produce identical miss rates on cyclic patterns
DLRU automatically detects cyclic patterns and switches to a larger effective cache
When the working set (5 blocks) is slightly larger than the cache (4 blocks), LRU evicts the block that was accessed longest ago — which is exactly the next block needed in the cycle. This produces a miss on every access. This is the classic failure mode of LRU, and it's why random replacement can outperform LRU on such workloads despite seeming less sophisticated.
Question 2 Multiple Choice
Why do real processors use pseudo-LRU instead of exact LRU for highly associative caches?
APseudo-LRU produces fewer misses than exact LRU in all workloads
BExact LRU requires tracking the full access order of all blocks in a set, demanding too much hardware state and logic
CFIFO is preferred over both LRU variants in modern cache designs
DPseudo-LRU is mandated by the x86 architecture specification
For a 2-way cache, LRU needs only 1 bit per set. For an 8-way set-associative cache, tracking exact access order requires log2(8!) bits and complex update logic per access — prohibitively expensive at cache speeds. Pseudo-LRU tree-based schemes approximate 'least recently used' with far fewer bits and simpler updates, trading some accuracy for practical implementation.
Question 3 True / False
Random replacement is a naive fallback strategy that is typically outperformed by LRU and FIFO in practice.
TTrue
FFalse
Answer: False
Random replacement is a well-studied policy used in production CPUs (including some ARM Cortex designs). It performs within a few percent of LRU on typical workloads and actually outperforms LRU on adversarial cyclic patterns, because its misses are unpredictable rather than systematically worst-case. 'Random' avoids the pitfalls of deterministic policies.
Question 4 True / False
FIFO can exhibit more cache misses when cache size is increased — a phenomenon called Belady's anomaly.
TTrue
FFalse
Answer: True
Belady's anomaly is a counterintuitive property of FIFO: for certain access sequences, adding more cache slots actually increases the miss rate. This occurs because FIFO evicts the oldest-loaded block regardless of recency, which can displace a block that will be needed soon. LRU does not exhibit Belady's anomaly.
Question 5 Short Answer
Why can random replacement sometimes outperform LRU, and what does this reveal about replacement policy design?
Think about your answer, then reveal below.
Model answer: LRU assumes temporal locality — the least-recently-used block is the safest to evict. On cyclic access patterns where the working set is slightly larger than the cache, LRU systematically evicts the next-needed block, producing near-100% misses. Random replacement has no such deterministic worst case — its eviction choices are unpredictable and avoid the adversarial pattern. This reveals that replacement policy design is a tradeoff: LRU is better on average for many workloads, but its determinism can be exploited. Robustness to worst-case behavior is a real design criterion alongside average-case hit rate.
This is the key insight: no single policy is universally optimal. The 'obvious' choice (LRU) has specific failure modes that a 'dumb' choice (random) avoids. In hardware design, implementation cost and worst-case robustness matter as much as average-case performance, which is why random replacement is not merely a fallback but a legitimate engineering choice.