When physical memory fills up, the operating system faces a choice: which page should be evicted to make room for new data? This decision happens thousands of times per second on a busy server, and the algorithm behind it directly shapes application performance, latency distribution, and resource efficiency.

Page replacement is the core mechanism of virtual memory management. Every process sees a large, contiguous address space, but only a subset of pages resides in RAM at any given time. When a process accesses a page that isn’t present, a page fault occurs, the OS loads the page from disk or swap, and something else must be evicted if memory is full. The replacement algorithm determines what goes.

The Classic Algorithms

LRU (Least Recently Used) evicts the page that hasn’t been accessed for the longest time. It’s intuitive and effective for workloads with temporal locality—recently used pages are likely to be used again soon. The challenge is implementation cost. True LRU requires tracking access order for every page, which is expensive at scale. Most systems approximate it.

Clock (Second Chance) is the practical LRU alternative used in many production kernels. Pages are organized in a circular list with a reference bit set by the hardware on each access. The clock hand sweeps through the list; if a page’s reference bit is set, the bit is cleared and the hand moves on. If the bit is already clear, the page is evicted. This approximates LRU with minimal overhead and no per-access sorting.

LFU (Least Frequently Used) tracks access frequency instead of recency. It handles scan-resistant workloads better—bulk operations that touch many pages once won’t immediately evict hot pages. The tradeoff is complexity and the risk of stale frequency counts polluting the cache over time.

FIFO (First In, First Out) evicts the oldest page by arrival time, ignoring access patterns entirely. It’s simple and cheap, but performs poorly in practice because age has little correlation with future utility. Belady’s anomaly—where adding more memory can paradoxically increase page faults—famously occurs with FIFO.

Why the Algorithm Matters

The gap between a good and bad replacement policy shows up in page fault rates, which translate directly to disk I/O and latency spikes. A page fault to SSD might cost 100 microseconds; to spinning disk, 10 milliseconds. Multiplied across thousands of faults per second, poor eviction decisions can collapse throughput.

Modern systems face diverse workloads within a single machine: working sets that fit entirely in memory, streaming scans over large datasets, and bursty access patterns with shifting hot sets. A single fixed algorithm can’t handle all of them optimally. This has driven systems toward adaptive policies.

Adaptive and Hybrid Strategies

ARC (Adaptive Replacement Cache) maintains two LRU lists—one for pages seen once, another for pages seen multiple times—and dynamically adjusts the balance between them based on recent hit rates. It adapts to both recency and frequency without manual tuning.

CAR (Clock with Adaptive Replacement) applies similar logic to clock-based structures, reducing overhead while preserving adaptability.

LIRS (Low Inter-reference Recency Set) distinguishes between pages with high and low reuse distance, keeping high-reuse-distance pages out of the main cache to preserve space for frequently accessed data. It handles workloads with large scans more gracefully than pure LRU.

Linux uses a two-list system—active and inactive LRU lists—with periodic promotion and demotion based on reference bits. Pages must prove their value by being accessed while on the inactive list to move to active. This balances recency with frequency and resists one-time scans polluting the cache.

Thrashing and Working Set Protection

When memory pressure becomes severe and the working set exceeds available RAM, systems can enter thrashing: constant paging with almost no useful work. Page replacement algorithms can’t solve this—no eviction policy performs well when every decision is wrong—but good algorithms delay the onset and degrade more gracefully.

Some systems track working set size and refuse to start new processes when existing ones can’t be given enough pages to avoid thrashing. Others implement page fault rate control, slowing or suspending processes that fault excessively.

The Reality of Modern Systems

Most production kernels don’t implement textbook algorithms directly. They approximate LRU with clock-like structures, blend recency and frequency heuristics, incorporate page type (anonymous vs. file-backed), and add tunables for different memory zones and workload classes.

The choice of page replacement algorithm is invisible when it works well and catastrophic when it doesn’t. Understanding the tradeoffs helps diagnose mysterious latency spikes, optimize memory-constrained workloads, and reason about system behavior under pressure.