Virtual Memory — Demand Paging, Page Faults & Copy-on-Write
Why Virtual Memory — The Vast Library
A process's logical address space can be far larger than the physical RAM it uses at any moment. Only the pages a program is actively touching need to be resident; the rest wait on disk until referenced. The program sees one big, continuous memory — the illusion of infinite memory.
What Virtual Memory Buys You
All three benefits fall out of a single idea: don't keep in RAM what you aren't using. The page table already maps pages to frames — virtual memory just adds the honesty to admit that some pages simply aren't loaded yet.
Virtual Space, Physical RAM & Disk
The MMU maps resident pages to physical frames (page 0 → f4, page 2 → f1, page M → f7). Pages like page 5 aren't loaded — they live in the swap area on disk until the program touches them. The result: a 4 GB program runs comfortably on 512 MB.
Demand Paging — Load Only What's Touched
Programs obey locality of reference — at any moment they touch a small working set of pages. Loading everything upfront wastes time and RAM on pages that may never run. Demand paging brings a page in only on its first reference, and the valid bit is how the hardware knows the difference.
The Valid / Invalid Bit
Each page-table entry gains a valid bit. Set to v, the frame number is real and the access runs normally. Set to i, either the page is on disk and must be brought in, or the address isn't part of the process at all (a bug). The hardware raises a fault and lets the OS decide which.
Detecting Faults in a Sequence
For each reference the MMU reads the entry: a v yields the frame and completes instantly; an i (pages 2 and 4 here) raises a page fault and hands control to the OS. In real workloads the fault rate must be far below this cold-start figure — the next slides show why.
Servicing a Page Fault — Six Steps
The OS verifies the address is legal, finds a free frame (evicting a victim if none is free), reads the page from the backing store, marks the entry valid, and restarts the faulting instruction. For this to work the instruction must be restartable — the CPU state is restored exactly as if the fault never happened.
Pure Demand Paging vs Prepaging
Pure demand paging never loads a page that isn't needed but pays many faults up front; prepaging hides latency but risks wasted reads. Production kernels use hybrid heuristics — demand-fault the unknown, read ahead where locality predicts the next pages.
Effective Access Time for Faults
# Effective Access Time for demand paging EAT = (1 − p) × ma + p × Tfault # p = fault probability = (1 − p) × 200 ns + p × 8,000,000 ns
Because a fault (disk) is about 40,000× slower than a RAM access, even a tiny p wrecks the average. A mere 0.1% fault rate multiplies access time roughly 8×. Practical systems need p well below 1 in 100,000.
EAT at Three Fault Rates
Given ma = 200 ns, Tfault = 8 ms = 8,000,000 ns. EAT = (1 − p)·ma + p·Tfault.
| Fault rate p | EAT working | EAT | Slowdown |
|---|---|---|---|
| 0.001 (1 in 1,000) | 0.999×200 + 0.001×8,000,000 = 199.8 + 8,000 | 8,199.8 ns ≈ 8.2 µs | ≈ 41× |
| 0.0001 (1 in 10,000) | 0.9999×200 + 0.0001×8,000,000 = 199.98 + 800 | 999.98 ns ≈ 1 µs | ≈ 5× |
| target: < 10% slowdown | need EAT ≤ 1.1×200 = 220 ns | p ≤ 2.5 × 10⁻⁶ | ≈ 1 in 400,000 |
# Part (c): largest fault rate for under 10% slowdown (1 − p)·200 + p·8,000,000 ≤ 220 200 + 7,999,800·p ≤ 220 → 7,999,800·p ≤ 20 p ≤ 20 / 7,999,800 ≈ 2.5 × 10⁻⁶ # about 1 fault per 400,000 accesses
At 1 fault in 1,000 accesses memory runs 41× slower; even 1 in 10,000 is 5× slower. To keep the slowdown under 10%, the OS must hold faults below 1 per 400,000 accesses — which is exactly what good page-replacement and a healthy working set achieve.
Translation With Page Faults
Page size 1024 B, 8 pages. Table: 0→3(v), 1→i, 2→1(v), 3→5(v), 4→i, 5→2(v), 6→7(v), 7→i. p = L÷1024, d = L mod 1024.
| Logical L | p, d | valid? | Physical = f×1024 + d |
|---|---|---|---|
| 500 | p=0, d=500 | v (f=3) | 3×1024 + 500 = 3572 |
| 1500 | p=1, d=476 | i | PAGE FAULT |
| 2500 | p=2, d=452 | v (f=1) | 1×1024 + 452 = 1476 |
| 4500 | p=4, d=404 | i | PAGE FAULT |
| 5500 | p=5, d=380 | v (f=2) | 2×1024 + 380 = 2428 |
Addresses landing on valid pages translate straight to 3572, 1476 and 2428. Addresses 1500 and 4500 fall on pages 1 and 4 — both marked invalid, so each triggers a page fault that the OS services before the access can complete.
Copy-on-Write — Near-Free fork()
After fork(), parent and child share every page read-only. Reads cost nothing. The first write faults; the OS makes a private copy of just that one page, marks it writable, and restarts the write. Pages that are only read — or never touched — are never duplicated, so fork() of a multi-gigabyte process is near-instant.
Virtual Memory in the Real World
Eight Rules for Virtual Memory
The Illusion of Infinite Memory
From demand paging and the valid bit, through page-fault handling and the EAT maths, to copy-on-write — you can trace any reference, tell a hit from a fault, and compute how a rare disk trip reshapes access time.
Virtual memory only works if the OS chooses good victims when RAM is full. Next come the page-replacement algorithms — FIFO, Optimal and LRU — plus Belady's anomaly and thrashing, the heart of keeping the fault rate low.
🪄 End of tutorial · Press ← to review, or click Restart