Virtual Memory: Demand Paging, Replacement and Thrashing

Demand paging and page faults

With demand paging, a page is loaded only when it is first accessed. The page-table entry has a valid (present) bit; accessing an invalid page traps to the OS — a page fault:

1. The MMU traps to the kernel (the instruction is interrupted).
2. The kernel checks the address: illegal → kill the process (segmentation fault); legal but not in memory → continue.
3. Find a free frame (or choose a victim page, writing it back to disk if dirty).
4. Schedule a disk read of the page into the frame (the process blocks; the CPU runs another process).
5. When the I/O completes, update the page table (valid = 1, frame number).
6. Restart the instruction that faulted.

A minor fault is resolved without disk I/O (e.g., the page is in the page cache or is a new zero page); a major fault requires reading from disk.

The cost of a page fault

EAT = (1 − p) × memory access + p × page-fault service time

With a 100 ns memory access and an 8 ms fault (hard disk):

• p = 1/1000 → EAT = 0.999 × 100 + 0.001 × 8,000,000 ≈ 99.9 + 8,000 = 8,100 ns — 81 times slower!
• To stay within 10 % of normal speed (110 ns): p × 8,000,000 < 10 → p < 1.25 × 10⁻⁶, i.e., fewer than one fault per 800,000 accesses.

With a fast NVMe SSD (≈ 100 µs per fault) and p = 1/1000: 99.9 + 100 ≈ 200 ns — still 2× slower. Page faults must be rare.

Copy-on-write

fork() creates a child with a copy of the parent's address space — but most children immediately call exec(), so copying everything would be wasted. With copy-on-write (COW), parent and child share all pages, marked read-only. When either writes to a shared page, a fault occurs and the kernel copies only that page.

Example: a 4-page process forks; the child writes page 1, the parent writes page 2, the child writes page 3: 3 pages copied instead of 4, and with a second fork and one more write, 4 copies instead of 8 (8 frames in use instead of 12). Redis uses fork + COW to save snapshots while serving requests; Android's Zygote uses it to start apps fast.

Page replacement

When no frame is free, the OS must evict a page. Goal: minimize page faults. Algorithms are compared on a reference string (sequence of page numbers). Classic string with 3 frames:

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

• OPT needs the future — impossible in practice, but it is the benchmark for other algorithms.
• LRU uses the past as a prediction of the future (locality). Exact LRU needs a timestamp or a list update on every memory access — too expensive in hardware.
• LRU approximations use the reference bit set by hardware on each access. Clock: frames in a circle with a hand; on replacement, if the hand's page has reference bit 1, clear it and move on (second chance); if 0, evict it. (In this course, a newly loaded page starts with reference bit 1.)
• Enhanced clock uses (reference, dirty) pairs: prefer (0, 0) — not used, clean — then (0, 1), (1, 0), (1, 1). Evicting clean pages avoids a disk write.

Belady's anomaly. With FIFO, more frames can cause more faults. Reference string 1 2 3 4 1 2 5 1 2 3 4 5: 9 faults with 3 frames, 10 with 4. LRU and OPT are stack algorithms — the set of pages in memory with n frames is always a subset of the set with n + 1 frames — so they never show the anomaly.

Frame allocation

• Equal allocation: m frames / n processes.
• Proportional allocation: a process of size sᵢ gets sᵢ / S × m frames. Example: 62 frames, P1 = 10 pages, P2 = 127 pages → P1 gets 10/137 × 62 ≈ 4, P2 ≈ 57.
• Global replacement (a process can take frames from others — better throughput, less predictable) vs. local replacement (only its own frames — isolation). Linux uses global replacement, but cgroups limit each container.

Thrashing and the working set

If processes do not have enough frames for the pages they actively use, they fault constantly: each fault evicts a page that will be needed soon. The CPU waits on the disk, CPU utilization collapses, and a naive scheduler sees "low CPU usage" and admits more processes — making it worse. This is thrashing.

Working-set model. The working set WS(t, Δ) is the set of pages referenced in the last Δ references. Let D = Σ |WSᵢ| be the total demand:

• If D > available frames → thrashing risk → suspend (swap out) a process.
• If D is well below → another process can be admitted.

Example (Δ = 4, 7 frames): two processes each move into a new phase and their working sets grow to 4 pages: D = 8 > 7 → suspend one of them; with 8 frames, both fit.

Page-fault frequency (PFF) is a simpler control: if a process's fault rate is above an upper bound, give it more frames; below a lower bound, take frames away.

Memory-mapped files, swap and compressed memory

• Memory-mapped files (mmap): a file is mapped into the address space; reading the array reads the file, page by page, through page faults. Databases (LMDB, older MongoDB), and AI frameworks loading model weights (mmap of safetensors/GGUF files) use it — the model starts fast and only the touched pages are read.
• Swap: disk space for evicted anonymous pages (heap, stack). Linux's vm.swappiness sets the preference between evicting file pages and swapping.
• Compressed memory (zram, zswap, macOS and Windows memory compression): compress evicted pages in RAM instead of writing them to disk — a "fault" costs microseconds of decompression. Android and ChromeOS rely on it.
• Linux reclaim: the kswapd daemon keeps free memory above a watermark using active/inactive LRU lists (a clock-like approximation); if reclaim fails, the OOM killer chooses a victim.

Virtual memory beyond one machine

Live migration. To move a running VM or container from one edge server to another (e.g., following a mobile user, or before maintenance), the hypervisor copies memory while the VM runs (pre-copy), using dirty bits to find the pages modified during each round; it then pauses the VM briefly to copy the last dirty pages. With 4 GB of memory, 1 GB/s bandwidth and 200 MB/s dirtying rate: 4 s + 0.8 s + 0.16 s of pre-copy leave about 32 MB → about 32 ms of downtime.

Paged KV cache for LLM serving. Serving large language models requires a key-value cache per request that grows token by token. Allocating it contiguously wastes memory (like contiguous allocation, Chapter 9). vLLM's PagedAttention (2023) stores the KV cache in fixed-size blocks with a block table per request — paging applied to GPU memory — raising the number of requests served per GPU several-fold.

Key takeaways

• Demand paging loads pages on first access; a page fault blocks the process while the page is read.
• EAT = (1 − p) · ma + p · fault time; with 8 ms faults, p must be about 10⁻⁶ for < 10 % slowdown.
• COW shares pages after fork and copies only on write.
• Replacement on 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 (3 frames): FIFO 15, LRU 12, OPT 9, Clock 14. Clock = LRU approximation with reference bits; enhanced clock prefers clean pages.
• Belady's anomaly (FIFO: 9 faults with 3 frames, 10 with 4); stack algorithms (LRU, OPT) are immune.
• Proportional allocation; global vs. local replacement.
• Thrashing when Σ working sets > frames; fix by suspending processes (working set) or PFF control.
• mmap, swap, zram; live migration uses dirty pages; PagedAttention brings paging to GPU memory.