Demand Paging and Thrashing — What Happens When Memory Runs Short

In a nutshell

Loading pages only when needed lets you run programs larger than physical memory, but a single fault costs tens of thousands of times more than a memory access, so even a small rise in the fault rate brings the system down.

Why this was needed

There is no need to load the whole program into memory. Many parts, such as error-handling code, are almost never executed, and it is common for only part of a large array to be actually used. If you load pages only at the moment they are needed (demand paging), you can run more processes at the same time, and programs also start faster.

How it works

A valid bit is placed in each page table entry. Accessing an invalid page causes a page fault, which is handled in the following order.

1. A trap is raised and the kernel is entered.
2. The kernel decides whether the access was illegal (outside the address range) or merely to a page that has not been loaded yet.
3. It looks for a free frame. If there is none, it picks a victim page and evicts it. If that page has been modified (dirty), it is written to disk first.
4. It reads the page from disk into the frame.
5. It updates the page table and re-executes starting from the instruction that caused the fault.

The cost is frightening when you calculate it. Suppose a memory access takes 200ns and handling a page fault takes 8ms. When the fault probability is p, the effective access time is (1 − p) × 200 + p × 8,000,000.

• With p = 0.001, that is, one fault in a thousand accesses, the effective access time is about 8,200ns, which is 40 times slower than with no faults.
• To keep the performance degradation within 10 percent, p must be about 0.0000025 or less. That is one in 400,000.

The characteristics of page replacement algorithms are also worth knowing. Given the reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 and 3 frames, FIFO causes 15 faults, LRU causes 12, and OPT, the theoretical optimum, causes 9. FIFO even exhibits Belady's anomaly, in which adding frames increases the number of faults. Real systems use the clock (second-chance) algorithm, which uses a reference bit, instead of pure LRU, because it gets performance close to LRU at much lower cost.

Thrashing is a vicious cycle: frames run short, so faults explode, so the CPU sits idle, so the operating system decides "we're idle, let's load more processes", and the situation gets even worse. The response is to track the working set (the set of pages actually referenced during a recent interval) and guarantee that many frames, or to monitor the fault rate directly and adjust the frames.

What it looks like in the field

When you put a memory limit on a container, there are two possible endings. If swap is off, the OOM Killer kills the process. It is abrupt, but the cause is clear. If swap is on, thrashing starts instead. The process is alive, but responses become dozens of times slower, and CPU utilization is low while only iowait spikes. This is why people say being killed is actually easier to diagnose. This unpredictability is also part of the background to Kubernetes having long required swap to be turned off.

What to check in the quiz that follows

Check whether you can calculate the page fault cost yourself, and whether you can explain why thrashing is a vicious cycle that reinforces itself.