Virtual memory

Chapter 0.1 told you memory is one flat byte array and an address is an index into it. That model earned its keep for seven chapters, and it was a fiction the whole time. The addresses your program sees, prints, and does arithmetic on are virtual: the CPU emits them, but they are not the numbers that reach DRAM. On every single access, a piece of hardware called the MMU (memory management unit) translates the virtual address into a physical one, using tables the operating system maintains.¹

You can catch the lie red-handed: run two programs at once and have both print the address of their first local variable. They can print the same number, and write to it, without touching each other. Two indices, one physical byte array, no collision. That is only possible if each process gets its own private, per-process address space: a large, sparse illusion that holds all of its code and data, with the OS and hardware turning every reference into a physical location behind its back.²

Why go to this trouble? Three jobs at once: isolation(no process can even name another's memory), simplicity (every program believes it starts at the same tidy addresses), and capacity(the illusion can be larger than the physical memory behind it). The flat array of 0.1 survives; there is just one per process, and it's a rented illusion.³

SourcesOSTEP Ch. 13 · pp. 109–115CS:APP 3e §9.1 · pp. 839–840

Translating every byte individually would need a mapping table as big as memory itself. So the mapping works in fixed-size chunks called pages: 4 KB (4096 bytes) on essentially every system you'll touch. Virtual memory is carved into 4 KB pages, physical memory into 4 KB page frames, and the map only records which page lives in which frame. Within a page, bytes stay in order.⁴

That makes translation a bit-slicing operation. Since 4096 = 2¹², the low 12 bits of a virtual address are the offset within the page, and every bit above them is the virtual page number (VPN). The page table, one per process and maintained by the OS, maps each VPN to a physical frame number (PFN). The hardware rebuilds the physical address as (PFN << 12) | offset: the offset is never translated, because pages and frames have identical internal layout.⁵

What exactly sits in one page table entry (PTE)? The PFN, plus a handful of bits that turn out to run the world: a valid bit (is this part of the address space mapped at all?), protection bits (read/write/execute; the hardware enforces them on every access), a present bit (is the page in physical memory right now, or out on disk?), plus dirty and accessed bits the OS uses to decide what to write back and what to evict, the same bookkeeping logic you met inside caches in 0.5, now in software.⁶

Before you feel the cost, feel the size. A 32-bit address space with 4 KB pages has a 20-bit VPN (about a million pages), and at 4 bytes per entry, that's a 4 MB page table per process. Run a hundred processes and the OS is spending hundreds of megabytes on nothing but translations. This is why the table lives in ordinary memory, not in some special on-chip bank, and that placement is about to cost us.¹⁶

SourcesOSTEP Ch. 18 · pp. 169–178CS:APP 3e §9.3.2 · p. 842

Here is the catch: because the page table lives in memory, paging taken literally requires one extra memory reference to fetch the translationbefore every real load, store, or instruction fetch. Memory traffic doubles; OSTEP puts it bluntly: this alone would "slow down the process by a factor of two or more," and the memory wall from 0.4 gets twice as tall.⁷ The fix should feel inevitable by now: cache the translations. The TLB (translation lookaside buffer) is a small, very fast cache inside the MMU holding recently used VPN→PFN entries. OSTEP calls it what it really is, an address-translation cache, and credits it with making virtual memory practical at all.⁸

The access protocol is chapter 0.5 verbatim: extract the VPN, look it up; on a hit, concatenate the cached PFN with the offset and go, with no page-table visit; on a miss, walk the page table in memory, install the entry, and retry the instruction.⁹ And because one entry covers 4096 consecutive bytes, the TLB runs on the same fuel as every cache: spatial locality(0.6). OSTEP's own worked trace, a 10-int array straddling three pages, goes miss, hit, hit, miss, hit, hit, hit, miss, hit, hit: one miss per page touched, everything else rides free.¹⁰

But TLB reach is tiny. Even a generous 1,024-entry TLB at 4 KB per entry covers just 4 MB of address space, against gigabytes of RAM. Sweep sequentially and you miss once per 4 KB; hop randomly across a large heap and every access can miss the TLB and the data cache, stacking a page-table walk on top of a DRAM fetch.

One PTE bit deserves its own paragraph: present. Touch a page that is mapped but not in physical memory and the hardware raises a page fault; the OS steps in, finds the bytes (or allocates a fresh frame), updates the table, and restarts your instruction as if nothing happened: a cache miss handled in software, with the OS as the miss handler.¹¹ Pages + page tables + present-or-not is the exact machinery vLLM's PagedAttention borrows in chapter 3.6 to manage the KV cache. Same idea, different bytes. Segmentation, swap-replacement policy, and malloc's free-list internals also live in this neighborhood; they exist, but they're not on our path.

SourcesOSTEP Ch. 19 · pp. 183–186CS:APP 3e §9.6.2 · p. 853CS:APP 3e §9.3.4 · p. 844

Page size 4 KB, so the offset is the low 12 bits: exactly three hex digits. Suppose the page table says VPN 0x403 maps to PFN 0x1F2.