Cache memory makes use of replacement algorithms to evict stored elements. This is largely dependent on the cache’s architecture.
For a direct-mapped architecture, it’s trivial to decide which cache line to evict since there’s an easy correspondence between main memory and the cache. For an associative cache, this is not so easy, but we can rely on locality. We can pick the least recently used (LRU) block to remove in the LRU replacement algorithm. The LRU algorithm can lead to poor performance, though it performs well for many access patterns. For example, when accesses are made to an array that is slightly too large to fit into the cache there can be bad performance.
The LRU algorithm keeps track of references to all blocks with a counter. When a hit occurs, the counter is set to 0. Otherwise, the other counters are incremented. If a miss occurs, the value of all other counters are incremented. When a line needs to be replaced, a line with a maxed out counter are removed and a new block put in its place.
Performance problems with the LRU algorithm can be improved with a small amount of stochasticity in choosing which block to remove. In the same sense, a simpler algorithm is to just choose a random block to remove (and this turns out to be pretty effective).