Chapter 6: Memory Management II: Virtual Memory and Page Replacement

Why this matters

Chapter 5 explained how paging maps virtual addresses to physical frames. This chapter explains the trick that makes modern computing actually work at scale: a process's total virtual memory can exceed the amount of physical RAM in the machine entirely — programs run correctly using more "memory" than physically exists, through a combination of lazy loading and disk-backed overflow. Understanding this mechanism explains copy-on-write from Chapter 2, the OOM killer from Chapter 1, and a huge amount of container/cloud memory behavior that otherwise looks mysterious.

The core concept: demand paging

[BEGINNER] Virtual memory decouples what a process believes it has (a large, private virtual address space) from what's physically backing it at any given moment. Demand paging means pages are only loaded into physical RAM when actually accessed for the first time — not all at once when a program starts. A page table entry can be marked "not present," and accessing it triggers a page fault.

Chapter 5 already introduced page faults in the context of invalid accesses (segfaults). This chapter's page faults are the legitimate, expected kind:

1. Process accesses virtual address in Page 5, which is marked "not present" in the page table.
2. CPU raises a page fault (an interrupt to the OS — see Chapter 9).
3. The OS checks: is this a LEGITIMATE page (part of the process's valid address space,
   just not loaded yet) or an ILLEGITIMATE one (Chapter 5's segfault case)?
4. If legitimate: OS finds a free physical frame, loads the page's actual content
   (from the executable file on disk, or a swap file, or zero-fills a new heap page),
   updates the page table to mark it "present," and resumes the process — which never
   knew any of this happened.
5. If illegitimate: SIGSEGV, as covered in Chapter 5.

This is why a large program starts almost instantly even though it might be hundreds of megabytes on disk — only the pages actually touched during execution ever get loaded, and most large programs only touch a small fraction of their total code/data in any given run.

Copy-on-write, explained properly

[SENIOR INSIGHT] Chapter 2 mentioned that fork() gives a child process "its own copy" of the parent's memory, efficiently, via copy-on-write (COW). Now that page tables and page faults are established, the mechanism is straightforward: fork() doesn't actually copy any memory content immediately. Instead, it copies the page table (cheap — just mappings) and marks every page in both parent and child as read-only. Both processes initially point to the exact same physical frames.

Immediately after fork():
Parent's page table: Page 0 -> Frame 7 (read-only)   Child's page table: Page 0 -> Frame 7 (read-only)
                          \_______________ same physical frame ________________/

The moment EITHER process tries to WRITE to that page:
1. The write triggers a page fault (the page is marked read-only).
2. The OS sees this is a COW page, allocates a NEW physical frame, copies the content into it,
   updates ONLY the writing process's page table entry to point to the new frame, and marks it writable.
3. The process resumes, and its write proceeds normally against its own private copy.

This means fork() is cheap regardless of how much memory the parent process uses — no memory is actually duplicated unless and until something writes to it, and pages that are only ever read (a large chunk of most programs, especially their code) may never be duplicated at all for the entire lifetime of both processes. This is the concrete mechanism that makes fork()-based process models (like the traditional Apache web server's worker-process-per-request model) practical.

Page replacement: what happens when physical memory is full

[BEGINNER] Demand paging means physical RAM can fill up even though the process's virtual memory hasn't. When a page needs to be loaded and no free frame exists, the OS must evict some currently-resident page to make room — chosen by a page replacement algorithm. If the evicted page is later needed again, it causes another page fault and must be reloaded (from a swap file/partition on disk, if it was modified and can't just be re-read from its original source).

Algorithm	How it chooses a victim	Trade-off
FIFO	Evicts the oldest-loaded page, regardless of recent use	Simple, but can evict a heavily-used page just because it happened to load first (Belady's anomaly: more frames can sometimes increase faults)
LRU (Least Recently Used)	Evicts the page not accessed for the longest time	Matches temporal locality (Chapter 3) well — usually performs close to optimal in practice — but tracking exact access recency for every page has real overhead
Clock / Second-Chance	An approximation of LRU: pages arranged in a circle with a "recently used" bit; sweeps looking for a page with the bit unset, clearing bits it passes over	The practical, low-overhead approximation actually used in most real systems (including Linux, in spirit) — a deliberate trade of exact LRU accuracy for far lower bookkeeping cost
Optimal (Bélády's algorithm)	Evicts the page that won't be needed for the longest time in the future	Provably the best possible — but requires knowing the future access pattern, so it's used only as a theoretical benchmark to measure other algorithms against, never in a real system

[IN PRACTICE] The reason Clock/Second-Chance (rather than "true" LRU) is what real operating systems actually implement is a direct instance of this book's recurring theme: exact LRU requires updating bookkeeping on every single memory access, which is far too expensive at the frequency memory is accessed; Clock approximates the same temporal-locality intuition using a single bit checked periodically, trading a small amount of replacement-quality for a massive reduction in constant overhead.

Thrashing: when virtual memory stops helping

[SENIOR INSIGHT] If the total actively-used memory across all running processes ("working set") genuinely exceeds physical RAM, the system enters thrashing: pages are evicted and then immediately needed again, causing a page fault almost every time a process touches memory, which means the system spends nearly all its time servicing page faults (each involving a slow disk read, per Chapter 3's hierarchy) and almost none doing actual useful work. Thrashing is recognizable as a system that's "busy" (high disk I/O, everything sluggish) while accomplishing almost nothing — a distinct symptom from ordinary high CPU load, and one that adding more concurrent processes makes dramatically worse, not better.

Connecting back to Chapter 1's OOM killer

[IN PRACTICE] On Linux specifically, when physical RAM and swap space are both exhausted (rather than just RAM alone, which swapping can absorb, at the thrashing cost above), the kernel cannot satisfy a memory allocation request through any legitimate means — this is exactly when the OOM killer from Chapter 1 activates, selecting a process (via a heuristic scoring system, /proc/<pid>/oom_score) to kill outright to free memory, since the alternative is the entire system becoming unresponsive. This is why container memory limits (cgroups, covered in Chapter 11) matter so much in production: a container with no explicit memory limit can consume enough memory to trigger OOM kills against unrelated processes on the same host, not just itself.

Common mistakes

1. Assuming a program's total virtual memory size reflects actual physical RAM usage. Demand paging means only touched pages are ever loaded — a process can report a large virtual memory size while using a small resident set (RSS in top/ps, the pages actually in physical RAM).
2. Believing fork() is expensive because it "copies all the memory." Copy-on-write means the actual copy only happens per-page, lazily, on write — the immediate cost of fork() is proportional to page table size, not process memory size.
3. Confusing thrashing (severe performance collapse from excessive paging) with ordinary high memory usage. High memory usage with a healthy page-fault rate is normal; a page-fault rate that dominates all CPU time, with near-zero forward progress, is thrashing specifically.
4. Not setting explicit memory limits on containers/processes in shared environments, allowing one runaway process to trigger OOM kills against unrelated neighbors — a direct, practical consequence of how the kernel-wide OOM killer operates.

Checklist: reasoning about virtual memory in practice

1. Distinguish virtual memory size from resident set size (RSS) when investigating a process's actual physical memory footprint — top/ps aux show both, and only RSS reflects real RAM pressure.
2. Remember fork()'s cost is proportional to page-table size, not memory content size, thanks to copy-on-write — this changes the calculus on whether fork()-based concurrency is "too expensive" for a given workload.
3. Recognize thrashing's signature (high disk I/O, sluggish system, low actual throughput) as distinct from ordinary CPU or memory pressure, and address it by reducing concurrent working-set size, not by "optimizing code" that isn't actually the bottleneck.
4. Set explicit memory limits on processes/containers in shared/multi-tenant environments to contain the blast radius of a memory leak or spike, rather than leaving the kernel's OOM killer to make an uncontrolled choice.

Discussion / interview questions

1. "What is demand paging, and why does it let programs start almost instantly regardless of their total size on disk?" Strong answer: Pages are loaded into physical memory only when actually accessed (triggering a page fault if not yet loaded), rather than all at once at startup — most programs only touch a small fraction of their total code/data in a given run, so startup cost is proportional to what's actually used, not total size.

2. "Explain how copy-on-write makes fork() efficient, using the concept of page tables from Chapter 5." Strong answer: fork() copies only the page table (cheap) and marks all pages read-only in both processes, initially sharing the same physical frames; an actual physical copy of a given page happens only when either process writes to it, triggering a page fault that the OS handles by allocating a private frame for the writer.

3. "Why do real operating systems use Clock/Second-Chance instead of 'true' LRU for page replacement?" Strong answer: True LRU requires updating exact access-recency bookkeeping on every memory access, which is prohibitively expensive at that frequency; Clock approximates the same temporal-locality intuition with a single per-page bit and a periodic sweep, trading some replacement accuracy for dramatically lower constant overhead.

4. "What is thrashing, and how would you recognize it as distinct from ordinary high memory or CPU usage?" Strong answer: A state where the working set across running processes exceeds physical RAM, causing pages to be evicted and immediately re-needed, so the system spends nearly all its time servicing page faults (slow disk I/O) instead of doing useful work — recognizable as a system that appears very busy (especially in disk I/O) while making almost no forward progress, distinct from a CPU-bound system that's simply doing a lot of real computation.

Chapter summary / cheat sheet

• Demand paging: pages load only on first access (via a legitimate page fault), letting programs start quickly and use less physical memory than their virtual size suggests.
• Copy-on-write: fork() shares physical frames read-only between parent and child until either writes, at which point only that page is actually duplicated — making fork()'s cost independent of process memory size.
• Page replacement algorithms (FIFO, LRU, Clock/Second-Chance, Optimal) choose what to evict when physical memory is full; real systems use Clock as a low-overhead approximation of LRU.
• Thrashing: when the combined working set exceeds physical RAM, causing near-constant page faults and collapsing real throughput — a distinct, recognizable failure mode from ordinary resource pressure.
• The Chapter 1 OOM killer activates specifically when RAM and swap are both exhausted — explicit memory limits (cgroups, Chapter 11) contain the blast radius in shared/production environments.

---