Skip to main content

LRU replacement with hit and miss

Short answer

LRU replaces the least recently used block. On a hit, the accessed block becomes most recent. On a miss with a free line, the new block is loaded as most recent. On a miss with a full cache, the least recent block is evicted. Example: 4-block cache with reference string 2,3,2,1,5,2,4,5,3,2,5,2 yields 6 hits, 6 misses, hit ratio 0.5.

Explain the Least Recently Used (LRU) replacement algorithm in case of hit and miss with suitable example.

LRU (Least Recently Used) replaces the cache block that has not been used for the longest time. It uses temporal locality: a block used recently is likely to be used again soon. The hardware keeps an age (or use) counter for each line; on each access the age of the used line is reset and others are increased.

  • Hit: the block is in the cache; no replacement. The block becomes the most recently used.
  • Miss with free line: the block is loaded into a free line and becomes the most recently used.
  • Miss with cache full: the least recently used block is removed and the new block is loaded.

Example: cache of 4 blocks, reference string 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2

Ref  Result            Cache (most recent first)
2    Miss              [2]
3    Miss              [3, 2]
2    Hit               [2, 3]
1    Miss              [1, 2, 3]
5    Miss              [5, 1, 2, 3]
2    Hit               [2, 5, 1, 3]
4    Miss (evict 3)    [4, 2, 5, 1]
5    Hit               [5, 4, 2, 1]
3    Miss (evict 1)    [3, 5, 4, 2]
2    Hit               [2, 3, 5, 4]
5    Hit               [5, 2, 3, 4]
2    Hit               [2, 5, 3, 4]

Hits = 6, misses = 6, hit ratio = 6/12 = 0.50. When 4 was referenced the cache was full and the least recently used block was 3, so 3 was evicted; when 3 came back, block 1 was the least recently used, so 1 was evicted.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computer Organization and Architecture chapter 6 questions →