Page tables and multi-level paging: Question bank — Hardware deep dive

Intuition How to use this bank

This is the concept-trap child of the parent note. Each line is a question, then :::, then the answer. Cover the right side, say your reasoning out loud in full sentences, then reveal. If your answer was "yes/no" with no why, you got it wrong — the whole point here is the justification.

Before you start, make sure these words feel solid (build them from the parent if not): a page is a fixed-size block of the virtual address space; a frame is the same-size block of physical RAM; the VPN (virtual page number) is the high bits of an address that name which page; the offset is the low bits that name a byte inside the page; a PTE (page table entry) is one row holding a PFN (physical frame number) plus flags. If any of these are fuzzy, revisit Virtual Memory and Address Space Layout first.

True or false — justify

Every line: decide true/false, then explain in one breath.

A flat (single-level) page table is smaller than a two-level table for a process using all of its address space.

True — if every page is used, the tree adds overhead (inner-table pointers, extra top table) with no empty branches to prune, so the flat table is leaner. The tree only wins when the address space is sparse.

Multi-level paging makes a single translation faster than a flat table.

False — each level is one more sequential RAM read, so a walk is slower, not faster. The tree buys memory savings; the TLB is what buys back speed.

The offset field is transformed during translation.

False — because a page and a frame have the same size

P

, byte

k

inside a page is byte

k

inside its frame, so the low

p = lo g_{2} P

bits are copied verbatim. Only the page/frame number changes.

Every level of a multi-level table indexes using the full VPN.

False — the VPN is partitioned into disjoint slices, one per level. Level 1 uses only its slice

i_{1}

, level 2 uses only

i_{2}

, and so on; no level sees the whole VPN.

A page table entry stores the virtual page number it maps from.

False — the VPN is encoded implicitly by the array position (the index). The entry stores only the PFN plus flags. Position is the key, contents are the value.

Increasing the number of levels always saves memory.

False — more levels help only if the address space is sparse. For a densely-used space, extra levels add table overhead. There is a sweet spot; blindly adding levels can cost memory and definitely costs walk time.

Two processes can safely share the same physical frame while keeping separate page tables.

True — each process's PTE can point at the same PFN, giving shared memory or shared libraries. Isolation lives in which pages each table exposes, not in the frames themselves.

If a page is 4 KiB, the offset is always 12 bits regardless of address width.

True — the offset counts bytes inside one page, so it depends only on page size:

p = lo g_{2} 4096 = 12

. The address width

V

only changes how many bits are left for the VPN.

A larger page size reduces page-table size.

True — bigger pages mean fewer pages to describe, hence fewer PTEs (more offset bits, fewer VPN bits). The trade-off is coarser granularity and more internal fragmentation (wasted bytes inside partly-used pages).

The TLB stores data from memory.

False — the TLB caches VPN → PFN translations, not the actual data bytes. The data lives in the data cache / RAM; the TLB just tells you where.

Spot the error

Each statement contains one flaw. Name it and correct it.

"To translate, mask off the high bits of the address and look up the low bits in the table."

Backwards — you keep the low bits (offset) unchanged and translate the high bits (VPN). The correct move is: index the table with the VPN, then append the untouched offset. See Bit Manipulation and Masking.

"The physical address equals PFN times VPN."

Wrong operation — the physical address is

(PFN \times P) + offset

, i.e. (PFN << p) | offset. The VPN is only used to find the PFN; it never appears in the final address arithmetic.

"With a 10/10/12 split, each inner table holds 4 KiB worth of entries because 10 bits addresses 4096 entries."

Miscount — 10 index bits address

2^{10} = 1024

entries, not 4096. At 4 bytes each that is

1024 \times 4 = 4

KiB, which happens to equal one page — the reasoning lands on the right size via the wrong entry count.

"An invalid PTE still points to a real frame; the OS just refuses to use it."

Wrong — an invalid PTE points to nothing; its PFN field is meaningless and no frame is allocated. Touching such a page triggers a page fault, which may then allocate a frame.

"A TLB miss means the data isn't in memory, so it causes a page fault."

Conflates two mechanisms — a TLB miss only means the translation wasn't cached; you then walk the page table. A page fault happens only if the walk finds an invalid PTE. A TLB miss on a valid mapping just does a walk and moves on.

"Since the top-level table has 1024 entries, a two-level scheme can map at most 1024 pages."

Wrong — each of the 1024 top entries points to a full inner table of another 1024 entries, so the reach is

1024 \times 1024 = 2^{20}

pages. You multiply the levels, not add them.

Why questions

Answer with the reason, not just the fact.

Why does a flat 32-bit page table cost 4 MiB even for a tiny program?

Because a flat table reserves one entry per possible page (

2^{20}

entries × 4 B), whether or not the page is used. It cannot skip unused ranges — that's exactly the flaw the tree fixes.

Why is 4 KiB such a common page size?

With 4-byte PTEs, a 4 KiB table holds exactly

2^{10} = 1024

entries, and a 10-bit index fills exactly one page — so each table fits perfectly in one frame, simplifying allocation and alignment.

Why must the page-table base (e.g. x86 CR3) be a physical address?

Because the base is the starting point of translation itself — if it were virtual, you'd need to already have a translation to find it, an infinite regress. Translation must bottom out on a physical anchor.

Why does a sparse address space let the tree save so much memory?

Because unused top-level entries are marked invalid and point to no inner table — the entire subtree of

2^{v_{2}}

potential entries is simply not allocated. You pay only for branches you actually walk.

Why does adding a level multiply memory reads per translation?

Each level lives in RAM, and you must read one level to learn the address of the next. The reads are strictly sequential (a dependency chain), so

n

levels means

n

reads before you even touch the data.

Why doesn't the TLB need to store the offset?

Because the offset is never translated — it rides through unchanged. The TLB only needs to cache the part that does change: VPN → PFN. The offset is reattached afterward.

Why can two virtual addresses in different processes map to the same VPN yet different physical frames?

Because each process has its own page table; the same VPN indexes into different tables holding different PFNs. That's precisely how isolation works — identical virtual layouts, disjoint physical backing.

Edge cases

The boundary and degenerate scenarios the topic quietly assumes you'll handle.

What is the "page number" of virtual address 0?

VPN 0, offset 0 — it's the very first byte of the very first page. Nothing special about translation; but many systems deliberately leave page 0 unmapped so that dereferencing a null pointer faults.

What happens for the last byte of a page, at offset

P - 1

It translates fine — offset

P - 1

is the maximal in-page offset and still fits the

p

offset bits. The next byte rolls into offset 0 of the next VPN, possibly a different (or unmapped) frame.

If page size equals the whole address space, how many levels do you need?

Zero page-number bits remain — the entire address is offset, so there is exactly one page and no translation table is needed. The degenerate limit of paging.

If the page size were 1 byte, what happens?

Then

p = 0

: there is no offset, every byte is its own page, and the VPN is the full address — the table becomes as large as memory itself. This is why tiny pages are absurd; it shows the offset's whole purpose is to amortize one PTE over many bytes.

What does a walk do when a mid-level (not final) PTE is invalid?

It stops immediately and raises a page fault — there's no inner table to descend into, so the entire subtree under that entry is absent. You never reach the final level.

Can the same physical frame appear in a page table twice (two VPNs → one PFN)?

Yes — this is aliasing, used for shared memory or copy-on-write. It's legal but demands care: a write via one VPN is visible via the other, and caches must handle the two virtual names of one frame.

What if a virtual address's high bits index past the valid part of the top table?

On real hardware the index simply selects a top-level entry that is marked invalid (or the address is rejected as non-canonical on 64-bit). Either way translation fails with a fault — there's no "out of bounds" wraparound.

Active Recall

Which does multi-level paging optimize, time or space?

Space — it avoids allocating tables for unused ranges, at the cost of more memory reads per walk.

Where do the offset bits go during translation?

They are copied verbatim into the physical address; only the VPN → PFN part is translated.

What is stored at a PTE versus encoded by its position?

The position encodes the VPN (implicit key); the entry stores the PFN plus flags (the value).

What recovers the speed lost to a multi-level walk?

The TLB, which caches recent VPN → PFN mappings so most translations skip the walk entirely.

Why must the page-table base register hold a physical address?

Otherwise translating it would itself need a translation — an infinite regress; translation must anchor on physical memory.