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

Before we start, one shared picture. Every virtual address in these problems is a row of bits cut into named fields — the blue and yellow blocks together form the VPN, and the green block is the offset that rides through untouched. We reference this picture directly in Solutions 2.1 and 2.2, so study it now.

Figure — Page tables and multi-level paging

Definition The symbols we reuse (all earned in the parent)

$V$ = width of a virtual address in bits (e.g. 32 means the address is 32 binary digits).
$P$ = page size in bytes; $p = lo g_{2} P$ = number of offset bits (the low bits naming a byte inside a page).
$v = V - p$ = number of VPN bits (VPN = virtual page number, the "which page" part).
$≪$ means "shift left" (append zeros on the right — multiply by a power of two). $≫$ means "shift right" (drop the low bits off the right end — integer-divide by a power of two; it is the exact undo of $≪$ ). $∣$ means bitwise-OR (glue non-overlapping bit fields). See Bit Manipulation and Masking if these feel new.
$⌊ x ⌋$ = floor: round $x$ down to the nearest whole number (throw away any fraction). $a mod b$ = modulus: the remainder left after dividing $a$ by $b$ . Both are the plain "integer divide, keep the quotient / keep the remainder" operations — see Bit Manipulation and Masking for how they equal shifting and masking on powers of two.
A PTE (page table entry) is one row of a table: it stores a PFN (physical frame number) plus flag bits.

L1 — Recognition

Problem 1.1

A system has $V = 32$ -bit virtual addresses and page size $P = 4 KiB$ . State $p$ (offset bits), $v$ (VPN bits), and the number of entries a flat page table would need.

Recall Solution 1.1

WHAT we compute: the field widths, then the table length. WHY: $P = 4 KiB = 4096 = 2^{12}$ bytes. The number of bits to name a byte inside one page is exactly $lo g_{2}$ of how many bytes it holds: $p = lo g_{2} P = lo g_{2} 2^{12} = 12 bits.$ The rest of the address names the page: $v = V - p = 32 - 12 = 20 bits.$ A flat table has one entry per possible page, i.e. one per VPN value: $entries = 2^{v} = 2^{20} = 1048576 \approx 1 million.$ Answer: $p = 12$ , $v = 20$ , entries $= 2^{20}$ .

Problem 1.2

Match each item to what it stores: (a) the index into a page table, (b) a page table entry (PTE).

Recall Solution 1.2

WHAT/WHY: The parent's rule "position is the key, entry is the value" decides this.

(a) The index is the VPN (or the slice of VPN for that level) — it is implied by position, it stores nothing itself.
(b) The PTE stores the PFN + flags (valid, read/write, user/supervisor, dirty, accessed). Answer: index ↔ virtual page number (positional); PTE ↔ physical frame number + flags.

L2 — Application

Problem 2.1

$V = 32$ , $P = 4 KiB$ . For virtual address 0x00003FFF, compute the offset and the VPN.

Recall Solution 2.1

WHAT: split the address at bit $p = 12$ — exactly the green/coloured boundary in the shared picture (figure s01). WHY offset first: the low $p = 12$ bits are the offset (the green block); masking them off leaves the VPN (the blue+yellow blocks). See Bit Manipulation and Masking. Recall from the symbol list that $a mod b$ keeps the remainder and $⌊ \cdot ⌋$ keeps the whole-number quotient: $offset = addr mod P = 0x00003FFF mod 0x1000 .$ 0x00003FFF = 0x3 * 0x1000 + 0xFFF, so offset $= 0xFFF = 4095$ (the remainder). $VPN = ⌊ \frac{addr}{P} ⌋ = 0x00003FFF ≫ 12 = 0x3 = 3.$ Here $≫ 12$ (shift right by 12, from the symbol list) drops the 12 offset bits off the right end — the exact undo of building the address with $≪ 12$ . Answer: offset $= 0xFFF = 4095$ , VPN $= 3$ .

Problem 2.2

Same system. Two-level split 10 / 10 / 12 ( $i_{1}$ = top 10 bits, $i_{2}$ = next 10, offset = 12). For virtual address 0x00801234, find $i_{1}$ , $i_{2}$ , offset. If L2[i2].PFN = 0x000AB, give the final physical address.

Recall Solution 2.2

WHAT: carve the address into three fields — literally the blue $i_{1}$ , yellow $i_{2}$ , green offset blocks of the shared picture (figure s01) — then reassemble the physical address. Write the address in binary. 0x00801234: $0x00801234 = 0000000010000000000100100011010 0_{2} .$ Offset = low 12 bits = 0001 0010 0011 0100... take the last 12: 0010 0011 0100 $= 0x234$ . WHY: $p = 12$ , so 12 low bits ride through unchanged. The remaining top 20 bits are 0000 0000 1000 0000 0001 $= 0x00801$ . Split those 20 bits into $i_{1}$ (top 10) and $i_{2}$ (next 10):

top 10: 0000 0000 10 $= 2$ , so $i_{1} = 2$ .
next 10: 00 0000 0001 $= 1$ , so $i_{2} = 1$ . Final PA: glue the delivered PFN to the untouched offset: $PA = (PFN ≪ p) ∣ offset = (0x000AB ≪ 12) ∣ 0x234 = 0x000AB234 .$ Answer: $i_{1} = 2$ , $i_{2} = 1$ , offset $= 0x234$ , PA $= 0x000AB234$ .

L3 — Analysis

Problem 3.1

For $V = 32$ , $P = 4 KiB$ , a flat table uses 4 MiB (with 4-byte PTEs). Explain why the 10/10/12 two-level split makes each table exactly one page — and show the arithmetic.

Recall Solution 3.1

WHAT: count entries per table and multiply by PTE size. Each 10-bit index selects one of $2^{10} = 1024$ entries. With 4-byte PTEs: $table size = 2^{10} \times 4 B = 4096 B = 4 KiB = P .$ WHY this is elegant: a table that is exactly one page can itself be paged, allocated, and swapped by the very same machinery it describes — no special "big region" is needed. The 10/10/12 numbers are chosen precisely so $2^{10} \times 4 = P$ . Answer: each level's table = $1024 \times 4 B = 4 KiB =$ one page.

Problem 3.2

A process uses exactly one code page and one stack page, far apart in the address space. Compute the total page-table memory for (a) flat, (b) two-level 10/10/12. State why they differ.

Recall Solution 3.2

WHAT: sum the tables actually allocated. (a) Flat: the table is fixed-size regardless of usage: $2^{20} entries \times 4 B = 4 MiB = 4194304 B .$ (b) Two-level: you always need the one top table (4 KiB). Code and stack are "far apart," so they fall under different top-level entries ⇒ two inner tables (4 KiB each): $1 \times 4 KiB + 2 \times 4 KiB = 3 \times 4096 = 12288 B = 12 KiB .$ WHY they differ: the flat table pre-reserves a slot for all $2^{20}$ pages even though almost all are untouched. Concretely: the top table has $2^{10} = 1024$ slots; the process uses only $2$ of them, leaving $1022$ unused top-level slots. Each of those $1022$ slots would have pointed to an inner table of $1024$ entries, i.e. it stands in for $1022 \times 1024 = 1046528$ page-entries that the flat table reserves but the tree never allocates. The tree marks those $1022$ unused top entries invalid, allocating no inner table for them (see Page Faults and Demand Paging for what "invalid" triggers on access). Answer: flat $= 4194304 B$ ; two-level $= 12288 B$ .

L4 — Synthesis

Problem 4.1

A 64-bit machine uses $P = 4 KiB$ and a four-level page table with a 48-bit usable virtual address (like x86-64), each level a 9-bit index. Verify the field widths add up, and compute how many RAM accesses a full walk needs, then the total to actually read the target byte.

Recall Solution 4.1

WHAT: check $9 + 9 + 9 + 9 + 12 = 48$ , then count accesses. Offset bits: $p = lo g_{2} 4096 = 12$ . Four index levels of 9 bits each: $9 + 9 + 9 + 9 + 12 = 48 = V_{usable} . ✓$ WHY 9-bit levels: $2^{9} \times 8 B = 512 \times 8 = 4096 B = P$ — each table is one page (64-bit PTEs are 8 bytes). Same "table = one page" trick as L3. Walk cost: each level is one memory read to fetch the next-level pointer, so a 4-level walk = 4 reads. Then one more read for the actual data byte: $total accesses (TLB miss) = 4 + 1 = 5.$ Answer: widths sum to 48; walk = 4 reads; total to reach data = 5 reads.

Problem 4.2

Using the model $avg = t_{T L B} + (miss rate) \times (walk cost)$ , suppose $t_{T L B} = 1$ cycle, walk cost $= 4$ memory reads $\times$ 100 cycles/read $= 400$ cycles, and the TLB miss rate is $2% = 0.02$ . Compute the average translation time. Then find the miss rate that would double it.

Recall Solution 4.2

Term note: here "walk cost" means only the page-table reads that find the frame — the 4 translation accesses of Problem 4.1, not the final data fetch. The data read is a separate cost that happens after translation regardless, so it does not belong in a translation-time model. (If you ever include it, say "translation + data" = 5 reads, as in Problem 4.1.) WHAT: plug in, then invert for the target. $avg = 1 + 0.02 \times 400 = 1 + 8 = 9 cycles.$ Doubling means target $= 18$ cycles. Solve for the miss rate $m$ : $18 = 1 + m \times 400 \Rightarrow m = \frac{17}{400} = 0.0425 = 4.25%.$ WHY this matters: the walk cost dominates whenever the miss rate is non-tiny, which is why the TLB exists — see Cache Memory Basics for the same "hit fast / miss slow" trade-off. Answer: avg $= 9$ cycles; doubling needs miss rate $= 0.0425$ ( $4.25%$ ).

L5 — Mastery

Problem 5.1

You are designing paging for a new 32-bit CPU. You may pick page size $P \in {4 KiB, 16 KiB}$ and 1, 2, or 3 levels. Requirement: every table must fit in exactly one page, PTEs are 4 bytes. For $P = 16 KiB$ , how many entries fit in one page-table page, how many index bits is that, and does a clean 2-level design cover all $V = 32$ bits? Show the split.

Recall Solution 5.1

WHAT: derive the per-page index width, then fit the levels to $V$ . $P = 16 KiB = 2^{14}$ bytes ⇒ offset $p = 14$ bits, VPN $v = 32 - 14 = 18$ bits. Entries per one-page table: $\frac{P}{PTE size} = \frac{2 ^{14}}{4} = \frac{16384}{4} = 4096 = 2^{12}$ entries, i.e. a 12-bit index per level. Can 2 levels cover 18 VPN bits? Two 12-bit indices give $12 + 12 = 24$ bits of indexing capacity — more than the $18$ we need, so yes, comfortably. A clean split uses one full 12-bit level and a smaller top level: $v = 18 = i_{1} 6 + i_{2} 12, address = [i_{1} : 6 ∥ i_{2} : 12 ∥ offset : 14] .$ WHY the top level is only 6 bits: the top table then uses just $2^{6} = 64$ of its 4096 possible slots — it doesn't have to be full; unused high slots are simply marked invalid. This is legal because indexing capacity ( $24$ ) $\geq$ VPN width ( $18$ ). Answer: $P = 16 KiB$ ⇒ 4096 entries/page = 12-bit index; 2 levels (12+12=24 ≥ 18) suffice; split $6/12/14$ .

Problem 5.2

Defend or refute: "For this same 32-bit, $P = 16 KiB$ machine, a single-level flat table is now perfectly reasonable — no tree needed." Back it with a size calculation and one design caveat.

Recall Solution 5.2

WHAT: size the flat table, then judge. Flat table entries $= 2^{v} = 2^{18} = 262144$ . With 4-byte PTEs: $size = 2^{18} \times 4 = 262144 \times 4 = 1048576 B = 1 MiB per process.$ Verdict — partly defensible: 1 MiB is far smaller than the 4 KiB-page case's 4 MiB, because bigger pages mean fewer pages to track ( $v$ dropped from 20 to 18, and each page covers 4× more memory). For a machine with few processes, 1 MiB flat can be acceptable. Caveat (why we still prefer a tree): the flat 1 MiB is allocated whole even for a process touching two pages; a $6/12/14$ tree would need only top table $+$ used inner tables. And 16 KiB pages waste memory via internal fragmentation (a 1-byte allocation still burns a 16 KiB frame). Trade-off is space-vs-space here, not the usual space-vs-time. Answer: flat table $= 1048576 B = 1 MiB$ ; defensible for low process counts but the tree still wins on sparse usage; 16 KiB pages raise internal fragmentation.

Recall One-line summaries to self-quiz

Offset bits from page size ::: $p = lo g_{2} P$ . Flat 32-bit / 4 KiB table size ::: $2^{20} \times 4 B = 4 MiB$ . Two-level, 1 code + 1 stack page ::: $\approx 12 KiB$ (top + 2 inner tables). x86-64 4-level walk memory reads (miss) ::: 4 to translate, 5 including the data read. What a tree buys vs what a TLB buys ::: tree buys space, TLB buys time.

Parent: Page tables and multi-level paging · See also Address Space Layout, Virtual Memory, TLB and Translation Caching.