Cache Replacement Policies

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

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

Types of Cache replacement policies

  1. FIFO
  2. LRU
  3. MRU
  4. RANDOM

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

1. FIFO

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 came in the cache then the element of position 1 is replaced in any case.

Question 1: Consider a 4-way set associative cache with total of 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

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

FIFO (Cache Replacement Policy)

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

2. LRU

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

Question:1

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 example. And so on 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 request are 0,255,1,4,3,8,133,159,216,129,63,8,48,32,73,92,155,16. 

Solution:

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

LRU (Cache Replacement Policy) Question 2

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest