Why Do 64-Bit Systems Use Multi-Level Page Tables?
64-bit architectures use multi-level hierarchical page tables instead of flat page tables because a flat table for a 64-bit virtual address space would require an impossibly large amount of physical memory just to store the table itself. By organizing page tables into a tree-like hierarchy, operating systems only allocate table entries for the regions of virtual memory that a process actually uses, saving gigabytes or even terabytes of RAM per process.
The Problem with Flat Page Tables
In a virtual memory system, a flat page table maps every virtual page number directly to a physical frame number using a single, contiguous array. For a 32-bit architecture with 4 KB (\(2^{12}\) bytes) pages, there are \(2^{32} / 2^{12} = 2^{20}\) virtual pages. If each page table entry (PTE) is 4 bytes, a flat page table requires \(2^{20} \times 4\text{ bytes} = 4\text{ MB}\) per process, which is manageable on modern systems.
On a 64-bit architecture, however, the address space grows exponentially. Even with a 48-bit virtual address space (common in x86-64 and ARM64 systems) and 4 KB pages, there are:
\[\frac{2^{48}}{2^{12}} = 2^{36}\text{ virtual pages}\]
If each PTE is 8 bytes, a single flat page table would require:
\[2^{36} \times 8\text{ bytes} = 2^{39}\text{ bytes} = 512\text{ GB}\]
Every running process would need 512 GB of contiguous physical RAM just for its page table, even for a tiny program that only uses a few megabytes of memory. For a full 64-bit virtual address space, the table size would be millions of terabytes.
How Multi-Level Page Tables Solve the Problem
Multi-level (or hierarchical) page tables split the virtual address into multiple index fields, forming a tree structure. For example, standard 4-level paging on x86-64 divides a 48-bit virtual address into four 9-bit page table indices and a 12-bit page offset (\(9 + 9 + 9 + 9 + 12 = 48\) bits).
Each level contains tables of 512 entries (\(2^9\)), where each entry is 8 bytes, making every individual page table exactly \(512 \times 8 = 4096\text{ bytes}\) (4 KB)—the exact size of a single physical page.
When a process starts, most of its virtual address space is unmapped. In a hierarchical structure:
- If an entire 512-entry subtree is unused, its parent entry is simply marked as not present.
- No memory is allocated for the lower-level tables of unused regions.
- A small process using only a few megabytes of memory might only need a handful of 4 KB page tables (tens of kilobytes total) instead of 512 GB.
Trade-offs of Hierarchical Paging
While multi-level page tables solve the memory overhead problem, they introduce a performance trade-off:
- Increased memory accesses: A Translation Lookaside Buffer (TLB) miss requires the hardware page table walker to perform multiple memory reads—one for each level of the hierarchy (e.g., 4 reads for 4-level paging, or 5 reads for 5-level paging)—before accessing the actual data.
- Mitigation via TLB and huge pages: Modern processors rely heavily on large, multi-level TLBs to cache recent translations and avoid page walks. Additionally, using larger page sizes (such as 2 MB or 1 GB huge pages) reduces the depth of the walk and increases TLB coverage.
Despite the extra latency on a TLB miss, multi-level page tables remain the standard approach in 64-bit classical computing because they make sparse, massive virtual address spaces practical within real physical memory limits.