Demand Paging
Imagine launching a video editor that links against a 400 MB library. Your edit only touches three filters. Loading the entire binary before execution starts wastes memory, disk bandwidth, and time. Most of that library will never run in this session. An operating system that insists on loading everything upfront pays a fixed, large cost. This happens no matter how small the actual working set turns out to be. Demand paging is the answer: bring pages into memory only when a process actually references them, not before. It builds directly on The Page Table. It depends on the same address-translation hardware used by the Translation Lookaside Buffer. But it adds one crucial twist. A page table entry can point to nothing yet resident. The hardware must be able to say so cheaply. This single bit of bookkeeping, the valid bit, is the hinge on which the entire mechanism turns. The idea matters because it decouples a process's virtual address space from its physical memory footprint. A program can have a 64-bit address space and a multi-gigabyte executable. Yet it can use only a few megabytes of real RAM at any instant. This is what makes several things possible. It lets more processes run than would fit in memory simultaneously. It allows memory-mapping huge files without reading them wholesale. It lets large programs start almost instantly. Every modern general-purpose operating system — Linux, Windows, macOS, the BSDs — uses demand paging as its default execution model. This article builds the mechanism from the ground up. It shows how the valid bit turns a missing page into a controlled trap. It explains how the operating system services that trap. It also shows how to reason quantitatively about the resulting slowdown, using the effective access time model. It closes by connecting demand paging to the topics it directly sets up. These include Page Faults as a general fault-handling framework. They also include Memory-Mapped Files as demand paging applied to files. Finally, they include Page Replacement Algorithms for when memory finally runs out.
- Demand paging loads a page from backing store only on its first access, not at process start.
- The valid bit in each page table entry distinguishes "page is in memory" from "page is not yet loaded."
- Accessing an invalid page triggers a page fault, a synchronous trap the OS services transparently.
- Pure demand paging starts every process with zero resident pages, maximizing laziness.
- Performance is governed by the effective access time (EAT) formula, dominated by the page-fault rate.
- Because fault service costs ~milliseconds versus ~nanoseconds for a hit, even a tiny fault rate matters enormously.
A page table entry can mean "not here yet" as well as "here" — that one extra bit turns memory loading from eager to lazy.
The idea
A page table entry (PTE) normally maps a virtual page number to a physical frame number, enabling the address-translation step you already know from The Page Table. Demand paging adds a single-bit field to every PTE, the valid–invalid bit (sometimes just "valid bit" or "present bit"). When set to valid, the frame field is meaningful and the page truly resides in physical memory. When set to invalid, the frame field is meaningless, and the page currently lives only in backing store — typically a reserved region of disk or SSD, often called swap space, or in the case of memory-mapped files, the file itself. Under pure demand paging, a process starts execution with every page marked invalid. Nothing is loaded speculatively — not even the page containing the very first instruction. The instant the CPU tries to fetch that first instruction, translation hardware discovers the invalid bit, aborts the memory reference, and raises a page fault: a synchronous exception delivered to the operating system's fault handler. The handler locates the page's true location on backing store, allocates a physical frame, schedules the transfer, updates the PTE to valid with the new frame number, and then restarts — not resumes, but re-executes from scratch — the faulting instruction. From the process's point of view, nothing unusual happened except that the instruction took an unusually long time; correctness is entirely preserved, because the instruction is re-run only after its operand is now genuinely present. This lazy-loading discipline generalizes: any reference to any invalid page, whether an instruction fetch, a data load, or a data store, produces the same kind of fault, handled by the same general machinery — the foundation for the broader treatment of Page Faults. Demand paging is thus best understood not as a special-purpose trick but as the default configuration of a fault-driven memory system, where "load nothing until proven necessary" is the governing policy and every departure from it (prepaging, working-set prediction, read-ahead) is an optimization layered on top.
How it works
The mechanism has three moving parts: the extended page table entry, the CPU's translation-time check, and the operating system's fault handler. Consider the full life cycle of a single memory reference under pure demand paging.
Step 1 — Process creation. When a process is created (or a program is exec'd), the OS builds a page table whose entries all have their valid bit cleared. No physical frames are allocated for the process's code or data yet; the page table only records where each page can be found on backing store (an offset into the executable file, or a reserved swap slot).
Step 2 — Memory reference. During instruction execution, the CPU generates a virtual address. The Translation Lookaside Buffer is consulted first, as always. On a TLB miss, the hardware or a software handler walks the page table to find the relevant PTE.
Step 3 — Validity check. The hardware inspects the valid bit.
- If valid, translation completes normally: the frame number is used, physical address is formed, and the memory access proceeds. This is the common case once a process has been running for a while (its resident pages are now warm).
- If invalid, the hardware immediately traps into the operating system. This trap is the page fault.
Step 4 — Fault handling. The kernel's page-fault handler executes a well-defined algorithm: ``` function HANDLE_PAGE_FAULT(process, virtual_address): page_number ← EXTRACT_PAGE_NUMBER(virtual_address) pte ← process.page_table[page_number]
# Distinguish a legitimate lazy-load from a real protection error if pte.backing_location == NONE: raise SEGMENTATION_FAULT(process) # address was never valid return frame ← ALLOCATE_FREE_FRAME() if frame == NONE: victim_frame ← SELECT_VICTIM_FRAME() # see Page Replacement Algorithms EVICT(victim_frame) frame ← victim_frame SCHEDULE_DISK_READ(pte.backing_location, frame) BLOCK(process) # process is descheduled; CPU runs another process WAIT_FOR_IO_COMPLETION() pte.frame_number ← frame pte.valid ← TRUE UPDATE_TLB_OR_INVALIDATE_STALE_ENTRY(page_number) UNBLOCK(process) RESTART_INSTRUCTION(process) # re-execute the faulting instruction, not resume mid-way ```
Step 5 — Restart. Once the handler returns, the CPU re-executes the entire faulting instruction from its beginning. This is why the instruction must be restart-able: any partial side effects it had (e.g., a multi-operand instruction that had already modified one operand before faulting on another) must either not yet have happened, or the architecture must guarantee they can be redone safely. Most instruction-set architectures are carefully designed with this property, precisely to support demand paging and virtual memory generally.
Step 6 — Resume translation. With the PTE now valid, translation proceeds exactly as in step 3's valid branch, and the instruction completes normally, oblivious (from the program's semantic perspective) to the detour it just took.
Complexity & correctness
Space. The valid bit costs a fixed, tiny overhead per PTE — typically one bit, folded into unused bits of an already word-aligned entry, so it adds essentially zero space overhead beyond the page table structure required by The Page Table anyway. The real space savings are on the other side of the ledger: physical memory usage is proportional to the process's actual resident set, not its virtual address space size, which is the entire point.
Time — the effective access time model. Let ``` p = probability of a page fault on a given memory reference ma = memory access time (no fault) — nanoseconds, e.g. 200 ns pf = page-fault service time — milliseconds, e.g. 8 ms ``` The effective access time is the expectation over the two outcomes: ``` EAT = (1 − p) · ma + p · pf ``` This is a direct application of linearity of expectation: each reference either hits (probability `1 − p`, cost `ma`) or faults (probability `p`, cost `pf`, which itself typically already includes a final memory access after the fault is serviced). Because `pf` is on the order of milliseconds (dominated by rotational/seek or flash latency, context switch overhead, and queueing for the I/O device) while `ma` is on the order of nanoseconds, the ratio `pf / ma` is roughly `10^6`. Consequently: ``` EAT ≈ ma + p · pf (since (1−p)·ma ≈ ma for small p) ``` Even `p = 0.001` (one fault per thousand references) with `ma = 200 ns` and `pf = 8 ms = 8,000,000 ns` gives: ``` EAT = 0.999 × 200 + 0.001 × 8,000,000 ≈ 200 + 8,000 = 8,200 ns ``` a 41× slowdown relative to no faulting at all. This single calculation is the quantitative heart of demand paging: it explains why operating systems fight so hard to keep the fault rate low (good Page Replacement Algorithms, sufficient physical memory, locality-aware prefetching) — because the fault penalty is so many orders of magnitude larger than a hit that even fractions of a percent of faulting references dominate overall performance.
Correctness argument. The mechanism is correct if two properties hold: 1. Transparency: after fault handling, the program's observable semantics are identical to a hypothetical machine with infinite physical memory where the page was "always there." This follows because the fault handler only ever changes where a page's bytes live physically, never their logical content or address, and the instruction is restarted only once the page is genuinely present and valid — so no instruction ever completes with a phantom or stale operand. 2. Progress: every fault eventually resolves, because `ALLOCATE_FREE_FRAME` either finds a free frame or evicts one via a well-defined victim-selection policy, and disk/flash I/O is guaranteed to complete in bounded (if slow) time. Thus the loop of "fault → service → restart" always terminates in at most one extra fault per instruction operand, never in infinite re-faulting, provided the replacement policy never evicts a frame that the very same instruction still needs before it finishes restarting (a subtlety handled by pinning frames involved in an in-progress fault, discussed further under Page Replacement Algorithms).
Tradeoffs. Demand paging trades a memory-and-startup win for a tail-latency risk: any given reference might be catastrophically slow relative to its neighbors, and pure demand paging maximizes this risk by refusing to load anything speculatively, even a program's obviously-needed first page. Real systems soften this with hybrid strategies — prepaging a small working set, clustering nearby pages into one I/O request, or exploiting locality of reference so that after the first fault in a region, subsequent nearby references mostly hit. None of these change the underlying model; they simply try to keep `p` small.
Worked example
Trace a small process with a 4-entry page table (pages 0–3), pure demand paging, one free physical frame available at a time (to make eviction visible), `ma = 100 ns`, `pf = 10 ms`.
| Step | Reference | PTE state before | Outcome | Action taken | PTE state after |
|---|---|---|---|---|---|
| 1 | Page 0 (first instruction) | invalid | Fault | Load page 0 from executable file into frame F0 | valid → frame F0 |
| 2 | Page 0 (next instr., same page) | valid | Hit | Normal access, 100 ns | valid → frame F0 |
| 3 | Page 1 (branch target) | invalid | Fault | Load page 1 into frame F1 (2nd free frame) | valid → frame F1 |
| 4 | Page 0 | valid | Hit | Normal access | valid → frame F0 |
| 5 | Page 2 (data access) | invalid | Fault, no free frames left | Evict page 1 (victim chosen by policy), load page 2 into F1 | page1 invalid; page2 valid → F1 |
| 6 | Page 1 (loop revisits) | invalid (just evicted!) | Fault again | Evict page 2 or page 0, reload page 1 | ... |
Even in this tiny trace, steps 5–6 exhibit thrashing-in-miniature: with too few frames, pages are evicted just before they are needed again, causing repeat faults on data that was already loaded once. This foreshadows exactly the problem that Page Replacement Algorithms exist to minimize — the eviction choice in step 5 determined whether step 6 was a hit or a fault. Now compute the running effective access time over these six references. Faults occurred at steps 1, 3, 5, 6 (4 faults out of 6 references); hits at steps 2, 4 (2 hits): ``` total time = 4 × 10 ms + 2 × 100 ns = 40,000,000 ns + 200 ns ≈ 40,000,200 ns EAT (average per reference) = 40,000,200 / 6 ≈ 6,666,700 ns ≈ 6.67 ms ``` Compare this to a hypothetical fully-resident process with `p = 0`: average access time would be a flat `100 ns`. The observed slowdown factor here is roughly 66,667× — an extreme number precisely because the trace is dominated by cold-start faults and a too-small frame budget, illustrating why real fault rates must be kept far below what this toy example shows for demand paging to pay off in practice.
Common pitfalls & traps
| Pitfall | Why it happens | Consequence |
|---|---|---|
| Confusing a page fault with a segmentation fault | Both are traps from a "bad" memory access | A legitimate lazy-load fault (backing location exists) must be distinguished from an access to an address never allocated at all (`pte.backing_location == NONE`); conflating them crashes valid programs or, worse, silently ignores real errors |
| Forgetting to restart the whole instruction | Assuming execution can resume mid-instruction | Partial side effects from before the fault can corrupt state unless the ISA guarantees safe restart; naive handlers that "resume" rather than "restart" break multi-operand instructions |
| Treating `p` as negligible without measuring it | `p` looks small in isolation (e.g., 0.1%) | Because `pf ≫ ma` by ~10^6, even small `p` dominates EAT; underestimating fault rate leads to wildly wrong performance predictions |
| Evicting a frame that the current fault itself needs | Victim selection runs concurrently with fault service | Can cause an infinite fault loop (thrashing on a single instruction) if the frame just brought in is immediately chosen as a future victim before use — frames involved in an active fault must be pinned |
| Ignoring TLB invalidation after remapping a PTE | Focusing only on the page table, forgetting cached translations | A stale TLB entry can point to an old, now-reused frame, causing a subtle and hard-to-reproduce data-corruption bug |
Pioneers & history
Demand paging emerged from 1960s research into giving programs the illusion of memory far larger than physical RAM, work inseparable from the broader invention of virtual memory itself.
Origins · 1 minFritz-Rudolf Güntsch and how this was discovered
Güntsch's 1957 doctoral work proposed automatic loading of program segments from slower "background" storage into a faster store, laying an early conceptual foundation for what would become paging-based virtual memory.
Kilburn led the Atlas project (1962), whose one-level store was the first working demand-paged virtual memory system, automatically fetching pages from drum storage into core memory on reference and evicting them when needed.
Denning formalized the working set model in 1968, giving a rigorous vocabulary for reasoning about which pages a process needs resident to avoid thrashing — the theoretical backbone behind modern Page Replacement Algorithms.
Where this matters
Every general-purpose kernel — Linux, the Windows NT family, macOS/XNU, FreeBSD — uses demand paging as the default mechanism for loading executables and libraries: `exec()` maps a binary's segments lazily rather than reading the whole file at launch, which is why large programs still start quickly. Container runtimes and serverless platforms rely on the same laziness to make cold starts of large images tractable, deferring the cost of touching most of a container's filesystem image until code paths actually execute. Virtual machine hypervisors apply an analogous idea one layer down, demand-paging guest physical memory from host storage. Copy-on-write fork() is a direct descendant of the valid-bit idea: child and parent share pages marked read-only/valid until a write fault triggers an actual copy. And Memory-Mapped Files generalize demand paging so that ordinary file I/O — reading a multi-gigabyte database file — becomes "access the address, let a page fault bring in the 4 KB block you actually touched," unifying file access and memory access under one fault-driven abstraction, with Page Replacement Algorithms deciding what to evict when physical memory finally fills up.
Ask the tutor: How does the choice of victim frame during a page fault affect whether the next fault happens sooner or later?
Is demand paging the same thing as swapping?
No, though they're related. Swapping (in the classical sense) moves an entire process's memory image out to disk and back as a unit, usually for medium-term scheduling decisions. Demand paging operates at the granularity of individual pages and is driven by actual references rather than scheduler decisions. Modern systems mostly use page-granularity swapping — evicting individual pages under memory pressure — which is really demand paging's eviction side, formalized further in Page Replacement Algorithms. The term "swap space" persists as the name for the backing store demand paging uses, even though whole-process swapping is largely historical.
Does demand paging make every memory access slower?
Only probabilistically, and the slowdown is concentrated in rare, expensive events rather than spread evenly. Most references, after a brief warm-up period, hit valid pages and cost the same as an access under any other memory model — nanoseconds, unaffected by demand paging's existence. The overall effective access time model shows that even a very small fault probability contributes a large expected cost, because a single fault is worth roughly a million ordinary accesses in time. So the average is affected, but individual hits are not slowed down at all.
What happens if a fault occurs on a page that genuinely does not belong to the process?
The page-fault handler checks whether the faulting virtual address maps to any valid backing-store location for that process at all. If it does not — the address falls outside every mapped region — the kernel raises a protection violation, typically delivered to the process as a segmentation fault signal (e.g., SIGSEGV on Unix-like systems), rather than servicing it as a lazy load. Distinguishing "not yet loaded but legitimate" from "never valid" is essential; conflating them would let a program silently succeed at accessing memory it was never entitled to touch.
Why is the page-fault service time so much larger than a memory access?
Because it typically involves mechanical or I/O-bound operations far slower than electronic memory access: locating the page on backing store, possibly evicting another page (which may itself require writing dirty data back to disk), issuing and waiting for a disk or flash read, and a context switch to let another process run in the meantime. Even fast NVMe storage measured in tens of microseconds is roughly a thousand times slower than DRAM access measured in nanoseconds, and traditional spinning disks push that ratio into the millions, which is why the effective access time formula is so sensitive to the fault probability `p`.
How does demand paging interact with the TLB?
The TLB caches recent virtual-to-physical translations to avoid repeated page table walks, as covered under Translation Lookaside Buffer. When a page fault is serviced and a PTE transitions from invalid to valid with a new frame, any stale TLB state for that page must be invalidated (or simply absent, since an invalid PTE would never have produced a cached valid translation). After the instruction restarts, the translation hardware performs a normal TLB lookup, misses, walks the now-valid page table entry, and caches the fresh translation — so subsequent nearby accesses benefit from both the resident page and a warm TLB entry.
Can demand paging cause thrashing?
Yes, if the number of frames available to a process (or to the whole system) is too small relative to its active working set. Pages get evicted just before they're needed again, so the process spends most of its time faulting rather than computing — visible in the worked example above, where a two-frame budget caused a fault-eviction-fault cycle. This pathology is the direct motivation for the working-set model and for the careful victim-selection strategies studied under Page Replacement Algorithms; demand paging itself is not the cause, insufficient frame allocation is.
Why does the operating system block the faulting process instead of busy-waiting?
Because the I/O operation to fetch the page takes milliseconds — an eternity in CPU cycles — blocking lets the scheduler run another ready process on the CPU during that time, which is exactly the kind of overlap that keeps a multiprogrammed system's CPU utilization high. Busy-waiting would burn the CPU pointlessly for the entire fault-service duration, which at ~10 ms could be tens of millions of wasted instruction cycles. Blocking and switching context is therefore not an incidental detail but essential to demand paging's practical performance.