
The Illusion of Contiguous Private Memory
Every user-space process on a modern operating system operates under a convenient hardware illusion: it appears to own a vast, contiguous, private address space starting near zero, completely isolated from every other running program.
In physical reality, RAM is shared among dozens of concurrent processes, and the physical memory backing any single process is scattered across non-contiguous hardware framesβor temporarily evicted to disk. The hardware-software mechanism that maintains this illusion is virtual memory paging, mediated by the CPU’s Memory Management Unit (MMU) and the kernel’s page tables.
Why Fixed-Size Pages?
Early operating systems allocated physical memory to processes in contiguous variable-sized blocks. As processes started, grew, and terminated, free physical RAM fractured into small, non-contiguous gapsβexternal fragmentationβwhere plenty of total free memory existed, yet no single contiguous region was large enough to fit a new process.
Paging eliminates external fragmentation by decoupling logical contiguity from physical contiguity:
- The virtual address space seen by a process is partitioned into fixed-size blocks called pages (typically $4\text{ KiB} = 2^{12}\text{ bytes}$).
- Physical RAM is partitioned into blocks of the exact same size called page frames.
Because every virtual page and every physical frame have the exact same size, any virtual page can map to any available physical frame. This gives the kernel four structural capabilities:
- Zero External Fragmentation: Any free physical frame can satisfy any single-page allocation request.
- Demand Paging: A process does not need all of its pages in RAM to execute; pages are allocated and loaded only when the CPU actually touches them.
- Process Isolation: Because Process A’s page table only contains mappings to Process A’s frames, it is impossible for Process A to even nameβlet alone corruptβProcess B’s private physical memory.
- Zero-Copy Sharing: Shared libraries (
libc.so) and Copy-on-Write (fork) map the same physical frame into multiple page tables with read-only permissions.
The Mechanics of Address Translation
With a page size of $2^p$ bytes (for $4\text{ KiB}$ pages, $p = 12$), the hardware splits every $W$-bit virtual address $v$ into two bitfields without performing any division:
- Virtual Page Number (VPN): The upper $W - p$ bits ($v \gg p$), which index into the process’s page table.
- Page Offset: The lower $p$ bits ($v \mathbin{&} (2^p - 1)$), which specify the exact byte offset within the page. Because pages and frames are the same size, the offset passes through translation unchanged.
| |
When the MMU translates a virtual address:
- It indexes the process’s Page Table at entry $\text{VPN}$ to read the Page Table Entry (PTE).
- If the PTE’s
presentbit is0, the page is not in RAM: the MMU raises a Page Fault exception, trapping into the kernel so the OS can allocate a physical frame, populate the PTE, and retry the instruction. - If
present == 1and access permissions (writable,user) pass, the MMU extracts the Physical Frame Number (PFN), sets the hardwareaccessedbit (anddirtybit on writes), and forms the physical address:
$$\text{Physical Address} = (\text{PFN} \ll 12) ;\mid; \text{Offset}.$$
Accelerating Lookups with the TLB
There is a glaring performance problem with naive page table translation: the page table itself lives in main memory. If every CPU load or store instruction required reading a Page Table Entry from RAM before reading the target data from RAM, every memory access would take twice as long.
Hardware solves this by placing a small, associative hardware cache inside the MMU called the Translation Lookaside Buffer (TLB). The TLB caches recent $\text{VPN} \to \text{PFN}$ translations along with their permission bits:
- TLB Hit (< 1 cycle): The MMU translates the address immediately on-chip without touching the page table in RAM.
- TLB Miss: The hardware page walker (or OS trap handler on software-managed TLBs) reads the Page Table Entry from RAM, inserts the mapping into the TLB, and completes the access.
Because programs exhibit strong spatial and temporal localityβaccessing variables on the same $4\text{ KiB}$ stack or heap page hundreds of times in a rowβeven a 64-entry TLB achieves hit rates above $99%$.
Simulating an MMU, Page Table, and TLB in C
Let’s implement a complete, self-contained simulation of an MMU with demand-allocated frames, permission enforcement, and a round-robin TLB in modern C.
Instead of returning magic signed -1 values inside unsigned address types, we return an explicit MmuStatus result enum and use bitwise shifts (>> 12, & 0xFFF) exactly as hardware does:
| |
Key Takeaways from the Simulation
- Bitwise Decomposition: Extracting
vpn = vaddr >> 12andoffset = vaddr & 0xFFFrequires a single cycle in hardware because page sizes are always powers of two. - Cold Misses vs. Warm Hits: In
main(), the first 5 writes touch 5 unmapped pages, triggering 5 TLB misses and 5 demand page faults. The subsequent 5 reads hit directly in the TLB (TLB hits = 5, TLB misses = 5, Page faults = 5). - Context-Switch Flushing: Because TLB entries map process-local VPNs to physical frames, switching to a different process requires either flushing the TLB (on
CR3reload) or tagging TLB entries with an Address Space Identifier (ASID / PCID) so multiple processes can coexist in the TLB without colliding.