Paging’s other bill: the table itself. A 32-bit space with 4KB pages and 4-byte PTEs means a million entries — 4MB per process, hundreds of megabytes across a busy system, all spent on translations.
The Crux: How To Make Page Tables Smaller?
Simple array-based (linear) page tables are too big. How can we make them smaller? What are the key ideas? What inefficiencies arise from the new data structures?20.1 Simple Solution: Bigger Pages
Quadruple the page size — 16KB pages in a 32-bit space — and the table shrinks fourfold:
The reduction exactly mirrors the page-size increase. But big pages punish us inside each page: applications allocate a page and use bits of it, and memory fills with mostly-empty giants — internal fragmentation internal fragmentation Wasted space INSIDE an allocated unit — e.g., the unused gap between heap and stack in a fixed base/bounds slot. defined in ch. 15 — open in glossary again. So common cases stay small: 4KB (x86), 8KB (SPARCv9).
Aside: Multiple Page Sizes
Many architectures (MIPS, SPARC, x86-64) support several page sizes: a 4KB default, plus large pages (e.g. 4MB) on request — so a DBMS can drop a hot, giant structure onto ONE page, consuming a single TLB entry. The main motive isn’t table space at all: it’s reducing TLB tlb coverage The total memory the TLB's entries can map at once; touch more pages than that in a short window and misses dominate (Culler's Law: RAM isn't always RAM). Larger pages stretch it. defined in ch. 19 — open in glossary pressure. The cost is a notably more complex VM manager — which is why large pages are often granted only through an explicit application interface.20.2 Hybrid Approach: Paging and Segments
When two reasonable approaches both fall short, try the combination — chocolate, meet peanut butter. Years ago Multics (Jack Dennis) did exactly this to shrink page tables. First, stare at the waste a linear table carries for a barely-used address space:
click a region marked ⓘ for details
| PFN | valid | prot | present | dirty | |
|---|---|---|---|---|---|
| VPN 0 | 10 | 1 | r-x | 1 | 0 |
| VPN 1 | — | 0 | — | — | — |
| VPN 2 | — | 0 | — | — | — |
| VPN 3 | — | 0 | — | — | — |
| VPN 4 | 23 | 1 | rw- | 1 | 1 |
| VPN 5 | — | 0 | — | — | — |
| VPN 6 | — | 0 | — | — | — |
| VPN 7 | — | 0 | — | — | — |
| VPN 8 | — | 0 | — | — | — |
| VPN 9 | — | 0 | — | — | — |
| VPN 10 | — | 0 | — | — | — |
| VPN 11 | — | 0 | — | — | — |
| VPN 12 | — | 0 | — | — | — |
| VPN 13 | — | 0 | — | — | — |
| VPN 14 | 28 | 1 | rw- | 1 | 1 |
| VPN 15 | 4 | 1 | rw- | 1 | 1 |
Twelve of sixteen entries describe emptiness — for a 16KB space. Don’t imagine the 32-bit version; it’s far too gruesome.
The hybrid: one page table per logical segment — code, heap, stack. The MMU keeps chapter 16’s base/bounds pairs, repurposed: the base register no longer points at the segment but at that segment’s page table in physical memory; the bounds register holds the segment’s maximum valid page. A 32-bit address then carries three fields:
On a TLB miss the hardware picks the pair by segment and indexes that segment’s table — virtually the linear lookup, with three base registers instead of one:
SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT
VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT
AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))The saving lives in the bounds register: a code segment using three pages keeps a three-entry page table, and the unallocated sea between heap and stack — belonging to no segment — costs nothing. Accesses beyond a segment’s end fault, as ever.
But the hybrid inherits its parents’ flaws. It’s still segmentation: a large, sparsely-used heap drags a long page table again — the usage-pattern rigidity of chapter 16. And page tables are now arbitrary-sized (any multiple of PTEs), so finding memory for them resurrects external fragmentation — chapter 17’s whole battle, waged now on behalf of the bookkeeping itself. People kept looking.
Tip: Use Hybrids
Two good, opposing ideas? Check the combination — hybrid corn beats every natural species. But not every cross is a Reese’s cup: behold the Zeedonk (zebra × donkey), which exists, and which you should look up, prepared to be amazed.Check yourself
1.Quadrupling the page size (4KB → 16KB) shrinks the linear page table 4× (4MB → 1MB). Why don't systems just keep going?
2.Many architectures let a 'smart' application place a hot data structure in one 4MB large page. What's the MAIN motivation?
3.In the Multics-style hybrid, what do the segment base and bounds registers hold — and where do the savings come from?
4.The hybrid saves real memory, yet the book keeps looking. What are its two lingering problems?
5.The tiny 16KB address space uses 4 of its 16 pages, and its linear page table shows it. What's the lesson of Figure 20.2?