- 2071 Magh · 3 marks
Cache replacement policies
Short answer
Common cache replacement policies include: random (choose any block), FIFO (evict the oldest-loaded), LRU (evict the least recently used), and LFU (evict the least frequently used). LRU typically yields the best hit rate but needs tracking circuitry. Direct-mapped caches require no policy.
Write the cache replacement policies.
When a miss occurs and the cache (or the set) is full, a block must be evicted. The common replacement policies are:
- Random: pick a line at random. Simple and cheap, but may remove a frequently used block.
- FIFO (first in, first out): evict the block that has been in the cache the longest. Easy, but ignores how often the block is used.
- LRU (least recently used): evict the block not used for the longest time, using locality of reference. Best hit ratio, but needs usage-tracking hardware.
- LFU (least frequently used): evict the block with the fewest accesses, using counters.
Direct-mapped caches need no policy, since each block has only one possible line.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Cache write policy and replacement algorithm · Embedded System, chapter 4
- Need for replacement algorithm in cache · Computer Organization and Architecture, chapter 6