Page-Replacement Algorithms

Physical memory is finite; the virtual memory processes ask for is not. When every frame is full and a process faults on a page that must be brought in, the operating system faces the defining decision of virtual memory: which resident page do we evict to make room? Guess well and the victim is a page nobody wanted again — the fault is nearly free. Guess badly and you evict a page that is needed one instruction later, forcing it right back in. Over billions of references, that policy is worth enormous performance.

This is a pure policy question — the mechanism (fault, fetch, update the page table) is fixed; only the choice of victim varies. This lesson walks the classic ladder of replacement algorithms, from the impossible-but-optimal, through the naive, to the clever approximations real kernels actually ship — and the tiny scraps of hardware help (two status bits) that make the good ones possible.

OPT — the oracle you cannot build

Start with the impossible ideal. Bélády's OPT algorithm evicts the page that will not be used for the longest time in the future. It is provably optimal — no algorithm can produce fewer faults on a given reference string. There is just one problem: it requires knowing the future. OPT cannot be implemented for real workloads; its value is as a yardstick. When we measure a real algorithm we ask "how close to OPT did it get?", and the gap tells us how much a better predictor could possibly buy.

OPT evicts the page used furthest in the future — provably minimises faults, but is unrealisable (it needs the future);
real policies approximate OPT by using the past as a predictor of the future — recency (LRU) and reference frequency;
the hardware helps with two per-PTE bits: an accessed (reference) bit set on use and a dirty bit set on write — the OS samples and clears them to approximate LRU cheaply.

FIFO — simple, and quietly broken

The simplest realisable policy: evict the page that has been resident longest, regardless of use — a queue. It needs no hardware help, just a list. But FIFO has no idea which pages are useful; it will happily evict a hot, constantly-used page simply because it arrived early. Worse, FIFO suffers Bélády's anomaly: giving it more memory can produce more faults — a violation of the obvious intuition that more RAM should never hurt. The runnable comparison below includes the famous anomaly-triggering reference string.

Run the reference string 1,2,3,4,1,2,5,1,2,3,4,5 through FIFO. With three frames it takes 9 faults; with four frames it takes 10. Adding a frame made things worse. The reason is that FIFO's eviction order isn't a subset relationship across memory sizes: the set of pages resident with 4 frames is not guaranteed to contain the set resident with 3, so a larger cache can evict something a smaller one kept. Algorithms that are immune — where the resident set only grows as memory grows — are called stack algorithms; LRU and OPT are stack algorithms, FIFO is not. It is one of the great "wait, what?" results of systems.

LRU — right idea, wrong price

Least Recently Used evicts the page unused for the longest time in the past, betting that recency predicts the future — and for real programs, thanks to locality, it usually does. LRU is a stack algorithm (no anomaly) and typically lands close to OPT. So why not just use it? Because exact LRU is far too expensive. To know the true least-recently-used page you would have to timestamp or reorder a list on every single memory reference — that is hardware the MMU does not have and software far too slow to run per access. Exact LRU is a beautiful policy that no one can afford at page granularity.

The way out is the two status bits the hardware does give us. The MMU sets a PTE's accessed bit whenever the page is touched and its dirty bit whenever it is written. The OS cannot see the exact order of accesses, but it can periodically read and clear the accessed bit to learn "was this page used since I last looked?" That single bit of recent-use information is enough to build a cheap LRU approximation.

CLOCK — the approximation everyone ships

CLOCK (second-chance) is the workhorse. Arrange the frames in a circle with a moving hand. To find a victim, look at the page under the hand:

if its accessed bit is 0, it hasn't been used since we last passed — evict it;
if its accessed bit is 1, give it a "second chance": clear the bit to 0 and advance the hand, moving on to the next frame.

A page that keeps getting used keeps getting its bit re-set before the hand returns, so it survives; a page that falls out of use eventually meets the hand with a 0 bit and is evicted. CLOCK gets most of LRU's benefit for almost none of its cost — one bit and a circular scan. Real kernels refine it: Linux keeps two LRU-ish lists (active/inactive) and factors in the dirty bit (evicting a clean page is cheaper — no write-back needed). Compare all four policies on the same reference string:

// Compare FIFO, LRU, CLOCK (second-chance) and OPT on one reference string. // Count page faults for each. (The string is Belady's classic anomaly string.) const refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]; const FRAMES = 3; function fifo(rs: number[], k: number): number { const q: number[] = []; let faults = 0; for (const p of rs) { if (!q.includes(p)) { faults++; q.push(p); if (q.length > k) q.shift(); } } return faults; } function lru(rs: number[], k: number): number { let mem: number[] = []; let faults = 0; // front = least recently used, back = most recent for (const p of rs) { const hit = mem.includes(p); mem = mem.filter((x) => x !== p); // pull it out if present if (!hit) faults++; mem.push(p); // (re)insert as most recently used if (mem.length > k) mem.shift(); // evict least recently used } return faults; } function clock(rs: number[], k: number): number { const frame: number[] = []; const use: number[] = []; let hand = 0; let faults = 0; for (const p of rs) { if (frame.includes(p)) { use[frame.indexOf(p)] = 1; continue; } faults++; if (frame.length < k) { frame.push(p); use.push(1); continue; } while (use[hand] === 1) { use[hand] = 0; hand = (hand + 1) % k; } frame[hand] = p; use[hand] = 1; hand = (hand + 1) % k; } return faults; } function opt(rs: number[], k: number): number { const mem: number[] = []; let faults = 0; for (let i = 0; i < rs.length; i++) { const p = rs[i]; if (mem.includes(p)) continue; faults++; if (mem.length < k) { mem.push(p); continue; } // Evict the resident page used furthest in the future (or never). let victim = 0, farthest = -1; for (let j = 0; j < mem.length; j++) { let next = rs.indexOf(mem[j], i + 1); if (next === -1) { victim = j; break; } if (next > farthest) { farthest = next; victim = j; } } mem[victim] = p; } return faults; } console.log(`string: ${refs.join(" ")} frames = ${FRAMES}`); console.log(`FIFO : ${fifo(refs, FRAMES)} faults`); console.log(`LRU : ${lru(refs, FRAMES)} faults`); console.log(`CLOCK: ${clock(refs, FRAMES)} faults`); console.log(`OPT : ${opt(refs, FRAMES)} faults (the unbeatable lower bound)`); console.log(`FIFO with 4 frames: ${fifo(refs, 4)} faults <- Belady's anomaly (worse than 3!)`);

Beyond CLOCK: fixing LRU's blind spots

Plain LRU has a famous weakness: a single sequential scan of a huge file (a backup, a \texttt{grep} over everything) touches millions of pages once and, in strict recency order, evicts your entire hot working set to cache data you will never reread. Modern replacement algorithms defend against exactly this by considering frequency, not just recency:

Algorithm	Key idea	Guards against	Seen in
2Q	a probationary queue for one-hit pages; promote only on a second hit	scan pollution	PostgreSQL-style buffer pools
ARC	self-tunes the balance of recency vs frequency using ghost lists	changing workloads	ZFS, IBM storage
LIRS	ranks by reuse distance (inter-reference recency)	weak-locality scans	research, some DB caches

The common thread: a page touched once should not have the same standing as a page touched often. ARC (Adaptive Replacement Cache) is the star — it keeps "ghost" entries recording pages it recently evicted, and if it sees a ghost come back it shifts its own recency-versus-frequency balance automatically. It is why a ZFS box stays fast across wildly different workloads without hand-tuning.

A frequent error is to treat the hardware accessed bit as if it were a timestamp or a use-counter. It is neither — it is a single bit that means "touched at least once since I last cleared it." You cannot read an access order out of it, and you cannot tell a page touched once from a page touched a million times. That coarseness is exactly why CLOCK only approximates LRU rather than implementing it, and why algorithms wanting frequency information (ARC, LIRS) have to build it up in software over time by sampling and clearing the bit repeatedly. Never claim your policy "is LRU" when it is really "second-chance driven by a one-bit sampled signal." The gap between them is the whole subject.

Which page? — the mechanism/policy split, one last time

Notice what stayed constant through all of this. The mechanism — trap on fault, allocate a frame, write back a dirty victim, fetch the wanted page, patch the page table, restart the instruction — never changed. Only the policy (pick the victim) moved, from OPT's oracle to FIFO's queue to CLOCK's one-bit approximation to ARC's self-tuning. That is the OS design pattern in its purest form: build the expensive machinery once, and let a cheap, swappable decision ride on top. The next lesson, demand paging and thrashing, asks what happens when no policy can win — when the working sets simply do not fit.