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
- FIFO
- LRU
- MRU
- RANDOM
Not Applicable on Direct mapping, because we fix for each block to come in a particular cache line.
1. FIFO
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
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 is given in the following diagram
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.
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 the example. And so on, the next incoming block is 22, which will be replaced with block no. 3.
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.
Solution:
Note: 4 blocks can exist in any line at a time. So
