Noesis
4.2.26 · D5Operating Systems

Question bank — Multi-level page tables — why, overhead

1,558 words7 min read↑ Back to topic
🇮🇳 Yeh page Hinglish mein padho →

Quick vocab refresher so nothing below is a surprise:

  • VPN = virtual page number, the "which page" part of a virtual address.
  • PFN = physical frame number, the "which slot in real RAM" part.
  • PTE = page table entry, one row that stores a PFN plus flags (present, dirty, ...).
  • L1 / directory = top table; L2 = second-level table it points to.
  • Walk = the act of reading each level of the tree, in order, to translate one address.
  • TLB = a tiny cache of recent VPN→PFN answers.

True or false — justify

Multi-level page tables always use less memory than a flat table.
False. If a process touches its entire address space, every L2 table must exist anyway, and you pay an extra directory page on top — so it is slightly larger. The saving only appears when the table is sparse.
A "not present" entry in the directory means one specific page is missing from RAM.
False. A not-present directory entry means an entire L2 table (a whole region of pages) was never allocated at all. Not-present at the leaf PTE level is what means a single page is absent.
Splitting the virtual address into more levels increases the total address space you can map.
False. The address space is fixed by , the number of virtual-address bits. Splitting only reorganises the same bits into stages; it changes storage layout, not reach.
For a -level table, every memory reference costs memory accesses.
False in practice. It costs only on a TLB miss. A TLB hit supplies the PFN directly, so the reference costs about one access — which is the common case under good locality.
Making the page table 3-level instead of 2-level makes the best-case memory footprint bigger.
True. Each extra level adds another mandatory top table on the path to any used region, so the minimum "just one page in use" cost grows by one page per level.
The page offset bits are transformed during translation.
False. The offset is copied through unchanged; only the VPN (the upper bits) is looked up. Translation replaces which page, never where inside the page.
A TLB permanently removes the multi-level walk cost.
False. A TLB miss still pays the full -level walk. Context switches, huge working sets, or TLB flushes bring the walk cost right back.
If two levels use 10 bits each, both tables must hold the same number of entries.
True (of entry count), but watch the trap. entries each. They hold different kinds of entries though: L1 entries point to tables, L2 entries point to frames.
A flat page table and a fully-populated multi-level table store the same number of leaf PTEs.
True. Both need one leaf PTE per virtual page; the multi-level version just adds directory pages above them. The leaf count is identical.

Spot the error

"Address space ."
Wrong. Bits add, sizes don't multiply like that. , and address space is . Levels are about splitting the VPN, not scaling the space.
"We chose 10/10/12 for 32-bit paging to make the directory as small as possible."
Wrong reason. The 10 for L2 is chosen so an L2 table () fits exactly one page, making it easy to allocate and swap. The directory size just falls out of the remaining bits.
"Worst-case multi-level overhead is , same as flat, so it's a wash."
Missing a term. You forgot the directory page: . It's slightly worse than flat in the worst case, not equal.
"Every process gets a bigger page table with multi-level, so it wastes RAM."
Wrong. Real processes use a tiny sparse slice of their address space, so almost all L2 tables are never created — a typical process needs a handful of pages of tables, not megabytes.
"With a 98% TLB hit rate on a 2-level table, the average reference costs ."
Wrong. That's the miss-only cost. Blend them: . The whole point of the TLB is that the 3× cost is rare.
"A not-present PTE and an invalid PTE waste the same amount of memory."
Sloppy. Both entries occupy one PTE slot, but the real memory story is about whether the L2 table itself exists. Sparsity savings come from skipping whole tables, not from individual entry flags.

Why questions

Why does a single flat table waste memory even though it's "just a list"?
Because it reserves one PTE for every possible virtual page, present or not — a 32-bit space forces entries () even if the process touches a few dozen pages.
Why does multi-level turn sparsity into savings?
An unused region collapses to a single "not present" directory entry, and its entire L2 table is simply never allocated. Empty regions cost one entry instead of thousands.
Why do we deliberately size an L2 table to fit exactly one page?
So the OS can allocate, free, and swap a page table with the same machinery it uses for ordinary pages — no special-case memory management.
Why does deeper paging (like x86-64's 4 levels) not cripple performance?
Because locality keeps translations in the TLB, and large pages shorten walks. The 5-access worst case is rare in steady-state execution.
Why is time overhead considered "the real cost," not space?
Space savings are guaranteed by sparsity, but each level lives in memory and must be read to walk the tree — turning one access into . That latency is what the TLB exists to hide.
Why do inverted page tables exist if multi-level already saves space?
Inverted tables size the structure by physical memory instead of per-process virtual space, so their cost doesn't grow with the number of processes — a different trade-off, not a strict improvement.

Edge cases

A process that touches exactly one page: how many page-table pages exist?
Two — one directory (L1) and one L2 table. That's versus flat, roughly a 500× win from a single not-present pattern in the directory.
A process that uses its entire address space: better or worse than flat?
Worse, but only barely. You need every L2 table plus the extra directory page: vs . Multi-level's edge cases confirm it only wins when sparse.
TLB hit rate drops to 0 (cold cache after a flush): what does each reference cost?
The full walk on every reference: accesses. For a 2-level table that's 3 memory accesses per reference until the TLB warms up again.
Zero-sized PTE or zero index bits at a level — is that meaningful?
No. A level with zero index bits does nothing (it can address only one entry), and a zero-size PTE can't store a PFN. Every level must have index bit and PTEs wide enough to hold a frame number plus flags.
What happens at the boundary where a used region spans two directory entries?
Both directory entries become present and each gets its own L2 table. A region straddling the split costs two L2 tables even if only a few pages near the boundary are actually used.
If page size doubles (bigger pages), what happens to the number of levels needed?
More offset bits ( grows), so fewer VPN bits remain to split — you may need fewer levels, and each L2 table still fits one (now larger) page. Large pages are a standard way to shorten walks.
Recall One-sentence self-test

If you can explain why "multi-level always saves memory" is false, why the offset never changes, and why a TLB miss resurrects the full walk cost — you own this topic. Where do all the memory savings actually come from? ::: From never allocating L2 tables for unused (sparse) regions, not from the tree structure itself.

Connections