LRU Cache & Page Replacement theory

The memory hierarchy organizes storage into tiers balancing latency, capacity, and cost: CPU registers/caches (0.5–10 ns, MBs), DRAM main memory (50–100 ns, GBs), and secondary SSD/HDD storage (10 µs–10 ms, TBs). Because DRAM is too small to hold all concurrent application data, the operating system virtualizes memory into 4KB pages. When a process accesses a page not resident in DRAM, a page fault occurs, requiring the OS to fetch the page from disk and evict an existing resident page if physical memory is full. Page replacement algorithms decide which frame to evict, minimizing disk I/O to prevent system thrashing.

The Principle of Locality describes the empirical observation that software does not access memory uniformly at random. Temporal locality states that recently accessed memory locations are highly likely to be accessed again soon (e.g. loop variables). Spatial locality states that memory locations adjacent to recently accessed addresses are likely to be accessed soon (e.g. array indexing). Peter Denning formalized this in 1968 with the Working Set model W(t, Δ), defined as the set of distinct pages referenced by a process during a sliding time window Δ. If an OS allocates enough physical frames to satisfy |W(t, Δ)|, the process runs at near-DRAM speed with negligible page faults.

LRU approximates optimal replacement by evicting the page that has not been referenced for the longest period of time, using past recency as a predictor of future utility. To achieve strict O(1) time for both get() and put() operations, software LRU caches combine a Hash Map with a Doubly-Linked List. The hash map maps page keys to doubly-linked list node pointers in O(1) time. The doubly-linked list maintains pages in recency order: accessed pages are spliced out of their current position and moved to the head (MRU) in 4 pointer assignments, while evictions simply remove the node preceding the tail sentinel (LRU), both executing in strict O(1) scalar time.

Belady's Anomaly (Laszlo Belady, 1969) is the counterintuitive phenomenon where increasing the number of physical memory frames allocated to a process results in an INCREASE in the total number of page faults under certain replacement policies like FIFO. In 1970, Mattson proved that algorithms satisfying the Inclusion Property S(C) ⊆ S(C+1) (where the set of resident pages in cache size C is always a subset of those in cache size C+1) are 'Stack Algorithms'. Stack algorithms (including LRU, LFU, and Belady's OPT) are mathematically immune to Belady's anomaly because any cache hit in size C is guaranteed to hit in size C+1. FIFO and Clock do not satisfy inclusion and are vulnerable to Belady's anomaly.

Implementing true LRU in an operating system kernel requires updating timestamps or linked list pointers on every single memory reference executed by the CPU. Doing so in software would require a trap into kernel mode on every instruction, causing a 100× to 1000× slowdown. Instead, modern OS kernels approximate LRU using the hardware-assisted Second-Chance Clock Algorithm. The CPU Memory Management Unit (MMU) automatically sets a 1-bit reference flag (R = 1) in the page table entry whenever a page is accessed in hardware. The kernel organizes physical frames in a circular ring with a clock hand. On a page fault, the hand sweeps frames: if R = 1, it clears R = 0 and advances; if R = 0, the page is evicted. This provides near-LRU performance with zero per-instruction software overhead.

Effective Memory Access Time measures average memory latency: EMAT = h · t_hit + (1 - h) · t_fault, where h is the hit ratio, t_hit is DRAM latency (~100 ns), and t_fault is the page fault servicing time (~10,000 ns on an NVMe SSD). Because SSD page faults are 100× to 1,000× slower than DRAM, even a tiny 1% page fault rate (h = 0.99) doubles average memory access time from 100 ns to 200 ns. If the page fault rate climbs to 10% (h = 0.90), EMAT surges to 1,090 ns (an 11× slowdown), demonstrating why page replacement efficiency is paramount.

Belady's Optimal Algorithm (MIN or OPT, 1966) evicts the page whose next reference occurs furthest in the future. It is mathematically proven to achieve the absolute minimum number of page faults possible for any given reference string. However, because general-purpose operating systems cannot predict the future with clairvoyance, OPT cannot be implemented in online systems. Its value lies in serving as an ideal offline theoretical benchmark: by comparing the performance of practical algorithms (LRU, Clock, FIFO) against Belady's OPT, computer scientists can quantitatively determine how close an online heuristic approaches theoretical perfection.