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