What is a Multilevel Page Table?
Learn how multilevel page tables save memory over flat tables, the translation walk, and why x86-64 uses 4-5 levels.
Expected Interview Answer
A multilevel page table splits a single flat page table into a hierarchy of smaller tables, where the virtual address is broken into multiple index fields that walk down each level, so unused regions of the address space never need any table allocated at all, drastically cutting memory overhead.
Instead of one giant array indexed by the full virtual page number, a two-level scheme (as classic x86 uses) splits the virtual address into a top-level directory index, a second-level table index, and a page offset; the MMU first indexes the top-level directory to find the physical address of a second-level table, then indexes that second-level table to find the actual frame number, and only allocates a second-level table for regions of the address space a process actually uses. This means a process with a small, sparse address space — most of it unused between the stack, heap, and code — pays for only the page-table entries it needs, rather than every possible virtual page in the space. The tradeoff is that translation now requires multiple sequential memory accesses instead of one direct array index, which is exactly the extra cost the TLB exists to hide on the common case of a cache hit. Modern 64-bit systems extend this to four or five levels (like x86-64's PML4/PDPT/PD/PT hierarchy) precisely because the address space is so vast that even a two-level scheme would still waste memory on unused regions.
- Avoids allocating page table space for unused regions of the address space
- Scales page table memory with actual usage rather than address space size
- Explains why the TLB is essential to hide multi-step translation cost
- Foundation for understanding real x86-64 4/5-level paging
AI Mentor Explanation
A multilevel page table is like a national cricket board keeping a top-level directory of which states actually field teams, and only within active states keeping a second-level directory of which specific clubs actually field teams, rather than pre-printing a roster slot for every conceivable club in every state whether or not it exists. Looking up a specific player requires first finding the state directory, then the club directory within it — two lookups instead of one giant flat roster. States and clubs that never fielded a team simply never get a directory page allocated, saving enormous paper.
Step-by-Step Explanation
Step 1
Split virtual address
The virtual address is divided into a top-level index, a second-level index, and a page offset.
Step 2
Walk top level
The top-level index looks up the directory entry pointing to a second-level table, if one is allocated.
Step 3
Walk second level
The second-level index looks up the actual physical frame number within that table.
Step 4
Combine with offset
The frame number is combined with the page offset to form the final physical address.
What Interviewer Expects
- Clear explanation of splitting the virtual address into multiple index fields
- Understanding that unused regions skip table allocation entirely
- Awareness of the extra memory-access cost per translation and the TLB's role
- Knowledge that real 64-bit systems use 4-5 levels, not just 2
Common Mistakes
- Thinking a multilevel table is slower with no memory-saving benefit
- Confusing multilevel with inverted page tables
- Not knowing why sparse address spaces motivate this design
- Forgetting the TLB is what makes the extra lookup steps affordable
Best Answer (HR Friendly)
“A multilevel page table breaks one giant lookup table into a hierarchy of smaller tables, so the operating system only has to allocate table space for the parts of a program's memory that are actually being used, instead of reserving space for the entire theoretical address range up front. It costs a bit more time per lookup since there are multiple steps involved, but that is exactly why the fast TLB cache exists to make that cost disappear on most accesses.”
Code Example
#define PDE_BITS 10
#define PTE_BITS 10
#define OFFSET_BITS 12
struct pte { unsigned frame; int present; };
struct pte *page_dir[1 << PDE_BITS]; /* array of pointers, many left NULL */
unsigned translate(unsigned vaddr) {
unsigned pd_idx = (vaddr >> (PTE_BITS + OFFSET_BITS)) & ((1 << PDE_BITS) - 1);
unsigned pt_idx = (vaddr >> OFFSET_BITS) & ((1 << PTE_BITS) - 1);
unsigned offset = vaddr & ((1 << OFFSET_BITS) - 1);
struct pte *table = page_dir[pd_idx];
if (table == 0) handle_page_fault(vaddr); /* whole region unmapped */
if (!table[pt_idx].present) handle_page_fault(vaddr);
return (table[pt_idx].frame << OFFSET_BITS) | offset;
}Follow-up Questions
- How many page table levels does x86-64 use, and why?
- How does a multilevel table save memory compared to a flat table for a sparse address space?
- What is the performance cost of a multi-level walk, and how does the TLB offset it?
- How would you compare a multilevel page table to an inverted page table?
MCQ Practice
1. What is the main advantage of a multilevel page table over a flat page table?
Multilevel tables only allocate lower-level tables for regions actually in use, saving memory for sparse address spaces.
2. What is the main cost of a multilevel page table versus a flat one?
Each level adds a memory access to the translation path on a TLB miss, which the TLB exists to hide on the common hit case.
3. How many levels of page tables does x86-64 typically use?
Classic x86-64 uses a 4-level hierarchy (PML4, PDPT, PD, PT), extended to 5 levels on newer CPUs supporting 5-level paging.
Flash Cards
What is a multilevel page table? — A hierarchy of smaller page tables that only allocates entries for regions of the address space actually in use.
Why does it save memory over a flat table? — Unused regions of the address space never get a lower-level table allocated.
What is the tradeoff of multilevel tables? — Translation requires multiple sequential memory accesses instead of one, mitigated by the TLB.
How many levels does x86-64 use? — 4 levels classically (PML4/PDPT/PD/PT), extendable to 5 on newer hardware.