Paging and page tables

Why it matters

Paging is the mechanism behind virtual memory, and its details explain things you meet in production: why memory comes in 4 KB units, why large databases ask for huge pages, why a write to read-only memory crashes with a segfault, and why copy-on-write and memory-mapped files work at all. It also shows a classic data-structure trade-off, a multi-level tree that stays small when the address space is mostly empty.

The idea

Memory is divided into fixed-size blocks: pages in the virtual address space and frames of the same size in physical memory, typically 4 KB. Any page can live in any frame, so physical memory never needs to be contiguous. A virtual address splits into a page number (which page) and an offset (where within the page). Translation replaces the page number with a frame number and keeps the offset.

Page table entries

Each page table entry holds the frame number plus flag bits the hardware checks on every access:

Bit	Meaning	Used for
Present	The page is in RAM	Absent pages fault: lazy allocation, swapped-out pages, mapped files not yet read
Writable	Writes are allowed	Read-only code, copy-on-write sharing
User	Accessible from user mode	Keeping kernel memory away from programs
No-execute	Instructions cannot be fetched from it	Stopping injected code in data or stack pages
Accessed	Set by hardware on any access	Deciding which pages to evict
Dirty	Set by hardware on a write	Knowing which evicted pages must be written back

A violation, such as writing to a read-only page or touching an unmapped one, triggers a page fault. The kernel decides: it may be legitimate (allocate a page, copy it for copy-on-write, read it from disk) or a real error, in which case the process gets SIGSEGV.

Why multi-level tables

A flat table for a 48-bit address space with 4 KB pages would need 2^36 entries, 512 GB per process. But real address spaces are sparse: some code at the bottom, heap above it, stacks near the top, and enormous empty gaps. Multi-level page tables form a tree: on x86-64, four levels each indexed by 9 bits of the address. A missing upper-level entry means the entire range below it is unmapped, so empty regions cost nothing. A typical process needs only a few dozen kilobytes of page tables. The price is that a translation without help would take four memory reads, which is why the TLB in the next lesson matters so much.

Huge pages

Larger pages (2 MB or 1 GB on x86-64) cover more memory per entry, so fewer TLB entries map a large working set and translations stop at an upper level. Databases, JVMs with big heaps and in-memory analytics gain measurably. The costs: memory is allocated in larger units (more internal waste), and Linux's transparent huge pages, which promote pages automatically, can cause latency spikes during compaction, which is why some databases recommend turning them off and reserving explicit huge pages instead.

Paging versus segmentation

Older designs divided memory into variable-sized segments (code, data, stack) with a base and limit each. Variable sizes cause external fragmentation, gaps between segments too small to use. Paging trades that for internal fragmentation, the unused tail of a process's last page in each region, which is bounded by one page per region. Modern systems use paging almost exclusively.

Trade-offs

Fixed-size pages make allocation simple and eliminate external fragmentation, at the cost of translation overhead and internal waste. Multi-level tables save memory for sparse address spaces and lengthen the walk on a TLB miss. Larger pages reduce translation cost and increase waste and allocation latency.

In an interview

Most interviews only need the shape: "Memory is managed in 4 KB pages; each process has a multi-level page table mapping its pages to physical frames with permission bits; faults are how the kernel implements lazy allocation, copy-on-write and swapping." Bring up huge pages when sizing a large in-memory store: "With a 200 GB heap we use 2 MB pages so the working set fits in far fewer TLB entries."