Once the cache is full and we need to make space for a newer entry, we can decide which block to replace by using the following methods.
Least Recently Used (LRU)
We assign age bits to each cache entry. We initialize them to their line number usually (but we can init randomly as well, so we get factorial choices). So cache line 0 would have age 0 so on.
When we get a new entry and its a miss, we simply replace the lowest age cache block (usually 0). Update its age to be the maximum (max = number of cache blocks). And then decrement all other ages by 1 (if age > 0).
If however there was a hit, then we just update the hits age (X) bits to max, and decrement all ages which are greater than the hit's age before updating it (X).
We replace the LRU block with the newer entry.
We have to keep track of the age bits and the age sequences. For higher set associativity, this means we have to keep track of a lot of bits, which means huge overhead.
First In First Out (FIFO)
Its just simpler LRU. Maintain a queue and push every cache entry we update. When we have to replace, just replace the queue's top and then pop.
Least Frequently Used (LFU)
We assign a frequency to each block. We init it to 1 and then increment it for each hit.
When a miss occurs, we check the lowest frequency block and replace it.
If there is a tie, we use FIFO and remove whichever block was first added to cache.