Memory & Storage · lesson 4 of 4 · about 28 min
How every program gets its own private memory and what it costs: how a virtual address is split and translated, why page tables are trees, how the TLB caches translations and why huge pages help, what a page fault really costs, why running out of RAM is a cliff, and how fork() with copy-on-write can double a process's memory. Tap any for a plain-language card.
Virtual addresses
Translating means walking that tree: use the top 9 bits to pick an entry in the first table, follow it to the next table, and so on, until the last entry gives the physical page. Type an address to see how it breaks up, and switch to 2 MB “huge pages”, which skip the last level.
Change one digit of the address and watch which index changes. Consecutive addresses inside one page share all four indices and differ only in the offset.
| Part of the address | Value | Does what |
|---|---|---|
| Level 4 (PML4) | 254 (9 bits) | Selects an entry that points to the next table |
| Level 3 (PDPT) | 232 (9 bits) | Selects an entry that points to the next table |
| Level 2 (PD) | 145 (9 bits) | Selects an entry that points to the next table |
| Level 1 (PT) | 325 (9 bits) | Selects the final entry: the physical page frame |
| Offset | 1,656 (12 bits) | Byte inside the page |
0x7f3a12345678 splits into table indices 254, 232, 145, 325 and an offset of 1656. A 4 KB page means 4 table lookups before the real access, so an uncached translation costs 5 memory reads in place of one.
Real x86-64 address arithmetic: 48 usable bits, 9 bits per level, 12-bit (4 KB) or 21-bit (2 MB) page offset.
Page tables
For a process using 500 MB in 6 regions, the tree needs a few hundred 4 KB tables, about a megabyte. Larger pages shrink it further (fewer leaves) and make each translation shorter. The table walk costs time too, which is why the CPU caches recent translations in the , the next scene.
Compare the flat table with the tree for 500 MB, then raise the memory to 20 GB and see the tree grow only linearly.
A flat table would cost 512.0 GB for this process. The four-level tree needs 271 tables, 1.1 MB, about 0.2% of the memory it describes; with 2 MB pages only 88 KB.
Estimate: leaf tables = pages ÷ 512, plus one table per region at each level (sparse regions rarely share), plus the root. 8-byte entries, 4 KB tables.
The TLB
Huge pages (2 MB, or 1 GB) multiply the reach by 512 with the same number of entries. That is why databases, JVMs and in-memory stores often enable them, and why a big server with a large working set can run noticeably faster after the change. The cost is rigidity: a huge page is allocated and moved as one block, which can waste memory and cause latency spikes if the OS has to compact memory to find a contiguous 2 MB.
With a 2 GB working set, 4 KB pages hit the TLB only about 15% of the time; 2 MB pages hit about 98%.
A TLB with 1,536 entries of 4 KB reaches 6 MB. Against 2.0 GB of hot data it hits 15% of the time, making the average access 441 ns instead of 100 ns.
LRU TLB simulation over 60,000 Zipf-skewed accesses (exponent 0.8); a miss costs a 4-read page walk at 100 ns each. Real CPUs have several TLB levels and walk caches.
Page faults
The average access time is (1 − p) × RAM + p × fault time. Because a fault is 1,000 to 80,000 times slower than a RAM access, even a tiny fault rate p dominates. To stay within 10% of full speed with a hard disk, faults must be rarer than about one in 80,000 accesses. This is the real reason “it fits in RAM” is such a strong statement about performance.
Leave faults at 1 in a million on a hard disk (8% slower), then try an NVMe SSD, then push the fault rate to 1 in 10,000.
With 1 access in 1,000,000 faulting to hard disk, the average access takes 108 ns, 1.08 times the 100 ns RAM time. To keep the slowdown under 10% the fault rate must be below 1 in 799,990.
Average = (1 − p) × RAM time + p × fault time. Fault latencies are typical orders of magnitude for each device.
Thrashing
The transition is a cliff, not a slope. A program that loops through its data cyclically with LRU replacement faults on every access as soon as it has even one frame too few. Skewed access (a hot core and a long tail) degrades more gently, which is why caches work at all. This is a simulation of LRU replacement: slide the RAM available as a share of the working set and see the fault rate.
With the looping pattern, drop from 100% to 95% of the memory needed and faults jump from nothing to every access. With skewed access it rises smoothly.
With 90% of the memory it needs and a looping access pattern, 100.0% of accesses fault. At 100 µs per fault the program runs about 1,000 times slower. Cyclic access makes LRU evict exactly the page needed next: every access misses.
Real LRU simulation over 600 pages and 30,000 accesses; slowdown = (1 − p) + p × (fault time ÷ 100 ns).
Which fix?
Match the memory symptom to the remedy: not enough RAM, translation overhead, wasted memory, or snapshot copies. Each answer is worth 20 XP.
Ask: is it faults to disk, TLB misses, memory that is not needed, or a fork that duplicates pages?
A 40 GB hot dataset on a 32 GB server shows constant major page faults.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Four published sources on virtual memory.
'The Working Set Model for Program Behavior'
Denning showed that a program runs well when the set of pages it is actively using fits in memory and thrashes when it does not, and proposed measuring the working set to decide how many programs can share memory. The principle is still how operating systems and capacity planners think about memory.
four- and five-level page tables
Linux on x86-64 uses four-level page tables for 48-bit addresses and, since kernel 4.14, can use five levels for 57-bit addresses (128 petabytes), adding one more table level only for machines that need the larger space.
RDB snapshots with fork and copy-on-write
Redis documents that it saves snapshots by forking a child that shares memory copy-on-write, that memory usage can grow while the child runs if the parent keeps writing, and that transparent huge pages can make the copied memory and latency worse, so they should be disabled.
the huge_pages setting
PostgreSQL's documentation says that using huge pages reduces the overhead of memory management, especially with large shared_buffers, by shrinking page tables and the work the processor does on each access.
Interview angle
Six questions, each worth 20 XP. Virtual memory shows up in questions about performance, containers and databases.
Explain pages, the page-table walk, the TLB, and what happens when the working set no longer fits.
What does the MMU do on every memory access?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
So the extra memory depends on how much the parent writes while the snapshot runs. A read-mostly workload copies little. A write-heavy one touches page after page; in the limit every page is copied, and the machine needs twice the dataset size in RAM. If it has only 1.6× the data, the kernel's out-of-memory killer ends the process, often at the worst moment. Hence the rule of thumb to leave headroom for snapshots (and why transparent huge pages, which make each copied page 2 MB, can make it much worse).
20 GB of data with 50,000 distinct pages written per second for a minute copies about 8.7 GB, enough to push a 32 GB machine to 28.7. Lengthen the snapshot to 5 minutes and it fails.
The snapshot copies about 8.7 GB of pages, so 28.7 GB of the 32 GB is in use: it fits, with 3.3 GB to spare. Write more, or snapshot for longer, and the margin disappears.
Expected pages copied = N × (1 − e^(−w·t ÷ N)) for N pages and w random page writes a second; 4 KB pages. Skewed writes copy fewer distinct pages.