Block Replacement
Replacement candidates are --
- Any block in a fully associative cache
- Any block of a set in set associative caches
- The indexed block for direct mapped
Replacement strategies --
- Opt is best, but impossible
- Least Recently Used (LRU) approximates Opt. Expensive
- Random is easy, but impossible for software management
For 2-way s.a., random has 1.1 times higher miss rate than LRU
"Use" bit can approximate LRU