When your system runs low on memory, something has to go. The operating system’s page cache—holding recently accessed file data in RAM—needs to make room for new requests. The algorithm that decides which pages to evict determines whether your database query hits memory or waits on disk, whether your web server responds in milliseconds or seconds.

Most developers learn that operating systems use “Least Recently Used” (LRU) eviction. The intuition is clean: keep the most recently accessed pages, evict the oldest. But true LRU requires tracking exact access timestamps for every page and maintaining a sorted list—expensive operations at the scale of millions of pages being accessed thousands of times per second.

Why True LRU Is Too Expensive

Implementing perfect LRU means updating metadata on every single memory access. In a system with gigabytes of page cache and microsecond-level access patterns, this overhead becomes prohibitive. You’d need to move pages in a linked list or update timestamps atomically on every read, adding latency to the very operations you’re trying to accelerate.

The kernel needs to make eviction decisions quickly when memory pressure hits. Scanning a perfectly ordered LRU list is feasible, but maintaining that order in real-time is not.

The Clock Algorithm: Approximate LRU

Most modern operating systems use variants of the clock algorithm (also called second-chance or NRU—Not Recently Used). Instead of tracking precise access times, the clock algorithm uses a single reference bit per page, set by the MMU (memory management unit) whenever the page is accessed.

The algorithm maintains a circular list of pages with a “clock hand” pointer. When eviction is needed:

1. The hand sweeps through pages in circular order
2. If a page’s reference bit is set, clear it and move on (the “second chance”)
3. If the reference bit is already clear, evict this page
4. Advance the hand and repeat until a victim is found

Pages accessed recently will have their reference bit set, surviving at least one full rotation. Pages not accessed since the last sweep become eviction candidates. The result approximates LRU with O(1) cost per access and efficient linear scanning during eviction.

Multi-Queue and Adaptive Refinements

Linux takes this further with a two-queue system separating active and inactive pages. The inactive list holds pages that haven’t been accessed recently. When the inactive list is scanned for eviction, any page accessed again gets promoted to the active list—a form of frequency tracking.

This handles workloads with sequential scans (like log processing) that would otherwise flush the entire cache under strict LRU. A file read once in a scan won’t immediately evict pages accessed repeatedly by other processes.

Modern kernels also distinguish between file-backed pages (which can be dropped if clean, or written back if dirty) and anonymous memory (which requires swap). Eviction policy balances these pools based on workload and available swap space.

Why This Matters for Application Performance

Understanding page cache eviction helps explain performance cliffs. When your application’s working set exceeds available memory, eviction becomes the critical path. A cache-friendly access pattern—reusing data before it ages out—keeps everything in memory. A cache-hostile pattern—single-pass scans or random access across huge datasets—triggers constant eviction and refill.

Database systems and large-scale applications often implement their own buffer pools with custom eviction policies rather than relying solely on the OS page cache. They can track access frequency, pin critical pages, and use workload-specific heuristics. But even these sit atop the kernel’s page cache, making the underlying eviction algorithm a fundamental performance boundary.

The gap between theoretical LRU and practical clock-based approximations is a classic systems tradeoff: perfect accuracy versus real-world speed. For page cache eviction, the approximation wins every time.