LRU (Least Recently Used) Page Replacement

When the FIFO algorithm disappointed system designers with Bélády's anomaly, and the optimal algorithm remained forever out of reach, the search turned to something more practical: an algorithm that could approximate optimal behavior using information available to the operating system. The answer came from a fundamental insight about how programs actually use memory—the principle of temporal locality.

Least Recently Used (LRU) emerged as the gold standard of practical page replacement. Its premise is deceptively simple: if a page hasn't been accessed in a long time, it probably won't be accessed soon. This single assumption, grounded in decades of program behavior analysis, has proven remarkably effective across virtually all workload types.

Before diving into LRU, we must understand the limitation that made it necessary. FIFO (First-In, First-Out) seemed intuitive—replace the oldest page in memory. But FIFO has a fatal flaw: it ignores what happened after a page arrived.

Consider this scenario:

• Page A arrives at time 0 and is accessed constantly (hot page)
• Page B arrives at time 1 and is never touched again (cold page)
• Page C arrives at time 2 and is used occasionally

Under FIFO, when we need to evict a page, we replace A—the oldest—even though it's still actively in use. Meanwhile, B (completely unused) stays in memory simply because it arrived later. This is catastrophically wrong from a performance perspective.

The insight: arrival time tells us nothing about future usefulness. What matters is recent access patterns—the recency of use. A page that was just accessed is likely to be accessed again soon. A page that hasn't been touched in a long time is probably no longer needed.

This observation, rooted in empirical studies of program behavior spanning decades, is called the principle of temporal locality.

Temporal locality is one of the two fundamental principles of program behavior (the other being spatial locality). It states:

If a memory location is accessed at time t, there is a high probability it will be accessed again at time t + Δ for small values of Δ.

In simpler terms: recently used memory will likely be used again soon.

This isn't just a theoretical assumption—it's an empirical observation that holds across virtually all program types:

The mathematical foundation of temporal locality gives rise to the stack distance model. For each memory access, we can measure how many distinct pages have been accessed since this page was last used. Pages with small stack distances (recently used) are likely to be used again; pages with large stack distances (long-unused) are likely cold.

LRU directly implements this stack distance intuition: it always evicts the page with the largest stack distance—the one accessed longest ago.

Least Recently Used (LRU) is a page replacement algorithm that, when a page fault occurs and no free frames are available, selects the page that has not been accessed for the longest time—the page whose most recent access is furthest in the past.

Formal Definition:

Let M be the set of pages currently in memory frames, and let last_access(p) denote the time of the most recent reference to page p. When a page replacement is necessary:

$$\text{victim} = \arg\min_{p \in M} last_access(p)$$

In words: choose the page p in memory M whose last_access time is minimal (oldest).

The Core Assumption:

LRU makes a single assumption: the past predicts the future. Specifically, recent access patterns will continue into the near future. A page not used for a long time is assumed to not be needed soon.

The Optimal (OPT/MIN) algorithm achieves the minimum possible page faults by evicting the page that won't be used for the longest time in the future. This requires knowing the future—impossible in practice.

LRU uses the past to approximate the future. This is the key insight:

Why does this approximation work? Because of temporal locality: if a page was used recently, it will likely be used soon. If a page hasn't been used for a long time, it likely won't be used soon. The past reflects the future, asymmetrically.

Mathematical Perspective: Stack Algorithms

LRU belongs to a class called stack algorithms. A page replacement algorithm is a stack algorithm if, for a reference string, the set of pages in memory with n frames is always a subset of the pages in memory with n+1 frames.

Formally, if S_n(t) is the set of pages in memory at time t with n frames:

$$S_n(t) \subseteq S_{n+1}(t) \text{ for all } t$$

This has a crucial implication: stack algorithms never exhibit Bélády's anomaly. More frames always mean fewer or equal page faults—never more.

Both OPT and LRU are stack algorithms. FIFO is not. This mathematical property is why LRU is fundamentally superior to FIFO for general workloads.

Let's trace through LRU with a concrete example. Consider the reference string:

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

With 3 frames available, let's track each reference, noting LRU order (leftmost = least recently used, must be evicted next).

Analysis Results:

• Total references: 20
• Page faults: 12
• Hit rate: 8/20 = 40%
• Fault rate: 12/20 = 60%

Comparison with other algorithms on the same string (3 frames):

LRU provides 3 fewer faults than FIFO (20% improvement) and is only 3 faults more than optimal. For this workload, LRU is a good approximation of optimal.

LRU is not perfect. Its effectiveness depends on programs exhibiting temporal locality. When this assumption breaks, LRU can perform poorly—sometimes as bad as random replacement or worse.

Pathological Case 1: Sequential Scans Larger Than Memory

Pathological Case 2: Loop Larger Than Memory

A loop that cycles through more pages than available frames causes every single access to be a fault under LRU. The "least recently used" page is always the one we're about to need.

LRU's elegance as an algorithm contrasts sharply with the difficulty of implementing it efficiently. The core challenge:

Every memory access must update the recency ordering.

Consider a modern system:

• CPU runs at ~3 GHz (3 billion cycles/second)
• Each instruction may access memory
• Memory accesses can occur billions of times per second

For each of these accesses, a pure LRU implementation must:

1. Check if the page is in memory
2. If yes, update its position to "most recently used"
3. This update must be atomic and correct

The Cost Analysis:

Why can't we just update on every reference?

At billions of memory references per second:

• Software updates add 10-100ns overhead per access
• This would slow the CPU by 10-100x
• The memory management overhead would dwarf actual computation

The practical reality:

No modern operating system implements pure LRU. Instead, they use approximations that:

• Update recency information periodically (not every access)
• Use hardware assistance (reference bits)
• Accept imperfect ordering in exchange for speed

The subsequent pages in this module explore the exact implementations: counters, stacks, and ultimately the practical approximations that real systems use.

The Origins of LRU

LRU emerged in the 1960s as researchers at IBM, MIT, and other institutions grappled with the newly invented concept of virtual memory. The algorithm was formalized in the context of the Atlas computer (1962) and later refined through work on the Multics and IBM System/360 systems.

Key milestones:

• 1962: Manchester Atlas demonstrates automatic paging
• 1966: Bélády publishes the OPT algorithm analysis
• 1968: Denning introduces the Working Set model, providing theoretical grounding for LRU's effectiveness
• 1969: MULTICS implements sophisticated page replacement
• 1970s: Stack algorithm classification proves LRU's advantageous properties

We've established the foundational understanding of LRU. Let's consolidate the key insights:

What's Next:

Now that we understand the LRU principle, the next page examines Recency-Based Decision Making in depth—how recency is precisely defined, how it relates to the concept of stack distance, and the mathematical models that predict LRU performance.