Page Faults

A page fault is a synchronous trap generated by the memory management unit (MMU) when a running program references a virtual address whose page-table entry has its valid/present bit cleared, or whose access violates the entry's protection bits (for instance, a write to a read-only page). Unlike an interrupt, which is caused by external hardware and is asynchronous to instruction execution, a page fault is a trap: it is caused directly by the instruction currently executing, arrives synchronously, and — crucially — is precise, meaning the processor guarantees the faulting instruction can be identified and later restarted cleanly. There are two broad categories of address-translation failure that a fault can represent. A minor fault occurs when the desired page actually exists in memory already — perhaps it is shared with another process, or was recently evicted but not yet reused — so the kernel merely needs to fix up the page table, no disk I/O required. A major fault occurs when the page genuinely must be read from backing store (a swap area or a file on disk), which is orders of magnitude slower. The term "page fault" without qualification usually refers to the major case, since that is where the interesting cost lies, but the distinction matters for real performance analysis. The entire scheme rests on a contract between hardware and the operating system established when The Page Table is built: each entry carries a present/valid bit. When that bit is 0, the MMU refuses translation and instead vectors control to a fault handler in the kernel, passing along the faulting virtual address (often in a dedicated register, e.g. `CR2` on x86) and an error code describing the nature of the violation (not-present vs. protection, read vs. write, user vs. supervisor). Everything that follows — allocating a frame, reading from disk, updating the table, resuming execution — is software, executed by the operating system's page-fault service routine.

The full lifecycle of a page fault spans hardware and software in six recognizable phases.

1. Address generation and translation attempt. The CPU executes an instruction that references a virtual address. The MMU walks (or consults the TLB for) the page table to translate it.

2. Trap. The MMU discovers the present bit is 0 (or a protection violation), and instead of completing the memory operation it traps: it saves the program counter and processor state needed to resume this exact instruction, switches to kernel mode, and jumps to the fault-handler entry point, passing the faulting address and fault-type code.

3. Validation. The kernel's fault handler checks whether the reference is legal. It consults the process's memory map (e.g., the list of valid virtual memory areas). If the address falls outside any region the process is permitted to touch, this is a genuine error — a segmentation violation — and the process is terminated (typically via `SIGSEGV`). Otherwise the fault is legitimate and demand paging proceeds.

4. Frame acquisition. The kernel needs a physical frame to hold the page. If a free frame exists, it is taken from the free-frame list. If none is free, a victim frame must be selected and, if dirty, written back — this is where a page-replacement policy is invoked (a topic developed in its own right elsewhere).

5. Data fetch and table update. The kernel schedules a disk (or backing-store) read to bring the required page into the chosen frame. The faulting process is blocked and the CPU is rescheduled to other work during this I/O, since it takes milliseconds. When the transfer completes, an interrupt notifies the kernel, which updates the page table entry: sets the frame number, sets the present bit, restores any other necessary state (e.g. clearing a "swapped" flag), and possibly updates the TLB.

6. Restart. The process is placed back on the ready queue; when scheduled, the exact instruction that faulted is re-executed from the beginning. This time, translation succeeds — the present bit is now 1 — and execution proceeds as if the fault never happened. ``` function handle_page_fault(fault_addr, error_code): vma = find_vma(current_process, fault_addr) if vma is None or not permission_ok(vma, error_code): deliver_signal(current_process, SIGSEGV) # illegal access return frame = get_free_frame() if frame is None: victim = select_victim_frame() # replacement policy if victim.dirty: write_back(victim) # flush to backing store invalidate_pte(victim.owner_process, victim.page_no) frame = victim.frame_no block(current_process) # yield CPU during I/O schedule_disk_read(vma.backing_store, fault_addr, frame) wait_for_io_completion() pte = page_table[current_process][page_number(fault_addr)] pte.frame_no = frame pte.present = true pte.dirty = false flush_tlb_entry(fault_addr) unblock(current_process) restart_instruction(current_process) # re-execute faulting instruction ``` The critical, easily-overlooked design detail is step 6: correctness demands that instruction restart reproduces exactly the state the CPU had before the faulting memory access began, not some partially-executed state. For simple instructions (load a register from memory) this is trivial — nothing irreversible happened before the fault. But consider an x86 instruction like `MOVS` that copies a block of memory and updates two pointers and a counter as a side effect, or an instruction with two memory operands where the second operand's page is the one missing. If the first operand's page was already written before the fault on the second operand is detected, naive restart would apply that side effect twice. Architectures handle this in one of two ways:

• Prevent the problem: before executing an instruction, the CPU (or a preceding decode/microcode step) checks that all operands it will touch are already resident, refusing to begin the instruction at all if any page is missing (used historically on some designs for exactly this reason).
• Undo the problem: the CPU records enough microarchitectural state (saved registers, a shadow copy of altered values) to reverse partial side effects before repeating the instruction from scratch. Modern x86 processors take this general approach, which is one reason instructions like `REP MOVS` are more complex to implement precisely than a load or a store.

Either way, the OS-visible contract is simple and must hold: the instruction stream, from the process's point of view, behaves as though the fault took zero time and never disturbed any state — this is what makes the page-fault mechanism transparent.

Time cost of a single fault. A minor fault (page already in memory, just not mapped for this process) costs roughly a TLB shootdown plus a few page-table updates: microseconds. A major fault requires a disk seek and transfer, dominated by mechanical or flash latency: typically 1–10 milliseconds for spinning disks, tens of microseconds for SSDs — still 10³–10⁵ times slower than a DRAM access (roughly 100 nanoseconds). This asymmetry is the entire reason page-fault rate matters so much, and it is quantified precisely below.

Space cost. No extra asymptotic memory is required beyond what demand paging already uses: one present bit per page-table entry (already present in The Page Table format) and O(1) bookkeeping per fault (which frame, which victim). The kernel-side data structures involved (free-frame lists, per-process VMAs) are the same ones demand paging needs regardless of fault frequency.

Correctness argument. The precise-trap contract is what makes the whole edifice sound. Define the observable process state as the tuple of (register file, memory contents, program counter) visible to the user program at instruction boundaries. The correctness invariant is: > For any instruction `I` that triggers a page fault, the state observed immediately before `I` completes (after the fault is serviced and `I` is restarted) must be identical to the state that would have existed had `I` executed successfully on the first attempt, with no partial side effects from the aborted attempt persisting. This invariant holds because: 1. The MMU detects the missing translation before any store to memory or any architecturally-visible register write is committed (or, if partial writes occurred, the hardware undoes them before restart) — call this the no-partial-commit property. 2. The trap handler is guaranteed to preserve the entire register file and program counter of the interrupted process (standard trap/interrupt save-state discipline, the same mechanism used for any interrupt). 3. Page-table updates performed during service (steps 4–5 above) only ever change entries from invalid to valid for the process's own address space; they never alter any already-valid mapping the instruction had already used before faulting, so subsequent re-execution behaves identically to the never-faulted case for any operands already resolved. 4. Since the OS suspends only the faulting process (not the CPU itself) during the I/O wait, other processes continue running — a scheduling/throughput property, not a correctness one, but essential for why the enormous latency of a major fault does not stall the whole system. Given (1)–(3), re-executing `I` from scratch after the page is made present is behaviorally indistinguishable from an alternate universe in which the page had been resident all along — which is precisely the illusion demand paging promises the programmer.

Tradeoffs. The mechanism buys enormous flexibility (processes can vastly overcommit physical memory, programs need not be fully loaded before running, memory-mapped files become possible) at the cost of unpredictable, sometimes very large, per-access latency and a nontrivial hardware requirement (precise traps, undoable or checked instructions). Real-time systems often avoid or bound this unpredictability by locking critical pages in memory (`mlock`), trading flexibility back for predictability.

Setup. Suppose the memory-access time is `ma = 100 ns`, and the page-fault service time (dominated by disk I/O) is `pf = 8 ms = 8,000,000 ns`. Define the effective access time (EAT): ``` EAT = (1 − p) × ma + p × pf ``` where `p` is the probability that any given memory reference faults.

Reading the table. With `p = 10⁻⁶` — one fault per million references, seemingly negligible — the system already runs 8% slower than a fault-free machine. At `p = 10⁻³`, a rate that sounds "small" in casual conversation, the effective access time balloons by 81×. This nonlinearity is exactly why operating-system courses hammer the point: because `pf ≫ ma` by four to five orders of magnitude, even tiny fault probabilities dominate the average.

Turning the formula around: budgeting a target slowdown. Suppose we want at most a 10% slowdown, i.e. `EAT ≤ 1.10 × ma = 110 ns`. Solve for `p`: ``` 110 = (1 − p)(100) + p(8,000,000) 110 = 100 − 100p + 8,000,000p 10 = 7,999,900 p p ≈ 1.25 × 10⁻⁶ ``` So to keep the slowdown under 10%, fewer than roughly 1 in 800,000 memory references may fault — a concrete, derivable target that explains why systems invest heavily in large physical memory, good Page Replacement Algorithms, and prefetching: the acceptable fault rate is astonishingly small given the disk/memory speed gap.

A second case — faster backing store. Repeat with an SSD-backed swap area, `pf = 60 µs = 60,000 ns` instead of 8 ms: ``` EAT(p=10⁻³) = (0.999)(100) + (0.001)(60,000) ≈ 99.9 + 60 ≈ 159.9 ns (≈1.6× slowdown, versus 81× on spinning disk) ``` This demonstrates concretely why SSD-backed swap and NVMe storage dramatically change the economics of paging: the same fault rate that was catastrophic against a hard disk becomes merely noticeable against flash, because the gap between `ma` and `pf` shrank by over two orders of magnitude.

The page fault as a formal mechanism emerged from the same lineage that produced virtual memory and paging itself — the effort, beginning in the late 1950s, to let programs run without being bound by the size of physical memory.

Every general-purpose operating system — Linux, Windows, macOS, the BSDs — relies on page faults as the trigger for demand paging, copy-on-write process creation (`fork` maps parent and child to the same read-only pages, faulting only on the first write), and memory-mapped file I/O via `mmap`, where reading a file becomes indistinguishable from touching memory. Language runtimes exploit the same mechanism for generational garbage collectors (write-protected pages fault to detect mutation) and for guard pages that catch stack overflows. Hypervisors use nested/second-level page faults to implement memory overcommitment across virtual machines, and container runtimes rely on the same primitive for lazy image loading. Database systems that memory-map large files depend on predictable fault-service latency, which is precisely why understanding the effective-access-time tradeoff — and the deeper questions of which page to evict, covered under Page Replacement Algorithms — is central to performance engineering, not just OS theory.

Ask the tutor: How does the choice of page-replacement algorithm change the fault rate `p`, and therefore the effective access time?