The table that won't fit
By now you have the flat picture from guide 2: a page table is one big array, indexed by page number, whose entries hand you the frame to use. It is a book's index — look up the page number, read off where it really lives. That picture is correct and it is enough for a small machine. The trouble starts when the address gets big, and modern addresses are very big.
Let us do the arithmetic, because it is the whole reason this guide exists. Take a 32-bit address and a 4 KB page. The offset eats the low 12 bits, since 2^12 = 4096 = 4 KB. That leaves 32 - 12 = 20 bits for the page number, so there are 2^20 = about a million pages, hence a million entries. If each page-table entry is 4 bytes, the flat table is 2^20 times 4 = 4 MB. Now here is the sting: that is 4 MB per process, and the whole table must be in memory and contiguous. With a hundred processes you have spent 400 MB just on tables.
And 32 bits is the easy case. Repeat the sum for a 64-bit address: the page number is now 64 - 12 = 52 bits, so a flat table would have 2^52 entries — that is millions of gigabytes, larger than all the RAM that has ever been manufactured, for a single process. A flat table is simply impossible here. But notice something hopeful: a process with a 64-bit address space does not actually use most of it. Its code, heap, and stack occupy a few small regions, and the vast middle is empty. We are paying to store a mostly-empty index. Every trick in this guide is a way to stop paying for the empty parts.
A tree of small tables
The first and most common escape is the multi-level (hierarchical) page table. The idea is to page the page table itself: instead of one giant array, split the page number into parts, use the first part to look up a small top-level table whose entries point to second-level tables, whose entries finally point to frames. Think of a phone book split into volumes by first letter — the thin outer index tells you which volume to open, and only the volumes you actually need have to exist. Concretely, take that 32-bit, 4 KB-page case again, where the page number is 20 bits. Split those 20 bits into 10 and 10. The top 10 bits index an outer table of 2^10 = 1024 entries; each of those points to an inner table of another 1024 entries; the bottom 12 bits are the offset as before. So one logical address now reads as three fields instead of two: (outer index, inner index, offset). Each individual table is 1024 entries times 4 bytes = 4 KB — exactly one page, which is no accident: each level fits neatly in a frame, so the OS can store and even page out the tables themselves.
32-bit logical address, 4 KB pages:
| 10 bits | 10 bits | 12 bits |
| outer | inner | offset |
index index
outer table inner table frame in RAM
+----------+ +----------+ +-----------+
| [outer]--|-------->| [inner]--|------->| byte at |
+----------+ +----------+ | offset |
(1024 entries, (1024 entries, +-----------+
one page) one page)
Win: an unused outer entry = NO inner table at all (saves 4 KB).Here is where the saving appears. A process that uses only a little memory needs its one outer table plus just the few inner tables that cover its actual pages; every outer entry pointing at an empty region is simply marked absent, and that whole inner table is never allocated. A tiny process might use the outer table and two inner tables — about 12 KB total instead of 4 MB. The mostly-empty middle of the address space now costs almost nothing, which is exactly what we wanted. Real 64-bit machines just add more levels: typical x86-64 uses four levels (and newer chips offer five) to cover the 48- or 57-bit addresses they actually implement.
Walking a two-level address
Let us trace one translation by hand so the mechanism feels real, using our two-level scheme of (10 bits, 10 bits, 12 bits). Say the CPU produces the logical address 0x00402_C04 — concretely, suppose it decodes to outer index 1, inner index 2, and offset 3076. The hardware (the page-table walker inside the MMU) does the following, and crucially the page-table base register tells it where the outer table lives.
- Split the address. The hardware carves the bits into (outer = 1, inner = 2, offset = 3076). No memory touched yet — this is just wiring.
- Read the outer table. Go to the page-table base register, jump to entry 1 of the outer table, and read it. (Memory access number one.) If that entry is marked absent, the region is unmapped — raise a fault. Otherwise it holds the physical address of an inner table.
- Read the inner table. Jump to entry 2 of that inner table and read it. (Memory access number two.) Check its valid bit and protection bits; if invalid, fault. Otherwise it gives the frame number — say frame 87.
- Form the physical address. Combine frame 87 with the offset 3076 to get the real physical address, then finally read or write the data the program actually wanted. (Memory access number three — the useful one.)
Count the cost: three memory accesses to fetch one byte, two of them pure overhead spent walking the tree. That overhead repeats on every single instruction, which would triple your memory traffic and cripple the machine. This is the address translation cost made vivid, and it is why the TLB exists — it caches the final (page number to frame) result so the next access to a nearby address skips steps 2 and 3 of the walk entirely and goes straight to the data.
When the tree is still too tall: hashed and inverted tables
The multi-level tree saves space, but on a 64-bit machine the tree itself can grow tall — four or five levels means four or five walk accesses on a TLB miss. Two alternative designs sidestep the deep tree. The first is the hashed page table. Instead of indexing by page number directly, you hash the page number and use that as an index into a hash table. Each slot holds a small chain of entries, and each entry records the actual page number it stands for (so you can tell collisions apart), plus the frame. You hash the page number, jump to that slot, then walk the short chain comparing page numbers until you find the match.
The win is that the table size tracks how many pages are actually mapped, not how huge the address space could be — a sparse 64-bit space costs little. The catch is the chain: a translation might compare several entries, and bad hashing makes chains long. Hashed tables shine for the enormous, sparsely-used address spaces of 64-bit systems.
The second design is the boldest: the inverted page table. Notice that every scheme so far keeps one table per process and indexes it by page number. Inverting flips this on its head: keep just one table for the whole machine, with exactly one entry per physical frame of RAM. Each entry says which process and which virtual page currently occupies that frame. Since RAM is fixed and modest (a few million frames), this one table is small and its size never depends on how big or how many address spaces exist. A 256-frame box has a 256-entry table, full stop.
But inverting creates a new headache. To translate, the CPU has a (process, page number) and wants a frame — yet the table is indexed by frame, the wrong way round. In principle you would have to scan every entry looking for the matching (process, page) pair, which is hopeless on every access. The real fix is to pair the inverted table with a hash: hash the (process, page number) to jump near the right entry, then check. And of course the TLB still sits in front, so most accesses never touch the inverted table at all. One more cost worth naming: sharing a frame between processes is awkward, because each frame has just one entry naming one owner — a topic the next guide picks up.
Choosing — and what stays the same
There is no single winner; each design trades one cost for another. The multi-level tree is the default on common hardware: simple, well-supported, but it can need several walk accesses, and it still uses one tree per process. Hashed tables let table size follow actual usage and suit huge sparse spaces, but a translation may chase a chain. Inverted tables bound total table size to physical RAM regardless of how many processes run, but make lookup and sharing harder and lean heavily on a hash plus the TLB. The right choice depends on the address-space size and the hardware you are building for.
Through all three designs, hold on to what does not change, because that is the durable understanding. The split of a logical address into (page number, offset) is identical everywhere — these schemes only change how the page number is turned into a frame, never the offset. The per-page bookkeeping bits travel with the entry no matter the structure: the valid bit, the protection bits (read/write/execute), and the dirty bit you met in guide 2 still live in each page-table entry. And the TLB sits in front of all of them, so on a hit the chosen structure's cost vanishes entirely — multi-level, hashed, or inverted, a TLB hit looks the same to the CPU.