Virtual memory and paging: Visual walkthrough — Hardware deep dive

Step 1 — What an address even is (a ruler of bytes)

WHAT. Memory is one gigantic row of numbered boxes, each holding one byte (8 bits). An address is just the box number. Box 0, box 1, box 2, … all the way up.

WHY. Before we can "translate" an address, we must agree it is nothing mystical — it is a position on a ruler. If your addresses are $n$ bits wide, the biggest number you can write is $2^{n} - 1$ , so you can name $2^{n}$ boxes total.

PICTURE. Below, the black ruler is memory. The red tick is one address pointing at one box.

Step 2 — Chop the ruler into equal pages

WHAT. Take that long ruler and cut it into equal-length segments. Each segment is a page. If a page is $P$ bytes long and $P = 2^{p}$ , then every page holds exactly $2^{p}$ boxes.

WHY. We choose the length to be a power of two, $P = 2^{p}$ , on purpose — this is the single most important decision in the whole derivation. In binary, dividing by $2^{p}$ is just "ignore the lowest $p$ bits," and the remainder is "the lowest $p$ bits by themselves." We will lean on that in Step 4. If $P$ were, say, $1000$ , none of this bit-magic would work.

PICTURE. Same ruler, now sliced. Each slice (page) is the same width. The red slice is page number 2, and inside it the boxes are numbered $0.. P - 1$ again, locally.

Step 3 — Split the address: VPN and offset

WHAT. Write the address $A$ in binary. The high $n - p$ bits answer "which page?" — call them the Virtual Page Number (VPN). The low $p$ bits answer "how far in?" — call them the offset.

A = high n - p bits: which page VPN ∥ low p bits: how far into it offset

$A$ — the full virtual address (the box number the program uses).
$∥$ — "written next to," i.e. concatenation of bit-groups, not multiplication.
VPN — the page's index in the sliced ruler of Step 2.
offset — the local position inside that page, always in $0 \dots 2^{p} - 1$ .

WHY. Because Step 2 sliced along power-of-two boundaries, the bits literally fall into two clean groups. No arithmetic tricks needed to separate "which page" from "where inside" — the split is just cutting the bit-string.

PICTURE. The bit-string $A$ with a red divider dropped between bit $p$ and bit $p - 1$ . Everything left of the line is VPN; everything right is offset.

Step 4 — Extract each part with shift and mask

WHAT. We now compute VPN and offset with real operations:

offset = A & (2^{p} - 1), VPN = A ≫ p

$&$ — bitwise AND: keeps a bit only where both inputs are 1.
$2^{p} - 1$ — a number that is $p$ ones in binary (e.g. $2^{12} - 1 = 0xFFF$ ). ANDing with it keeps exactly the low $p$ bits and zeroes the rest → that is the offset.
$≫ p$ — shift right by $p$ : slide every bit down $p$ places, so the low $p$ bits fall off the end and the VPN lands at the bottom.

WHY these two tools and not division? $A ≫ p$ is $⌊ A / 2^{p} ⌋$ and $A & (2^{p} - 1)$ is $A mod 2^{p}$ — but shift and mask are single, one-cycle hardware operations. We picked $P = 2^{p}$ in Step 2 precisely so the expensive division becomes a free wire-shift. That is the payoff of the power-of-two choice.

PICTURE. Left: the mask (a red band of $p$ ones) sitting under $A$ , keeping only the offset. Right: the arrow of a right-shift sliding the VPN down into place.

Step 5 — Look up the frame in the page table

WHAT. Feed the VPN into the page table — a per-process lookup array — and read out the Physical Frame Number (PFN):

PFN = PageTable [VPN]

PageTable — an array indexed by VPN; entry number $k$ tells you where virtual page $k$ really lives.
$[VPN]$ — "the entry at row VPN," ordinary array indexing.
PFN — the physical frame's index (a slot in real RAM), the same size as a page.

WHY. This is the only step where fiction becomes fact. The offset is never touched (Step 6 explains why); only the page's identity is remapped. This indirection is what lets each process own its own map — see Multi-level page tables for how the table itself is stored cheaply.

PICTURE. The VPN points into a black table; the red arrow leaves the matched row carrying the PFN out to the physical side.

Step 6 — Rebuild the physical address

WHAT. Glue the frame number back onto the untouched offset:

PA = (PFN ≪ p) ∣ offset

$PFN ≪ p$ — shift the frame number left by $p$ , i.e. multiply by $2^{p}$ . This lands PFN in the high bits and creates $p$ empty low bits.
$∣$ — bitwise OR: drops the offset into those freshly-emptied low bits.
Result: PA — the real box number RAM will access.

WHY the left shift? Frame $f$ begins at physical byte $f \times 2^{p}$ (frames are $2^{p}$ bytes apart, back to back). So the frame's starting byte is $PFN ≪ p$ , and adding the offset walks us the rest of the way in. Because the low $p$ bits of $PFN ≪ p$ are guaranteed zero, OR and add give the identical result — no carry can collide.

PICTURE. The offset from Step 4 (kept in red the whole time) reunites with the shifted PFN to form PA. Notice the red offset bits are bit-for-bit the same as in Step 3.

Step 7 — The degenerate & edge cases

Never leave the reader in an unshown scenario. Four corners of this machine:

Offset = 0. The address sits exactly on a page boundary — the first byte of a page. Then $PA = PFN ≪ p$ , a clean frame base. Nothing breaks; the OR just adds zero.
Offset = $2^{p} - 1$ . The last byte of a page (all offset bits 1). Still stays inside the same frame — the offset can never overflow into the PFN because it is only $p$ bits wide. This is the guarantee that makes "only the VPN differs" true.
VPN not in the table (or marked "not present"). The lookup in Step 5 fails → a page fault fires. This is not a crash: the OS fetches the page from disk, fills the table entry, and re-runs the same instruction. Then Steps 1–6 succeed.
VPN genuinely invalid (out of the process's allowed range). Now it is a real error — a segfault. Compare with Segmentation, where whole regions, not fixed pages, are checked.

PICTURE. Two tiny rulers side by side: the leftmost box (offset 0, red) and the rightmost box (offset $2^{p} - 1$ , red) both land safely inside one frame — the offset never spills over the frame's edge.

Step 8 — Worked number, end to end

The one-picture summary

Everything above, compressed: an arrow flows from the virtual address, splits into VPN + offset, the VPN detours through the page table to become a PFN, and the two rejoin as the physical address. Follow the red offset — it rides straight through, untouched, from VA to PA.

Recall Feynman retelling — the whole walk in plain words

Memory is one long shelf of numbered boxes (Step 1). We tape it into equal-size pages, each a power-of-two long (Step 2), so an address naturally reads as "which page, then how far in" — VPN and offset (Step 3). Splitting is free: shift right for the page number, mask for the how-far-in (Step 4). Only the page number visits the page table, which swaps it for the real frame number (Step 5). We shove that frame number up top and drop the untouched offset back underneath — that's the real address (Step 6). Edge boxes (first and last of a page) still stay in the frame, missing pages just cause the OS to fetch them and retry, and truly-bad addresses are the only real error (Step 7). Run it on real hex and the offset comes out unchanged, proving the rigid-slide idea (Step 8).

Recall Quick self-check

VA→PA in one sentence? ::: Split off the offset, translate only the VPN through the page table into a PFN, then recombine PFN‹‹p with the untouched offset. Why must the page size be a power of two? ::: So the VPN/offset split is a free shift-and-mask instead of a division. Does the offset ever change during translation? ::: No — it is copied bit-for-bit from VA to PA. What happens if the VPN's entry is "not present"? ::: A page fault; the OS loads the page from disk and re-runs the instruction — not a crash.

Related: 5.4.11 Virtual memory and paging (Hinglish) · CPU caches · Locality of reference · Page replacement algorithms · Multi-level page tables