DEMAND PAGING: bring a page into memory only when it is REFERENCED, never in advance. · a page-table entry has a VALID/INVALID bit · valid → the page is in memory, translate normally · invalid → either the address is illegal, OR the page is on disk and not yet loaded The MMU cannot tell those two cases apart, so it traps to the OS, which consults its own records. THE PAGE-FAULT SEQUENCE — six steps, and it is examined: 1. the MMU finds valid = 0 → TRAP to the OS 2. the OS checks: is this a legal address for this process? NO → SIGSEGV, terminate the process YES → continue 3. find a FREE FRAME (or evict one — see page replacement) 4. schedule a disk read of the page into that frame 5. update the page table: frame number, valid = 1 6. RESTART the faulting instruction Step 6 is subtle: the instruction is re-executed from the beginning, not resumed. That requires the CPU to be able to restart any instruction cleanly, which constrains instruction set design — a block-move instruction that has already copied half its bytes must be restartable or the fault is unrecoverable. MINOR vs MAJOR FAULTS — the distinction that matters in practice: MINOR (soft) fault the page is in memory already but not mapped in THIS page table — a shared library another process loaded, or a zero-fill-on-demand page. No disk I/O. Cost: microseconds. MAJOR (hard) fault the page must be read from disk. Cost: milliseconds on a spinning disk, ~100 µs on SSD. A high MINOR fault count is normal. A high MAJOR fault count means thrashing.

/* Verified on Darwin arm64, 16 KB pages. Allocate 64 MB, then
   touch one byte in every page and count the faults. */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/resource.h>
#include <time.h>

static void faults(const char *tag) {
    struct rusage r; getrusage(RUSAGE_SELF, &r);
    printf("  %-28s minor=%-8ld major=%ld\n",
           tag, r.ru_minflt, r.ru_majflt);
}
#define MB 64
int main(void) {
    long n = (long)MB*1024*1024;
    faults("at start");
    volatile char *p = malloc(n);       /* ALLOCATE only */
    faults("after malloc (untouched)");
    for (long i = 0; i < n; i += getpagesize()) p[i] = 1;
    faults("after touching every page");
    for (long i = 0; i < n; i += getpagesize()) p[i] = 2;
    faults("after SECOND pass");
    return 0;
}
MEASURED OUTPUT:
  at start                     minor=284      major=1
  after malloc (untouched)     minor=286      major=1
  after touching every page    minor=4382     major=1
  first touch of 64 MB: 8.7 ms
  after SECOND pass            minor=4382     major=1
  second pass:          5.2 ms
  pages in 64 MB at 16KB = 4096

THREE THINGS THAT OUTPUT PROVES, exactly as the theory predicts: 1. malloc ALLOCATED NOTHING PHYSICAL. 284 → 286 faults for a 64 MB allocation: just two, for the allocator's own bookkeeping. The 64 MB exists as ADDRESS SPACE with no frames behind it. This is why a program can malloc more than it will ever use, and why "allocation succeeded" does not mean "memory is available". 2. EXACTLY ONE FAULT PER PAGE ON FIRST TOUCH. 4382 − 286 = 4,096 faults 64 MB / 16 KB = 4,096 pages A perfect match. Every page was faulted in on demand, one at a time, precisely when first written. 3. ZERO FAULTS ON THE SECOND PASS. 4382 → 4382. The pages are resident, so translation succeeds in hardware with no OS involvement at all. Time fell from 8.7 ms to 5.2 ms — the residual difference is the memory writes themselves plus TLB misses. That 8.7 → 5.2 ms gap IS the cost of 4,096 minor faults: (8.7 − 5.2) ms / 4096 ≈ 0.85 µs per fault Sub-microsecond, because these are MINOR faults — the OS only had to allocate a zeroed frame, with no disk I/O. A MAJOR fault on an SSD would be ~100 µs, over 100× more. That ratio is why the fault-rate arithmetic below is so unforgiving. WHY major=1 THROUGHOUT: exactly one hard fault, during program startup (loading the binary). Everything afterwards was served from memory. On a warm system, major faults are rare — which is the healthy state.

EAT = (1 − p) × memory_access + p × page_fault_time where p is the page-fault RATE (probability a given access faults). WORKED EXAMPLE — the classic figures: memory access = 200 ns page fault time = 8 ms = 8,000,000 ns EAT = (1 − p)(200) + p(8,000,000) = 200 − 200p + 8,000,000p = 200 + 7,999,800p p = 0 → 200 ns (no slowdown) p = 0.001 → 8,200 ns 41× SLOWER p = 0.0001 → 1,000 ns 5× slower p = 0.00001 → 280 ns 1.4× slower ONE FAULT PER 1,000 ACCESSES MAKES THE SYSTEM 41× SLOWER. FOR LESS THAN 10% DEGRADATION: 220 > 200 + 7,999,800p 20 > 7,999,800p p < 0.0000025 = 1 fault per 400,000 accesses That is the number to remember: to keep paging overhead under 10%, fewer than one access in 400,000 may fault. Virtual memory works only because locality of reference makes real fault rates far below that. REDO WITH AN SSD (100 µs = 100,000 ns): EAT = 200 + 99,800p p = 0.001 → 299.8 ns, only 1.5× slower An SSD makes paging roughly 80× more forgiving. That single change is why swap became usable again after two decades of "never enable swap" advice — the advice was correct for spinning disks and is wrong for SSDs. COPY-ON-WRITE — demand paging applied to fork(): · after fork(), parent and child SHARE all pages, marked read-only · the first WRITE by either causes a protection fault · the OS copies just that page and marks both writable → fork() copies only the page TABLE, not the data This is why fork was measured at 356 µs (in the threads topic) rather than seconds: a 1 GB process forks without copying 1 GB. And exec() immediately afterwards discards the address space entirely, so in the common fork+exec case almost nothing is ever copied. PAGE PREFETCHING / PREPAGING: bring in several adjacent pages on a fault, betting on spatial locality. ✔ fewer faults if the guess is right ✗ wasted I/O and wasted frames if wrong Modern kernels do READAHEAD for sequential file access (detected by pattern), which is the same idea applied to the page cache.