Part 2 of 7 · 2 min read
The problem
Think of it this way. A hotel register with one line for every possible guest in the world, whether or not the guest is staying, would be enormous and almost empty. A real register has lines only for the rooms in use. Page tables face the same choice.
In plain words: The sizes, from page 3: a 32-bit address space with 4 KiB pages has 2^20 pages. At 4 bytes per entry, a flat table takes 2^20 × 4 = 4 MiB for each process. A 48-bit space has 2^36 pages. With 8-byte entries, a flat table would take 2^36 × 8 bytes = 512 GiB for each process, far more than the memory of most machines.
Yet a typical process uses little of the space. Look back at the layout of page 1: code, data and heap clustered near the bottom, libraries in the middle, the stack at the top, and a vast gap of unused addresses between them. A flat table spends 8 bytes on each entry of the gap. The remedy is to build the table so that the gap costs nothing.
Sparse address space
A sparse address space is an address space in which only a small part of the possible addresses is in use, in a few clusters separated by large unused gaps; this is the usual case for a process.
Example: a process with 3 MiB of code, data and heap, and 1 MiB of stack, uses 4 MiB out of 4 GiB, and the other 99.9% of the space is empty.
Check yourself: 1. How large is a flat page table for a 32-bit address space with 4 KiB pages and 4-byte entries? 2. Why is a flat table for a 48-bit space impractical? 3. Why is it wasteful to have table entries for the unused gap?