Virtual memory gives each process its own virtual address space, offering isolation and flexible mapping to physical memory or backing storage on disk. The operating system (OS) maintains these mappings in page tables, while the CPU’s [Memory Management Unit] and its Translation Lookaside Buffer translate virtual addresses to physical addresses on every memory access.
Page Tables
Page tables are data structures used by the operating system to map virtual addresses (used by programs) to physical addresses (used by the hardware) in memory. A page table is a data structure that associates virtual pages (fixed-size blocks, often 4 KB) with physical pages in RAM (or indicates a page is on disk and must be loaded). Each page table entry (PTE) generally includes:
- The physical page address (if present in RAM).
- Permission bits (read, write, execute).
- Status bits (present/not-present, dirty, accessed).
Page Tables Hierarchy
To provide the fastest possible performance, we need to guarantee O(1) lookup in the page table. If we use a simple array that we address by prefix (i.e. the first 18 bits in a 32-bits system, since we keep 14bits for the 4kb page), we need to allocate a 2^18 elements array even if we only have few pages really in use in our process
We can use a hierarchical structure at two levels instead. When a virtual address translation occurs, the Memory Management Unit (MMU):
- Uses the first 10 bits to select an entry in the top-level table.
- Uses the next 10 bits to find the right PTE in the second-level table.
- Combines the PTE’s physical base address with the address’s offset to form the final physical address.
In this way, large unused portions of the address space do not require pre-allocated entries, preventing the massive memory waste of a single-level design.
Translation process
The translation processes is executed by the MMU trying to leverage the Translation Lookaside Buffer. Each time the process executes an instruction that accesses memory (LOAD, STORE), it uses virtual addresses. Under the hood:
- The CPU checks the TLB for a valid “virtual → physical” translation.
- If a valid TLB entry exists, the CPU immediately knows which physical RAM to access.
- If there is no valid TLB entry (a TLB miss), the MMU performs a page table walk in main memory, locating the mapping in the page table hierarchy
- Locates the mapping in the process’s page table.
- Loads that mapping into the TLB if found.
- Raises a page fault if the page is not present or permissions are violated. The kernel’s page-fault handler allocates a new page, loads from disk, or signals an error.
CR3
On x86-64, the operating system places the physical address of the top-level (root) page table into a special CPU register, CR3. Whenever a context switch occurs (i.e., switching from one process to another), the OS loads that process’s page-table root into CR3. If a TLB miss happens, the MMU follows the pointer in CR3 to walk the multi-level page table structure in memory and locate the correct PTE.
Page Table Hierarchy
The page table hierarchy for the process, often called process address space is created by the Kernel when the process is started
Allocating New Memory (Heap)
When a process requires more memory (for example, after calling malloc):
- The C library allocator (e.g., glibc on Linux) may already have space from previously allocated pages.
- If it needs additional pages, it calls sbrk (older approach) or mmap with MAP_ANONYMOUS to request more virtual pages from the kernel. The kernel adjusts the process’s page table, marking those pages as “allocated” but potentially not mapped to physical RAM yet.
- On first access to any newly mapped page, a page fault occurs. The OS allocates a physical page or updates the mapping if it’s file-backed, then sets the appropriate page table entry.
When mappings are removed or changed (via munmap, mprotect), the OS may need to invalidate TLB entries on each core (a TLB shootdown) so that no stale translations remain active.