Foundations — Page tables and multi-level paging

Before you can read the parent note Page Tables and Multi-Level Paging without tripping, you need to own every symbol it throws at you. This page builds each one from the ground up: plain words → the picture → why the topic needs it. Read top to bottom; each idea leans on the one above it.

1. A "bit" and a "power of two" — the alphabet of everything

Line up $n$ switches in a row and each switch can be flipped independently. So the number of distinct patterns you can make is $2\times 2\times \dots$ ($n$ times):

The picture: think of a car odometer, but each wheel has only two symbols ($0,1$) instead of ten. With 3 wheels you can show $000,001,010,\dots ,111$ — that is $2^3=8$ distinct readings.

Why the topic needs it: every "size" in paging — how many pages, how big a page, how many table entries — is a power of two, because it is counted by some number of address bits.

2. Bytes and addresses — giving every locker a number

The picture: a hallway of identical mailboxes, each with a little number plate. The plate is the address; whatever letter is inside is the byte.

• $V=32$ ⇒ $2^{32}$ bytes = 4 GiB of addressable space.
• $V=64$ ⇒ an astronomically larger space (this is why flat tables die).

Why the topic needs it: the whole job of paging is turning one address into another. $V$ tells you how big the "from" world is.

3. Virtual vs physical — the pretend number and the real number

The picture: two hallways side by side. The left (virtual) is what the program sees — clean, complete, all its own. The right (physical) is the real, shared, half-full building. Arrows cross from left boxes to scattered right boxes.

Why the topic needs it: without this split, two programs both wanting "locker 5" would clash. Virtual addresses let each program pretend it owns everything, while physical reality stays shared and safe. See Virtual Memory and Address Space Layout for the bigger story.

4. Pages and frames — cutting both hallways into equal blocks

The picture: take both hallways from figure s02 and draw thick dividers every $P$ boxes. Each virtual block (page) maps to one physical block (frame). Because the blocks are the same size, a virtual page can drop into any free frame — like same-size bricks fitting any same-size slot.

Why the topic needs it: fixed equal-size blocks kill external fragmentation and make the low bits of the address untouchable — the two pillars everything else stands on.

5. Splitting an address: page number | offset

Now cut a single address into two fields using the dividers from Section 4.

Why these two operations?

• $\lfloor \text{addr}/P\rfloor$ (integer divide, drop the remainder) answers "how many whole blocks of $P$ fit below this address?" — that is the block number.
• $\text{addr}\mathrm{mod}P$ (the remainder) answers "how far into the current block are we?" — that is the offset.

The picture: an odometer where a vertical line splits the wheels. Wheels left of the line = page number; wheels right = offset. Turning offset wheels never touches the page-number wheels until they roll over past $P$.

Why the topic needs it: translation only ever rewrites the page number; the offset is copied verbatim. This split is the whole engine.

6. Bit operations: masking &, shifting << >>, and |

The formulas above use $\ll$, $\gg$, and $\mathrm{mod}$ that are cheaper than real division on a computer. Because $P$ is a power of two, the "divide" and "remainder" are pure bit surgery. (Full detail in Bit Manipulation and Masking.)

Why the topic needs it: the parent writes $(\text{PFN}\ll p)|\text{offset}$ and $\text{addr}\mathrm{mod}P$ everywhere. These are the same thing said two ways — powers of two make division into shifting.

7. The lookup table, the entry, and its flags

The picture: a spreadsheet. Row number = VPN (you don't store it — it's just where the row sits). The cell contents = PFN + flags. Index in, value out.

Why the topic needs it: "the array position is the key, the entry is the value" is one of the parent's steel-manned mistakes. If you don't see the table as indexed by VPN, none of the multi-level walk makes sense.

8. A "level" and a base register — why one table becomes a tree

A single flat table with $2^{20}$ rows is mostly empty for a real program. So we index in stages: chop the VPN itself into slices, and use each slice to step down one level of a tree of small tables.

The picture: a table of contents (top table) points to chapters (inner tables), which point to pages (frames). You only print the chapters someone actually reads. Each level costs one real RAM read — that is where the TLB later earns its keep, just as a plain cache rescues slow memory.

How it all feeds the topic

Equipment checklist

Once every line above feels obvious, go read the parent note — or the Hinglish version.