Replacement policies
Replacement Policy
With associative caches, a replacement policy is required when deciding which block to remove from a **full cache**. The block to be removed is called the **victim block**.
Link to original
In most domains, the optimal replacement policy is not possible.
LRU
If we want to optimise for temporal locality we will want to kepe the most recently used blocks in the cache and remove blocks that have not been used for a long time.
We can use least-recently used (LRU) algorithm to keep track of the last time each cache block was accessed. The victim block is then the block which has been unused for the longest period of time. The LRU algorithm is complex; we have to maintain an access history for each block.
FIFO
A First-In First-Out (FIFO) policy is a popular and simple cache replacement policy. The block that has been in cache the longest is the victim block.
There is still a small overhead of keeping track of when things were added.
Random
A random policy is where we select a victim block at random and replace it with a new block. There is no overhead but we are equally as likely to remove the best and worst blocks.