Demand Paging and Thrashing

When you launch a 2\,\text{GB} program it starts in milliseconds, long before that much data could ever be read from disk. The trick is that the operating system loads almost nothing up front. It builds the page tables so the whole address space is valid, but marks the pages not present, and lets the very first access to each page take a fault that pulls it in. This is demand paging: pay for a page only when, and if, it is actually touched. Most of a program's pages are never touched at all, so you never pay for them.

Demand paging is what makes virtual memory feel free — until the day the pages a program actively needs no longer fit in RAM. Then the system tips over an edge into thrashing, where it spends all its time shuttling pages to and from disk and gets almost no real work done. This lesson is about both: the elegant laziness that makes memory abundant, and the cliff it walks up to.

Major faults, minor faults, and the ones that aren't faults at all

"Page fault" sounds like an error; it is not. It is the ordinary mechanism by which the OS lazily populates memory. The crucial distinction — the one that separates a fast program from a slow one — is where the page comes from:

Kind	What happened	Cost
Minor (soft) fault	page is already in RAM — just not mapped into this process (e.g. shared page, page cache hit, zero page)	microseconds — no I/O
Major (hard) fault	page must be read from disk/swap	milliseconds — thousands× slower
Invalid access	address not in any valid mapping (a real bug)	SIGSEGV — the program dies

A minor fault is a bookkeeping blip; a major fault stalls the process for milliseconds while a disk (or, today, an SSD or swap device) delivers the page. The ratio of major to minor faults is one of the first things you look at when a system feels slow: many major faults means the working data does not fit in RAM.

Demand paging: pages are marked valid-but-not-present and brought in on first touch, so a process only occupies RAM proportional to what it actually uses;
a major fault fetches from disk (milliseconds); a minor fault only re-maps a page already in RAM (microseconds);
the working set W(t,\Delta) is the set of distinct pages referenced in the last \Delta accesses — the memory a process currently needs; thrashing occurs when the working sets of the runnable processes sum to more than physical memory.

The working-set model

How much memory does a process "need"? Not its whole address space, and not one page — it needs whatever it is actively using right now. Denning's working-set model makes this precise: the working set W(t,\Delta) is the set of distinct pages referenced in the last \Delta memory accesses (the window). Because programs have locality, this set is small and stable for a while, then shifts as the program moves to a new phase. Keep each process's working set resident and its major faults nearly vanish; let it fall below, and faults explode. Run the window over a reference string and watch the working set breathe:

// The working-set model: W(t, delta) = distinct pages referenced in the last `delta` accesses. // A program with two locality phases; watch the working set stay small, then shift. const refs = [1, 2, 1, 2, 3, 1, 2, 3, 7, 8, 9, 7, 8, 9, 8, 7]; const DELTA = 4; // window size let peak = 0; for (let t = 0; t < refs.length; t++) { const lo = Math.max(0, t - DELTA + 1); const window = refs.slice(lo, t + 1); const ws = [...new Set(window)].sort((a, b) => a - b); peak = Math.max(peak, ws.length); console.log(`t=${String(t).padStart(2)} ref ${refs[t]} W = {${ws.join(",")}} |W| = ${ws.length}`); } console.log(`peak working-set size = ${peak} pages -> give the process at least this many frames`); console.log("Notice |W| jumps briefly when the program switches locality (1,2,3 -> 7,8,9), then settles.");

This is the basis of a real allocation policy: the OS estimates each process's working-set size (by sampling the accessed bits over a window) and tries to keep that many frames allocated to it. If it cannot — if the working sets do not all fit — some process must be suspended entirely and swapped out, because running it would only thrash everyone.

The thrashing cliff

Here is the counter-intuitive shape every OS student must know. Add more processes (raise the degree of multiprogramming) and at first throughput rises — more processes means the CPU always has something to run while others wait on I/O. But each process needs its working set resident. Past the point where the working sets stop fitting in RAM, adding one more process forces eviction of pages that are still in use, so every process starts faulting, the disk queue saturates, and throughput falls off a cliff. Drag the working-set slider: fatter working sets move the cliff to the left, because fewer processes fill memory.

The system is worst exactly when it is busiest: at the peak of thrashing the CPU is idle most of the time, waiting on disk, even though the run queue is full. The fix is not "work harder" — it is to reduce the degree of multiprogramming: suspend a process, free its frames, and let the survivors keep their working sets. This is the page-fault-frequency (PFF) policy in one sentence.

Page-fault frequency: a thermostat for memory

Working sets are expensive to track exactly, so real systems use a feedback signal that is trivial to measure: each process's page-fault rate. PFF sets an upper and lower band:

if a process's fault rate climbs above the upper band, it does not have enough frames — give it more (or, if none are free, suspend some other process);
if it drops below the lower band, it has more than it needs — take some frames away for others.

It is a thermostat: fault rate is the temperature, frames are the heat, and the OS holds each process in a comfortable band. When the whole machine is over-committed and even PFF cannot keep everyone in band, the last resort is swapping: evict an entire process's pages to the swap device and mark it non-runnable until memory frees up. Swapping a process out to rescue the rest is the OS admitting that no replacement policy can help when the demand simply exceeds the RAM.

Once thrashing sets in, everything slows down — including the code that is supposed to fix it. The memory manager, the shell you are typing into, even the mouse cursor's handler must all be paged back in to run, and they are stuck behind a saturated disk queue. So the machine that most needs to suspend a process is the one least able to, because the tool for suspending it is itself paged out. This "swap death" is why an over-committed server can become totally unresponsive rather than merely slow, and why the kernel eventually invokes the blunt instrument of last resort — the OOM killer, which simply picks a memory hog and terminates it to break the spiral.

Why one major fault ruins your averages

Demand paging is only cheap because major faults are rare. To see how brutally a small fault rate hurts, compute the effective access time. Let a RAM access take t_m = 100\,\text{ns} and a page-fault service (disk) take t_f = 8\,\text{ms} = 8{,}000{,}000\,\text{ns}. With fault probability p,

\text{EAT} \;=\; (1-p)\,t_m \;+\; p\,t_f.

Plug in a fault on just one access in a thousand (p = 0.001): \text{EAT} \approx 0.999\times100 + 0.001\times8{,}000{,}000 \approx 8100\,\text{ns} — the machine now runs 81× slower than its fault-free speed, from a fault rate of one in a thousand. That is the whole argument for keeping working sets resident: because a major fault is \sim 10^5 times a memory access, you can tolerate only a vanishingly small fault rate before it dominates everything.

Two slips travel together. First, "fault" does not mean error: the overwhelming majority of page faults are the intended way memory gets populated, and the process resumes as if nothing happened. The genuine error — touching an address in no valid mapping — is a segmentation fault, a different beast. Second, do not assume every fault hits the disk. A minor fault — mapping in a page that is already in RAM (a shared library other processes loaded, a file already in the page cache, a copy-on-write or demand-zero page) — costs microseconds and never queues an I/O. When you profile, the number that predicts pain is the major-fault count, not the total. Conflating the two will make you fear cheap faults and miss the expensive ones.