How Does LRU Cache Replacement Decide Which Line to Evict?

The Least Recently Used replacement policy decides which cache line to evict upon a cache miss by selecting the line that has gone the longest time without being accessed. When a cache is full and new data must be loaded, the policy assumes that data used recently is more likely to be needed again soon, while the oldest unused data is the least valuable to keep.

Cache Hits, Cache Misses, and Temporal Locality

In classical computing, a cache sits between the processor and slower main memory to speed up data access. The LRU policy relies on the principle of temporal locality, which observes that programs tend to reuse the same memory addresses within short time intervals.

When the processor requests data, one of two outcomes occurs:

  • Cache Hit: The requested data is already in the cache. The cache returns the data and updates the line's recency metadata so that it is marked as the most recently used.
  • Cache Miss: The requested data is not in the cache. The cache must fetch the line from main memory. If the target cache set still has an empty slot, the new line is placed there. If the set is full, the cache must evict an existing line to make room.

Under LRU, the eviction candidate is always the line with the oldest access timestamp or lowest recency rank in that set.

How Hardware and Software Track Recency

To identify the least recently used line, the cache must maintain an ordering of all lines within a set. In an \(N\)-way set-associative cache, each set contains \(N\) cache lines, and the replacement policy only compares lines within the same set.

Common implementation strategies include:

  1. Age Counters or Timestamps: Each cache line stores a counter value. Whenever a line is accessed, its counter is set to \(0\) (or the current global timestamp), while other lines in the set increment their counters. Upon a miss, the line with the maximum counter value is evicted.
  2. Doubly Linked List with a Hash Map: In software caches, a doubly linked list orders items from most recently used at the head to least recently used at the tail. A hash map provides \(O(1)\) lookup, and moving an accessed item to the head or evicting the tail also takes \(O(1)\) time.
  3. Recency Matrix: Hardware implementations for small \(N\) often use an \(N \times N\) bit matrix. Accessing line \(i\) sets row \(i\) to \(1\) and column \(i\) to \(0\). The line whose row contains all \(0\)s is the least recently used.

Step-by-Step Eviction Process

When a cache miss occurs in a full set of \(N\) ways, the LRU controller follows a deterministic sequence:

  1. Identify the Victim: Scan the recency metadata of the \(N\) lines in the target set to find the line with the lowest recency rank.
  2. Handle Dirty Data: If the victim line has been modified (marked dirty) in a write-back cache, its contents are written back to main memory before overwriting. If it is clean, it is discarded immediately.
  3. Insert the New Line: The newly fetched cache line replaces the victim in that slot.
  4. Update Recency: The newly inserted line is marked as the most recently used, shifting all other lines in the set down by one rank.

Limitations and Practical Approximations

While exact LRU is optimal for many workloads, tracking exact ordering becomes expensive in hardware as associativity \(N\) grows, requiring roughly \(\lceil \log_2(N!) \rceil\) state bits per set. Because of this overhead, many modern processors use Pseudo-LRU (PLRU) algorithms, such as tree-based PLRU, which approximate the behavior of LRU using only \(N - 1\) bits per set while still avoiding the eviction of recently accessed data.