Skip to main content

Need for replacement algorithm in cache

Short answer

When a set is full in associative or set-associative mapping, a new block must replace an existing one on a miss. The replacement algorithm (LRU, FIFO, etc.) selects the block to evict, aiming to keep frequently/recently used data for high hit ratio. Direct mapping needs no algorithm.

Why is a replacement algorithm used when designing the cache? Explain with example.

The cache holds only a few of the many blocks of main memory. In associative and set associative mapping, a new block may be placed in any line of the cache or the set. When all these lines are full and a miss occurs, one block must be removed to make room. The replacement algorithm chooses that block. It is needed so that the cache keeps taking new blocks while keeping the most useful ones, which keeps the hit ratio high. (In direct mapping the line is fixed, so no algorithm is needed.)

Replacement algorithms

  • LRU: removes the block unused for the longest time.
  • FIFO: removes the oldest block.
  • LFU: removes the block with the fewest accesses.
  • Random: removes a random line.

Example: cache with 3 lines, references 1, 2, 3, 1, 4, 1, 2

Ref  FIFO cache  Result   LRU cache   Result
1    [1]         miss     [1]         miss
2    [1, 2]      miss     [1, 2]      miss
3    [1, 2, 3]   miss     [1, 2, 3]   miss
1    [1, 2, 3]   hit      [2, 3, 1]   hit
4    [2, 3, 4]   miss     [3, 1, 4]   miss
1    [3, 4, 1]   miss     [3, 4, 1]   hit
2    [4, 1, 2]   miss     [4, 1, 2]   miss

FIFO gets 1 hit and LRU gets 2 hits out of 7 references. At reference 4 the cache is full, so a block must be replaced. FIFO removes 1 (loaded first) even though it was just used, and later has to fetch 1 again. LRU removes 2 (least recently used) and keeps 1, so it gets an extra hit. The replacement algorithm therefore decides how many misses follow.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computer Organization and Architecture chapter 6 questions →