Virtual memory — concept, page table, virtual-to-physical translation: Worked examples

This page is the drill hall for the parent topic. The parent taught the machine: split the address, look up the page table, concatenate. Here we run that machine on every kind of input it can meet — clean hits, page faults, weird page sizes, the very first byte of a page, the very last byte, a permission error, and an exam-style twist.

Before we start, one promise: we only use ideas already built in the parent. Let us re-anchor the symbols we lean on, in plain words, so nothing sneaks in undefined.

The picture below fixes the geometry of a virtual address once — how a VA splits into VPN + offset, how the VPN becomes a PFN through the table, and how the offset slides straight through to form the PA. Every example points back to it.

Figure — Virtual memory — concept, page table, virtual-to-physical translation

Read it top to bottom: the blue VPN half (bits 31…12) is looked up in the page table and replaced by the green PFN; the orange offset half (bits 11…0) is copied down untouched. That is the whole machine in one figure.

The scenario matrix

Every problem this topic can throw is one (or a mix) of the cells below. The worked examples that follow each announce which cell they cover, and together they fill the whole grid.

#	Cell (case class)	What makes it special	Covered by
C1	Clean hit, generic byte	valid=1, offset is somewhere in the middle	Ex 1
C2	Offset = 0 (page boundary, first byte)	tests that the base address is exactly PFN·2^p	Ex 2
C3	Offset = max (last byte of a page)	tests the off-by-one edge; next byte crosses into a new page	Ex 3
C4	Page fault (valid = 0)	data on disk; no PA yet — trap first	Ex 4
C5	Protection fault (valid=1 but write to read-only)	mapping exists, permission denies it	Ex 5
C6	Non-power-of-two-friendly sizing / different page size	1 KiB, 2 KiB, huge pages — recompute the split	Ex 6
C7	Degenerate: VA = 0	the very first byte of the whole space	Ex 7
C8	Real-world word problem	array walk, count how many pages / faults	Ex 8
C9	Exam twist: given PA, work backwards to VA	reverse the recipe	Ex 9
C10	Limiting behaviour: array crossing a page boundary	one logical access → two pages	Ex 10

Example 1 — the clean hit (cell C1)

Worked example Generic byte, valid mapping

System: 32-bit VA, 4 KiB pages → $p = 12$ . Page table: VPN 0x7 → PFN 0x2C (valid=1). Translate VA 0x7BE4.

Forecast: Before reading on — which hex digits are the offset? Which are the VPN? Guess the final PA.

Split. $p = 12$ so the low 12 bits = 3 hex digits are the offset. 0x7BE4 → offset 0xBE4, VPN = the rest = 0x7. Why this step? 12 bits is exactly 3 hex digits (4 bits each), so hex makes the slice visual — no binary needed.
Lookup. PageTable[0x7] = 0x2C, valid=1 → PFN 0x2C. Why this step? Only the VPN is translated; the table is our dictionary. valid=1 confirms the page is really in RAM, so the PFN is usable.
Concatenate. $PA = 0 x 2 C \times 2^{12} + 0 x B E 4 = 0 x 2 C 000 + 0 x B E 4 =$ 0x2CBE4. Why this step? PFN·2^p is the frame's base byte; offset walks inside. Notice the low 3 digits BE4 are unchanged — the offset survived.

Verify: Low 3 hex digits of input (BE4) match low 3 of output (BE4) ✓. High digits changed 7 → 2C as the table dictates ✓.

Example 2 — offset = 0, page boundary (cell C2)

Example 3 — offset = max, last byte (cell C3)

Worked example The final byte, and what happens one byte later

Same system. VPN 0x3 → PFN 0x81 (valid=1). Translate VA 0x3FFF, then think about 0x4000.

Forecast: How many distinct bytes are in one 4 KiB page, and what is the largest legal offset?

Split 0x3FFF. Offset = 0xFFF = 4095 (the maximum, since offsets run 0…4095). VPN = 0x3. Why this step? 0xFFF is 12 ones in binary — the biggest number 12 bits can hold. This is the last byte of page 3.
Concatenate. $PA = 0 x 81 \times 0 x 1000 + 0 x F F F =$ 0x81FFF. Why this step? Same recipe: PFN 0x81 gives the frame base 0x81000, and adding the maximal offset 0xFFF walks us to the very last byte of that frame — the mirror image of the byte's position in the virtual page.
One byte later: 0x4000 has offset 0x000 and VPN 0x4 — a different page needing its own table entry (maybe a different PFN, maybe a fault). Why this step? This is the limiting/edge case: crossing a page boundary silently switches which dictionary entry rules the address. See Ex 10.

Verify: 0x3FFF - 0x3000 = 0xFFF = 4095 = page size − 1 ✓. 0x81FFF + 1 = 0x82000 sits on the next frame boundary ✓.

Example 4 — page fault (cell C4)

Worked example valid = 0: no PA yet

Same system. Access VA 0xB210. PageTable[0xB].valid = 0.

Forecast: Will the MMU produce a physical address on this access? Why or why not?

Split. offset 0x210, VPN 0xB. Why this step? Even before we know the page's fate we must slice the VA, because the VPN is the key we need to look up and the offset is the part we will keep no matter what.
Lookup. Entry says valid = 0 → the page is not in RAM. There is no PFN to use. Why this step? The valid bit is the MMU's "is this real?" flag; 0 means "data is on disk (swap)".
Trap → OS. OS reads the page from disk into a free frame — say it chooses PFN 0x40 — then sets PageTable[0xB] = 0x40, valid=1. Why this step? We must put real data behind the lie before translation can mean anything.
Restart instruction. Retry now succeeds: $PA = 0 x 40 \times 0 x 1000 + 0 x 210 =$ 0x40210. Why restart? The faulting instruction never completed its memory access; it re-runs cleanly.

Verify: After the fault is serviced, low 3 digits 210 unchanged ✓; PA = 0x40210, and 0x40210 mod 0x1000 = 0x210 ✓.

Example 5 — protection fault (cell C5)

Worked example Mapping exists, permission denies

Same system. PageTable[0x2] = { PFN 0x55, valid=1, writable=0 } (recall: writable=0 means read-only). A program tries to write to VA 0x2ABC.

Forecast: valid=1 — so is this a page fault? Will the OS just load a page and retry?

Split. offset 0xABC, VPN 0x2. Why this step? Splitting is always the first move: we need the VPN as the lookup key and must keep the offset. This happens before any permission is judged.
Lookup. valid=1, PFN=0x55 — the data is in RAM. A read would translate to 0x55ABC. Why this step? The lookup fetches both the PFN and the flag bits; here valid=1 rules out a page fault, so any problem must come from the permission bits, not from absence.
Check permission for a write. writable=0 → the MMU raises a protection fault, not a "fetch from disk" fault. Why this step? Presence (valid) and permission (writable) are separate gates. This one is closed for writes.
OS response. Usually a signal (e.g. segmentation fault) — or, for copy-on-write, allocate a private writable copy and update the entry. Why this step? Loading a page would be pointless — the page is already here; the issue is policy.

Verify (the read path, to anchor the number): a read to 0x2ABC gives $0 x 55 \times 0 x 1000 + 0 x A B C =$ 0x55ABC ✓. The write is denied, so it yields no PA.

Example 6 — a different page size (cell C6)

Worked example 1 KiB pages, 16-bit VA

System: 16-bit VA, 1 KiB pages. VPN 0x5 → PFN 0x0C (valid=1). Translate VA 0x14D6.

Forecast: How many offset bits now? Warning: 10 offset bits is not a clean hex boundary — you cannot just slice hex digits. Predict what breaks.

Recompute the split. $1 KiB = 2^{10}$ → offset = 10 bits, VPN = $16 - 10 = 6$ bits. Why this step? Page size sets $p$ ; here $p = 10$ , so the slice is not on a 4-bit hex line. Go to binary.
Binary. 0x14D6 = 0001 0100 1101 0110. Offset = low 10 bits = 01 1101 0110. Reading those 10 bits: $011101011 0_{2} = 0 x 0 D 6 = 214$ . VPN = high 6 bits = 000101 = 0x5. Why this step? Because 10 isn't a multiple of 4, we must count bits, not hex digits — the classic exam trap. (The whole low 3 hex digits 4D6 = 1238 would be wrong; only the low 10 bits count, giving 214.)
Concatenate. $PA = 0 x 0 C \times 2^{10} + 214 = 12 \times 1024 + 214 = 12288 + 214 = 12502 =$ 0x30D6. Why this step? Same recipe, new $2^{p} = 1024$ .

Verify: offset value $= 0 x 14 D 6 mod 1024 = 214$ ✓; VPN $= ⌊ 0 x 14 D 6/1024 ⌋ = 5$ ✓; PA $= 12 \cdot 1024 + 214 = 12502 =$ 0x30D6 ✓.

Example 7 — degenerate input, VA = 0 (cell C7)

Worked example The very first byte of the address space

4 KiB pages. PageTable[0x0] = { PFN 0x00, valid=0 } (page 0 unmapped — a deliberate trap for null-pointer bugs). Access VA 0x0.

Forecast: VPN 0, offset 0. Is a null access special-cased by hardware, or by the page table?

Split. offset 0x000, VPN 0x0. Why this step? Even the trivial address obeys the same split; nothing is hard-wired.
Lookup. PageTable[0x0].valid = 0 → page fault / protection trap → this is how OSes catch dereferencing a null pointer. Why this step? Leaving page 0 unmapped turns *NULL into a clean fault instead of silently reading real data.
If it were mapped to, say, PFN 0x09: $PA = 0 x 09 \times 0 x 1000 + 0 =$ 0x9000. Why this step? We construct the hypothetical mapped result to show the machine still works normally on VA 0 — the fault in step 2 is a deliberate policy choice, not a limitation of the arithmetic. It anchors that offset-0 always lands on a frame boundary.

Verify: hypothetical mapped PA 0x9000 mod 0x1000 = 0 ✓ (offset 0 lands on a frame edge).

Example 8 — real-world word problem (cell C8)

Worked example Walking an array: how many page faults?

4 KiB pages. A program touches every byte of a freshly-allocated, contiguous array of 10000 bytes, starting at VA 0x8000 (page-aligned). Assume none of its pages are in RAM yet (all valid=0). How many page faults occur if you touch bytes in order?

Forecast: 10000 bytes over 4096-byte pages — guess the number of distinct pages, and hence faults.

Find the span. Bytes cover VAs 0x8000 … 0x8000 + 9999 = 0x8000 … 0xA70F. Why this step? We need the highest VA touched to know the last page.
Count distinct pages. $⌈ 10000/4096 ⌉ = ⌈ 2.44 ⌉ = 3$ pages: VPNs 0x8, 0x9, 0xA. Why this step? Each new page you step onto (valid=0) causes exactly one fault; touching more bytes of an already-loaded page does not.
Faults = 3 (one per first touch of each page). Why this step? Demand paging: a page is loaded on its first access, then subsequent accesses hit. This is why spatial locality matters — see Cache Memory and Locality.

Verify: ceil(10000/4096) = 3 ✓; last byte 0x8000 + 9999 = 0xA70F lies in VPN 0xA ✓ (0xA70F >> 12 = 0xA).

Example 9 — exam twist: reverse the recipe (cell C9)

Worked example Given the PA, find the VA

4 KiB pages. You are told the physical address is 0x2CBE4, and the reverse map says PFN 0x2C came from VPN 0x7. What was the original VA?

Forecast: Which part of the PA equals which part of the VA?

Extract offset from PA. offset = low 12 bits of 0x2CBE4 = 0xBE4. Why this step? Offset is identical in VA and PA — it is our bridge back.
Attach the given VPN. VA VPN = 0x7, so VA = (0x7 << 12) | 0xBE4. Why this step? The reverse map hands us the VPN; concatenate it with the shared offset.
Compute. VA = 0x7000 | 0xBE4 = 0x7BE4 — exactly the VA from Example 1, confirming the round trip. Why this step? Forward then backward must return the start; this is the consistency check.

Verify: 0x7BE4 mod 0x1000 = 0xBE4 = 0x2CBE4 mod 0x1000 ✓; forward translation of 0x7BE4 gave 0x2CBE4 (Ex 1) ✓.

Example 10 — limiting behaviour: a load that straddles two pages (cell C10)

Worked example One 4-byte read crossing a page boundary

4 KiB pages. Read 4 bytes (a 32-bit word) starting at VA 0x8FFE. Table: VPN 0x8 → PFN 0x30 (valid=1), VPN 0x9 → PFN 0x71 (valid=1).

Forecast: 0x8FFE is 2 bytes before the end of page 8. A 4-byte read needs bytes at 0x8FFE, 0x8FFF, 0x9000, 0x9001. How many pages does that span?

Locate the bytes. 0x8FFE and 0x8FFF are in page 8 (offsets 0xFFE, 0xFFF); 0x9000, 0x9001 are in page 9 (offsets 0x000, 0x001). Why this step? Crossing offset 0xFFF → 0x000 flips the VPN — the access spans two dictionary entries.
Translate the low half (page 8). $PA = 0 x 30 \times 0 x 1000 + 0 x F F E =$ 0x30FFE for byte 0; byte 1 at 0x30FFF. Why this step? The low two bytes still belong to VPN 0x8, so we apply the ordinary recipe with that page's PFN 0x30; the offsets 0xFFE/0xFFF are preserved as always.
Translate the high half (page 9). $PA = 0 x 71 \times 0 x 1000 + 0 x 000 =$ 0x71000 for byte 2; byte 3 at 0x71001. Why this step? The two halves land on non-adjacent physical frames (0x30FFE then 0x71000) even though they were adjacent in virtual space — the hardware must do two translations.

Verify: page-8 base 0x30FFE, 0x30FFE mod 0x1000 = 0xFFE ✓; page-9 base 0x71000, 0x71000 mod 0x1000 = 0 ✓; the frames differ (0x30 ≠ 0x71) so contiguity in VA ≠ contiguity in PA ✓.

The straddle picture below shows the split of a single word across two frames.

Active recall

Recall Cover the answers and test yourself

Ex 1 PA for VA 0x7BE4, PFN 0x2C, 4 KiB ::: 0x2CBE4 Ex 6 PA for VA 0x14D6, PFN 0x0C, 1 KiB pages ::: 0x30D6 (= 12502) Ex 8 number of page faults walking 10000 bytes over 4 KiB pages ::: 3 Ex 10: do the two halves of the word land on adjacent physical frames? ::: No — 0x30FFE then 0x71000; adjacency in VA does not imply adjacency in PA Difference between a page fault and a protection fault ::: page fault = valid=0, fetch from disk and retry; protection fault = valid=1 but the operation (e.g. write) is forbidden

Where to go next: the cost of these lookups (they live in RAM!) is tamed by the TLB — Translation Lookaside Buffer; the 4 MiB-per-process table blow-up is fixed by Multi-level Page Tables; and reloading the map on a context switch is Context Switching and CR3 / Page-Table Base Register. Compare the whole scheme with Paging vs Segmentation and see where it sits in the Memory Hierarchy.