Demand Paging and the Page Fault

Bring in only what is asked for

In the previous guide you saw the grand illusion this rung is built on: a process can have a logical address space far larger than the RAM you actually own, because not all of it has to be in physical memory at once. This guide answers the obvious next question — so when, exactly, does a piece get brought in? The honest, almost lazy answer is the heart of virtual memory: bring in a page only at the moment some instruction actually reaches for it, and not one moment sooner. That policy has a name, demand paging, and it is exactly what it sounds like: pages arrive on demand.

Picture a thick recipe binder for a banquet — the whole logical program on disk. A naive kitchen would photocopy every single page before the cook starts. Demand paging is the smarter cook who keeps the binder closed and only photocopies a page the instant a recipe calls for it. Many of those pages — the dessert section, the error-handling that never runs, a feature you never click — get photocopied late or never. The program starts almost immediately, because it only needed its very first page to begin, and it never wastes effort on bytes nobody asks for. When a program starts with absolutely nothing in memory and faults in its first instruction's page on the spot, we call that the extreme case, pure demand paging.

One bit that says 'here' or 'not here'

For demand paging to work, the hardware needs a way to ask, on every single access, a yes-or-no question: is this page in physical memory right now? You already met the page table — the book's index that maps each page number to the frame holding it. We now add one tiny extra column to every row: the valid / invalid bit. When it reads 'valid', the page really is sitting in some frame and the entry's frame number is trustworthy. When it reads 'invalid', the hardware must stop and refuse — and crucially, 'invalid' is overloaded with two very different meanings.

One meaning is 'this page is part of your address space, but it is currently out on disk, not in RAM' — legitimate, just absent. The other is 'this address is not in your address space at all — you have no business touching it'. The hardware itself cannot tell these apart from the bit alone; both read 'invalid'. So the bit's job is simply to bounce control up to the operating system, which keeps the fuller story (in its own tables) about which absent pages are legal. The hardware raises the alarm; the kernel, our building manager, decides whether the visitor is a tenant who lost their key or a burglar.

Picture the page table as rows, each with a page number, a frame number, and that one extra v/i column. Page 0 might read 'frame 12, valid' — it is in RAM and the frame number is good. Page 1 reads 'valid bit off': it is a legitimate page of yours, but it lives on disk right now, so its frame number is blank. Page 3 also reads 'invalid', yet for the second reason — it was never part of your address space at all. When the CPU asks for page 1, the hardware sees the bit is off, traps to the OS, and the OS consults its own map to learn that page 1 is merely absent (fetch it) while page 3 is illegal (kill the process).

The page fault: a doorbell, not a disaster

When an instruction reaches a page whose bit is 'invalid', the hardware raises a page fault. The word 'fault' sounds frightening, but for an absent-but-legal page it is completely routine — think of it less as a crash and more as a doorbell, an interrupt that says 'someone needs a page that is not in yet'. It is the same kind of trap into the kernel you met when a process makes a system call, except this one is triggered by the memory hardware mid-instruction rather than by the program asking on purpose. The program did nothing wrong; it simply touched a page that was not resident, and the OS quietly steps in to fix that.

Here is the full service sequence — the kernel's standard answer to that doorbell. It is worth walking once slowly, because guide 3 in this rung will dwell on each step's cost in detail; for now, get the shape of it.

1. The hardware spots the 'invalid' bit, freezes the offending instruction in its tracks, and traps into the operating system, handing it the faulting logical address.
2. The OS checks its own records: is this page a legitimate but absent part of the process, or an illegal reference? If it is illegal, the process is killed (this is the clean crash a stray pointer earns); if legitimate, carry on.
3. Find a free frame in physical memory. (If none is free, a victim page must be chosen and evicted first — that whole story is page replacement, the next rung's business.)
4. Schedule a disk read to copy the needed page from swap space (or the program file) into that frame. This is the slow part; the disk is glacial next to RAM, so the OS puts this process to sleep and runs someone else meanwhile.
5. When the read finishes, update the page table: write in the frame number and flip the bit to 'valid'. The page is now resident.
6. Restart the very instruction that faulted. It re-executes from the beginning, the access now succeeds, and the program never knew it had paused.

Restart the instruction — and why that is hard

That last step hides a deep requirement. The whole trick only works if the faulting instruction can be restarted from scratch as though it had never run — this is the restartable-instruction requirement. For a simple 'load a value from address X', restarting is easy: the load never completed, so just do it again. The danger is an instruction that has already done part of its work before hitting the absent page. Imagine a block-copy instruction that moves a chunk of bytes from one region to another; suppose it has copied half of them, then the destination crosses into a page that is not resident and faults.

If we naively restart that instruction after servicing the fault, it copies the whole block again — and the first half of the source may have been overwritten in the meantime, so we get garbage. CPUs solve this in different ways: some check that every page the instruction will touch is present before doing any of the work, others keep enough hidden state to undo the partial effects. The point for you is not the exact fix but the principle: an architecture can only support demand paging if its instructions are designed to be cleanly restartable. This is one of those quiet places where the hardware and the OS must be co-designed.

Why even a tiny fault rate hurts — and why it usually doesn't

Now the sobering arithmetic. A normal memory access takes maybe 100 nanoseconds. Servicing a page fault — going out to disk — can take millions of nanoseconds (call it 8 milliseconds, eight million nanoseconds). Let p be the page-fault rate, the fraction of accesses that fault. The effective access time is a simple weighted average: most accesses are fast, a few are catastrophically slow, and you blend them by how often each happens.

  effective access time = (1 - p) * 100 ns  +  p * 8,000,000 ns

  If p = 0          ->  100 ns           (the dream)
  If p = 1 in 1000  ->  about 8100 ns    (~80x slower!)
  If p = 1 in 1,000,000 -> about 108 ns  (only ~8% slower)

  A fault is ~80,000x slower than a hit, so 'rare' has to mean REALLY rare.

Look at the middle line: one fault in a thousand accesses — which sounds rare — already makes the machine roughly eighty times slower. To keep the slowdown to a tolerable few percent you need faults to be one in hundreds of thousands or rarer. So demand paging only works at all because of a happy fact about real programs: locality of reference. Programs do not scatter their accesses randomly across their whole address space; they cluster, hitting the same small set of pages over and over for a while (a loop, a hot data structure) before drifting elsewhere. That cluster of pages a process is actively using is its working set. Keep each process's working set in RAM and faults stay blissfully rare; the rest of this rung is largely about respecting locality so that p stays tiny.

The same trick, reused: cheap fork and mapped files

Once you have the page table, the valid/invalid bit, and the fault as a tool, the OS reuses them for clever wins beyond just 'fit more than RAM'. The best example is copy-on-write, which makes fork cheap. When a process forks, the child is supposed to get its own full copy of the parent's memory — naively, a huge, slow duplication. Instead the OS lets parent and child share the very same physical frames, marked read-only. Both can read freely. Only when one of them tries to write does a fault fire; the kernel then makes a private copy of just that one page, fixes up the writer's table, and lets the write proceed. Pages that are only ever read are never copied at all.

The other reuse is the memory-mapped file: instead of reading a file with explicit read(fd, buf, n) calls, you ask the OS to map the file's contents directly into your address space, so the file simply appears as a stretch of memory. Reading byte 5000 of the file becomes reading memory address 5000 of the mapping — and the page fault is what fetches each chunk from disk on first touch, exactly the demand-paging machinery you just learned, now serving a file instead of a swapped-out page. Guide 5 of this rung gives both of these their own full treatment; for now, just notice how one mechanism — fault, fix, restart — quietly powers three quite different features.