When all lines are occupied, bringing in a new block requires that an existing line be overwritten.

Direct mapping

  • No choice possible with direct mapping
  • Each block only maps to one line
  • Replace that line

Associative and Set Associative mapping

  • Algorithms must be implemented in hardware for speed
  • Least Recently used (LRU)
    • replace that block in the set which has been in cache longest with no reference to it
    • Implementation: with 2-way set associative, have a USE bit for each line in a set. When a block is read into cache, use the line whose USE bit is set to 0, then set its USE bit to one and the other line’s USE bit to 0.
    • Probably the most effective method
  • First in first out (FIFO)
    • replace that block in the set which has been in the cache longest
    • Implementation: use a round-robin or circular buffer technique (keep up with which slot’s “turn” is next
  • Least-frequently-used (LFU)
    • replace that block in the set which has experienced the fewest references or hits
    • Implementation: associate a counter with each slot and increment when used
  • Random
    • replace a random block in the set
    • Interesting because it is only slightly inferior to algorithms based on usage