3.6Replacement
The idea
When a set is full, a replacement policy chooses which block to evict. LRU evicts the least recently used; FIFO evicts the oldest arrival.
Think of it like this: Clearing a crowded desk: put away the book you have not touched for longest (LRU) versus the one that arrived first (FIFO).
Why it exists
Good choices keep the blocks you are about to reuse. The wrong choice can turn hits into misses.
How it works
- LRU tracks use order; a hit moves the block to "most recent".
- FIFO ignores hits: it only remembers arrival order.
- Both only matter if there is a choice (not in direct-mapped).
- Random is cheap and surprisingly decent.
Worked example: 4-line fully associative cache, blocks 0 1 2 3 0 4 0 1
FIFO: 7 misses (0 gets evicted despite a recent hit). LRU: 6 misses.
Now play with it
- →The simulator starts on FIFO. Step through to the end, then change Replacement to LRU and compare the hit ratio.
4 lines · 1 set(s) × 4 way(s) · cache = 32 bytes
| Set | Way 0 | Way 1 | Way 2 | Way 3 |
|---|---|---|---|---|
| 0 | · | · | · | · |
Check yourself
Which policy evicts the block that has been in the cache longest, even if it was just used?
Exam notes (the dense version)
LRU (best usually), FIFO, Random. Direct-mapped needs none.
Previous year questions: Cache Memory (22)
PYQs are grouped by topic, so this is the full set for Cache Memory; try the ones that match this subtopic. Open all 22 on the topic page.