From blocks to a lookup table
Guide 1 left you with the two halves of paging. A process's view of memory is sliced into equal-sized pages, physical RAM is sliced into equal-sized frames of the same size, and any page can sit in any frame. Because every block is the same size, a page slots into a frame the way a book slots into any empty shelf gap — that is the whole reason paging kills external fragmentation. But it leaves an obvious question dangling: if page 5 of my program can be in frame 200, frame 17, or anywhere at all, how does the hardware ever find it? Something has to remember where each page actually landed.
That something is the page table. Picture it as a book's index: one row per page, kept in page-number order, and each row tells you the frame that page currently lives in. The program never sees it — the program only ever uses logical addresses (page 5, byte 40), the comfortable made-up addresses it was compiled with. The page table is the dictionary that turns those into physical addresses (frame 200, byte 40), the real locations in RAM. There is one page table per process, because each process has its own private numbering of pages, and the kernel keeps it as part of the process's bookkeeping.
Splitting an address in two
Here is the clever trick that makes paging cheap: a logical address is not really one number, it is two numbers wearing a single coat. The high bits are the page number — which page — and the low bits are the offset — how far into that page. This is the page-number / offset split, and the hardware does it for free just by reading different bits of the same address. Nobody has to do division; the page size is a power of two precisely so the split is a clean cut between bit ranges.
Let us walk one address by hand. Say a 4 KB page, because that is the classic size. A 4 KB page is 2^12 = 4096 bytes, so the offset needs exactly 12 bits to name any byte inside one page. On a 32-bit machine that leaves 32 - 12 = 20 bits for the page number, so there are 2^20 = about a million possible pages. Now take a concrete logical address: page number 5, offset 40. The hardware reads the top 20 bits as 5, looks up row 5 of the page table, and finds — let us say — frame 200. It then glues frame 200 back together with the unchanged offset 40 to form the physical address. The offset never went through the table; only the page-to-frame swap happened.
logical address = ( page number , offset ) <- one address, two fields
32-bit address, 4 KB page (offset = 12 bits, page# = 20 bits)
[ page number = 5 | offset = 40 ]
| |
| look up row 5 | (unchanged, rides along)
v in page table |
page table[5] = frame 200 |
| |
v v
[ frame number = 200 | offset = 40 ] = physical addressNotice what the offset size quietly fixes: it is the page size. A 12-bit offset means a 4 KB page, full stop — you cannot have one without the other. This is also where paging's small confession lives. Because memory is handed out a whole page at a time, the last page of a process is almost never filled exactly to the brim, and the leftover slack inside it is wasted. That waste is internal fragmentation: paging trades away the messy external fragmentation of variable holes for a little tidy internal waste, at most one page per region. It is a genuinely good trade, but it is a trade, not a free lunch.
Where the table lives, and the two-access problem
So where is the page table itself? It is too big to keep in CPU registers — a million rows will not fit on a chip — so the page table lives in main memory, just like ordinary data. The CPU therefore needs to be told where, and that is the job of the page-table base register (PTBR): a single register holding the physical address of the start of the current process's table. To read row 5, the hardware computes PTBR + 5 times the entry size and reads that location. This is also exactly what makes a context switch cheap for paging: to switch to another process, the kernel just reloads the PTBR to point at that process's table. The whole address space changes with one register write.
But putting the table in memory has a brutal cost, and you should feel it. Every single memory reference the program makes now becomes two memory references: first the hardware reads the page table to translate the address, and only then reads the actual data the program wanted. Want one byte of your array? That is one access to consult the table, plus one access to fetch the byte — every time, on every instruction. This is the double-memory-access problem, and it means naive paging would run your machine at roughly half speed. Memory is already the slow part of the memory hierarchy; doubling every touch is not a tax you can pay.
It is worth being precise about who actually does all this. The translation is not software — the kernel does not run code on every memory access, that would be hopeless. It is hardware: a dedicated unit called the memory-management unit (MMU) sits between the CPU and memory and performs the lookup-and-substitute on the fly for every address. The kernel's role is to set up the table in memory and load the PTBR; the MMU does the per-access grunt work at hardware speed. This whole hardware dance — split the address, consult the table, build the physical address — is what we mean by address translation.
The fix: a tiny cache of recent translations
The escape from the double-access problem is the translation lookaside buffer (TLB). Think of it as the sticky notes you stick to the pages you just used. The full page table is the book's index, sitting in slow memory; the TLB is a handful of sticky notes — a small, very fast hardware cache, right on the MMU — that remembers the few most recently used (page number to frame number) pairs. Before walking out to the page table, the MMU glances at its sticky notes first.
On a TLB hit, the page number is already on a sticky note: the frame comes back essentially instantly and there is no extra trip to memory — translation costs almost nothing. On a TLB miss, the page number is not there, so the MMU must do the slow walk out to the page table in memory (the full second access), find the frame, and then add that pair to the TLB for next time, evicting an old note to make room. The whole bet rests on locality: programs touch the same handful of pages over and over (a loop, a stack, the current data), so once a page is on a sticky note, the next thousand accesses to it are hits.
You can put a number on why this works, and it is striking. Suppose a memory access takes 100 nanoseconds, the TLB lookup is so fast we round it to 0, and the TLB hit rate is 99%. The effective access time averages the two cases: a hit costs one access (100 ns) and a miss costs two (200 ns, one to read the table plus one for the data). So the average is 0.99 times 100 + 0.01 times 200 = 99 + 2 = 101 ns. We are paying barely 1% over the cost of unpaged memory, instead of the 100% penalty the double-access problem threatened. A small cache with a high hit rate turned a disastrous tax into a rounding error — which is exactly why guide 3 is devoted entirely to the TLB.
What else lives in a page-table entry
A row of the page table is more than a frame number. Each page-table entry (PTE) carries a few extra bits that the MMU checks on the fly, and they turn the table from a mere address map into the enforcer of memory safety. Three matter most. The valid bit says whether this page is actually mapped to a frame at all; if the program touches a page whose valid bit is off, the MMU refuses and raises a trap. That trap is how the kernel learns the program either made a wild reference or — more usefully — touched a page that is not in RAM right now, which is the doorway to page faults and virtual memory in the next rung.
The protection bits say what you are allowed to do with the page: readable, writable, executable, in any combination — the same read/write/execute idea you have already met as file permissions like rwxr-xr-x, now applied per page of memory. If a program tries to write a page marked read-only, or to execute a page marked non-executable, the MMU traps before any damage is done. This is how the OS keeps a process from scribbling on its own code, and how it can mark code pages execute-only for safety. Because these checks live in the PTE and are enforced by hardware on every access, protection costs nothing extra at run time.
The third bit is the dirty bit, and it is pure bookkeeping for later. The MMU sets it automatically the first time the page is written. Why bother? Because when virtual memory later needs to evict this page to make room, a clean (never-written) page can simply be dropped — its copy on disk is still good — while a dirty page must first be written back. The dirty bit lets the OS skip that write-back for unchanged pages, which is a real speed win you will lean on heavily two rungs from now. A small related point that the next guide develops: because the PTE names the frame, two processes can have entries pointing at the same frame, which is how shared pages let a library or read-only data be mapped once and used by many.