AMU 2026 — Computer PYQ

Cache replacement algorithms decide which cache block should be evicted when a new block needs to be loaded into a full cache slot.

• Why is Least Recently Used (LRU) preferred?

  LRU operates on the foundational principle of Temporal Locality (locality of reference), which states that programs are highly likely to access data memory locations that they have accessed recently in the past.

  Mathematically, if a block has not been accessed for the longest duration of cycles:

  $$\Delta t_{\text{last\_access}}=\max (t_{\text{current}}-t_{\text{access\_i}})$$

  It is designated as the prime candidate for eviction. LRU delivers an exceptionally high hit ratio across diverse standard software execution workloads.

Why other options are less optimal for modern processors:

• (a) First-In-First-Out (FIFO): Evicts the block that was brought into the cache first, regardless of how frequently or recently it is being accessed right now. This can accidentally evict a heavily reused loop variable.

• (c) Random Replacement: Selects an eviction candidate at random using pseudo-random allocation circuits. While it requires no tracking bits (saving hardware area), it offers no predictability and yields lower cache hit-rates than locality-based choices.

• (d) Least Frequently Used (LFU): Keeps track of absolute execution counter frequencies. It suffers from a flaw where a block heavily used at initialization remains stuck inside the cache forever even if it is never needed again (cache pollution).