Page Tables and Page Faults

The previous lesson reduced address translation to one question: given a virtual page number, what physical page number — if any — holds it? The answer lives in a per-process data structure the MMU reads on every access, the page table. This lesson defines that table and the fields inside its entries, runs a translation through it, and then handles the case the valid bit warns about: the page the program wants is not in memory at all, and the hardware must trap to the operating system. That event, the page fault, is what lets a virtual space be larger than RAM. And the same machinery, pushed a little further, is what makes fork cheap, loads executables lazily, and turns file I/O into memory access.

The page table is an array indexed by VPN

A page table is an array of page-table entries (PTEs), one per virtual page, indexed by the virtual page number. There is no searching: the VPN is the index. Each PTE describes the state of one page.

The kernel keeps a separate page table for each process, and a hardware register (the page-table base register, PTBR) points at the current process's table. With PTE size $s$ bytes, the MMU forms the entry address by scaling the VPN and adding the base:

Switching processes reloads PTBR with a different table, which is how the entire address space changes identity in a single register write.

The valid bit is the most important field, and it encodes three distinct situations, not two:

• valid = 1: the page is in DRAM, and the PTE's remaining bits give the PPN of its frame. Translation succeeds entirely in hardware.
• valid = 0, but a disk address is recorded: the page is allocated but on disk (swapped out, or never yet faulted in). Touching it must trap to the OS.
• valid = 0, no disk address: the page is unallocated: not part of the process's space at all. Touching it is a genuine bug (a wild pointer).

Anatomy of a PTE

Beyond the valid bit and the PPN, a real PTE packs a handful of one-bit fields that the rest of this lesson turns on. The x86-64 entry is 8 bytes; the fields that matter here, with their actual bit positions:

The fields divide by who writes them: the OS writes permissions and the hardware checks them; the hardware writes status and the OS reads them.

NX forbids instruction fetch, turning a classic class of injected-code attacks into immediate faults (see buffer overflows); U/S restricts a page to kernel mode. The MMU checks R/W, U/S, and NX on every reference, before the access completes. The A and D bits are the entire one-bit-wide interface the OS gets from hardware to drive replacement, a point the clock algorithm below turns into policy.

Translation as a table lookup

When the page is resident the whole translation is a single array read followed by a concatenation. The MMU indexes the table by the VPN, reads the PTE, checks that valid = 1 and the permissions allow the access, takes the PPN, and concatenates it with the page offset carried unchanged from the virtual address. For a page size $P=2^p$, the offset is the low $p$ bits and the VPN the rest; translation replaces the VPN with the PPN and leaves the offset fixed:

There is no arithmetic on the offset: it is the same $p$ bits, as established earlier.

If the valid bit is 1, the access proceeds and the only cost was the table read (which the next lesson makes nearly free with the TLB). If it is 0, none of this happens; the hardware raises an exception instead.

The page fault

A page fault is what the MMU does when it reads a PTE with valid = 0 on a legal access: it cannot supply a PPN, so it triggers an exception that transfers control to the operating system's page-fault handler. This is a recoverable fault, not a crash: the handler fixes the situation and the faulting instruction runs again.

The handler's job is a fixed sequence. It chooses a victim page currently in DRAM, writes it back to disk if it was modified, reads the wanted page from disk into the freed frame, updates the page table, and returns so the instruction re-executes, this time finding valid = 1.

Two details of this sequence deserve names. The disk region that holds paged-out pages is swap space: a dedicated partition or file the kernel treats as the backing store for anonymous pages (heap, stack) that have no other home on disk. And the eviction in step 2 is where the dirty bit pays off: if the victim was never written, the copy on disk is still correct and the frame can simply be reused; only a dirty victim costs a disk write before the frame is free. The dirty bit turns always write back the victim into write back only when the hardware saw a store, halving the disk traffic for read-mostly pages.

Demand paging, and why it works

The strategy of leaving pages on disk and pulling them in only when first touched is called demand paging, and modern systems are pure demand-paging systems: nothing is loaded in advance. When a program starts, the kernel does not copy the executable into memory; it builds a page table full of valid = 0 entries pointing at the file, and jumps to the entry point. The first instruction fetch immediately faults, and the first page of code arrives. Execution proceeds by faulting in exactly the pages the run actually touches; a code path never taken, a table never indexed, an error handler never triggered costs no memory at all.

The cost of a fault is enormous — a disk read is tens of thousands of times slower than a DRAM access — and that gap is what makes this the right design. With DRAM access $T_{\text{DRAM}}$, fault probability $p$, and fault-service time $T_{\text{fault}}$, the effective access time is

Because $T_{\text{fault}}/T_{\text{DRAM}}\sim 10^5$, EAT stays near $T_{\text{DRAM}}$ only while $p$ is minuscule. Faults are rare because locality keeps a program's working set, the pages it is actively touching, small and slowly changing. After a flurry of faults brings the working set in (cold misses, in cache vocabulary), the program hits in DRAM for millions of references at a stretch. The parallel with caching is exact: DRAM is a fully-associative, write-back cache for the disk, where any page can live in any frame and the OS, not hardware, runs the replacement policy because misses are so costly that a smart software policy pays for itself.

Page replacement: the clock algorithm

Which victim should the handler pick? The cache lessons' answer, least-recently used, is the right instinct: pages untouched for the longest time are the worst bets to be touched next. But true LRU is unimplementable here. Ordering pages by recency would require bookkeeping on every memory access, and accesses are handled by the MMU with no software in the loop. The only recency information software ever receives is the reference bit: hardware sets it to 1 when the page is touched, and the OS can read it and clear it.

The standard way to turn that single bit into a policy is the clock algorithm. Keep the resident frames in a fixed circular order, with a pointer, the hand, remembering where the last search stopped. To find a victim, advance the hand:

1. If the frame under the hand has reference = 1, the page was touched since the hand last came by. Give it another lap: clear the bit to 0 and advance.
2. If the frame has reference = 0, the page has not been touched in at least one full revolution. Evict it, and leave the hand just past it for next time.

Trace it once on four frames to see the second-chance behavior. The hand sits at frame 0; the reference bits, clockwise, are [1, 1, 0, 1], and a fault needs a victim.

1. Frame 0, r = 1. Touched since last sweep; clear it to 0 and advance. Bits now [0, 1, 0, 1], hand at frame 1.
2. Frame 1, r = 1. Same: clear to 0, advance. Bits [0, 0, 0, 1], hand at frame 2.
3. Frame 2, r = 0. Untouched for a full lap — evict it. The new page loads into frame 2, and the hand parks at frame 3 for next time.

Frame 3 kept its r = 1 and was never even examined, so it survives; frames 0 and 1 spent their second chance and would be evicted next time unless touched again before the hand returns. The algorithm never had to timestamp anything: it turned one bit per frame into a workable recency order, sweeping past the recently-used and catching the idle. Had every bit been 1, the hand would clear all four on one lap and evict the first frame on the second — degrading gracefully to FIFO when nothing distinguishes the pages.

The invariant is easy to state: a page is evicted only if it went untouched for a full revolution of the hand. Recently-used pages always have their bit set again by hardware before the hand returns, so they survive; idle pages get caught with the bit still clear. It is a coarse approximation of LRU, one bit of recency instead of a full ordering, but it costs nothing on the hit path, and in a system where a fault costs ten million cycles, a rough LRU that costs nothing beats an exact LRU that needs bookkeeping on every access. Refinements use the dirty bit too, preferring clean victims (free to drop) over dirty ones (must be written back first).

Memory mapping

The page-fault machinery was built to fake a big memory, but its parts — valid = 0 entries that point at data on disk — are more general than that. Memory mapping lets a process wire a range of its virtual address space directly to an object on disk, so that paging moves data in from that file rather than from swap. The Unix interface is mmap:

#include <sys/mman.h>

/* map the first len bytes of the file behind fd, read-only, private */
void *p = mmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, 0);

After this call, p[i] reads byte i of the file. No read system call, no buffer copies: the kernel built valid = 0 PTEs whose disk addresses point into the file, and the first touch of each page faults it in. This is how executables and shared libraries are loaded: the loader is a handful of mmap calls, and demand paging does the actual work. A mapping can be shared (stores go back to the file and are visible to other processes mapping the same object, which is how processes genuinely share memory) or private, which promises the file is not modified and any writes stay local to the process. Private mappings are implemented with copy-on-write, the subject of the next section.

fork and copy-on-write

When a process calls fork, the child is defined to get a copy of the parent's entire address space. Taken literally that would be expensive: a process using 1 GB would need 1 GB copied (a quarter of a million page copies) before the child executes one instruction, and the overwhelmingly common pattern is that the child immediately discards the copy by calling exec.

Copy-on-write (COW) makes the copy lazy. At fork time the kernel copies only the page table, so parent and child PTEs point at the same physical frames. Both copies of every writable PTE are then marked read-only, with a private flag noting the page is really copy-on-write. Reads proceed freely; both processes reading the same frame is harmless. The first time either process writes a shared page, the MMU raises a protection fault; the handler sees the COW flag, copies that one frame, points the writer's PTE at the new copy with write permission restored, and restarts the store.

Run the worked example: a 1 GB parent forks, and the child execs after touching 30 pages. Eager copying moves $2^{18}$ pages; COW copies the page table (a few hundred KB of entries), takes 30 protection faults, and copies 30 frames: about 120 KB of actual data movement, a factor of several thousand saved. The same mechanism backs MAP_PRIVATE mappings: every process privately mapping the C library shares one physical copy of its data segment until the moment, if ever, it writes to it.

Three kinds of bad reference

The MMU now performs two checks on every access — is the page valid, and do the permission bits allow this use? — and it pays to keep the outcomes straight, because they look similar from a distance and are handled completely differently. The valid bit and permission check together classify the fault:

• Page fault is normal operation, not an error: the OS repairs the mapping and restarts; the program never observes it.
• Protection fault means the page is present but the access is illegal — a store to read-only code, a fetch from an NX stack, a user-mode touch of a supervisor page. The one exception is copy-on-write, where the illegal store is expected and repaired; every other protection fault is a genuine violation.
• Segmentation fault names memory the process does not have. The handler finds no disk address and no COW flag, concludes it is a bug, and delivers SIGSEGV (a signal — module 8's subject); the default action terminates the process.

All three arrive through the same exception path; what differs is what the handler finds when it inspects the faulting address against the process's memory map. The check costs nothing extra either way: the PTE is being read for translation anyway, so protection is enforced on every single memory access for free.

Thrashing

Demand paging has a failure mode. All the good behavior above rested on one assumption: the working set fits in physical memory. When it does not — one process with a giant active footprint, or too many processes competing for the same frames — every fault's victim is a page that will be needed again in a moment. Pages are evicted and re-fetched in a continuous churn, the disk saturates, and the CPU sits mostly idle waiting on page I/O. This is thrashing, and it appears as a cliff rather than a slope: a workload touching $n$ pages runs at full speed while $n$ fits in DRAM and collapses by orders of magnitude once it does not, because the miss rate jumps from near-zero to near-one. The remedies are blunt (run fewer things at once, or buy more memory), and operating systems mostly aim to detect the state and shed load rather than to perform well inside it.

Replacement theory and the working set

The clock algorithm is a practical compromise, and the theory behind what it approximates is worth naming.

The benchmark is Belady's optimal algorithm (Belady, 1966, IBM Systems Journal): evict the page whose next use is furthest in the future. It is unimplementable — it requires knowing the future — but it is computable offline from a trace, so it serves as the yardstick every real policy is measured against, and it is why LRU (which bets the recent past predicts the near future) is a reasonable heuristic. Belady's name attaches to a second surprise, Belady's anomaly: for FIFO replacement, giving a program more frames can produce more faults, a non-monotonicity that LRU and clock-like stack algorithms provably avoid.

The concept that explains why demand paging works at all is Peter Denning's working set (Denning, 1968, CACM): $W(t,\tau )$ is the set of pages referenced in the window $[t-\tau ,t]$. Denning's thesis was that faults stay rare while each resident working set is held; when the working sets contend for too few frames — when ${\sum }_i|W_i|>M$ for $M$ physical frames — the system thrashes, the failure mode named at the end of this lesson. Modern kernels do not run pure clock; Linux uses a two-list refinement (active and inactive LRU lists, pages promoted on a second reference) that resists the classic failure of one-handed clock, where a single large streaming scan touches every page once and flushes the whole cache. Copy-on-write and demand paging, meanwhile, are so foundational that they define the shape of process creation in Unix: the fork/exec pair (Ritchie and Thompson, The UNIX Time-Sharing System, 1974, CACM) is cheap because of the COW trick this lesson built, and mmap made the page-fault machinery a general file-access mechanism rather than only a swap mechanism.

A table lookup on every access would double memory traffic, and a single flat table for a 64-bit space would be impossibly large. Both problems are solved at once by the TLB and multi-level page tables.