Page Replacement Algorithms

A page replacement algorithm is the decision procedure invoked when a process incurs a Page Fault and every physical frame allocated to it (or to the system, under global allocation) is already occupied. The algorithm selects a victim frame whose resident page is written back (if dirty) and then overwritten by the newly requested page. The central design question is: given only limited information about future memory accesses, how should the victim be chosen to minimize the number of future faults? To compare algorithms rigorously, we abstract a program's memory accesses into a reference string: the sequence of page numbers touched over time, with consecutive repeated references to the same page collapsed (since a repeated reference to a page already resident causes no fault and is irrelevant to the replacement decision). Given a reference string and a fixed number of frames f, a replacement algorithm produces a deterministic sequence of hits and faults, and the standard metric is simply the total fault count, or equivalently the fault rate (faults divided by string length). Two idealized extremes bound every real algorithm. At one end sits Belady's algorithm (also called MIN or OPT), which evicts the page whose next reference lies farthest in the future — provably the minimum possible number of faults for any algorithm, achievable only with perfect knowledge of the future reference string. At the other end sits blind randomness, which any sensible algorithm should beat. Practical algorithms — FIFO, LRU, and their approximations — are judged by how close they come to Belady's lower bound using only past information, since the future is unavailable in a real operating system.

The common framework. Every replacement algorithm plugs into the same fault-handling skeleton: on a fault, if a free frame exists, use it; otherwise, invoke the victim-selection rule, evict, and load. ``` function ACCESS_PAGE(p): if p is resident: record_use(p) # bookkeeping only; no fault return HIT

# page fault if a free frame exists: frame <- allocate_free_frame() else: victim <- SELECT_VICTIM() # the only part that differs per algorithm if victim is dirty: write_back(victim) frame <- frame_of(victim) mark_not_resident(victim) load p into frame mark_resident(p, frame) record_use(p) return FAULT ```

FIFO. Maintain a queue of resident pages in load order. `SELECT_VICTIM` pops the front (oldest-loaded) page, regardless of how recently it was actually used. ``` function FIFO_SELECT_VICTIM(): return queue.dequeue() # oldest page loaded, O(1) function FIFO_RECORD_USE(p): if p was just loaded: queue.enqueue(p)

# accesses to already-resident pages do nothing to the queue ``` FIFO is attractive because it needs no per-access bookkeeping beyond load order — an O(1) queue operation per fault. Its weakness is that "oldest loaded" has no necessary relationship to "least likely to be used soon"; a page loaded long ago but referenced constantly (e.g., a loop counter) can still be evicted purely because of when it entered memory.

Belady's optimal algorithm (MIN/OPT). For each resident page, look ahead in the reference string to find its next use; evict the page whose next use is farthest away (or never reused again, treated as infinity). ``` function OPT_SELECT_VICTIM(residents, future_string, current_index): victim <- None farthest <- -1 for p in residents: j <- index of first occurrence of p in future_string[current_index+1 ..] if j does not exist: j <- +infinity # p is never used again — evict it immediately if j > farthest: farthest <- j victim <- p return victim ``` OPT requires the entire future reference string — information no real system possesses at run time. It exists purely as a theoretical benchmark: no other algorithm can produce fewer faults on the same reference string with the same number of frames.

LRU (Least Recently Used). Evict the page whose most recent use is farthest in the past — the temporal mirror image of OPT, using history instead of prophecy. ``` function LRU_SELECT_VICTIM(residents, last_used_time): victim <- argmin over p in residents of last_used_time[p] return victim function LRU_RECORD_USE(p): last_used_time[p] <- current_logical_clock current_logical_clock <- current_logical_clock + 1 ``` A conceptually clean (if slow) implementation stamps every page with a logical timestamp on each access and scans for the minimum on eviction — O(n) per fault for n resident pages. Real implementations instead maintain an ordered structure (a doubly linked list with move-to-front on access, giving O(1) per operation) or, more commonly in hardware, approximate LRU with reference bits, which is exactly the idea generalized by the Clock Algorithm.

Time complexity per fault. FIFO: O(1) with a queue (dequeue oldest, enqueue newly loaded page). LRU, naive timestamp scan: O(n) where n is the number of resident frames, since eviction requires scanning for the minimum timestamp. LRU, linked-list implementation: O(1) amortized — move the accessed page to the head of a doubly linked list on every reference, evict from the tail on a fault. This works because both "move to front" and "remove from tail" are O(1) list operations given a hash map from page number to list node. OPT: cannot be computed online at all; even offline, computing "next occurrence" for every page at every step can be done in O(n) total (n = string length) via a single backward pass building a next-occurrence index, but this presupposes full knowledge of the future.

Space complexity. All three need O(f) space for the frame table (f = number of frames) plus O(f) auxiliary state: a queue for FIFO, timestamps or a linked list for LRU, and (for offline OPT simulation) an O(n) next-occurrence array.

Correctness of OPT as a lower bound. The claim is: for any reference string and any frame count f, no replacement algorithm produces fewer faults than Belady's MIN algorithm. The proof sketch is an exchange argument. Suppose some algorithm A produces fewer faults than MIN on some string. Consider the first point at which A's frame contents differ from MIN's because A evicted a page that MIN kept. At that step, MIN is holding a page that will be used sooner than the page A is holding in the corresponding slot (by MIN's own eviction rule, which always evicts the page used farthest in the future). One can show inductively that A's frame set can be transformed step by step into MIN's frame set without ever increasing A's fault count — meaning MIN is a valid lower bound, and any claimed improvement collapses. This is why OPT is used as a baseline, not a deployable policy: it needs the future, but it certifies how far from optimal any online algorithm is.

The stack property and why it matters. Define, for a reference string and algorithm, `Faults(f)` as the number of faults using f frames. An algorithm has the stack property if for every prefix of the reference string and every f, the set of pages resident with f frames is a subset of the set of pages resident with f+1 frames: ``` Resident(f) ⊆ Resident(f+1) for all f, at every step ``` If this invariant holds, then `Faults(f)` is monotonically non-increasing in f — more memory can never hurt. LRU provably satisfies the stack property: the f most recently used distinct pages under f frames are always a subset of the f+1 most recently used distinct pages under f+1 frames, because "the top f of a totally ordered recency list" is trivially nested inside "the top f+1 of the same list." OPT also satisfies it (the f pages with the nearest next-uses are a subset of the f+1 pages with the nearest next-uses, by the same nesting argument on a sorted order). FIFO does not satisfy the stack property, because "the f most recently loaded pages" is not a stable nested prefix of any single global ordering that survives evictions — a page's position in the FIFO queue depends on load history, which is disrupted by earlier evictions in a way that recency order is not. This gap is exactly what produces Belady's anomaly: a real, documented phenomenon where increasing the number of frames from f to f+1 increases the fault count under FIFO.

Belady's anomaly, concretely. Consider the reference string ``` 1 2 3 4 1 2 5 1 2 3 4 5 ``` Simulating FIFO with 3 frames yields 9 faults; simulating FIFO with 4 frames on the same string yields 10 faults — strictly more, despite strictly more memory. This is not a pathological edge case invented for lecture; it is the canonical textbook example, and it is exactly reproducible by hand-tracing the FIFO queue discipline. It demonstrates why the stack property is not a pedantic technicality: without it, capacity planning based on "more RAM can only help" is simply false.

Trade-off summary. FIFO is cheap and stack-anomaly-prone; OPT is optimal but unrealizable; LRU approximates OPT's spirit using only history, guarantees the stack property (so more memory never backfires), but costs more bookkeeping than FIFO — motivating cheaper approximations of LRU in real hardware, discussed under the Clock Algorithm.

Reference string with 3 frames: `7 0 1 2 0 3 0 4 2 3 0 3 2`. We trace FIFO, LRU, and OPT side by side. `F` = fault, `H` = hit; frame contents listed oldest-relevant-order left to right (for FIFO: load order; for LRU: recency order, most-recent first).

(For brevity the fully expanded FIFO queue at every step is elided in prose; the point is structural, not arithmetic.) Totals on this string: FIFO = 10 faults, LRU = 8 faults, OPT = 7 faults. This ordering — OPT ≤ LRU ≤ FIFO — is not guaranteed to hold on every string (LRU can occasionally tie or momentarily exceed FIFO on adversarial strings), but OPT ≤ every algorithm always holds, by the exchange argument above, and it holds decisively here because the access pattern `0 3 0 4 2 3` has strong recency locality that LRU exploits and FIFO's load-order bookkeeping ignores.

Second trace — Belady's anomaly itself, string `1 2 3 4 1 2 5 1 2 3 4 5`, FIFO only:

Tracing carefully frame-by-frame confirms the counter-intuitive result: 4 frames produce more faults than 3 frames under FIFO on this string — the textbook demonstration of Belady's anomaly. LRU and OPT, run on the same string, never exhibit this because both satisfy the stack property proven above.

László Bélády, working at IBM's Thomas J. Watson Research Center, published the analysis that both named the optimal algorithm (MIN) and exposed the anomaly that bears his name. His 1966 paper on virtual storage systems provided the mathematical vocabulary — reference strings, stack algorithms, the monotonicity property — that every subsequent treatment of page replacement still uses. The anomaly he documented in 1969, joint work identifying that FIFO could violate the intuitive "more memory helps" assumption, remains one of the most quoted counter-examples in systems theory precisely because it is surprising, verifiable by hand, and consequential for real capacity planning.

Every general-purpose operating system kernel — Linux, Windows, the BSDs, macOS's XNU — implements some approximation of LRU for its page cache and process page tables, because pure LRU's bookkeeping cost is too high at the scale of gigabytes of memory and millions of pages. Database buffer pool managers (PostgreSQL, MySQL's InnoDB) use LRU-family policies (often "LRU-K" or segmented LRU) to decide which disk pages to keep cached in memory, directly reusing the theory developed for OS page replacement. Content delivery networks and in-memory caches like Redis and Memcached expose configurable eviction policies — `allkeys-lru`, `volatile-lru` — that are literal implementations of the algorithm described here, applied to key-value objects instead of memory pages. CPU cache replacement (L1/L2/L3) faces the identical victim-selection problem at nanosecond timescales, where true LRU is often approximated with pseudo-LRU trees for hardware efficiency. Understanding the FIFO/OPT/LRU framework, and the stack property that separates well-behaved policies from anomalous ones, is the conceptual foundation beneath all of these systems — and it directly sets up the practical, low-overhead approximation used almost everywhere in practice, the Clock Algorithm, as well as the systemic failure mode that occurs when no replacement policy can keep the fault rate low because the total working set simply exceeds available memory: Thrashing and the Working Set.

Ask the tutor: Can you show me step-by-step why LRU can never exhibit Belady's anomaly, using the stack-property proof applied directly to the anomaly's classic reference string?