Cache Replacement Policy

The cache replacement policy is the technique for choosing which cache block to replace when a fully associative cache is full,or when a set associative cache's line is full.One thing that you must note here is their is no choice in a direct-mapped cache that is a main memory address always maps to the same cache address and thus replaces whatever block is ready there.There are three common replacement policies for the cache.The first one is random replacement policy that chooses the block to replace randomly.While simple to implement,this policy does nothing to prevent replacing a block that is likely to be used soon.

The second replacement policy is least recently used(LRU) replacement policy replaces the block that has not been accessed for the longest time,assuming that this means that it is least likely to be accessed in near future.This technique provides for an excellent hit/miss ratio but requires expensive hardware to keep track of the times blocks are accessed.The third and last replacement policy is first in first out replacement policy uses a queue size N,pushing each block address onto the queue when the address is accessed,and then choosing the block to be replaced by popping the queue.