Block Replacement

With direct-mapped placement the decision is simple because there is no choice: only one block frame is checked for a hit and only that block can be replaced.

With fully-associative or set-associative placement , there are more than one block to choose from on a miss.

Primary strategies:

  Random - to spread allocation uniformly, candidate blocks are randomly selected.
Advantage:  simple to implement in hardware
Disadvantage:   ignores principle of locality

  Least-Recently Used (LRU) - to reduce a chance of throwing out information that will be needed soon, accesses to blocks are recorded. The block replaced is the one that has been unused for the longest time.
Advantage: takes locality into account
Disadvantage: as the number of blocks to keep track of increases, LRU becomes more expensive (harder to implement, slower and often just approximated).

Other strategies:

First In First Out (FIFO)
Most-Recently Used (MRU)
Least-Frequently Used (LFU)
Most-Frequently Used (MFU)

For more hands-on approach you can see the problem (with solution) on calculating speedup ratio for systems with cache relative to system without cache assuming different caches are used.