Page replacement algorithms

Why it matters

Demand paging hands out frames only as pages are touched, so eventually every frame is full and the next fault must push one out. The victim decides whether a database's hot index survives a backup streaming through the page cache, whether a node near its memory limit degrades gently or falls off a cliff, and why Postgres and MySQL run their own eviction. It is also the staple of operating-systems papers: reference string, frame count, count the faults.

The idea

When a fault needs a frame and none is free, the kernel runs a page replacement algorithm to pick a victim. A dirty victim is written to swap or its file first; a clean one is dropped. The Swapping and thrashing lesson covers thrashing and The TLB and page faults lesson the fault path; this lesson is the choice, scored on a reference string: the page numbers a program touches, against a fixed number of frames, counting faults.

The classic algorithms

1. 1

   FIFO

   Evict the page resident longest. Cheap, and blind to use.
2. 2

   Optimal (Belady's MIN)

   Evict the page whose next use is furthest away. Unrunnable, since it needs the future, but the floor every real policy is measured against.
3. 3

   LRU

   Evict the page unused for longest. Exact LRU needs a timestamp or list move on every access, which no CPU does in hardware.
4. 4

   Clock (second chance)

   Frames form a ring with a hand. The hardware sets an accessed bit on any touch; the hand clears set bits as it passes and evicts at the first clear one. One bit approximates LRU almost for free.
5. 5

   Enhanced clock

   Prefer, in order, untouched and clean, untouched and dirty, touched and clean, touched and dirty: no write-back while a clean victim exists, at up to four sweeps.
6. 6

   LFU

   Evict the page with the fewest accesses; counts must be aged or a page hot at start-up never leaves.

Belady's anomaly, worked

Run FIFO on 1 2 3 4 1 2 5 1 2 3 4 5 with three frames, then four:

ref      1  2  3  4  1  2  5  1  2  3  4  5
FIFO/3   F  F  F  F  F  F  F  .  .  F  F  .    9 faults
FIFO/4   F  F  F  F  .  .  F  F  F  F  F  F   10 faults

With four frames, 1 and 2 hit once the queue is full, then 5 evicts 1 just before 1 is needed, and every fault from there evicts the page wanted next. This is Belady's anomaly. LRU and optimal are stack algorithms: the pages resident with n frames are always a subset of those with n plus one, so more memory never adds faults. FIFO gives no such guarantee, and clock, FIFO with second chances, is not a stack algorithm either, even though on this string it happens to match LRU.

Working set and fault frequency

The other half is frames per process. Denning's working-set model calls the pages touched in the last N references (say 10,000) the working set, keeps the sum of working sets within RAM, and suspends a whole process rather than exceed it. Measuring the window is expensive, so page-fault frequency is the cheap proxy: a process faulting above an upper rate gets more frames, below a lower rate gives some back.

How Linux does it

Linux reclaims globally, per NUMA node and per cgroup. Each node keeps an inactive and an active LRU list for anonymous pages and another pair for file pages. A new page enters the inactive list; reclaim scans its tail, checks and clears the accessed bit in every page table entry mapping the page, evicts untouched pages and promotes the rest. When the inactive list runs short the active tail is demoted, so a page must keep proving itself, and a quick refault signals the inactive list is too small. swappiness tilts reclaim between the two pairs. Since kernel 6.1 the multi-generational LRU (MGLRU, via /sys/kernel/mm/lru_gen/enabled) replaces each pair with several generations, ages pages by walking page tables instead of reverse maps, and evicts the oldest generation first.

Why databases run their own

A buffer pool is a page cache the database controls, and it knows what each page is for: a sequential scan over a 500 GB table must not flush a hot B-tree index, and the write-ahead log must reach disk before the dirty page it protects. Postgres runs a clock-sweep over shared_buffers with a usage count per buffer capped at five, raised on each pin and lowered as the hand passes, and gives large scans a small ring so they cannot evict the rest. InnoDB promotes a new page only if touched again after innodb_old_blocks_time. LRU-K records the Kth most recent access time, so a page needs K touches to count as hot: one access is not evidence of heat.

Trade-offs

Better victims cost metadata and CPU. Exact LRU is unaffordable at memory speed, so every real system runs a one-bit or few-bit approximation and accepts occasional bad evictions. Global reclaim lets a greedy process squeeze its neighbours, which is why cgroup limits exist; per-process budgets waste frames an idle process holds. A buffer pool using O_DIRECT gains control and loses the page cache's free caching.

In an interview

Narrate the frames step by step, not just the fault total. In a systems round: "The kernel approximates LRU with the accessed bit and two lists, so a backup that reads every file once only fills the inactive list and should not evict our hot heap pages; when it did, the cgroup limit had left no room for the file list."