Foundations — Virtual memory and paging

This page assumes you have seen none of the notation. We define bits, addresses, powers of two, the mod/shift operators, hex, and the split-and-combine machinery one brick at a time. Nothing is used before it is drawn.

0. A bit and a byte — the atoms

Why the topic needs it. Memory is nothing but a colossal row of bytes. Every "address" we translate is just a way of counting those bytes. If you cannot picture the row of bulbs, the words "address", "offset", and "page" have nothing to sit on.

Because a byte has 8 switches, it can show $2^8=256$ different patterns (from all-off to all-on). That "$2^8$" is our first power of two — meet it properly next.

1. Powers of two — the counting ruler of hardware

Why the topic needs it. Everything in paging is a power of two — page size $2^p$, number of pages $2^{n-p}$, address space $2^n$. Powers of two are chosen because they line up perfectly with bits: chopping off the low $k$ bits is the same as dividing by $2^k$. Hold that thought — it becomes the whole translation trick.

2. An address — a house number for one byte

If addresses are $n$ bits wide, the largest reachable house is $2^n-1$, so the street has exactly $2^n$ bytes. That number $2^n$ is called the address space.

Why the topic needs it. The entire subject is one machine: turn a VA into a PA. Two streets, one secret map between them. Every later symbol exists only to describe that map.

3. Hexadecimal — writing bits without going cross-eyed

Why the topic needs it. The parent's worked example writes $\text{VA}=0x1A2B3$. Because one hex digit = 4 bits and a 4 KiB page uses the low 12 bits $=$ 3 hex digits, the offset is simply "the last three hex digits" — you can read the split off by eye. This only works because hex groups bits in fours.

4. The offset operators — mod and shift

Now we earn the two symbols the parent uses without ceremony: $\mathrm{mod}$ and $\gg$.

Why the topic needs it. These two operators are the address split. Master them and lines like $\text{offset}=A\mathrm{mod}{2}^p,\text{VPN}=A\gg p$ stop being magic and become "keep the bottom bits / keep the top bits".

5. Building back up — shift-left << and OR |

Why the topic needs it. To rebuild a physical address the parent writes $\text{PA}=(\text{PFN}\ll p)\mid \text{offset}$. Shift-left opens the gap; OR drops the untouched offset into it. It is the exact reverse of step 4 — split apart, then snap together.

6. Page, frame, and the map between them

Since pages and frames are the same size, moving a page into a frame is a rigid shift: byte 5 of the page becomes byte 5 of the frame. That is precisely why the offset is copied unchanged and only the page/frame number is translated.

Why the topic needs it. This is the destination of every earlier brick: bits → address → split → look up VPN in the table → get PFN → rebuild. If memory is the row of bytes and locality is why the cache/replacement machinery pays off, this map is the heart.

Prerequisite map

Equipment checklist

Cover the right side and answer aloud before moving to the parent note.