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

We use the running system: 32-bit virtual addresses, 4 KiB pages, byte-addressable. Numbers pinned down so you can see each bit move.

---

Step 1 — Draw memory as one long ruler of bytes

WHAT. Before any "pages" or "frames", memory is just a line of numbered boxes. Box number $0$, box $1$, box $2$, … each box holds one byte. The number of a box is its address.

WHY. Every idea that follows is "how do I turn one box number into another box number?" You cannot translate an address until you agree an address is just a position on this ruler. No magic yet.

PICTURE. Look at the ruler below. The purple tick is address $0$, the ruler runs right. One address = one box. That is all an address is.

---

Step 2 — Cut the ruler into equal pages

WHAT. Chop the ruler into equal chunks of $2^p$ bytes each. Here $p=12$, so each chunk is $2^{12}=4096$ bytes $=4$ KiB. Call each chunk a page. Number the pages $0,1,2,\dots$ left to right.

WHY. Equal-size chunks are the whole trick: any chunk fits any hole in real RAM (parent note: this kills external fragmentation). Making them a power of two ($2^{12}$) is what lets us later use bit-slicing instead of real division.

PICTURE. The magenta scissors cut every $4096$ boxes. Page $0$ = boxes $\mathrm{0..4095}$, page $1$ = boxes $\mathrm{4096..8191}$, and so on. The number above the cut is the Virtual Page Number (VPN).

---

Step 3 — Any address = (which page) + (how far in)

WHAT. Take any address $\text{VA}$. Two questions fully locate its box:

1. Which page is it in? → call that number $\text{VPN}$.
2. How far into that page is it? → call that number $\text{offset}$.

The remainder-and-quotient of dividing by the page size answers both at once.

WHY divide? Because "cut into equal chunks of size $2^p$" is division by $2^p$. The quotient literally counts how many whole pages you passed (= VPN); the remainder is what is left over inside the current page (= offset). We divide because division is the exact arithmetic name for "group into equal bins and see the leftover".

PICTURE. The orange bracket shows the offset (distance from the page's left edge); the violet label shows the VPN (how many pages we stepped over).

---

Step 4 — Dividing by $2^p$ is just slicing bits

WHAT. We claimed division is expensive but here it is free. Writing $\text{VA}$ in binary and cutting off the low $p$ bits gives offset; the bits above give VPN. No arithmetic circuit needed — just wires.

WHY this tool (binary slicing) and not real division? Dividing by $10$ is hard, but dividing by $2^p$ in binary is like dividing by $100$ in decimal: you just move the "decimal point" $p$ places. The low $p$ digits fall off as the remainder; the rest is the quotient. Hardware loves this because it is zero-cost — the MMU literally routes some wires up and some wires down.

PICTURE. Take $\text{VA}=\text{0x5A3C}$. In binary that is $\text{0101 1010 0011 1100}$. The low $12$ bits (orange) are the offset; the bits above (violet) are the VPN.

Check on $\text{0x5A3C}$: low $12$ bits $=\text{A3C}$, bits above $=\text{0x5}$. So $\text{VPN}=\text{0x5}$, offset $=\text{0xA3C}$.

---

Step 5 — The page table remaps only the VPN

WHAT. Real RAM is also cut into equal chunks called frames, same size $2^p$. The page table is a per-process array: hand it a VPN, it returns the Physical Frame Number (PFN) where that page actually lives. It does not touch the offset.

WHY leave the offset alone? Because a frame is the same size as a page and aligned to the same $2^p$ boundary. "Box number $7$ inside page $5$" and "box number $7$ inside frame $\text{0x12}$" describe the same within-block position. The offset is a distance from a left edge, and both blocks are equally wide — so the distance is unchanged. Translating it would corrupt the address (parent note's steel-manned mistake).

PICTURE. The dictionary arrow bends only the VPN: page $\text{0x5}$ (violet) is looked up and points to frame $\text{0x12}$ (magenta). The orange offset slides across unchanged.

---

Step 6 — Glue PFN and offset back into a physical address

WHAT. We now have the frame number (from the table) and the untouched offset. Rebuild a real ruler position: go to the start of frame $\text{PFN}$, then step in by $\text{offset}$ boxes.

WHY multiply then add (equivalently, shift then OR)? The start of frame $\text{PFN}$ is at physical box $\text{PFN}\cdot 2^p$ — because frame $0$ starts at $0$, frame $1$ at $2^p$, frame $2$ at $2\cdot 2^p$, i.e. each frame begins one page-size later. Adding the offset walks in from that edge. Since offset $<2^p$, it fits exactly in the low $p$ bits, so the add never collides with the frame bits — that is why hardware can use a cheap OR (concatenation) instead of a real adder.

PICTURE. Bottom bar: the magenta frame-base bits from PFN in the high slots, the orange offset bits dropped into the low slots. Snap them together → the physical address.

---

Step 7 — The degenerate case: valid bit = 0 (page fault)

WHAT. Sometimes the table says the page is not in RAM (valid $=0$). Then Step 5's PFN is meaningless. Access VA $=\text{0x9004}$ with PageTable$[\text{0x9}].\text{valid}=0$.

WHY handle this separately? Because the smooth Split→Lookup→Concatenate pipeline breaks here: there is no real frame to concatenate. The hardware cannot invent data; it must pause and let the OS fill in the truth behind the lie.

PICTURE. The lookup arrow hits a red wall (valid $=0$). Control jumps to the OS, which fetches the page from disk into a free frame, writes the new PFN, flips valid to $1$, then restarts the instruction — which now flows through Steps 5–6 normally.

Recall Edge cases you must be able to answer

• offset $=\text{0x000}$ ::: the very first byte of a page; PA is exactly the frame's base $\text{PFN}\cdot 2^p$.
• offset $=\text{0xFFF}$ ::: the last byte in a $4$ KiB page ($4095$); one more and it rolls into the next VPN.
• VPN unused / valid $=0$ ::: page fault → OS loads it, sets valid, restarts.
• Two processes, same VA ::: different page tables ⇒ different PFNs ⇒ different physical boxes (isolation).

---

The one-picture summary

Everything above compressed into a single flow: split the virtual address, look the VPN up (fault if invalid), keep the offset, concatenate. Trace the colored arrows once and you own the derivation.

Recall Feynman retelling — the whole walkthrough in plain words

Picture memory as one endless shelf of numbered boxes (Step 1). Take scissors and cut it into equal $4096$-box pages (Step 2). Now any box has a two-part name: which page and how far into it — which is exactly the quotient and remainder of dividing its number by $4096$ (Step 3). Because $4096$ is $2^{12}$, that "division" is just chopping off the low $12$ bits of the binary number — the low $12$ are the offset, the rest are the page number (Step 4). The page table is a private notebook: give it the page number, it tells you which real RAM frame holds that page — but it never touches the "how far in" part, because a frame is the same width as a page, so distance-from-the-left is identical (Step 5). To build the real address, jump to that frame's starting box (multiply the frame number by $4096$) and step in by the offset (Step 6) — in hardware, just shift and OR. If the notebook says "not here" (valid $=0$), stop, let the OS fetch it from disk, update the notebook, and rerun the instruction (Step 7). VPN picks the frame; offset stays the same.

---

See also: Parent · Multi-level Page Tables · TLB — Translation Lookaside Buffer · Context Switching and CR3 / Page-Table Base Register · Cache Memory and Locality · Memory Hierarchy · Paging vs Segmentation · Page Replacement Algorithms (LRU, FIFO, Clock)