Page Replacement

When a page fault needs a frame and none is free, the OS must evict a page (writing it to disk first if it is dirty).

Concept

When a page fault needs a frame and none is free, the OS must evict a page (writing it to disk first if it is dirty). The replacement policy decides which one; the goal is the fewest faults.

The page loaded earliest Simple; can evict hot pages; suffers Belady's anomaly OPT (Belady's optimal) The page used farthest in the future

Impossible in practice (needs the future); the benchmark The page unused for the longest time

Close to OPT for typical workloads; exact LRU is too expensive in hardware Clock (second chance)

Pages in a circle; a hand skips pages whose reference bit is set (clearing it) and evicts the first unreferenced one

Cheap LRU approximation using the hardware accessed bit Least / most frequently used Rarely used alone Working set / page fault frequency

Keep each process's recent working set resident Belady's anomaly: with FIFO, adding frames can *increase* the number of faults. LRU and OPT are stack algorithms and never show it.

Linux uses a variant of LRU with active/inactive lists (and since 6.1, the multi-generational LRU), distinguishing file-backed pages (can be dropped and re-read) from anonymous pages (must be swapped).

Why It Matters

Replacement policies show up well beyond the OS: CPU caches, database buffer pools (MySQL InnoDB uses an LRU variant), CDN and web caches, and every LRU cache interview question.

Syntax

Reference strings list the pages a program accesses in order; the exercise is to count faults for a given number of frames.

Example

20.1 FIFO, LRU, OPT and Clock, plus Belady's anomaly

"""Page replacement: FIFO, LRU, OPT and Clock on the same reference string, plus Belady's anomaly."""

def fifo(refs, frames):
    mem, faults, q = set(), 0, []
    for p in refs:
        if p not in mem:
            faults += 1
            if len(mem) == frames:
                mem.remove(q.pop(0))
            mem.add(p); q.append(p)
    return faults


def lru(refs, frames):
    mem, faults = [], 0
    for p in refs:
        if p in mem:
            mem.remove(p)
        else:
            faults += 1
            if len(mem) == frames:
                mem.pop(0)                         # least recently used is at the front
        mem.append(p)
    return faults


def opt(refs, frames):
    mem, faults = [], 0
    for i, p in enumerate(refs):
        if p in mem:
            continue
        faults += 1
        if len(mem) == frames:
            future = refs[i + 1:]
            victim = max(mem, key=lambda q: future.index(q) if q in future else len(future) + 1)
            mem.remove(victim)                     # evict the page used farthest in the future
        mem.append(p)
    return faults


def clock(refs, frames):
    slots, ref_bit, hand, faults = [None] * frames, [0] * f
…

Expected Result

On the textbook reference string with 3 frames: OPT 9 faults (the best possible), LRU 12, Clock 14, FIFO 15.

With FIFO on 1 2 3 4 1 2 5 1 2 3 4 5, 4 frames cause 10 faults but 3 frames only 9 — Belady's anomaly. LRU improves as expected (10 → 8).

reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 (20 references)
frames  FIFO  LRU  OPT  Clock
  3      15   12    9    14
  4      10    8    8     9

Belady's anomaly with FIFO on 1 2 3 4 1 2 5 1 2 3 4 5
  3 frames: FIFO 9 faults, LRU 10 faults
  4 frames: FIFO 10 faults, LRU 8 faults

Common Mistakes

Forgetting to count the initial compulsory faults.

Implementing LRU by timestamp scans on every access (O(n)) instead of a hash map + doubly linked list (O(1)).

Assuming more memory always reduces faults for every policy.

Best Practices

Use LRU approximations (Clock, segmented LRU) in real systems; exact LRU is costly.

Size caches for the working set; monitor the hit rate.

Protect against scans polluting an LRU cache (midpoint insertion, as InnoDB does).

Interview Relevance

Very high: "implement an LRU cache", "compare FIFO, LRU, OPT", "what is Belady's anomaly?", "how does the Clock algorithm work?", "count page faults for this reference string".

Practice Questions

Compute the FIFO faults for the textbook string with 3 frames by hand and compare.

Implement LFU and compare it with LRU on the same string.

Show the frame contents after each step for Clock with 3 frames.

Why can't OPT be implemented, and why is it still useful?

Quick Quiz

Q1. (Multiple choice) Which algorithm can suffer from Belady's anomaly? A) LRU B) OPT C) FIFO D) None

Answer: C (verified: 9 faults with 3 frames, 10 with 4).

Q2. (Predict the output) OPT faults on the textbook string with 3 frames?

Answer: 9 (verified).

Q3. (True/False) The Clock algorithm uses the page's reference (accessed) bit.

Answer: True. Q4. (Find the bug) An "LRU" cache moves an entry to the front only when it is inserted, not when it is read.

Answer: That's FIFO, not LRU: every hit must also move the entry to the most-recently-used position.

Coding Challenge

Implement an O(1) LRU cache (capacity 3) in Python with OrderedDict, apply the accesses A B C A D B E A, and print the hits, misses and final contents.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity, self.data = capacity, OrderedDict()

    def access(self, key):
        if key in self.data:
            self.data.move_to_end(key)             # most recently used goes to the end
            return True
        if len(self.data) == self.capacity:
            self.data.popitem(last=False)          # evict the least recently used (front)
        self.data[key] = True
        return False

cache = LRUCache(3)
results = [(k, "hit" if cache.access(k) else "miss") for k in "ABCADBEA"]
print(" ".join(f"{k}:{r}" for k, r in results))
print("hits", sum(r == "hit" for _, r in results), "final contents", list(cache.data))