Block Replacement

 

• On a cache miss, a block must be expelled before the new block is brought in from memory (unless the valid bit indicates that the cache block is empty)
• No choice for a direct-mapped cache
• Objective: to retain blocks which will be used again soon
  • Optimal (OPT): replace the block which will not be used for the longest time
  • Random
  • Least-recently used (LRU): replace the block which has been unused for the longest time

• LRU uses the past as an estimate of the future, i.e. the corollary of temporal locality: if recently used blocks are likely to be used again, the best candidate for replacement is the least recently used block

• ...
• ...