Pages, Frames, and the Page Table

Cut the illusion into equal tiles

In the previous guide we met the grand promise of virtual memory: every program believes it owns one long, private, contiguous stretch of addresses, while a translator quietly maps its imaginary rooms onto the real building. The obvious question is how — if a program asks for byte number 4,000,000, where does that byte actually live in physical RAM? Mapping every single byte individually would need a map as big as memory itself, which is absurd. So we do not map bytes. We map blocks.

The block is the central object of this whole rung, so meet it properly. We slice the virtual address space into equal-sized chunks called pages, and we slice physical RAM into equal-sized chunks of exactly the same size called frames (or page frames). A typical size is 4 KB — that is 4096 bytes, or 2^12. A page is just an idea, a tile in the program's imaginary house; a frame is a real slot in the actual building. The job of paging is to decide which page currently lives in which frame, and they need not be in the same order at all.

An address is secretly two numbers

Here is the beautiful part that makes paging cheap. Because pages are a power of two in size, a virtual address splits cleanly into two fields, exactly the way a cache address split into tag, index, and offset back in the memory-hierarchy rung. The low bits are the offset — which byte within the page — and the high bits are the page number — which page. With 4 KB pages, the bottom 12 bits (because 2^12 = 4096) are the offset, and everything above is the virtual page number.

  32-bit virtual address, 4 KB pages (offset = 12 bits)

     31                         12 11                0
    +-----------------------------+-------------------+
    |   virtual page number (20)  |   offset  (12)    |
    +-----------------------------+-------------------+
             |  translate                  |  copied
             v  (page -> frame)            v  unchanged
    +-----------------------------+-------------------+
    |   physical frame number     |   offset  (12)    |
    +-----------------------------+-------------------+

  example:  virtual 0x00402F00
            page# = 0x00402  ->  table says frame 0x019
            offset = 0xF00   ->  copied straight through
            physical = 0x019F00

Look at what this buys us. The offset never needs translating — a byte's position inside its tile is identical whether you call the tile a page or a frame. So the whole act of address translation reduces to one lookup: take the virtual page number, find the physical frame number it currently maps to, and glue that frame number in front of the unchanged offset. That single substitution, page number to frame number, is the entire trick. Everything else in this guide is just where we keep the substitution table and how we make the lookup fast.

The page table: one big lookup notebook

Where does the translator keep the page-to-frame mapping? In a structure called the page table — conceptually just a long array, indexed by virtual page number, where each slot tells you the frame that page lives in. To translate, you use the page number as an index into the table and read out the frame number. Crucially, each running program has its own page table, so the same virtual address in two different programs lands on two different frames. That is precisely how the house illusion works: identical room numbers, different real buildings.

Each entry in this notebook is a page table entry (PTE), and it holds more than just a frame number — it carries a handful of status bits that do the real safety work. A valid bit says whether this page is currently mapped to a real frame at all. Protection bits say what is allowed: readable, writable, executable. And a present (or resident) bit says whether the page is actually sitting in RAM right now, or has been pushed out to disk. The frame number plus these bits are the mapping — small, but every load and store the machine ever performs passes through one.

Those bits are how virtual memory delivers the second promise from the last guide: protection. If a load targets a page whose valid bit is off, or a store targets a page whose writable bit is off, the hardware refuses and traps to the operating system — this is what catches a wild pointer or a stray write before it can corrupt anything. The same machinery enforces the user/kernel boundary, since kernel pages are simply marked off-limits to user code. Translation and protection are not two systems bolted together; they are the same lookup, which is why we keep insisting virtual memory is address translation plus protection, never merely 'extra RAM'.

Walking one translation, step by step

Let us trace a single load through the page table, the long way, with no shortcuts yet. Suppose a program executes a load from virtual address 0x00402F00 with 4 KB pages. The hardware needs to turn that virtual address into a physical one before it can fetch the byte. Here is every step it takes.

1. Split the address. The low 12 bits, 0xF00, are the offset within the page. The high 20 bits, 0x00402, are the virtual page number. Only the page number will be translated.
2. Find this program's page table. A special hardware register (often called the page-table base register) points at the start of the current program's page table in physical memory.
3. Index into it. Use the virtual page number 0x00402 as the index and read out that page table entry — this read is itself a memory access.
4. Check the bits. Is the valid bit set? Is a load allowed by the protection bits? Is the page present in RAM? If any check fails, trap to the OS instead of continuing.
5. Assemble the physical address. Take the frame number from the entry — say 0x019 — and place the unchanged offset 0xF00 after it to get physical address 0x019F00. Now finally fetch the byte.

Notice the painful cost hiding in step 3. Reading the page table entry is itself a trip to memory. So a naive paged machine turns every single load or store into two memory accesses — one to read the mapping, then one to read the actual data. That would roughly halve performance, which is unacceptable. The fix is a tiny, fast cache of recent translations called the TLB, and it is the whole subject of guide 4; for now just register that the page table works, but on its own it would be ruinously slow.

The table is too big — so we page the table itself

There is a second problem, and it is about size, not speed. A flat page table needs one entry for every possible virtual page, whether the program uses it or not. On a 32-bit machine with 4 KB pages there are 2^20 pages, so about a million entries of, say, 4 bytes each — 4 MB of table per program. Bad, but survivable. On a 64-bit machine the same flat scheme would demand a page table larger than all the RAM that has ever been manufactured. A single contiguous array is simply impossible.

The cure is wonderfully self-referential: page the page table. A multilevel page table breaks the single giant array into a tree of small tables. The virtual page number is itself sliced into several fields, and each field indexes one level of the tree: the top field picks an entry in the root table, which points to a second-level table, whose entry points to the next, until the last level finally yields the frame. The genius is that subtrees covering unused address ranges simply do not exist — a program touching only a few megabytes pays for only a few small tables, not the whole impossible million.

All of this lookup — splitting the address, walking the levels, checking the bits, assembling the result — is done by a dedicated piece of hardware called the memory management unit (MMU), which sits between the processor and memory and translates on every access. The MMU and the multilevel walk are the deep subject of guide 5. The honest cost to remember: a multilevel table trades space for time, since now a single translation may require several memory reads to walk the tree — which is exactly why the TLB from guide 4 is not a luxury but a necessity. Virtual memory is a hardware/OS co-design, and a TLB miss or page fault can quietly dominate performance.