Cache replacement policies

Cache replacement policies choose which stored item to evict when a cache must make room for new data. They trade hit rate, computational cost, and implementation complexity.

Connect

Least recently used: A replacement policy that evicts the item whose most recent access was earliest. It uses recent access as a proxy for future reuse.
First-in first-out: A queue discipline that removes the item that entered the system earliest. FIFO tracks insertion order rather than how recently cached items were accessed.
CPU cache: A small, fast memory that stores copies of data used by a processor. Hardware caches use replacement rules when a set is full and a new memory block maps to it.
Cache hierarchy: An arrangement of storage levels with different capacities, speeds, and costs. Replacement operates within one level of a broader hierarchy, where misses may be served by another.
Belady's anomaly: The counterintuitive increase in page faults that can occur when certain replacement algorithms receive more memory frames. It shows that adding cache capacity does not guarantee fewer misses for every policy.
Least frequently used: A replacement policy that evicts the item with the fewest recorded accesses. It favors items with repeated use, even when their accesses are not recent.
Most recently used: A replacement policy that evicts the item accessed most recently. MRU reverses LRU's assumption and can work well when recently used items are unlikely to be reused soon.
Page replacement algorithm: An operating-system rule for choosing a memory page to remove when physical memory is needed. Virtual-memory paging applies similar replacement ideas to much larger, slower storage.
Cache line: The fixed-size unit of data transferred between memory and a cache. Hardware replacement usually evicts a cache line rather than an individual byte or variable-sized object.
Scan-resistant caching: Cache design that limits the damage caused by one-time sequential accesses displacing reusable data. Streaming scans can mislead recency-based replacement and pollute a cache.