Virtual memory and paging: Worked examples — Hardware deep dive

This page is the "no surprises" drill. The parent note taught you the machinery of address translation; here we hit every kind of number that machinery can be fed — clean cases, edge cases, degenerate cases, and the sneaky exam twists — so that when one shows up on paper you've already seen its twin.

Everything here rests on three ideas from the parent that we will re-use constantly, so let's re-anchor them in one breath (no new symbol without a picture):

Look at the figure: an address is a ruler. The red line at bit $p$ is the cut. Everything left of the cut is the VPN (it gets replaced), everything right stays glued on unchanged. Nothing in this page ever moves that red line except by changing the page size. Keep that picture in your head.

The scenario matrix

Every problem this topic can throw is one (or a combo) of these cells. We will hit all of them.

Cell	What makes it tricky	Covered by
A. Clean split	plain hex, digits line up	Ex 1
B. Non-nibble page size	$p$ not a multiple of 4, so hex digits split mid-digit	Ex 2
C. Offset = 0 (page boundary)	address sits exactly on a page start	Ex 3
D. Offset = max (last byte of page)	address is the very last byte before rollover	Ex 3
E. Reverse direction	given PA, recover VA (inverse map)	Ex 4
F. Table-size scaling	how RAM for tables grows with VA bits / entry size	Ex 5
G. Multi-level walk	VPN itself splits into index levels	Ex 6
H. Performance / EAT	limiting behaviour as hit ratio $h \to 1$ and $h \to 0$	Ex 7
I. Word problem	swap/disk timing, "is this a page fault?"	Ex 8
J. Degenerate / trap	invalid VPN, unmapped page, offset overflow	Ex 9

If a cell isn't in an example below, it's a bug in this page. Let's go.

Cell A — the clean split

Worked example Example 1 — textbook translation (

$p = 12$ ) Page size $= 4 KiB$ , so $p = 12$ . $VA = 0x2C4F9$ . Page table: VPN $0x2C \to$ PFN $0x15$ .

Forecast: guess the PA before reading on. (Hint: the last 3 hex digits survive.)

Split off the offset. $offset = 0x2C4F9 & 0xFFF = 0x4F9$ . Why this step? $2^{12} - 1 = 0xFFF$ = exactly 3 hex digits = the low 12 bits. With $p = 12$ the cut lands neatly on a hex boundary, so "keep last 3 hex digits" is the mask.
Extract the VPN. $VPN = 0x2C4F9 ≫ 12 = 0x2C$ . Why this step? Shifting right by 12 throws away those same 3 hex digits, leaving the page number.
Look up the frame. PFN $= 0x15$ . Why this step? Only the VPN is translated — this is the one table access.
Rebuild. $PA = (0x15 ≪ 12) ∣ 0x4F9 = 0x15000 ∣ 0x4F9 = 0x154F9$ . Why this step? Frame base is $PFN \times 2^{12}$ ; the offset drops into the low bits untouched.

Verify: $0x154F9 = 87289$ , and $0x15 \times 4096 + 0x4F9 = 21 \times 4096 + 1273 = 86016 + 1273 = 87289$ . ✓ Offset ( $0x4F9$ ) is unchanged between VA and PA — exactly what "offset stays" promised.

Cell B — the page size that splits a hex digit

Real exams love a page size like $1 KiB = 2^{10}$ , where $p = 10$ is not a multiple of 4. Now the cut runs through the middle of a hex digit, and "keep last few hex digits" silently fails. You must fall back to binary.

Cells C & D — offset at both extremes (page boundaries)

The two most misread inputs are the first byte of a page (offset $= 0$ ) and the last byte (offset $= 2^{p} - 1$ ). Let's do both at once and watch what happens if you step one byte past the last.

Worked example Example 3 — offset

$= 0$ and offset $= max$ ( $p = 12$ ) $p = 12$ , VPN $0x8 \to$ PFN $0x3$ .

Forecast: what PA does the first byte of virtual page 8 land on? And the last?

First byte: $VA = 0x8000$ . offset $= 0x8000 & 0xFFF = 0$ . VPN $= 0x8000 ≫ 12 = 0x8$ . Why this step? An address that is an exact multiple of $2^{p}$ has all-zero low bits — it sits on a page boundary.
$PA = (0x3 ≪ 12) ∣ 0 = 0x3000$ . Frame base, exactly, no offset added.
Last byte: $VA = 0x8FFF$ . offset $= 0xFFF = 4095$ (the max). VPN still $0x8$ . Why this step? $0xFFF$ is $2^{12} - 1$ , the largest offset a 4 KiB page holds.
$PA = 0x3000 ∣ 0xFFF = 0x3FFF$ .

Verify: page 8 spans VA $0x8000$ – $0x8FFF$ (that's $4096$ bytes ✓), mapping to PA $0x3000$ – $0x3FFF$ (also $4096$ ✓). One byte further, $0x9000$ , has VPN $0x9$ — a different table entry, possibly a different, non-adjacent frame. Contiguous in virtual ≠ contiguous in physical.

The figure shows it: virtual pages 8 and 9 sit side by side, but their frames (3 and, say, 7) are scattered in physical RAM. The page boundary is a hard wall — cross it and you re-consult the table.

Cell E — running the map backwards

Given a physical address, which virtual address produced it? The offset is trivial (unchanged). For the page part you invert the table: find the VPN whose entry is this PFN.

Worked example Example 4 — inverse translation (

$p = 12$ ) $p = 12$ . Table: VPN $0x1 \to$ PFN $0x9$ , VPN $0x2 \to$ PFN $0x4$ . Given $PA = 0x4ABC$ , find the VA.

Forecast: which VPN maps here — and is the answer even unique?

Split the PA. offset $= 0x4ABC & 0xFFF = 0xABC$ . PFN $= 0x4ABC ≫ 12 = 0x4$ . Why this step? Physical addresses split on the same $p$ — frames are the same size as pages.
Invert. Which VPN maps to PFN $0x4$ ? Table row: VPN $0x2$ . Why this step? We're reading the map right-to-left; the offset is already correct, only the page number needs undoing.
Rebuild the VA. $VA = (0x2 ≪ 12) ∣ 0xABC = 0x2ABC$ .

Verify: forward-translate $0x2ABC$ : VPN $0x2 \to 0x4$ , offset $0xABC$ , PA $= 0x4ABC$ ✓. Caveat: the inverse is unique only within one process's table. Two different processes could both have a VPN mapping to PFN $0x4$ — physical frames can be shared or reused, so "PA → VA" isn't globally invertible.

Cell F — how the table cost scales

Cell G — the multi-level walk

The fix for Cell F: split the VPN itself into index pieces, one per table level, and only build the sub-tables actually used.

Worked example Example 6 — two-level walk (

$p = 12$ ) $32$ -bit VA, $p = 12$ (offset). Remaining $20$ VPN bits split into VPN1 = top 10 bits, VPN2 = next 10 bits. $VA = 0x00403ABC$ .

Forecast: how many memory reads does one translation cost before the data read?

Peel the offset. offset $= 0x00403ABC & 0xFFF = 0xABC$ (low 12 bits).
VPN (all 20 bits) $= 0x00403ABC ≫ 12 = 0x00403 = 1027$ . Why this step? Same cut as before; we're just about to chop this VPN further.
VPN1 = top 10 bits $= 1027 ≫ 10 = 1$ . VPN2 = low 10 bits $= 1027 & 1023 = 3$ . Why this step? Level-1 table is indexed by VPN1 to find the level-2 table; level-2 is indexed by VPN2 to find the PFN.
Walk: L1[1] → address of L2 table; L2[3] → PFN. Then PA $=$ (PFN $≪ 12$ ) $∣$ offset.

Verify: reconstruct the VPN from its parts: $VPN1 \times 2^{10} + VPN2 = 1 \times 1024 + 3 = 1027$ ✓, and $1027 \times 4096 + 0xABC = 4206592 + 2748 = 4209340 = 0x00403ABC$ ✓. Cost: 2 table reads + 1 data read = 3 memory accesses on a TLB miss (vs 2 for single-level) — the price of shrinking the table.

Cell H — performance at the limits

Worked example Example 7 — EAT and its limiting behaviour

Recall $EAT = t_{T L B} + t_{m e m} + (1 - h) t_{m e m}$ (single-level miss penalty $=$ one extra $t_{m e m}$ ). Use $t_{T L B} = 1 ns$ , $t_{m e m} = 100 ns$ .

Forecast: what's EAT when the TLB always hits ( $h = 1$ ) and when it always misses ( $h = 0$ )?

$h = 0.90$ : $EAT = 1 + 100 + (0.10) (100) = 111 ns$ . Why this step? 10% of accesses pay the table walk; average it in.
$h \to 1$ (best case): $EAT \to 1 + 100 + 0 = 101 ns$ . Why this step? No misses ⇒ no walk; you pay only TLB + the real access.
$h \to 0$ (worst case): $EAT \to 1 + 100 + 100 = 201 ns$ . Why this step? Every access walks the table — nearly double the raw memory time. This is what Locality of reference saves us from.

Verify: the EAT is linear in $(1 - h)$ : it runs from $101 ns$ at $h = 1$ up to $201 ns$ at $h = 0$ , and at $h = 0.90$ sits at $111 ns$ , exactly $\frac{1}{10}$ of the way up the $100 ns$ span ✓.

The figure plots EAT versus hit ratio: a straight line from $(0, 201)$ to $(1, 101)$ . The steepness ( $100 ns$ per unit of hit ratio) is the miss penalty. Real TLBs live at the far-right ( $h > 0.99$ ), hugging $101 ns$ .

Cell I — the word problem (swap timing)

Worked example Example 8 — page fault to disk

A page is on disk (swapped out). Servicing a page fault costs $8 ms$ of disk I/O. A normal in-RAM access costs $100 ns$ . If 1 in 100 000 accesses faults, what is the average access time?

Forecast: guess before computing — will the tiny fault rate matter, given how slow disk is?

Convert units. $8 ms = 8000000 ns$ . Fault probability $= 1 0^{- 5}$ . Why this step? Never mix ms and ns — put everything in ns.
Average. $avg = (1 - 1 0^{- 5}) (100) + (1 0^{- 5}) (8000000)$ . Why this step? Weighted mean: almost always $100 ns$ , rarely $8 ms$ .
$= 100 - 0.001 + 80 = 179.999 ns \approx 180 ns$ .

Verify: $1 0^{- 5} \times 8000000 = 80 ns$ of pure fault contribution; a fault rate of just $1$ -in- $100000$ nearly doubles effective time. Lesson: disk is $80000 \times$ slower than RAM, so even a whisper of faulting dominates — this is why Page replacement algorithms fight so hard to keep the right pages resident.

Cell J — degenerate & trap inputs

Worked example Example 9 — invalid VPN and offset overflow (

$p = 12$ ) Table has valid entries only for VPN $0x0$ and $0x1$ ; the valid bit is 0 for all others.

Forecast: what happens for (a) $VA = 0x9004$ , and (b) trying to store $0x1000$ into a single 12-bit offset field?

(a) Access unmapped page. VPN $= 0x9004 ≫ 12 = 0x9$ . Table entry $0x9$ has valid bit $= 0$ . Why this step? Translation starts with the VPN lookup; the valid bit is checked first.
The MMU raises a fault. The OS inspects: is VPN $0x9$ merely swapped to disk (→ load it, resume) or never allocated / out of range (→ segmentation fault, kill the process)? See Segmentation. Why this step? Same hardware trap, two software meanings — distinguishing them is the OS's job.
(b) Offset overflow. An offset field holds $p = 12$ bits, max value $0xFFF = 4095$ . The value $0x1000 = 4096$ does not fit — it's not an offset at all, it's the base of the next page. Why this step? $4096 = 2^{12}$ carries out of the 12-bit field into the VPN, i.e. it increments the page number. Offsets are always in $[0, 2^{p} - 1]$ .

Verify: the largest legal offset is $2^{12} - 1 = 4095$ ✓; $4096 mod 4096 = 0$ with quotient $1$ , confirming it is the start of the next page, not an offset ✓. And VPN $0x9 = 9$ is outside the mapped set ${0, 1}$ , so the fault is correct behaviour, not a bug in our arithmetic.

Recall

Recall Which cell is this? (cover the answers)

Page size $1 KiB$ , VA $= 1500$ : what's the offset? ::: $1500 - 1024 = 476$ (Cell B — mask $1023$ , non-nibble).
PA sits exactly on a frame boundary. What's its offset? ::: $0$ (Cell C).
Given a PA, is recovering the VA always unique? ::: Only within one process's page table (Cell E).
48-bit VA, 4 KiB pages, 8-byte entries — flat table size? ::: $512 GiB$ , hence multi-level (Cell F).
Two-level walk: memory accesses per translation on a TLB miss? ::: 3 (2 table + 1 data) (Cell G).
EAT as $h \to 0$ with $t_{m e m} = 100, t_{T L B} = 1$ ? ::: $201 ns$ (Cell H).
Valid bit is 0 and the page was never allocated — what fires? ::: A segmentation fault (Cell J).