Virtual Memory

Virtual memory makes every address your program uses a lie the hardware agrees to maintain. The pointer says 0x7ffd4a2c; nothing at that location exists. On every load and store, the CPU swaps the address's top bits for the number of a physical frame, looked up in a table the operating system wrote. The bottom bits ride through untouched.

That lookup is the busiest operation in a computer, and its cost is not one number. It has three rungs, and they are orders of magnitude apart. If the translation is cached in the TLB, you pay about a cycle. If it is not, the CPU reads the page table — and the page table lives in RAM, so the lookup is itself a memory access, around 100 cycles. And if the table says the page is not in RAM at all, the CPU traps to the operating system, which goes to disk: a million cycles, give or take an order of magnitude.

A million against one. That gap is why virtual memory has the shape it does — why there is a TLB, why pages are 4 KB rather than 4 bytes, and why a fault that has to reach storage is not a slow memory access but a scheduling event, where the kernel gives up on your thread and runs somebody else's.

Not every fault goes that far. A minor fault is the kernel handing you a page it already has in memory — zeroing a fresh one, resolving a copy-on-write share, finding the page in its own cache — and it costs thousands of cycles, not millions. A major fault is the one that goes to storage. This page models the major kind, because it is the one whose cost you have to design around, but the two are worth keeping apart in your head and in your profiler.

How Virtual Memory Works

This page animates a scale model: a 6-bit virtual address space — 64 words, cut into 8 pages of 8 words — mapped onto a physical memory of 4 frames. That is 32 real words behind 64 addressable ones, which is the arrangement in miniature: a process may name more than the machine has.

Four of the eight pages are mapped: P0 is code, P1 is data, P2 is heap, P7 is stack. P3 through P6 are the hole between heap and stack, and nothing lives there. That layout is not decoration — it is why a wild pointer lands in nothing rather than in someone else's data.

Start with the address. Load a[9], and the hardware splits 001001 in two: the top three bits are the virtual page number (001, page 1), and the bottom three are the offset (001, word 1 inside it). No arithmetic is involved; the two fields are just different wires coming off the same address. The va // PAGE and va % PAGE notation is a readable description of the split, not work performed by an arithmetic unit.

Then the lookup, in the order the hardware tries it:

1. The TLB. A tiny fully-associative cache of recent translations — two entries in this model, roughly 1,500 in a real core. Every entry is compared at once, which is why an answer costs about a cycle. A hit means you are done: take the frame number, keep the offset, go read memory.
2. The page table. On a miss, the CPU reads the entry for this page number. The table is an ordinary array in RAM, so this read costs what a memory read costs. Each entry carries a valid bit and a frame number.
3. The disk. If the entry exists but valid is 0, the page is not in memory. That is a major page fault: a trap into the kernel, which finds a free frame, copies the whole page in from disk, sets valid to 1, and restarts the instruction. Which frame it picks is worth watching. It comes off a free list — the RAM column marks whichever one is next out — and has nothing to do with the page's virtual number.
4. Nothing. If there is no entry at all — the address fell in the hole — there is nothing to fetch and nothing to wait for. The kernel kills the process. That is a segfault, and it is the same walk as a page fault with a different verdict at the end.

Then the translation itself, which is one line: pa = frame * PAGE + offset. The page number was replaced. The offset was not, and could not have been: a page and a frame are the same size, so a word's position inside a page is its position inside the frame. That is the whole reason translation can be a table lookup on the top bits and nothing else — and the reason each mapping uses a page size supported by the hardware. Real systems can support several sizes, including huge pages.

The costs in this model are 1 cycle for the TLB probe, 100 for a memory read, and 1,000,000 for a disk service. So a TLB hit costs 101 (the probe plus the data read), a walk costs 201 (the probe, the table read, the data read), and a fault costs 1,000,201.

Virtual Memory Step by Step

The default run issues twelve loads with ordinary locality: three words of code, three of data, three of the heap, then back to code. 0 1 2 · 8 9 10 · 16 17 18 · 3 4 5.

Load 1 — a[0]. Page 0, offset 0. The TLB is empty, so: miss. The walk reads page-table entry 0, which is mapped (P0 is code) but has valid = 0 — the page has never been in memory. Page fault. The kernel pops a frame off the free list, and here is the first thing worth noticing: it gets F2, not F0. Nothing links a page's virtual number to its frame number, which is exactly what a page table is for. All eight words of P0 travel from disk into F2, the entry flips to valid, and the translation P0 → F2 is cached in the TLB. Bill: 1 + 100 + 1,000,000 + 100 = 1,000,201 cycles.

Load 2 — a[1]. Same page, offset 1. The TLB has P0 → F2, so the answer arrives in one cycle. pa = 2 × 8 + 1 = 17. 101 cycles, and nothing else moved.

Load 3 — a[2]. Identical. 101 cycles.

Load 4 — a[8]. Page 1 now — the data segment. TLB miss (it only knows P0), walk, valid = 0, fault. The next free frame is F0, so the second contiguous virtual page lands before the first one in physical memory. 1,000,201 cycles. The TLB now holds both P0 → F2 and P1 → F0, and it is full.

Loads 5 and 6 hit that new translation at 101 each.

Load 7 — a[16]. Page 2, the heap. Miss, walk, fault, and this time the frame is F3. The TLB has no room, so the least recently used translation — P0 → F2, last used on load 3 — is thrown out to make space. Note what did not happen: P0 is still sitting in F2. Only its cached translation is gone.

Loads 8 and 9 hit P2 → F3.

A TLB miss is not a page fault

Load 10 — a[3]. Back to the code page, and this is the load the lesson is built around. The TLB does not have P0 any more, so it is a miss. The walk reads entry 0, and the next beat holds on what it found: valid = 1, frame F2. No fault. The page never left RAM. This load costs 201 cycles, not 1,000,201, and the difference between those two numbers is the difference between "the translation was not cached" and "the page is not in memory." They are not the same failure, and confusing them is the most common way to reason wrongly about paging.

Loads 11 and 12 hit the freshly re-cached P0 → F2 at 101 each.

Three disk trips are 99.9% of the run

The tally: 3 page faults, 8 TLB hits, one no-fault walk, 16 memory reads, 3,001,612 cycles.

Now look at the strip the final beat draws. Three million of those cycles are the three disk trips. Everything else the hardware did in the entire run — twelve address splits, twelve TLB probes, four page-table walks, twelve data reads — comes to 1,612 cycles, which on a linear scale is a sliver about one pixel wide. The bar is drawn honestly, and it is drawn wider than it measures, because one pixel is the thinnest line there is.

That is the practical shape of virtual memory. Translation is nearly free. Faulting is not, and no amount of tuning the translation path will matter if you are faulting.

What the TLB Is Actually Worth

Switch the lesson variant from TLB to No TLB and run the same twelve addresses. The trace loses the lookup and hit path but nothing else: the same three page faults happen at the same three moments, and the total wall-clock barely moves, because it is dominated by disk either way.

What changes is the memory-read count: 24 instead of 16. Without a TLB, every single load reads the page table before it reads the data — two trips to memory where one would do. That is where "paging doubles memory traffic" comes from, and it is worth being exact about what doubles. Each translated access does. The run does not: four of these twelve loads had to walk the table anyway, so the total goes from 16 to 24 — half again as many, not twice. The TLB does not make faults cheaper. It removes the extra read that translating an address would otherwise cost, on the overwhelming majority of accesses that are not faults.

And it works only because of locality. Load the TLB thrash preset: four pages cycled three times through a TLB that holds two. The hit rate is zero. Each translation is evicted before its next use, so every load walks the page table — and removing the TLB entirely would cost precisely the same 24 reads. A cache you never hit is not a cache. The TLB has a working set just as the caches below it do, and this four-page loop exceeds the two-entry TLB by two pages.

The opposite extreme is the tight loop preset: twelve loads that never leave one page. One fault, eleven hits, thirteen memory reads. That is as good as paging gets, and it is what most real code looks like most of the time.

Between them, those two presets are the decision rule. When paging shows up in a profile, the fix for one half is no use against the other. High dTLB misses with few faults is a translation problem: the working set is too scattered for the entries you have, and the levers are locality, huge pages, and allocation layout. High major faults is a residency problem: the working set does not fit in RAM, or has not been touched yet, and the levers are memory size, warm-up, and how you do I/O. Wall-clock will not tell you which you have — in the run above it barely separates the two variants, because the disk drowns everything. Read the counters, not the clock.

Edge Cases

• First touch can fault, but need not. The model starts every mapped page nonresident. Real processes can inherit or preload resident mappings; file-backed pages may already be in the page cache and need only a minor fault. Demand-zero allocation and copy-on-write are also often minor faults. A major fault requires storage service. Warm-up helps distinguish first-touch work from the steady state.
• A TLB miss is not a page fault. Load 10 in the default run costs 201 cycles because P0 was resident the whole time — the animation stops on the valid bit to say so. The TLB caches translations; RAM caches pages. Losing one is not losing the other.
• A segfault is a page fault the OS cannot satisfy. Run the segfault preset. The fourth load asks for a[40], which is in P5 — the hole. The walk happens, the probe and the table read are both paid for, and then there is no mapping to act on. There is no page to fetch, no file to read from, no frame to allocate. The kernel does the only thing left and kills the process. Everything up to that point is the ordinary path. Two more loads were queued behind it; the ledger draws them greyed out and never charges for them, because a killed process does not get to finish its work.
• The offset never changes. Not in this model, not on real hardware. If you find yourself reasoning about a translation that alters the low bits, you have the wrong mental model — that is segmentation, not paging.
• This model never runs out of frames. Exactly four pages are mapped and there are exactly four frames, so no run here can force an eviction from RAM. That is deliberate: choosing which resident page to throw out is a policy question with its own answers (FIFO, clock, LRU approximations), and it gets its own lesson.

Common Mistakes

• Treating a major page fault as a slow memory access. A fault that reaches storage is four orders of magnitude away from a memory access, which puts it in a different category of event. The CPU cannot usefully wait for it, so the kernel context-switches to another process: it is a scheduling decision wearing a memory-access costume. A minor fault genuinely is closer to a slow memory access, which is the other half of why the two counters are worth reading separately.
• Assuming the page table is fast because it is a table. It is an array in RAM, and reading it costs what reading RAM costs. Common x86-64 configurations use four or five paging levels, and a walk can require several dependent table reads — which is why the TLB exists and why TLB misses show up in profiles as unexplained stalls.
• Believing virtual addresses near each other are physical addresses near each other. They are near each other within a page and nowhere else. Two consecutive pages can land in frames at opposite ends of RAM, and in the default run here, P0 and P1 land in F2 and F0 — out of order. Any reasoning that assumes contiguity across a page boundary is wrong; DMA and I/O code must follow device and OS mapping requirements: some devices require physical contiguity, while scatter-gather and IOMMUs can support noncontiguous frames. Ordinary malloc does not by itself provide a DMA mapping or pinning guarantee.
• Confusing "allocated" with "resident." A page-table entry can exist with valid = 0. The memory is yours, it is in your address space, and it is not in RAM. This is why a process's virtual size and its resident set size are two different numbers, and why the first touch of a freshly mmaped region is slower than the second.
• Thinking a bigger TLB fixes a TLB miss. Sometimes. But the thrash preset shows the other failure: the problem was the access pattern's footprint, not the TLB's size. The real lever on that side is bigger pages — huge pages cover more address space per entry, which is why databases and JVMs reach for them.
• Assuming a segfault means memory corruption. It means the access was not permitted. In this model that is always an unmapped address — the walk reached a hole and the kernel had nothing to offer — and unmapped addresses are the common case in practice too. But real page-table entries carry permission bits, so writing through a read-only mapping or jumping into a no-execute page raises the same signal on an address that is mapped perfectly well. Corruption is often the symptom behind either; the mechanism is much duller than the word suggests.

A Note on Simplification

This is a teaching model, not a simulator. Real systems often use 4 KB base pages and may support other base sizes and huge pages. x86-64 can use four or five paging levels, and a walk can require several dependent table reads, and the walk itself is done by a hardware page-table walker rather than by the code in the panel. Real TLBs are split into instruction and data, have multiple levels, and hold on the order of 1,500 entries. Real page-table entries carry permission, dirty, accessed and no-execute bits, none of which appear here; without permission bits there is no distinction between a read fault and a write fault, and no copy-on-write.

Nothing on this page models what happens when RAM fills up, which in a real system is most of what makes virtual memory interesting: choosing a victim page, writing it back if it is dirty, and the thrashing that follows when the working set exceeds physical memory. That is a policy question and it gets its own lesson.

The cycle counts are deliberately round. A memory read is more like 60–100 ns of latency depending on where it lands in the cache hierarchy; a page fault served by an NVMe SSD is closer to 100,000 cycles than 1,000,000, and one served by a spinning disk is worse than either. Treat them as orders of magnitude, which is the only precision the argument needs.

Measuring it on your own machine

Watch the fault counters rather than trusting any number here:

perf stat -e page-faults,minor-faults,major-faults,dTLB-load-misses ./your-program

The split between minor and major faults is the one to look at: a minor fault is the kernel handing you a page it already had, a major fault is a trip to storage. On macOS, vmmap and footprint show the resident-versus-virtual split for a running process, and sudo fs_usage -f pathname will show you the reads a major fault turns into.