Why an unbearably slow trick feels fast
In the last three guides we built demand paging: a process starts with almost nothing in RAM, and each time it touches a page that is not resident, the hardware raises a page fault, the kernel fetches that page from disk, and the offending instruction restarts. We were honest that fetching a page from disk is brutally slow — millions of times slower than reading RAM. So here is the puzzle this guide must answer: if every page fault is a catastrophe, why is demand paging not a disaster? Why does your laptop, which runs on this exact trick, feel instant?
The whole answer rests on one empirical fact about how real programs behave, not on any clever algorithm. Programs do not scatter their memory accesses randomly across their whole address space. They cluster. A loop runs the same dozen instructions thousands of times; a routine reads the same array straight through; a function pushes and pops the same few stack pages over and over. This clustering is called locality of reference, and it is the single load-bearing assumption under everything in this rung.
Two flavours of locality
Locality of reference comes in two distinct flavours, and it helps to name both. Temporal locality says: if you touched an address just now, you will probably touch it again very soon. The loop counter, the lock you just took, the current line of code — these get hit again and again within a tiny window of time. Spatial locality says: if you touched an address, you will probably touch its neighbours soon. You walk an array element by element; you read a file front to back; the CPU executes instruction after instruction in sequence.
Now connect this to pages. A page is, say, a 4 KB chunk of the address space — a whole block of neighbouring addresses bundled together. Spatial locality means that the very first access into a fresh page (which costs one page fault) is usually followed by hundreds or thousands of cheap accesses to other bytes in that same page, with no further fault. Temporal locality means that once a page is resident, the program keeps coming back to it for a while before moving on. Paging and locality are a beautiful match: the page is exactly the unit at which locality pays off.
This is the same principle that makes the whole memory hierarchy work at every level, not just for pages. The CPU cache bets on locality to keep hot data near the cores; the TLB, those sticky notes for the page numbers you just translated, bets on locality so most address translations skip the page table walk. Locality is not one trick used once. It is the same observation cashed in again and again, all the way down from registers to disk.
Putting a number on the pain: effective access time
Locality tells us faults are rare, but we should be quantitative about how rare is rare enough. Let the page-fault rate p be the fraction of memory accesses that fault. A plain RAM access takes some small time — call it 200 nanoseconds for our example. A page fault costs that plus the whole service routine: trap into the kernel, find a free frame, read the page from disk, update the page table, restart the instruction. The disk read alone dominates everything else; suppose the full fault service averages 8 milliseconds — that is 8,000,000 nanoseconds.
The effective access time is just the weighted average: most accesses are the cheap kind, a fraction p are the ruinous kind. The formula is effective access time = (1 - p) * 200 + p * 8,000,000 nanoseconds. The terrifying part is how lopsided the two costs are. The disk fault is forty thousand times more expensive than the RAM access, so an almost negligible p still drags the average up enormously. Watch what one fault in a thousand does.
Try p = 1/1000 — one fault per thousand accesses, which sounds harmlessly rare. The average becomes about 0.999 * 200 + 0.001 * 8,000,000 = roughly 8200 nanoseconds. That is 41 times slower than the 200 ns ideal, from a fault rate of a tenth of a percent. Push p down to 1/100,000 and you still pay about 280 ns, a 40% slowdown. To stay within about 10% of full speed you need fewer than roughly one fault per 400,000 accesses. That is an astonishingly tight budget, and it is precisely the budget locality must come in under.
Sit with that result, because it reframes everything. Virtual memory does not make programs faster — that is a common misconception worth killing outright. At best it adds zero overhead; every fault only ever slows you down. What virtual memory buys is not speed but possibility: it lets a program run at all when it is larger than RAM, or lets many programs coexist. The job of every mechanism in this rung is therefore not to speed faults up but to make them rare enough that the slowdown stays invisible. The number above — fewer than one fault in hundreds of thousands of accesses — is exactly the target locality has to hit.
Naming what a program needs: the working set
Locality says a program clusters its accesses around a small group of pages for a while, then shifts to a different group as it moves to a new phase of work. That changing group has a name: the working set. Informally, the working set of a process is the set of pages it has actually touched in the recent past — and, by locality, the set it is most likely to touch in the near future. It is the program's current centre of attention, and it changes over time as the program moves between phases (loading, computing, writing output).
We can make this precise with a sliding window. Pick a window size — say the last 10,000 memory accesses — and define the working set as the distinct pages referenced inside that window. As the window slides forward in time, pages that stop being used fall out of the set and freshly touched pages enter it. The size of this set, the working-set size, is the honest estimate of how many frames this process needs right now to run smoothly. Give it that many frames and faults stay rare; give it fewer and faults explode.
reference string (page numbers touched, left = oldest):
... 2 6 1 5 7 7 7 7 5 1 6 2 3 3 4 4 4 4 3 4 4 4 ...
|<------ window of 10 refs ----->|
^now
pages seen in the window = { 3, 4 }
WORKING SET SIZE = 2 frames right now
Earlier, mid-loop, the window held { 1, 5, 6, 7 } -> 4 frames.
The set SHRANK because the program entered a tighter phase.The working set gives the OS a memory-management policy that is hard to beat: try to keep every running process's whole working set resident in RAM, and you can spare it the constant faulting. If the sum of all processes' working sets fits in physical memory, the system hums. The moment that sum exceeds RAM, something has to give — and what gives is performance, in the ugliest way this rung has to offer.
When the set no longer fits: thrashing
Suppose you run too many programs at once, so the combined working sets need more frames than you have. Each process is now starved: it cannot keep even its own hot pages resident. So it faults, the kernel evicts some other process's needed page to make room, that process immediately faults to get its page back, which evicts the first process's page again, and on and on. The CPU spends almost all its time waiting for the disk, doing the bookkeeping of swapping pages in and out, and almost no time running actual program code. This collapse is called thrashing.
Thrashing has a vivid, counter-intuitive signature. As you add more processes, CPU utilization climbs at first — good, more work to overlap. But past the point where working sets stop fitting, utilization does not just stop rising; it falls off a cliff. The system gets dramatically slower precisely because you asked it to do more. Your laptop "freezes," the disk light is solid on, the cursor barely moves — yet the CPU is nearly idle, because every process is blocked waiting for a page that another process is about to steal back.
The cure follows straight from the diagnosis: do not let total demand exceed supply. If the OS detects thrashing, the right move is counter-intuitive but correct — suspend a whole process, swapping its pages out to swap space and freeing those frames, so the remaining processes finally get enough room to keep their working sets resident. Fewer runnable processes, paradoxically, means far more work actually gets done. This is the working-set model put to work: admit a new process only if its working set will fit alongside the others, and shed processes when the frames run short.
Where this leads next
Two big questions fall out of this guide, and the rung splits to answer them. First: when a fault arrives and RAM is already full, which resident page do we evict to make room? Get that choice wrong and you evict a page that is part of someone's working set, causing a fault almost immediately — exactly the seed of thrashing. Choosing the victim wisely is page replacement, the whole subject of the rung right after this one, where locality reappears as the justification for approximating the unrealizable optimal policy by simply favouring recently used pages.
Second: can we make faults cheaper, or avoid them entirely, by being cleverer about what shares a page and what gets loaded when? That is the subject of the final guide in this rung. Two ideas there are pure applications of locality and laziness. Copy-on-write lets a freshly forked child share every page with its parent until one of them writes, so a fork that logically duplicates a huge address space copies almost nothing — only the rare written page. Memory-mapped files let a file appear directly as pages in your address space, so reading it is just demand paging in disguise, with locality deciding which parts ever actually load.
Step back and the shape of the whole rung is clear. Demand paging is the mechanism; locality is the reason it works; the working set is how we measure what a program needs; thrashing is what happens when we ignore that measure; and copy-on-write and memory-mapped files are clever ways to need fewer pages and fewer faults in the first place. Every one of them leans on the same humble observation: programs use only a little of their memory at a time, and they keep coming back to it.