LRU Cache Replacement Algorithm

What is the LRU Replacement Algorithm?

The Least Recently Used (LRU) algorithm replaces the cache block that has not been accessed for the longest time.

The main idea is simple: if a memory block has not been used recently, it is less likely to be used again soon.

Therefore, when the cache is full and a new block must be inserted, LRU selects the block that was accessed the longest time ago and replaces it.

Example Setup

Consider a fully associative cache with 8 cache lines.

The cache lines are numbered:

Line0
Line1
Line2
Line3
Line4
Line5
Line6
Line7

In a fully associative cache, a memory block can be placed in any cache line.

The CPU generates a sequence of memory block requests called a block reference string.

Block Reference String

Example sequence of RAM block requests from the CPU:

4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7

Each number represents a RAM block number.

When the CPU requests a block:

• If the block is already in cache → Cache Hit
• If the block is not in cache → Cache Miss

Cache Hits and Misses

Initially, the cache is empty, so the first requests cause cache misses until the cache becomes full.

Once the cache is full, LRU determines which block should be replaced.

Example:

CPU requests block 45
Cache is full

LRU selects the block that was accessed least recently
That block is replaced by block 45

The same process continues for every new request.

Final Result of the Example

After processing the entire reference string using the LRU replacement policy:

• The page containing RAM block 7 ends up in cache line 5.

Therefore:

Answer = Cache Line 5

Total Cache Misses

Because the cache starts empty, the first accesses generate misses.

Additionally, every time a block must be replaced, a cache miss occurs.

For the given reference string:

Total Cache Misses = 12