---
title: Page Tables and Page Faults
module: Virtual Memory
moduleNumber: 7
lessonNumber: 2
order: 702
summary: >
  The page table is an array of page-table entries indexed by virtual page
  number; each entry's valid bit says whether the page is in DRAM, on disk, or
  unallocated, and its permission, reference, and dirty bits drive protection
  and replacement. We walk translation as a table lookup, the page fault and
  demand paging, the clock algorithm the OS uses to approximate LRU, memory
  mapping and copy-on-write (why fork is cheap), the taxonomy of bad
  references, and thrashing.
topics: [Virtual Memory]
sources:
  - book: Bryant & O'Hallaron
    ref: "CS:APP — §9 Virtual Memory"
  - book: Bistriceanu
    ref: "Computer Architecture Notes — §10 Virtual Memory"
---

The previous lesson reduced [address translation](/computer-architecture/virtual-memory/address-spaces-and-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:

$$
\text{PTE}_{\text{addr}} = \text{PTBR} + s \cdot \text{VPN}, \qquad
s = 8\ \text{on x86-64}.
$$

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

> **Definition (Page table / PTE).** A **page table** is a per-process array,
> indexed by virtual page number, whose elements are **page-table entries**. Each
> **PTE** carries at least a **valid bit**, and, when the page is resident, the
> **physical page number** of the frame holding it, plus permission and status
> bits.

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).

$$
% caption: The valid bit encodes three states, not two. valid = 1 means the page
% caption: is in DRAM and the PTE holds a PPN. valid = 0 with a disk address means
% caption: allocated but paged out (a reference faults). valid = 0 with no address
% caption: means unallocated (a reference is a protection fault).
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  vb/.style={draw, minimum width=10mm, minimum height=8mm, inner sep=2pt},
  ct/.style={draw, minimum width=32mm, minimum height=8mm, inner sep=2pt, anchor=west}]
  \definecolor{acc}{HTML}{2348F2}
  \node[vb, fill=acc!8] (r1) at (-1.6,1.4)  {v=1};
  \node[ct, fill=acc!8] at (r1.east) {PPN};
  \node[vb] (r2) at (-1.6,0.0)  {v=0};
  \node[ct] at (r2.east) {disk address};
  \node[vb] (r3) at (-1.6,-1.4) {v=0};
  \node[ct] at (r3.east) {none};
  \node[anchor=west] at (2.6,1.4)  {in DRAM (resident)};
  \node[anchor=west] at (2.6,0.0)  {on disk (faults in)};
  \node[anchor=west] at (2.6,-1.4) {unallo\/cated (bug)};
\end{tikzpicture}
$$

## 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:

$$
% caption: The fields of an x86-64 page-table entry (simplified; bit positions
% caption: above). P is the valid bit; R/W, U/S, and NX are permissions checked on
% caption: every access; A and D are set by hardware and read by the OS, which is
% caption: the entire interface the replacement policy is built on.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  f/.style={draw, minimum height=8mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[f, minimum width=10mm] (nx) at (0,0) {\texttt{NX}};
  \node[f, minimum width=28mm, fill=acc!8, anchor=west] (ppn) at (nx.east) {\texttt{PPN}};
  \node[f, minimum width=7mm, anchor=west] (d) at (ppn.east) {\texttt{D}};
  \node[f, minimum width=7mm, anchor=west] (a) at (d.east) {\texttt{A}};
  \node[f, minimum width=10mm, anchor=west] (us) at (a.east) {\texttt{U/S}};
  \node[f, minimum width=10mm, anchor=west] (rw) at (us.east) {\texttt{R/W}};
  \node[f, minimum width=7mm, anchor=west] (p) at (rw.east) {\texttt{P}};
  \node[anchor=south, font=\scriptsize] at (nx.north) {63};
  \node[anchor=south, font=\scriptsize] at (ppn.north) {51 : 12};
  \node[anchor=south, font=\scriptsize] at (d.north) {6};
  \node[anchor=south, font=\scriptsize] at (a.north) {5};
  \node[anchor=south, font=\scriptsize] at (us.north) {2};
  \node[anchor=south, font=\scriptsize] at (rw.north) {1};
  \node[anchor=south, font=\scriptsize] at (p.north) {0};
  \node[anchor=west, font=\scriptsize] at (-0.5,-0.8)
    {\texttt{P = present (valid)}};
  \node[anchor=west, font=\scriptsize] at (4.0,-0.8)
    {\texttt{R/W = writable?}};
  \node[anchor=west, font=\scriptsize] at (-0.5,-1.25)
    {\texttt{U/S = user or kernel}};
  \node[anchor=west, font=\scriptsize] at (4.0,-1.25)
    {\texttt{A = accessed (ref bit)}};
  \node[anchor=west, font=\scriptsize] at (-0.5,-1.7)
    {\texttt{D = dirty (written?)}};
  \node[anchor=west, font=\scriptsize] at (4.0,-1.7)
    {\texttt{NX = no-execute}};
  \node[anchor=west, font=\scriptsize] at (-0.5,-2.15)
    {\texttt{PPN = physical page number of the frame}};
\end{tikzpicture}
$$

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.

| Field | Bit | Written by | Read by | Meaning |
| --- | --- | --- | --- | --- |
| P | 0 | OS | HW | present (valid); 0 raises a fault |
| R/W | 1 | OS | HW | writable if 1, read-only if 0 |
| U/S | 2 | OS | HW | user-accessible if 1, kernel-only if 0 |
| A | 5 | HW | OS | accessed (reference bit) |
| D | 6 | HW | OS | dirty (written since last clear) |
| NX | 63 | OS | HW | no-execute: fetch faults if 1 |
| PPN | 51:12 | OS | HW | physical page number of the frame |

**NX** forbids instruction fetch, turning a classic class of injected-code attacks
into immediate faults (see
[buffer overflows](/computer-architecture/machine-level-x86-64/memory-layout-and-buffer-overflows));
**U/S** restricts a page to
[kernel mode](/computer-architecture/exceptions-and-io/interrupts-and-the-kernel).
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:

$$
\text{VPN} = \lfloor \text{VA} / P \rfloor, \quad
\text{offset} = \text{VA} \bmod P, \qquad
\text{PA} = \text{PPN} \cdot P + \text{offset}.
$$

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

$$
% caption: A page-table lookup. The VPN indexes the page table; the selected PTE
% caption: is valid and supplies a PPN; the PPN concatenated with the unchanged
% caption: page offset forms the physical address. The base register locates the
% caption: current process's table.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % virtual address split (top left)
  \node[draw, fill=acc!8, minimum width=24mm, minimum height=7mm, inner sep=0pt]
    (vpn) at (0,3.0) {VPN};
  \node[draw, minimum width=18mm, minimum height=7mm, inner sep=0pt, anchor=west]
    (vpo) at (vpn.east) {of\/fset};
  \node[anchor=east] at (vpn.west) {VA};
  % page table: column of PTEs (valid box + contents box per row)
  \foreach \i/\y/\vb in {0/1.6/1, 1/0.8/0, 2/0.0/1, 3/-0.8/1} {
    \ifnum\i=2
      \node[draw, fill=acc!8, minimum width=9mm, minimum height=7mm, inner sep=1pt]
        (pte\i) at (-0.7,\y) {v=\vb};
      \node[draw, fill=acc!8, minimum width=21mm, minimum height=7mm, inner sep=1pt,
        anchor=west] (cnt\i) at (pte\i.east) {PPN};
    \else
      \node[draw, minimum width=9mm, minimum height=7mm, inner sep=1pt]
        (pte\i) at (-0.7,\y) {v=\vb};
      \node[draw, minimum width=21mm, minimum height=7mm, inner sep=1pt,
        anchor=west] (cnt\i) at (pte\i.east) {...};
    \fi
  }
  \node[anchor=south] at (0.9,2.05) {page table};
  % VPN indexes the table (selects pte2)
  \draw[->,acc] (vpn.south) -- (vpn.south |- 0,2.35) -| (-1.7,0.0) -- (pte2.west);
  \node[anchor=east] at (-1.8,0.8) {index};
  % PTE -> PPN f\/ield of physical address
  \node[draw, fill=acc!8, minimum width=24mm, minimum height=7mm, inner sep=0pt]
    (ppn) at (5.8,-2.4) {PPN};
  \node[draw, minimum width=18mm, minimum height=7mm, inner sep=0pt, anchor=west]
    (ppo) at (ppn.east) {of\/fset};
  \node[anchor=east] at (ppn.west) {PA};
  \draw[->] (cnt2.east) -| (ppn.north);
  % of\/fset copied around and down, unchanged
  \draw[->,acc,thick] (vpo.south) -- (vpo.south |- 0,2.3) -- (7.9,2.3) -- (ppo.north)
    node[pos=0.75,right,xshift=1mm] {unchanged};
\end{tikzpicture}
$$

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](/computer-architecture/virtual-memory/the-tlb-and-multi-level-page-tables)).
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](/computer-architecture/exceptions-and-io/exceptional-control-flow), 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.

```algorithm
procedure HandlePageFault(va):
    vpn := va / PAGE_SIZE
    if PTE[vpn].disk_addr = none then       // unallocated: not a page fault
        deliver SIGSEGV; return
    frame := FreeFrame()
    if frame = none then                    // no free frame: evict a victim
        victim := ClockSelectVictim()
        if PTE[victim].D = 1 then           // dirty: write back first
            WriteToDisk(victim)
        PTE[victim].P := 0
        frame := FrameOf(victim)
    ReadFromDisk(PTE[vpn].disk_addr, frame)
    PTE[vpn].PPN := frame
    PTE[vpn].P := 1                          // now valid = 1
    restart faulting instruction             // this time it hits
```

$$
% caption: Handling a page fault. (1) The MMU reads a PTE with valid = 0 and
% caption: raises a fault. (2) The OS handler picks and evicts a victim page,
% caption: writing it back if dirty. (3) It reads the wanted page from disk into
% caption: the frame. (4) It sets the PTE valid with the new PPN and returns; the
% caption: CPU restarts the instruction, which now hits.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  box/.style={draw, minimum width=21mm, minimum height=11mm, inner sep=3pt, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (cpu) at (0,0) {CPU /\\MMU};
  \node[box, fill=acc!8] (os) at (3.8,0) {OS page-fault\\handler};
  \node[box] (disk) at (7.8,0) {disk\\(swap)};
  % 1: fault
  \draw[->] (cpu.east) -- (os.west)
    node[midway,above] {(1) fault};
  % 2: evict victim (loop on os, drawn above)
  \draw[->] (os.north) .. controls +(0,0.9) and +(0,0.9) .. (os.north east)
    node[midway,above] {(2) evict victim};
  % 3: load page from disk
  \draw[->] (os.east) -- (disk.west)
    node[midway,above] {(3) read page};
  % 4: update PTE + return, restart
  \draw[->] (os.south) |- ($(cpu.south)+(0,-0.95)$) -- (cpu.south);
  \node[anchor=north] at (1.9,-1.58) {(4) up\/date PTE, return, restart};
\end{tikzpicture}
$$

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

$$
\text{EAT} = (1-p)\,T_{\text{DRAM}} + p\,T_{\text{fault}}.
$$

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](/computer-architecture/memory-hierarchy/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.

$$
% caption: The clock algorithm. Resident frames form a fixed circle; the hand
% caption: advances, clearing reference bits as it passes (r = 1 becomes 0, the
% caption: page survives one more lap) until it lands on a frame with r = 0,
% caption: which becomes the victim. Pages touched since the last sweep are never
% caption: evicted: a one-bit approximation of LRU.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  fr/.style={draw, minimum height=7mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  % frames on a circle (clockwise from top)
  \node[fr, minimum width=11mm] (n135) at (-1.63,1.63) {\texttt{r=1}};
  \node[fr, minimum width=14mm] (n90)  at (0,2.3)      {\texttt{r=1}$\to$\texttt{0}};
  \node[fr, minimum width=14mm] (n45)  at (1.63,1.63)  {\texttt{r=1}$\to$\texttt{0}};
  \node[fr, minimum width=11mm, draw=acc, thick, fill=acc!8] (n0) at (2.3,0) {\texttt{r=0}};
  \node[fr, minimum width=11mm] (n315) at (1.63,-1.63) {\texttt{r=1}};
  \node[fr, minimum width=11mm] (n270) at (0,-2.3)     {\texttt{r=0}};
  \node[fr, minimum width=11mm] (n225) at (-1.63,-1.63){\texttt{r=1}};
  \node[fr, minimum width=11mm] (n180) at (-2.3,0)     {\texttt{r=0}};
  % hand pointing at the victim
  \fill (0,0) circle (1.2pt);
  \draw[->,acc,thick] (0,0) -- (1.6,0);
  \node[font=\scriptsize, anchor=north] at (0.75,-0.12) {hand};
  % sweep direction (outside arc, top)
  \draw[->,black] (120:3.35) arc (120:30:3.35);
  \node[font=\scriptsize, black] at (75:3.6) {sweep};
  % victim label
  \node[anchor=west, font=\scriptsize] at (3.05,0) {victim};
\end{tikzpicture}
$$

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`:

```c [mmap.c]
#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.

$$
% caption: Copy-on-write. After fork, parent and child page tables point at the
% caption: same frame, marked read-only. When the child writes, the protection
% caption: fault handler copies just that frame, remaps the child's PTE to the
% caption: writable copy, and restarts the store. Pages never written are never
% caption: copied.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  bx/.style={draw, minimum width=18mm, minimum height=9mm, inner sep=2pt, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  % left: after fork
  \node[anchor=south] at (1.6,1.7) {after \texttt{fork()}};
  \node[bx] (ppte) at (0,0.8) {parent PTE};
  \node[bx] (cpte) at (0,-0.8) {child PTE};
  \node[bx] (fa) at (3.4,0) {frame A\\(read-only)};
  \draw[->] (ppte.east) -- ([yshift=2mm]fa.west);
  \draw[->] (cpte.east) -- ([yshift=-2mm]fa.west);
  % separator
  \draw[dashed, black] (5.1,-1.7) -- (5.1,2.2);
  % right: after the child writes
  \node[anchor=south] at (8.4,1.7) {after the child writes};
  \node[bx] (ppte2) at (6.8,0.8) {parent PTE};
  \node[bx] (cpte2) at (6.8,-0.8) {child PTE};
  \node[bx] (fa2) at (10.2,0.8) {frame A};
  \node[bx, draw=acc, fill=acc!8] (fb2) at (10.2,-0.8) {frame B\\(new copy)};
  \draw[->] (ppte2.east) -- (fa2.west);
  \draw[->,acc] (cpte2.east) -- (fb2.west);
\end{tikzpicture}
$$

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:

| Fault | Condition | Handler action |
| --- | --- | --- |
| Page fault | valid = 0, page allocated | repair mapping, restart instruction |
| Protection fault | valid = 1, permission refused | COW: copy + restart; else violation |
| Segmentation fault | valid = 0, unallocated (or unrepairable) | deliver `SIGSEGV`, terminate |

- **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](/computer-architecture/exceptions-and-io/exceptional-control-flow));
  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.

> **Takeaway.** The **page table** is a per-process array of **PTEs** indexed by
> VPN. The **valid bit** distinguishes resident, on-disk, and unallocated;
> permission bits (**R/W**, **U/S**, **NX**) are checked by hardware on every
> reference; the **reference** and **dirty** bits are set by hardware and read
> by the OS. **valid = 0** on a legal access raises a **page fault**: the OS
> evicts a victim (chosen by the **clock algorithm**, a one-bit LRU
> approximation), loads the page, and **restarts the instruction**: demand
> paging, which works because working sets are small. The same machinery gives
> **memory mapping** (`mmap`, demand-paged executables) and **copy-on-write**
> (cheap `fork`); its failure mode, a working set larger than DRAM, is
> **thrashing**.

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](/computer-architecture/virtual-memory/the-tlb-and-multi-level-page-tables).