§18.1A Simple Example And Overview

The OS solves most space-management problems one of two ways. Chop things into variable-sized pieces — segmentation — and the space itself fragments. Or chop into fixed-sized pieces: in virtual memory this is paging paging Virtualizing memory by chopping the address space into fixed-sized pages mapped to physical page frames — no external fragmentation by design, and sparse address spaces come cheap (Atlas, early 1960s). defined in ch. 18 — open in glossary , an idea going back to the Atlas (early 1960s). The address space becomes fixed-size pages page A fixed-sized unit of a virtual address space; every page can live in any free physical frame, which is what makes free-space management trivial under paging. defined in ch. 18 — open in glossary ; physical memory becomes an array of page frames page frame A fixed-sized slot of physical memory holding exactly one virtual page; physical memory is viewed as an array of them. defined in ch. 18 — open in glossary , each holding exactly one page.

18.1 A Simple Example And Overview

A tiny example: a 64-byte address space of four 16-byte pages, placed into a 128-byte physical memory of eight frames. Follow the colors — each page landed wherever a free frame happened to be:

Two advantages are already visible. Flexibility: the system supports the address-space abstraction regardless of how the process uses it — no assumptions about which way the heap and stack grow. Simplicity: placing the address space took no fit policy, no splitting, no coalescing — the OS keeps a free list of pages and grabbed the first four (frames 3, 7, 5, 2). Any free frame serves any page; last chapter’s whole struggle dissolves.

To record where each virtual page landed, the OS keeps a per-process structure — the page table page table The per-process structure storing each virtual page's translation (VPN → PFN) plus per-page bits; one of the most important data structures in a modern OS — and, done naively, both too big and too slow. defined in ch. 18 — open in glossary — storing one translation per virtual page: (VP 0 → PF 3), (VP 1 → PF 7), (VP 2 → PF 5), (VP 3 → PF 2). Per-process matters: another process has its own table, its virtual pages mapping to different frames (sharing aside).

Translation. Suppose the process executes movl 21, %eax. Split the virtual address into two components: the virtual page number (VPN) — the top bits, enough to name every page (4 pages → 2 bits) — and the offset within the page (16 bytes → 4 bits). Then replace the VPN with the frame number the page table reports, and keep the offset exactly as-is — it names a byte within the page, and the page moved as one intact unit:

Virtual 21 = binary 010101: VPN 01 → page 1; page table says PFN 7 (111); physical address 1110101 = 117 — byte 5 of frame 7, precisely where Figure 18.2 drew page 1’s bytes.

With the overview in hand, the beguiling questions queue up: where are these page tables stored? What exactly is in them, and how big do they get? Doesn’t this make everything slow? Read on.