Why do operating systems use multi-level page tables?
A single flat page table needs an entry for every possible page, even unused ones. A multi-level table splits it into pieces and only allocates the pieces for regions actually in use, saving a large amount of memory.
Explain it simply
A flat page table is like printing a phone directory with a slot for every possible number in the country, even the ones nobody owns. A multi-level table is like a book index: first the section by area code, and only the areas with subscribers get a detailed page.
With 32-bit addresses and 4 KB pages, a flat table has 2^20 entries (4 MB per process). Most processes use only a small part of their address space, so most of that 4 MB is wasted.
Example
A two-level split of a 32-bit address:
| outer index 10 bits | inner index 10 bits | offset 12 bits |- The outer table has 2^10 = 1024 entries, each pointing to an inner table.
- Each inner table has 1024 entries x 4 bytes = 4096 bytes, exactly one page.
- An inner table is created only when its 4 MB region of the address space is used (1024 pages x 4 KB).
A small process using code, heap and stack in 3 separate regions needs 1 outer table plus 3 inner tables = 4 pages = 16 KB, not 4 MB.
The cost: translation needs one extra memory access per level on a TLB miss. The TLB hides most of this. 64-bit systems use four or five levels.
What to say in the interview
"Multi-level paging stores page tables in pieces, so unused regions need no table memory. A small process might need 16 KB of tables instead of 4 MB. The price is an extra memory access per level on a TLB miss."
Common mistakes
- Forgetting that each level adds a memory access on a miss.