Introduction
Cache Basics Direct Mapped Cache Direct Mapped Example 1 Direct Mapped Example 2 Direct Mapped Problem 1 Direct Mapped Problem 2 Direct Mapped Problem 3 Direct Mapped Problem 4 Direct Mapped Comparators Direct Mapped Disadvantages Direct Mapped Locality Direct Mapped UVM Example Associative Mapped Cache Associative Mapped Problem 1 Associative Mapped Problem 2 Associative Mapped Problem 3 Associative Mapped Problem 4 Set Associative Mapped Cache Set Associative Mapped Comparators Set Associative Mapped Problem 1 Set Associative Mapped Problem 2 Set Associative Mapped Problem 3 Set Associative Mapped Problem 4 Set Associative Mapped Problem 5 Other Mapping Problem - Example 1 Cache Replacement Algorithms LRU Cache Replacement Algorithm FIFO Cache Replacement Algorithm MRU Cache Replacement Algorithm PLRU Cache Replacement Algorithm Round Robin Cache Replacement Algorithm
UVMArena

Cache Memory Replacement Algorithm – MRU (Most Recently Used)

The Most Recently Used (MRU) replacement algorithm is a cache replacement policy where the cache block that was accessed most recently is replaced when a new block needs to be loaded and the cache is full.

Unlike FIFO, the order in which blocks were inserted into cache does not matter. What matters is which block was accessed most recently by the CPU.

Key Idea of MRU

  • When cache is full and a new block must be inserted:
  • Identify the most recently accessed block.
  • Replace that block with the new memory block.

MRU is based on the assumption that if a block was used very recently, it may not be needed again soon.

Important Observations

  • The order of filling cache lines does not matter.
  • Only the recent access history is important.
  • This makes MRU different from FIFO, where insertion order must be tracked.
  • The most recently referenced block is always the replacement candidate.

Example Scenario

Assume the cache contains 8 cache lines and the CPU generates the following reference string: 


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

The cache initially starts empty.

  • Pages are loaded until the cache becomes full.
  • If the requested page already exists → Cache Hit
  • If it does not exist → Cache Miss
  • When cache is full → replace the Most Recently Used page

Results of the Example

  • Total Cache Misses: 11
  • Total Cache Hits: 6

For this particular reference string, the MRU algorithm performs better than FIFO and LRU because it results in fewer cache misses.

Final Cache State

After executing the entire reference string using MRU replacement:

  • Memory block 7 is stored in cache line 2.

(Cache blocks are typically indexed starting from 0.)

Important Note

The performance of cache replacement algorithms depends heavily on the reference string (the order in which the CPU accesses memory).

  • MRU may perform better in some workloads.
  • LRU may perform better in others.
  • No single replacement policy is universally optimal.