Why LRU Evicts the Least Recently Used Page First

What Is LRU?

LRU (Least Recently Used) follows the "use‑it‑or‑lose‑it" principle: pages that have been accessed recently are likely to be needed again, while pages not accessed for a long time are unlikely to be used and are evicted.

Why LRU Works – Locality Principle

Programs exhibit temporal and spatial locality. For example, a loop accessing arr[i] repeatedly shows that the loop variable i and adjacent array elements are accessed frequently, supporting the intuition that recent accesses predict future ones.

LRU Hit‑Rate Example

Access sequence: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Frames: 3

LRU steps:
1 → load 1   [1]
2 → load 2   [1,2]
3 → load 3   [1,2,3]
4 → miss, evict 1   [2,3,4]
1 → miss, evict 2   [3,4,1]
2 → miss, evict 3   [4,1,2]
5 → miss, evict 4   [1,2,5]
1 → hit   [1,2,5]
2 → hit   [1,2,5]
3 → miss, evict 5   [1,2,3]
4 → miss, evict 1   [2,3,4]
5 → miss, evict 2   [3,4,5]

Misses: 10, Hits: 2

Exact Implementation Methods

1. Counter Method

Each page keeps a "last‑access time" counter. On access, the counter is set to the current time; eviction scans all pages to find the smallest counter. This incurs O(n) overhead and requires maintaining counters for every page.

2. Stack Method

A stack records pages in order of recent use. On access, a page is moved to the top; when the stack is full, the bottom element is evicted. The diagram shows the stack top as the most recent.

3. Linked‑List Method

A doubly‑linked list stores pages from oldest (head) to newest (tail). Access moves a page to the tail; eviction removes the head. This provides O(1) updates with pointer manipulation.

Hardware Support

Counter Hardware

Each frame could have a hardware counter updated on every memory access, with eviction selecting the smallest counter. The approach is rarely used because counters are numerous and updating them is costly.

Reference‑Bit Hardware

A simplified scheme uses a single reference bit per page: set to 1 on access, periodically cleared to 0. Eviction chooses a page whose reference bit is 0, approximating LRU with lower overhead.

Approximate LRU Algorithms

Clock (Second‑Chance) Algorithm

while (find victim) {
    if (R == 1) {
        R = 0;   // give a second chance
        next++;
    } else {
        return current; // evict page with R == 0
    }
}

Aging Algorithm

Each page holds an 8‑bit counter. On each interval the counter is right‑shifted; if the page is accessed, the high bit is set to 1. The page with the smallest counter is evicted.

Working‑Set Algorithm

The working set is the set of pages referenced in the last w accesses. Pages outside the working set are eligible for eviction. Example: with recent accesses 1,2,3,4,1,2,3,4 and w=4, the working set is {1,2,3,4}.

Pros and Cons of LRU

Advantages

Aligns with locality principle → high hit rate and good performance.

No Belady anomaly – more frames never increase miss rate.

Conceptually simple and easy to understand.

Disadvantages

Implementation overhead – needs to maintain timestamps, stacks, or linked lists (O(n) or pointer work).

Hardware support can be expensive (counters or reference bits).

Performance may degrade under pathological access patterns.

Practical Cases

Python Simple LRU Cache

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key in self.cache:
            self.cache.move_to_end(key)  # mark as recently used
            return self.cache[key]
        return -1

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # evict least recent

Redis LRU Policies

Redis offers two LRU‑based eviction policies: allkeys-lru: applies LRU to all keys. volatile-lru: applies LRU only to keys with an expiration time.

Redis samples a subset of keys and evicts the one with the lowest recent‑use estimate; this is an approximation because exact LRU would be too costly.

LRU vs. Other Algorithms

OPT : Highest hit rate, impossible to implement, no Belady anomaly.

LRU : High hit rate, high overhead, no Belady anomaly.

FIFO : Low hit rate, low overhead, suffers Belady anomaly.

Clock : Medium‑high hit rate, medium overhead, no Belady anomaly.

Random : Medium hit rate, very low overhead, no Belady anomaly.

Conclusion

LRU follows the "use‑it‑or‑lose‑it" rule, evicting the page that has not been accessed for the longest time. It can be realized with counters, stacks, linked lists, or approximated by Clock, Aging, and Working‑Set techniques. While it offers high hit rates and avoids Belady’s anomaly, its implementation cost and hardware requirements often lead systems to adopt approximate variants.