LRU Approximation Algorithms

In the previous module, we discovered that LRU (Least Recently Used) offers excellent page replacement performance, closely approximating the theoretically optimal algorithm. However, we also uncovered a brutal reality: true LRU requires timestamping every memory access or maintaining perfectly ordered data structures updated on every memory reference—operations that occur billions of times per second on modern systems.

This overhead is simply unacceptable. A memory reference that takes 100 nanoseconds cannot afford additional bookkeeping that might double or triple its latency. So how do real operating systems achieve LRU-like behavior without LRU-like cost?

The answer lies in a elegant hardware-software partnership: modern processors provide a single-bit indicator called the reference bit (also known as the access bit or used bit), which the hardware sets automatically on every memory access. The operating system periodically samples and clears these bits, using the accumulated information to approximate page access recency without any per-access software intervention.

Before diving into the reference bit, let's precisely quantify why true LRU is impractical. This understanding motivates the clever compromises that make LRU approximation both necessary and valuable.

True LRU Implementation Options:

1. Timestamp Approach: Record the current time on every memory access, then scan all pages to find the oldest timestamp during replacement
2. Stack Approach: Maintain a stack where accessed pages move to the top, with the LRU page always at the bottom
3. Counter Approach: Each page has a counter; on access, copy the clock value to the page's counter

Each approach requires significant work per memory reference:

The scale problem:

Consider a modern system running a workload with the following characteristics:

• Memory references: 1 billion per second (conservative for modern CPUs)
• Memory access time: 100 nanoseconds
• Software overhead for true LRU: 10-50 nanoseconds per access (optimistic)

Adding even 10ns of overhead per access increases total memory access time by 10%, which translates directly to application slowdown. For memory-intensive workloads, this overhead compounds—the CPU spends more time on bookkeeping than on actual computation.

The fundamental insight:

We don't actually need to know the exact order of page accesses. We need to know approximately which pages were used recently and which weren't. This relaxation of requirements opens the door to dramatically more efficient solutions.

The reference bit (R-bit) is a single bit associated with each page table entry (PTE) that indicates whether the page has been accessed since the bit was last cleared. This deceptively simple mechanism provides the foundation for all practical LRU approximation.

Core semantics:

• Hardware sets the bit to 1 automatically whenever the page is read from or written to
• Software clears the bit to 0 periodically to track access within time windows
• The bit persists until explicitly cleared by the operating system

This creates an elegant information flow:

1. OS clears all reference bits at time T₀
2. Hardware sets bits as pages are accessed during interval [T₀, T₁]
3. At time T₁, OS samples the bits: R=1 means "accessed recently," R=0 means "not accessed recently"
4. OS clears bits again, beginning a new sampling interval

Key properties of the reference bit:

1. Binary, not temporal: The bit only records whether access occurred, not when or how many times

2. Per-page granularity: Each page has its own reference bit, enabling per-page access tracking

3. Zero per-access software overhead: The hardware sets the bit as part of normal address translation—no software intervention required

4. Sampling-based information: The OS must periodically sample and clear bits to convert binary information into temporal approximations

5. Physical implementation: The bit exists in the page table entry, which resides in main memory and is cached in the TLB

Understanding how the reference bit works at the hardware level illuminates why this mechanism is so efficient. The setting of the reference bit is integrated into the address translation process that must happen anyway for every memory access.

Address Translation with Reference Bit Setting:

When the CPU issues a memory access with a virtual address, the MMU performs the following steps:

1. Extract page number from the virtual address
2. Check TLB for cached translation
3. If TLB miss, walk the page table hierarchy to find the PTE
4. Check permissions (read/write/execute, user/supervisor)
5. Set reference bit in the PTE if not already set (atomic hardware operation)
6. If write access, also set the dirty bit (covered separately)
7. Cache the translation in the TLB
8. Form physical address and complete the memory access

The critical insight: step 5 adds negligible overhead because the PTE must be read anyway for translation. The hardware simply performs a conditional write-back as part of the same memory transaction.

x86/x86-64 Page Table Entry Format:

On x86-64 systems, the reference bit is bit 5 of the 64-bit page table entry (called the "Accessed" bit in Intel terminology):

63    62:52    51:M    M-1:12    11:9   8     7     6     5     4     3     2     1     0
┌─────┬───────┬───────┬─────────┬──────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ NX  │ Avail │ Rsvd  │ Frame # │Avail │ G   │ PAT │ D   │ A   │ PCD │ PWT │ U/S │ R/W │ P   │
└─────┴───────┴───────┴─────────┴──────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
                                                        ▲
                                                        │
                                           Reference Bit (Accessed)

• Bit 5 (A - Accessed): Set by hardware on any access (read or write)
• Bit 6 (D - Dirty): Set by hardware only on write access
• The "Avail" fields are available for OS use, not touched by hardware

While hardware sets the reference bit automatically, the operating system controls the sampling and clearing of these bits. This gives the OS flexibility in how it uses reference bit information for page replacement decisions.

The OS's Role:

1. Periodic clearing: Clear reference bits at regular intervals (e.g., every timer interrupt)
2. Sampling: Read reference bits when making replacement decisions
3. Aggregation: Combine information across multiple sampling intervals to approximate recency
4. Policy decisions: Use accumulated data to select victim pages

Clearing strategies:

The TLB Invalidation Imperative:

When the OS clears a reference bit in the page table entry, it must also invalidate the corresponding TLB entry. Otherwise:

1. The TLB may still have the old PTE with R=1 cached
2. Future accesses hit the TLB and use the cached translation
3. The hardware doesn't re-read the PTE, so the memory's R=0 remains unchanged
4. The OS incorrectly concludes the page was never accessed

This TLB invalidation adds some overhead to the clearing operation, but it's essential for correctness. Fortunately, clearing happens infrequently (e.g., 10-100 times per second) rather than on every memory access.

A single reference bit provides binary information: accessed (1) or not accessed (0). To approximate LRU, we need temporal information: when was the page last accessed, or at least a ranking of pages by recency.

The key insight is that repeated sampling over time converts binary snapshots into temporal approximations.

Single-sample information:

• R=1: Page was accessed sometime during the last sampling interval
• R=0: Page was NOT accessed during the last sampling interval

Multi-sample information accumulation:

The Aging Algorithm (Preview):

To capture this history, operating systems often use an aging technique:

1. Each page maintains an age counter (typically 8 bits)
2. On each sampling interval:
   • Shift the age counter right by 1 bit (divide by 2)
   • If R=1, set the leftmost bit of the age counter
   • Clear R to begin tracking the next interval

The result: recent accesses contribute to high-order bits (large value), while older accesses shift into low-order bits (small contribution). A page with age 0b10000000 (128) was accessed in the last interval; a page with 0b00000001 (1) was accessed 7 intervals ago and not since.

Mathematical formalization:

If Rᵢ represents the reference bit value in interval i (most recent = interval 0), then:

Age = R₀×2⁷ + R₁×2⁶ + R₂×2⁵ + R₃×2⁴ + R₄×2³ + R₅×2² + R₆×2¹ + R₇×2⁰

This makes recent accesses exponentially more significant than older ones, approximating LRU while requiring only 8 bits of storage per page.

While the reference bit is remarkably useful, it has inherent limitations that shape the design of LRU approximation algorithms.

Fundamental Limitations:

Architectural variations affecting reference bit behavior:

Multi-core complications:

On multi-core systems, multiple CPUs may access the same page simultaneously. The reference bit must be set atomically to avoid race conditions. Modern architectures handle this through:

1. Atomic read-modify-write operations on PTE updates
2. Hardware cache coherency protocols ensuring all cores see the update
3. TLB shootdown mechanisms to invalidate cached translations across cores

When the OS clears reference bits, it must issue inter-processor interrupts (IPIs) to force all cores to flush relevant TLB entries—a significant overhead on many-core systems.

The reference bit serves as the fundamental building block for all practical LRU approximation algorithms. Each algorithm represents a different approach to extracting maximum useful information from this single-bit signal.

The algorithm landscape built on reference bits:

Comparing information usage:

The following pages will explore each of these algorithms in detail, revealing how they transform the simple reference bit into effective page replacement policies.

The reference bit exemplifies elegant systems design: a minimal hardware mechanism that enables sophisticated software policies. Let's consolidate the key concepts:

What's next:

With the reference bit mechanism firmly understood, we'll explore specific algorithms that use this information. The next page examines the Second-Chance (Clock) Algorithm, which provides an elegant circular-queue implementation for efficient LRU approximation.