Multi-Level Page Tables

The motivation

A single-level page table for a 64-bit address space with 4 KB pages would need $2^{52}$ entries (offset = 12 bits, page number = 52 bits). At 8 bytes per PTE, that’s $2^{55}$ bytes — 32 PB — per process. The table would be larger than physical memory and almost entirely empty (most processes use only a few GB of the 64-bit space).

Multi-level paging solves this by representing the page table as a sparse tree. Only the branches that correspond to actually-allocated regions of the address space exist. The rest of the tree is never allocated.

The tree structure

The page number is divided into $k$ equal-size fields (typically 9 bits each on 64-bit systems). Each field indexes one level of the tree. The top-level entry points to a second-level page table, which points to a third-level, and so on down to the level that finally contains the frame number.

If an entry at any level is marked not present, its entire subtree does not exist — saving all the memory those lower tables would have consumed.

Trade-off: space vs time

A multi-level page table reduces memory overhead for sparse address spaces, but increases the translation cost:

• Single level: 1 memory access for the PTE + 1 for the data = 2 accesses.
• Two levels: 1 access for the outer PTE + 1 for the inner PTE + 1 for the data = 3 accesses.
• $k$ levels: $k+1$ memory accesses per logical memory reference.

Without a TLB, this overhead is severe. With a TLB (which caches the final translation), the walk is only needed on a TLB miss, which is rare (typical miss rate < 1%).

Forward-mapped page tables

The standard tree described above is forward-mapped: the virtual page number indexes into the structure top-down. The root of the tree is a physical page, pointed to by the PTBR (CR3 on x86).

Alternative representations exist:

Scheme	Description
Inverted page table	One entry per physical frame, not per virtual page. The table is indexed by (PID, VPN) through a hash function. Space-efficient for large address spaces with sparse allocation, but complex coherent page sharing.
Hashed page table	Use a hash table mapping (PID, VPN) → frame number. Chaining handles collisions. Used by some RISC architectures (PowerPC, IA-64).

Inverted page tables

An inverted page table has exactly one entry for each physical frame, regardless of how many processes exist. A virtual address is translated by hashing (PID, VPN) to find the corresponding frame.

Advantage: Space proportional to physical memory, not virtual address space size. With 16 GB of RAM and 4 KB pages, only 4M entries are needed — independent of how many 64-bit processes are running.

Disadvantage: Translation requires a hash lookup (potentially walking a chain), which is slower than a deterministic multi-level walk. Sharing a physical page between multiple processes is messy because each virtual mapping would need its own hash entry, and there is only one entry per physical frame. Workarounds exist (e.g., store multiple virtual tags per entry) but increase complexity.

Summary

• Multi-level page tables are sparse trees that save memory by not allocating subtrees for unmapped regions.
• The cost is additional memory accesses per translation — paid only on TLB misses.
• Inverted page tables use space proportional to RAM, not virtual address space, but complicate sharing and require hashing.
• The TLB makes the multi-level walk irrelevant in the common case.