Paging: the virtual address is notation, the physical address is its meaning.
The compiler lays out every program the same way, and the machine has one memory. Either the second program is relocated, or every address is a name the kernel resolves at run time.
That is virtual memory. The program's addresses are virtual: notation. The memory chip's are physical: meaning. The kernel owns the mapping, and a program that cannot name a physical address cannot touch another's memory.
Isolation as a translation problem: the Meaning chapter's semantics, applied to addresses.
Cut both address spaces into 4 KB blocks: pages on the virtual side, frames on the physical. A 32-bit address is a 20-bit page number and a 12-bit offset: translate the page number through a table, copy the offset. Positional notation in base 4,096.
A million pages means a million entries, 4 or 8 MB if flat, which selfie accepts. Real systems use a tree, and a cache, the TLB.
In selfie, tlb translates, on every load, store and fetch. Find it; it is a few lines.
A new machine context has an empty page table. Its first fetch is a page fault: the translation fails, the machine stops, the kernel takes over, allocates a frame, writes the entry, and lets the machine retry. On-demand paging: creating a machine costs nothing until it runs.
The same exception distinguishes a legitimate first touch from an error. A fault in the heap below the program break, or in the stack, gets a frame. A fault anywhere else is a segmentation fault, and the kernel decides what to do with a program that did that: in selfie, it stops it.
Flat: one array, one lookup, a million entries whether used or not. Tree: a directory of tables, two lookups, only the touched regions allocated. Both denote the same function from pages to frames.
Same meaning, different cost: the pattern of the Cost chapter, seen for the first time in this class. The kernel chooses the notation; the program observes only the meaning. Which is exactly what makes the choice free.
In mipster, nobody has to: the emulator is a program with its own memory, the guest's memory is an array inside it, and translation is index arithmetic. No self-reference.
On real hardware, the kernel runs on the same processor with the same address translation switched on. So the page table that maps the kernel must itself be mapped, and the code that writes page tables runs through one. The bootstrap problem of week 6, in its spatial form.
Read tlb, map_page and the page fault handling in mipster. No new assignment: finish self-assembler. Next week time: the timer interrupt, and why it is the kernel's answer to the halting problem.
Strauss · Die Frau ohne Schatten — Böhm, Vienna 1977. The Empress has no shadow: an address with nothing mapped behind it, and the opera is the page fault handler, three acts of it. Virtual memory, at Hofmannsthal’s scale.
Virtual Memory — Denning, 1970, in Computing Surveys: the whole subject, paging, working sets and thrashing, as it stood when it was new. And, more technical, One-Level Storage System — Kilburn, Edwards, Lanigan and Sumner, 1962: the Atlas paper, where paging was invented.