Virtual memory and paging: Exercises — Hardware deep dive

Before we start, one picture ties every problem together — the anatomy of an address.

Recall The three operations you will reuse everywhere

Let page size be $P = 2^{p}$ bytes. For a virtual address $A$ :

offset $= A mod 2^{p} = A & (2^{p} - 1)$ — the low $p$ bits (what byte inside the page).
VPN $= ⌊ A / 2^{p} ⌋ = A ≫ p$ — the high bits (which page).
Rebuild: $PA = (PFN ≪ p) ∣ offset$ .

Everything below is these three lines applied with care.

Level 1 — Recognition

Exercise 1.1

Which of these is translated by the MMU, and which is copied unchanged: the VPN or the offset?

Recall Solution

The VPN is translated (it becomes a PFN by looking it up in the page table). The offset is copied unchanged.

Why: moving a page into a frame is a rigid shift — byte 5 of the page is still byte 5 of the frame. Only the base changes. Look at figure s01: the yellow offset bits pass straight through, the coloured VPN bits go through the table.

Exercise 1.2

A system uses 4 KiB pages. How many bits is the offset, and what is $p$ ?

Recall Solution

$4 KiB = 4 \times 1024 = 4096 = 2^{12}$ bytes. So $p = 12$ and the offset is 12 bits.

Why: the offset must be able to name every byte inside one page. With $2^{12}$ bytes per page, you need exactly $12$ bits to count $0$ through $4095$ .

Level 2 — Application

Exercise 2.1

Page size $= 4 KiB$ ( $p = 12$ ). The virtual address is $VA = 0x2C4F7$ . Split it into VPN and offset.

Recall Solution

Low $12$ bits $=$ last three hex digits (each hex digit is $4$ bits, so $3 \times 4 = 12$ ). $offset = 0x2C4F7 & 0xFFF = 0x4F7$ $VPN = 0x2C4F7 ≫ 12 = 0x2C$ Why the last-3-digits shortcut: shifting right by $12$ bits is the same as dropping the last $12/4 = 3$ hex digits. So VPN $= 0x2C$ , offset $= 0x4F7$ .

Exercise 2.2

Continuing 2.1: the page table maps VPN $0x2C \to$ PFN $0x5$ . What is the physical address?

Recall Solution

$PA = (PFN ≪ 12) ∣ offset = (0x5 ≪ 12) ∣ 0x4F7 = 0x5000 ∣ 0x4F7 = 0x54F7$ Why shift the PFN by 12: frame number $f$ begins at physical byte $f \times 2^{12}$ . Shifting left by $12$ builds that base address ( $0x5000$ ); ORing the untouched offset lands on the exact byte.

Level 3 — Analysis

Exercise 3.1

A machine has a $32$ -bit virtual address, $4 KiB$ pages, and each page-table entry is $4$ bytes. Compute the number of entries and the total size of a single-level page table per process.

Recall Solution

Entries $= \frac{2 ^{32}}{2 ^{12}} = 2^{20} = 1, 048, 576$ (about a million). Why: one entry per virtual page; there are (address-space size)/(page size) pages. $Table size = 2^{20} \times 4 bytes = 2^{22} bytes = 4 MiB per process$ Why care: with $100$ processes that is $400 MiB$ of RAM spent purely on translation tables — the pressure that motivates Multi-level page tables.

Exercise 3.2

$t_{m e m} = 100 ns$ , $t_{T L B} = 1 ns$ , TLB hit ratio $h = 0.98$ (single-level table). Find the effective access time (EAT).

Recall Solution

Rebuild the formula: on a hit, pay TLB + memory. On a miss, pay TLB + one table walk ( $t_{m e m}$ ) + the real access ( $t_{m e m}$ ). $EAT = h (t_{T L B} + t_{m e m}) + (1 - h) (t_{T L B} + t_{m e m} + t_{m e m}) = t_{T L B} + t_{m e m} + (1 - h) t_{m e m}$ $= 1 + 100 + (0.02) (100) = 1 + 100 + 2 = 103 ns$ Why only $+ 2$ ns: the extra table walk is only paid by the $2%$ of accesses that miss the TLB. Averaged over all accesses, that's $0.02 \times 100 = 2 ns$ . This is why the TLB, exploiting Locality of reference, makes translation nearly free.

Level 4 — Synthesis

Exercise 4.1

A two-level page table on a $32$ -bit machine with $4 KiB$ pages splits the $20$ -bit VPN into a $10$ -bit outer index and a $10$ -bit inner index. A process uses only its first $4 KiB$ of virtual memory (one page). Count the page-table memory actually needed, assuming $4$ -byte entries and that each table (outer or inner) fits in one $4 KiB$ page.

Recall Solution

Why split the VPN: so we only allocate inner tables for regions the process actually touches. See figure s02 — the outer table has $2^{10}$ slots but only one points to a real inner table.

The outer table always exists: $2^{10}$ entries $\times 4$ bytes $= 4096$ bytes $= 4 KiB$ .
Exactly one inner table is needed (the process touches one page, which lives under one outer slot): another $2^{10} \times 4 = 4 KiB$ . $Total = 4 KiB + 4 KiB = 8 KiB$ Why this crushes the single-level cost: single-level needed $4 MiB$ (Ex 3.1). Two-level needs $8 KiB$ for a sparse process — a $512 \times$ saving. Unused outer slots simply stay empty (no inner table allocated).

Exercise 4.2

Same machine (two levels, $t_{m e m} = 100 ns$ , $t_{T L B} = 1 ns$ ). On a TLB miss the MMU must walk both levels (two memory reads) before the real access. With hit ratio $h = 0.98$ , find EAT.

Recall Solution

Why two extra reads: a miss now reads the outer table (1 access) then the inner table (1 access) to get the PFN, then the real data. $EAT = h (t_{T L B} + t_{m e m}) + (1 - h) (t_{T L B} + 2 t_{m e m} + t_{m e m})$ $= 1 + 100 + (0.02) (2 \times 100) = 1 + 100 + 4 = 105 ns$ Why only $+ 4$ vs $+ 2$ before: the deeper walk costs $2 t_{m e m} = 200 ns$ instead of $100 ns$ , but it is still only paid by the $2%$ that miss: $0.02 \times 200 = 4 ns$ . Locality keeps even a taller tree cheap.

Level 5 — Mastery

Exercise 5.1

Design check. You must support a $48$ -bit virtual address space with $4 KiB$ pages, and you want each page table (at every level) to fit in exactly one $4 KiB$ page, using $8$ -byte entries. How many levels does the page table need?

Recall Solution

Step 1 — offset. $p = 12$ , so the VPN is $48 - 12 = 36$ bits. Step 2 — how many index bits per level. One $4 KiB$ page holds $\frac{2 ^{12} bytes}{8 bytes/entry} = 2^{9} = 512$ entries, so each level consumes $9$ VPN bits. Step 3 — divide. Levels $= \frac{36 VPN bits}{9 bits/level} = 4$ levels. Answer: 4 levels (this is exactly real x86-64's 4-level scheme, PML4 → PDPT → PD → PT). Why it works out whole: $36$ is divisible by $9$ ; if it weren't, the top level would use fewer bits (a partially-filled table).

Exercise 5.2

Capstone. On that $48$ -bit, $4$ -level machine ( $t_{m e m} = 100 ns$ , $t_{T L B} = 1 ns$ ), a program strides through a huge array touching a fresh page almost every access, so the TLB hit ratio collapses to $h = 0.10$ . Compute EAT, and state in one sentence which principle the program violated.

Recall Solution

A miss now walks four levels ( $4 t_{m e m}$ ) then does the real access: $EAT = h (t_{T L B} + t_{m e m}) + (1 - h) (t_{T L B} + 4 t_{m e m} + t_{m e m})$ Plug in $h = 0.10$ : $= 0.10 (1 + 100) + 0.90 (1 + 400 + 100)$ $= 0.10 (101) + 0.90 (501) = 10.1 + 450.9 = 461 ns$ That's over $4.6 \times$ slower than the $100 ns$ raw memory time. Principle violated: poor locality of reference — by touching a new page every access, the program defeats the TLB (see Locality of reference), so almost every access pays the full $4$ -level walk.

Recall

Recall One-line self-test

Which part of a VA is translated? ⟶ the VPN; the offset is copied.
Single-level table entries for $32$ -bit VA, $4 KiB$ pages? ⟶ $2^{20}$ ( $4 MiB$ ).
EAT formula, single level? ⟶ $t_{T L B} + t_{m e m} + (1 - h) t_{m e m}$ .
Why do multi-level tables save memory? ⟶ inner tables are allocated lazily, only for used regions.
Levels for $48$ -bit VA, $4 KiB$ pages, $8$ -byte entries, $4 KiB$ tables? ⟶ $4$ .