a replacement policy
Your small desk is full and a new book must go down — so one of the books already there has to be returned to the shelf. Which one do you give up? You would probably return the one you have not opened in the longest while, betting you will not need it again soon. A replacement policy is exactly this rule: when a cache set is full and a new line must be brought in on a miss, the policy decides which existing line to evict to make room.
In a set-associative cache, a missing block can occupy any of the n ways in its set; if all n are already full, one must be chosen for eviction. The gold-standard heuristic is LRU (least recently used): evict the line that has gone longest without an access, a direct bet on temporal locality (recently used is likely to be used again, so the least-recently used is the safest to drop). True LRU is expensive to track for many ways, so real hardware uses approximations: pseudo-LRU (a small tree of bits that roughly orders the ways), not-recently-used, or even random replacement, which is surprisingly competitive, needs almost no hardware, and avoids pathological worst cases. A direct-mapped cache needs no policy at all — there is only one possible home, so the choice is forced.
Replacement matters because the wrong eviction throws away a line you are about to need, turning a would-be hit into a miss. But it is honestly a second-order lever: the gap between a good policy and a mediocre one is usually small compared to the gap between good and bad locality in your code, or between too-small and adequate cache capacity. There is also a humbling theoretical fact — the provably optimal policy (Belady's, evict the line whose next use is farthest in the future) requires knowing the future, so it cannot be implemented; it serves only as an unreachable benchmark against which real policies are measured.
A 2-way set holds lines A and B; A was used most recently. On a miss for new line C, LRU evicts B (the less-recently-used). If the program's very next access is to B, that was a bad guess and B must be re-fetched — but on typical code LRU guesses right far more often than not.
On a miss into a full set, the policy picks which line to evict; LRU bets recently-used will recur.
The provably best policy (Belady's optimal) evicts the line used farthest in the future — which is unimplementable because it requires knowing the future. Real policies (LRU approximations, random) only estimate it, and the practical difference between decent policies is often small.