Replacement Algorithm in Cache Memory

Replacement Algorithm

Disk Cache is a buffer in the main memory for disk sectors. The ‘ Disk Cache‘ contains the same copy of some of the sectors in the disk. When an I/O request is made for a particular sector, the CPU/DMA/I/O processor checks the disk cache for that sector. If the sector is available then read that one. Otherwise not available then write that sector into ‘disk cache’ from disk and then read by CPU.

1. LRU: The expansion of LRU is ‘least recently used‘. The criteria of this algorithm are replacing a block that has not been used for the longest period. The disk cache maintains a stack of blocks, the most recently used block occupies the top of the stack. And least recently used one occupied the bottom of the stack. So, delete a block from the bottom and add a block to the top for block replacement.

The main drawback of this method is the difficulty to remove a block from the bottom of the stack.

2. LFU: The expansion of LFU is least frequently used. In this algorithm, each block maintains a counter, with each reference to the block counter incremented.