Address Spaces and Translation

The memory hierarchy ended with a convenient fiction: that a program addresses one flat array of bytes that is entirely its own. On a real machine that array does not exist. Physical memory, the DRAM chips, is a single shared resource, smaller than the address each program is allowed to name, and used at the same time by dozens of processes. Virtual memory is the mechanism that makes the fiction true for each process: every program gets its own private array of bytes, and hardware translates each access into a location in the one physical memory underneath. This lesson sets up the two address spaces and the translation that connects them; the next two build the data structures that make it work.

Two address spaces

A program issues virtual addresses: the addresses in its code, its pointers, its %rip. The set of all $2^n$ such addresses on an $n$-bit machine is the virtual address space. Underneath, DRAM is named by physical addresses, and the set of $2^m$ of those (with $m$ usually smaller than $n$) is the physical address space. The processor's word size fixes $n$; the amount of installed RAM fixes the useful range of $m$.

The sizes matter. A modern x86-64 processor uses 48-bit virtual addresses: $2^{48}$ bytes is 256 TB of nameable space, per process. A machine with 16 GB of DRAM has physical addresses covering about $2^{34}$ bytes. Every process can name sixteen thousand times more memory than exists, and dozens of processes do so simultaneously; address translation is what makes this workable.

The three jobs of virtual memory

Virtual memory solves three problems at once, all with the same mechanism: a level of indirection on every address. The machinery of the next two lessons exists to serve exactly these jobs.

A cache for disk. A process can name far more bytes than the machine has DRAM, so the full contents of its address space live on disk, and DRAM holds only the subset in active use. This makes DRAM one more level of the memory hierarchy: a cache whose backing store is disk. But the numbers force an extreme design. A DRAM access costs tens of nanoseconds; a read from an SSD costs tens of microseconds, and from a spinning disk around $10\text{ms}$ — a miss penalty of three to five orders of magnitude, dwarfing the roughly 100x gap that SRAM caches bridge. Consequently the blocks are large (4 KB pages rather than 64-byte lines, to amortize the transfer), placement is fully associative (any page may occupy any frame, so no placement constraint ever forces a bad eviction), the write policy is always write-back (writing through to disk on every store would be absurd), and replacement is decided by operating-system software, because when a miss costs ten million cycles, spending a few thousand choosing the right victim is free.

The magnitudes force every one of those design choices. Line up the levels a reference might reach: an L1 hit is about 1 ns, a DRAM access about 100 ns (a $100\times$ gap, the one SRAM caches exist to bridge), an SSD read about $50\mu \text{s}=50,000$ ns, and a spinning-disk read about $10\text{ms}=10,000,000$ ns. So a page fault to a spinning disk is roughly 100,000 times slower than the DRAM access it stands in for, and to an SSD still about 500 times slower. If a DRAM access were one second, a disk page fault would be over a day. When a single miss costs that much, it pays to spend freely both avoiding it and handling it: large blocks (one 10 ms seek should return a lot of data), full associativity (never evict a useful page over a placement technicality), and a software replacement policy (a few thousand cycles of deliberation is invisible against ten million cycles of disk) all follow directly from the size of that number.

A memory manager. Because each address space is private, every process can use the same layout: on x86-64 Linux, code starting at 0x400000, the heap growing up from the end of the data segment, shared libraries in the middle, the stack growing down from the top. The linker bakes absolute addresses into every executable without knowing, or caring, where in DRAM the program will land. Allocation gets simpler too: when a process asks for $k$ contiguous pages of heap, the kernel can satisfy it with $k$ page frames scattered anywhere in DRAM, because contiguity in virtual space never requires contiguity in physical space. And sharing falls out for free: the kernel keeps one physical copy of the C library's code and maps the same frames into every process that uses it, at whatever virtual address each expects.

A protection boundary. Isolation holds by construction: a process cannot read or clobber another's memory because no virtual address it can form maps there. Within a process, the mapping is the natural place to hang finer permissions — this page is read-only code, that one is non-executable stack, those belong to the kernel — checked by hardware on every single reference. The next lesson shows that these checks cost nothing extra, because they ride along with a lookup translation was doing anyway.

Pages and page frames

Translating each byte individually would be hopeless: there are $2^{48}$ of them. Instead virtual memory works in fixed-size chunks. The virtual space is cut into pages and physical memory into equally-sized page frames, and the unit of mapping is one page into one frame. A typical page is $P=2^p=4\text{KB}$, so $p=12$.

Because the page size is a power of two, a virtual address splits cleanly into two fields, exactly as a cache address split into tag, index, and offset. The low $p$ bits are the virtual page offset (VPO): which byte within the page. The high $n-p$ bits are the virtual page number (VPN): which page.

The MMU translates the page number, not the offset

Translation is done in hardware by the memory management unit (MMU), a block that sits between the CPU's address output and main memory. On every memory reference the CPU hands the MMU a virtual address; the MMU returns the physical address, and only then does DRAM see anything.

The translation itself is the lesson's central fact, and it is simpler than it looks. The MMU maps the virtual page number to a physical page number (PPN); that is the only lookup. The offset is not translated: because a page and a frame are the same size and the same alignment, byte $k$ of a page is byte $k$ of its frame. So the physical page offset (PPO) equals the VPO, bit for bit. The MMU replaces the high field and copies the low field through unchanged.

So a virtual address VPN | VPO becomes the physical address PPN | VPO. Two properties follow immediately. First, the number of offset bits — and therefore the page size — is shared by both spaces; only the page-number widths can differ ($n-p$ virtual bits map to $m-p$ physical bits). Second, the whole job of the address-translation machinery reduces to one question: given a VPN, what is the PPN? That mapping is held in a per-process table.

A translation, bit by bit

Run one translation end to end on a small machine (the example system of CS:APP §9.6.4): $n=14$ virtual address bits, $m=12$ physical address bits, and $P=64$-byte pages, so $p=6$. The derived widths follow mechanically:

• VPO = PPO = 6 bits, because $p=6$;
• VPN $=n-p=8$ bits, so the virtual space has $2^8=256$ pages;
• PPN $=m-p=6$ bits, so physical memory has $2^6=64$ frames.

Notice $m<n$: this machine's virtual space (16 KB) is four times larger than its physical memory (4 KB), so at most a quarter of the virtual pages can be resident at once. Now let the CPU read virtual address 0x03D4.

1. Write out the 14 bits. 0x03D4 is 00 0011 1101 0100.
2. Split at bit 6. The high 8 bits, 0000 1111, are the VPN: page 0x0F. The low 6 bits, 01 0100, are the VPO: byte 0x14 within the page.
3. Look up VPN 0x0F. The page table (next lesson's subject) says this page is resident in frame 0x0D, so the PPN is 0x0D; in bits, 00 1101.
4. Form the physical address. Concatenate PPN and the untouched offset: 0011 0101 0100, which reads as 0x354. That 12-bit address goes to memory.

Every translation the rest of this module performs — through page tables, TLBs, and multi-level walks — is this same four-step skeleton. Only step 3, the lookup, gets more elaborate.

One more property of the split, worked through with the same numbers because it is a common source of confusion: which bits move and which do not. The offset 0x14 appears verbatim in both the virtual address (0x03D4) and the physical address (0x354) — the low six bits are 01 0100 in each. Only the high field changed, from VPN 0x0F to PPN 0x0D. So two virtual addresses in the same page always land in the same frame at the same relative position: 0x03D4 and 0x03D5 (offsets 0x14 and 0x15 of page 0x0F) become 0x354 and 0x355, adjacent in memory just as they were adjacent in the program. Crossing a page boundary, though, is a discontinuity: 0x03FF is the last byte of page 0x0F, and 0x0400 is byte 0 of page 0x10, which the table may map to any frame at all — physically nowhere near frame 0x0D. Contiguity in virtual space survives translation only within a page; across pages it is the table's to decide, and usually it scatters.

Page hit, page fault

Step 3 hides one assumption: that the page was resident. The lookup structure records, for each virtual page, whether a frame currently holds it, and the two answers produce two very different control flows.

A page hit is the common case, and it is handled entirely in hardware. The CPU sends the virtual address to the MMU; the MMU reads the page's page-table entry (PTE) from memory, finds the page resident, forms the physical address, and the access completes. The program never knows any of this happened.

A page fault is what happens when the PTE says the page is not resident. Hardware cannot fix that — fetching a page from disk, choosing which resident page to evict from its frame, and updating the bookkeeping are policy decisions — so the MMU raises an exception that transfers control to a software routine in the kernel, the page-fault handler. The handler brings the page into a frame, updates the lookup structure, and returns. Then the CPU re-executes the faulting instruction from scratch, and this time the reference hits. The program cannot tell the fault occurred, except by the clock.

The division of labor is deliberate. Hardware handles the fast, common case (hits) with no software in the loop; software handles the slow, rare case (faults) with full policy freedom. The next lesson fills in both halves: the structure the MMU reads, and what the handler actually does.

One physical memory, many virtual spaces

Putting the pieces together: each running process has its own virtual address space, its own VPN-to-PPN mapping, and the freedom to use identical virtual layouts. Those mappings funnel into the single physical memory, where the kernel hands out frames as it sees fit. Two processes may map their page 5 to entirely different frames (isolation), or — for shared libraries — deliberately to the same frame (sharing).

From Atlas to five-level paging

Virtual memory is one of the oldest ideas in computer architecture that is still exactly as described here, and the history explains why the design looks the way it does.

The mechanism was invented on the Atlas computer at the University of Manchester (Kilburn, Edwards, Lanigan, and Sumner, One-Level Storage System, 1962, IRE Trans.). Atlas gave programmers a single flat store of 1 M words while backing it with 16 K words of core and a drum, paging between them automatically — the one-level storage of the title is precisely the convenient fiction this lesson opened with. Every element here, the page, the page fault, the automatic fetch from backing store, is in that paper. What Atlas lacked was a fast way to do the lookup on every reference; that arrived as the translation lookaside buffer, and its principle is the third lesson of this module.

The design also keeps expanding along the one axis the arithmetic exposes: address width. This lesson's 48-bit x86-64 space ($2^{48}$ = 256 TB) was generous when it shipped, but large servers outgrew it, so Intel and AMD added 5-level paging (a fifth table level lifting virtual addresses to 57 bits, $2^{57}$ = 128 PB), supported in Linux since 2017 and shipping on Ice Lake servers. The page-table lessons that follow show why adding reach is as cheap as adding one more level to the walk. And the isolation this lesson credits to no virtual address maps there has a hardware caveat: the Meltdown attack (Lipp et al., 2018, USENIX Security) showed that speculative execution could momentarily read across the protection boundary the page table is supposed to enforce, and the fix, kernel page-table isolation, gives the kernel its own set of page tables so a user process's tables cannot even name kernel memory — protection by construction, taken one level further than this lesson's version.

The mapping from VPN to PPN lives in a structure the MMU consults on every access: the page table, and what happens when a page is not in DRAM at all.