Types of cache replacement policies

In this article, we are going to discuss the types of cache replacement policies and also learn these replacement policies with the help of a suitable example in computer organization.
Submitted by Prerana Jain, on August 10, 2020

In the direct-mapped cache, the position of each block is predetermined hence no replacement policy exists.
In fully associative and set-associative cache there exist policies.
When a new block is brought into the cache and all the position that it many occurs are full, and then the controller needs to decide which of the old blocks it can overwrite

First in First out policy

The block which has entered first in the main be replaced first.
This can lead to a problem known as "Belady's Anamoly", it starts that if we increase the no. of lines in cache memory the cache miss will increase.

Belady's Anamoly: For some cache replacement algorithm, the pages fault or miss rate increase as the number of allocated frame increase.

Example: Let we have a sequence 7, 0 ,1, 2, 0, 3, 0, 4, 2, 3, and cache memory has 4 lines.

There are a total of 6 misses in the FIFO replacement policy.

LRU (least recently used)

The page which was not used for the largest period of time in the past will get reported first.
We can think of this strategy as the optimal cache- replacement algorithm looking backward in time, rather than forward.
LRU is much better than FIFO replacement.
LRU is also called a stack algorithm and can never exhibit belady's anamoly.
The problem which is most important is how to implement LRU replacement. An LRU page replacement algorithm may require a sustainable hardware resource.

Example: Let we have a sequence 7, 0 ,1, 2, 0, 3, 0, 4, 2, 3 and cache memory has 3 lines.

There are a total of 6 misses in the LRU replacement policy.

Optimal Approach

The page which will not be used for the largest period of time in future reference will be replaced first.
The optimal algorithm will provide the best performance but this is difficult to implement as it requires the future knowledge of pages which is not possible.
It is used as a benchmark for the cache replacement algorithm.
It is mainly used for comparison studies.
The use of this cache replacement algorithm guarantees the lowest possible page fault rate for a fixed rate of frames.

Example: Let we have a sequence 7, 0 ,1, 2, 0, 3, 0, 4, 2, 3 and cache memory has 4 lines.