Cache Replacement Policies

Cache replacement is applied with Cache and Main Memory. When the cache is full, we replace a block (line) of the cache with the main memory Block.

 Page Replacement is applied with RAM and Hard Disk. When RAM is full, we replace a page of RAM with the Frame of the Hard Disk.

Types of Cache Replacement Policies

  1. FIFO
  2. LRU
  3. MRU

Not Applicable on Direct mapping, because we fix for each block to come in a particular cache line.


The First-in-First-out (FIFO) algorithm replaces the oldest block stored in the cache.

Note: If there are 4 positions in the cache when the 5th block comes into the cache, then the element of position 1 is replaced in any case.

Question 1: Consider a 4-way set associative cache with a total of 16 cache blocks. Main memory block requests are


As 4 blocks can reside in each line at a time. So, the solution is given in the following diagram

FIFO (Cache Replacement Policy)

Note: A block at position 1 in any cache line will be replaced after the line is full. If the same block comes again, it will be a cache hit. It does not change the block position from 1 to any else.

2. LRU

Replace the cache block, which was not used for the longest period of time in the past.


Consider a fully associative cache with 8 cache blocks (0-7) and the following sequence of memory block requests: 4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25 and 7. By using LRU, find the position of memory block 7 in the cache.

Solution: At point 45, the 8 blocks of cache are filled, and no free space is available to accommodate a new block in the cache. So we check back the reference string at point 45 and replace the least recently used block in the cache, which is 4 in the example. And so on, the next incoming block is 22, which will be replaced with block no. 3.

LRU (Cache Replacement Policy)

Question: 2

Consider a 4-way set associative cache mapping with 16 cache blocks. Main memory block requests are 0,255,1,4,3,8,133,159,216,129,63,8,48,32,73,92,155,16. 


Note: 4 blocks can exist in any line at a time. So

LRU (Cache Replacement Policy) Question 2