Virtual memory in earnest: what a page fault really costs

Tier 1 established the shape of it: the address the program sees is virtual, the MMU translates it through a page table, and a page that is not in RAM produces a fault that brings it in from disk. That was the map. Now we walk the route, because the details are where the performance actually lives and dies.

The first thing the map hides is that the MMU cannot afford to read the page table on every access. A four-level page table means four dependent reads of RAM before you even touch the data, which would make every access five times slower. So the processor keeps a small cache of recent translations: the TLB, typically 64 to 1536 entries, fully associative, right next to the pipeline. A hit costs a cycle. This is why a program touching 100 MB with good locality runs at nearly full speed even though the page table is enormous: it only ever uses a few thousand distinct pages at a time.

When the TLB misses and the page is not in memory, the whole pipeline stops. The hardware walks the page table, finds the present bit clear, and raises a fault. The instruction is abandoned mid-flight, the trap handler runs, the kernel finds or frees a frame, reads 4 KiB from the device, updates the page table, installs a TLB entry and returns to retry the instruction - which now succeeds. Hardware handles the easy part in nanoseconds; software handles the expensive part in microseconds.

TLB hit: 1 cycle
walk: 3 or 4 reads
RAM: 30 ns
SSD: 0.1 ms
HDD: 8 ms

fault rate: 1/1000
0.001 x 0.1 ms = 100 ns
30 ns -> 130 ns per accessThe cost ladder. The SSD is fast enough that a low fault rate is survivable, and the rotating disk is not.

When a frame is needed and memory is full, something must be evicted. The best possible choice, if you could see the future, is the page used furthest in the future: the optimal policy of Belady. It is unimplementable, but it is the yardstick. The best practical approximation is LRU - evict the page unused for the longest time - and here is the catch that matters: exact LRU is also unimplementable. It requires a timestamp on every access, which means writing to memory on every read, which is exactly what the TLB exists to avoid. So real kernels approximate it, and the approximation they use is the clock algorithm.

The clock algorithm keeps frames in a circular list with one reference bit each. The hardware sets that bit on every access, and hardware can do it for free. When a frame is needed, the hand advances: if the bit is set, the page has been used recently, so clear the bit and give it a second chance; if the bit is clear, it has gone a full revolution untouched, so evict it. That second chance is the clever part - it separates pages used once in a burst from pages genuinely in the working set, at a cost of one bit and one pass of a hand.

for (;;) {
  frame = frames[hand];
  if (frame.ref_bit == 1) {
    frame.ref_bit = 0;
    hand = (hand + 1) % nframes;
  } else {
    evict(frame);
    break;
  }
}The clock algorithm in full. The hand sweeps, giving every recently used page exactly one more chance.

Now the property that makes replacement policies interesting. A stack algorithm is one where the set of pages resident in N frames is always a subset of the set resident in N+1 frames. LRU is a stack algorithm, so giving it more memory can never cause more faults. FIFO is not, and neither is clock, and the consequence is the Belady anomaly: there exist sequences of accesses where four frames produce more faults than three. It is not a rare curiosity - it is the direct symptom of a policy that makes decisions without a global notion of recency, and it is why production kernels care about LRU-ish age tracking rather than plain round-robin.

reference string   1 2 3 4 1 2 5 1 2 3 4 5

3 frames           9 faults
4 frames          10 faults

FIFO    more frames -> more faults
CLOCK   more frames -> more faults
LRU     more frames -> never worse
OPT     more frames -> never worseThe classic reference string. The first five faults differ, and that is enough to make four frames worse than three.

The working set of a process is the set of pages it is actively using in a window of time. If that set fits in the memory it has been given, the fault rate is low and matters little. If it does not fit, the process is in trouble: every page it evicts is a page it will need again shortly, so the next access faults, which evicts another page it will need, and so on.

working set: 20 MiB
5 threads: 100 MiB
RAM: 64 MiB

resident set: 12 MiB
fault -> evict -> fault -> evictA concrete case: five threads with 20 MiB each in a container capped at 64 MiB of RAM.

This is thrashing, and it explains the symptom everybody has seen and few can name. The machine appears completely frozen: the mouse stutters, nothing responds, the disk light is solid. You check the processor usage and it is not busy at all. The reason is that a faulting process is blocked, not running. It sits in the wait queue while the device works, so the CPU is idle - and the scheduler then runs a different process, which promptly faults on its own pages, evicts pages belonging to the first one, and blocks too. The processor is idle because every runnable thread is waiting for a 4 KiB read, and the system is slow not because it is computing too much but because it is computing almost nothing between two disk operations. Adding more processes makes it worse, which is the opposite of the intuition that more work keeps the CPU busy.

Two hardware notes that change the numbers. First, transparent huge pages: the kernel can back parts of memory with 2 MiB pages instead of 4 KiB ones, which cuts the number of TLB entries needed by 512 times. That can be a large win for a database scanning a table. Second, and in the other direction, it can be a loss: a 2 MiB page must be written out whole, so a program that dirties 4 KiB of a huge page pays 2 MiB of I/O. This is why the kernel has both always and madvise modes, and why the default has flip-flopped across versions.