The Page Table

A page table is a per-process data structure that records, for every virtual page a process is permitted to use, where that page currently lives in physical memory. Concretely, it is an array indexed by virtual page number (VPN); the entry at index `i` is the page table entry (PTE) for virtual page `i`. The PTE's central payload is the physical frame number (PFN), the address (in frame-sized units) of the physical memory that backs this virtual page. Because pages and frames are the same fixed size (commonly 4 KiB), a virtual address splits cleanly into two independent fields: a VPN, used only to index the page table, and a page offset, which never changes during translation and is simply copied through to the physical address. The PTE is more than a frame number, however. It is a compact record of everything the hardware needs to decide, in a single lookup, three questions: is this mapping legitimate at all (valid bit), what operations does the process have permission to perform on this page (protection bits — readable, writable, executable), and has this page been used or modified since some reference point (reference bit and dirty bit, consumed by the page-replacement and write-back machinery). Because translation happens on nearly every instruction, all of this must be resolved by dedicated hardware — the memory management unit (MMU) — walking a table that the operating system builds and installs, but does not itself touch on the common path. The crucial architectural decision embodied in the page table is the separation of concerns between the OS and the hardware. The OS decides the mapping — which frame backs which page, and under what permissions — and writes that decision into the table. The hardware performs the translation — the actual arithmetic of turning a VPN into a PFN — on every memory reference, transparently to the running program. This division is what makes paging fast enough for general use: software configures policy once per page-table-changing event (a page fault, a mapping call, a context switch), while hardware executes the mechanism billions of times per second.

Address translation, step by step

A virtual address of `n` bits, with a page size of `2^p` bytes, is interpreted by hardware as two fields: ``` virtual address = [ VPN (n - p bits) | offset (p bits) ] ``` The offset is never translated — it addresses a byte within whichever frame the page maps to, and physical frames are the same size as virtual pages, so the offset transfers unchanged. Translation reduces entirely to looking up the VPN. ``` PSEUDOCODE: hardware address translation (single-level page table) function TRANSLATE(virtual_address): VPN = virtual_address >> p # top (n - p) bits offset = virtual_address & (2^p - 1) # bottom p bits if VPN >= page_table_length: raise SEGMENTATION_FAULT # VPN outside allocated table PTE = page_table[VPN] # single array access, O(1) if PTE.valid == 0: raise PAGE_FAULT(VPN) # trap to OS: page not resident if current_access is WRITE and PTE.writable == 0: raise PROTECTION_FAULT(VPN) if current_access is EXECUTE and PTE.executable == 0: raise PROTECTION_FAULT(VPN) PTE.reference = 1 # hardware sets on every access if current_access is WRITE: PTE.dirty = 1 # hardware sets on writes only PFN = PTE.frame_number physical_address = (PFN << p) | offset return physical_address ``` Every branch above except the final arithmetic is a protection or presence check; the actual translation is one shift, one mask, and one concatenation. The expensive part in a naive design is the memory access to fetch `page_table[VPN]` itself, which is why real systems cache recent translations (foreshadowing the Translation Lookaside Buffer).

Anatomy of a page table entry

A typical PTE, drawn to scale for a 32-bit system with 4 KiB pages (so a 20-bit frame number), looks like this: ``` PSEUDOCODE: PTE field layout (illustrative 32-bit entry) bits 31..12 : Frame Number (PFN) — 20 bits, physical frame address bit 11 : Valid — 1 = mapping exists, 0 = fault on access bit 10 : Protection: Read — 1 = readable bit 9 : Protection: Write — 1 = writable bit 8 : Protection: Execute — 1 = executable bit 7 : Dirty (modified) — 1 = page written since loaded bit 6 : Reference (accessed) — 1 = page read or written recently bit 5 : Cache-disable — 1 = bypass cache (e.g., MMIO pages) bit 4 : User/Supervisor — 1 = accessible from user mode bits 3..0 : reserved / OS-defined — e.g., copy-on-write markers ``` The exact bit widths and positions vary by architecture (x86-64 PTEs are 64 bits and include a no-execute bit, for instance), but every production page table encodes some version of this same set of fields, because each field answers a question the hardware must resolve on every access:

• Valid bit — is there a mapping at all? If 0, the VPN may be entirely unused, or the page may be legitimately mapped but currently swapped to disk; either way, hardware cannot proceed and must trap to the OS, which resolves the situation (allocate, deny, or fetch from disk) — the mechanism behind Page Faults.
• Protection bits — what operations are allowed? Read-only pages (like `.text` segments) reject writes; non-executable pages (like the stack, on modern hardware) reject instruction fetches, blocking a large class of code-injection exploits.
• Dirty bit — has this page been modified? Set by hardware on writes, read by the OS's eviction logic: a clean page can be discarded and reloaded from its backing file for free, but a dirty page must first be written back to disk.
• Reference bit — has this page been touched at all? Set by hardware on any access, periodically cleared and sampled by the OS to approximate least-recently-used behavior for page replacement, without paying the cost of maintaining an exact LRU order.

Who sets each bit, and when

This division of labor is easy to state and important to remember precisely:

The pattern is: the OS decides policy and writes it once; hardware observes activity and records it continuously; the OS periodically reads and resets the observation bits to make replacement decisions. No instruction the running program executes directly manipulates a PTE — that would break the entire protection model — so all of this happens invisibly, at the cost of one indirect memory access per reference.

Time complexity. A single-level page table gives O(1) translation: the VPN is used as a direct array index, so lookup is a single arithmetic computation plus one memory read — no searching, no comparisons against stored keys. This is the entire point of using a page table rather than, say, a hash map or sorted list of mappings: arrays support constant-time random access by construction, and the VPN is already exactly the index we need. Compare this to a hypothetical scheme that stored mappings as `(VPN, PFN)` pairs to be searched linearly — that would cost O(number of resident pages) per memory reference, which is obviously unusable when every load and store needs a translation. The catch is that this O(1) lookup is paid in addition to the actual memory access the program requested — translating an address costs one extra memory reference to fetch the PTE, then a second memory reference to fetch the actual data. Naively, every memory instruction becomes two memory accesses, roughly doubling effective memory latency. This overhead is precisely why hardware caches recent translations in a Translation Lookaside Buffer, turning the common case back into effectively one access; that mechanism is developed as its own topic but the need for it originates entirely here.

Space complexity. A single-level page table requires one PTE per virtual page in the address space that the table covers, regardless of how many of those pages are actually resident in physical memory. For a 32-bit virtual address space with 4 KiB pages, there are `2^32 / 2^12 = 2^20` (roughly one million) possible VPNs; at 4 bytes per PTE, that is a 4 MiB table — per process, even for a process that only actually uses a few kilobytes of memory. This is the central space inefficiency of the flat, single-level design: table size scales with the size of the address space, not with the amount of memory actually used. On a 64-bit address space the naive table would need to cover `2^52` or more entries, which is physically impossible to allocate contiguously — this scaling failure is exactly what motivates Multilevel Page Tables (which only allocate table space for regions of the address space actually in use) and Inverted Page Tables (which size the table by physical frames rather than virtual pages).

Correctness argument. The correctness of hardware-walked translation rests on a simple invariant that the OS must uphold and the hardware must enforce: > Invariant: at any instant, for every VPN with `valid = 1` in process P's page table, the corresponding frame number is a physical frame that is validly, exclusively (or intentionally shared) allocated to P, and no other process's page table maps that same frame with conflicting permissions unless sharing is deliberate. Given this invariant, the translation algorithm is correct by direct inspection: it checks validity before dereferencing the frame number (so it never follows a stale or garbage mapping), checks the requested operation against the protection bits before allowing the access (so a process can never write to a read-only page or execute non-executable data through a legitimate translation), and otherwise performs a pure, side-effect-free (aside from setting reference/dirty bits) computation from VPN to PFN. Maintaining the invariant is the OS's responsibility: it must update the page table atomically with respect to memory allocation and deallocation (never leave a valid PTE pointing at a freed frame), and must flush stale cached translations whenever it changes a mapping — a concern that becomes sharper once a TLB is introduced, but the underlying correctness obligation exists even for a page-table-only design.

Honest tradeoffs. The single-level table is simple to reason about and to implement, and gives worst-case-optimal O(1) lookup time. Its cost is memory: it is wasteful for sparse address spaces (most 64-bit processes use a tiny fraction of their address space) and it must be entirely resident (or itself paged, which reintroduces the very problem paging solves) for translation to proceed. It is the right mental model to build first, precisely because every more sophisticated structure covered next is a targeted fix for this one weakness.

Consider a toy machine with 16-bit virtual addresses and a page size of 256 bytes (`2^8`), so the address splits into an 8-bit VPN and an 8-bit offset. Process A has been allocated frames 0x2A, 0x3F, and 0x08 for its first three pages, and its stack lives in the highest virtual page, VPN 0xFF, backed by frame 0x71. All other entries are invalid. The relevant portion of process A's page table:

Trace 1 — a legal write. The CPU executes a store to virtual address `0x01C4`. 1. Split: VPN = `0x01C4 >> 8 = 0x01`, offset = `0x01C4 & 0xFF = 0xC4`. 2. Fetch `page_table[0x01]`: valid = 1, writable = 1, frame = 0x3F. 3. Requested operation is WRITE and `writable = 1` → permitted. 4. Set reference = 1 (already 1), set dirty = 1 (already 1). 5. Physical address = `(0x3F << 8) | 0xC4 = 0x3FC4`. The store proceeds to physical address `0x3FC4`. No trap occurs.

Trace 2 — a protection fault. The CPU attempts to execute an instruction fetched from virtual address `0x0050` (inside VPN 0x00). 1. Split: VPN = `0x00`, offset = `0x50`. 2. Fetch `page_table[0x00]`: valid = 1, executable = 1, frame = 0x2A. 3. Requested operation is EXECUTE and `executable = 1` → permitted. 4. Physical address = `(0x2A << 8) | 0x50 = 0x2A50`. Now suppose instead the CPU attempts a write to `0x0050` (VPN 0x00 has `writable = 0`): 3'. Requested operation is WRITE, but `writable = 0` on VPN 0x00 → protection fault raised. The hardware traps into the OS, which typically delivers a segmentation-violation signal to the process, because VPN 0x00 (holding, say, read-only code) was never meant to be written.

Trace 3 — an unmapped access triggering a page fault. The CPU accesses virtual address `0x0301` (VPN `0x03`). 1. Split: VPN = `0x03`, offset = `0x01`. 2. Fetch `page_table[0x03]`: valid = 0. 3. Hardware raises a page fault, trapping to the OS before any physical address is computed. 4. The OS's fault handler inspects why VPN 0x03 is invalid: perhaps it is genuinely unmapped (segmentation violation), or perhaps it is a legitimately allocated page currently swapped to disk. In the latter case the OS allocates a frame, loads the page's contents, updates the PTE (`valid ← 1`, `frame ← new_frame`), and retries the faulting instruction — the beginning of the story told fully under Page Faults. This example shows the three outcomes translation can produce — success, protection fault, page fault — all emerging from the same handful of bits inspected in a fixed order.

The page table's lineage is inseparable from the invention of virtual memory itself, which arose from a very concrete engineering pressure: programs in the 1950s and 1960s routinely needed more address space than physically installed memory, and manual overlay management by programmers was slow and error-prone. Researchers at the University of Manchester built the Atlas computer, whose "one-level store" introduced hardware-assisted address translation and demand paging — the direct ancestor of every page table since. The core idea, that hardware could transparently remap addresses on every access while the operating system managed the mapping in the background, is the same idea this article has walked through bit by bit.

Every general-purpose operating system kernel in production — Linux, Windows, macOS/XNU, the BSDs, Android's kernel, and every hypervisor performing nested translation for virtual machines — maintains per-process page tables walked by the CPU's MMU on essentially every memory access. The protection bits described here are the mechanism behind memory isolation between processes: a bug or malicious code in one process cannot read or overwrite another process's memory because their virtual addresses translate through entirely separate page tables into disjoint (or deliberately shared) frames. The executable-permission bit is a first line of defense against a large class of exploits that attempt to run injected data as code (data-execution prevention / "NX bit" protections rely on exactly this field). The dirty and reference bits are the raw signal consumed by every page-replacement algorithm — clock, second-chance, and approximations of LRU — that decide which pages to evict under memory pressure, connecting this article directly to Page Faults and the broader machinery of demand paging. And the scaling limitation exposed at the end of the complexity discussion — that a flat table costs space proportional to virtual address space size — is the direct, explicit motivation for the two major structural alternatives covered next: Multilevel Page Tables, which allocate table space lazily by region, and Inverted Page Tables, which invert the indexing to scale with physical memory instead.

Ask the tutor: How does a multilevel page table reduce the memory overhead of a sparse address space while keeping translation reasonably fast?