Thrashing: When the System Grinds to a Halt

A machine that is busy doing nothing

Imagine you open the kitchen to too many cooks at once. There is only one small counter, and every recipe needs ingredients laid out on it. With three cooks, each keeps their handful of ingredients on the counter and works smoothly. Add a tenth cook and the counter overflows: now every cook, before each step, has to clear someone else's ingredients away and fetch their own from the pantry — over and over. The kitchen is frantically busy, yet almost no dish moves forward. That is exactly what happens to a computer in thrashing.

Recall from guide 4 that the OS splits a fixed pool of frames among all running processes via frame allocation. As long as each process gets at least enough frames to hold the pages it is actively using, virtual memory hums along and the page-fault rate stays tiny. Thrashing is the name for what happens when too many processes share too few frames: each process is starved below the minimum it needs, so it faults almost on every memory access, and the CPU sits mostly idle waiting for the disk.

The feedback spiral: how it gets worse on its own

What makes thrashing so dangerous is that it feeds itself. The trigger is usually a well-meaning decision by an old-style scheduler that watches CPU utilization. The scheduler reasons: "the CPU is only 20% busy, the machine is under-loaded, let me admit more processes to keep it productive." But the CPU was idle precisely because the existing processes were all stuck waiting on the disk for page-ins. Admitting more processes makes it worse, not better.

1. Many processes run; the OS gives each only a few frames. Each process is just below the number of frames it actually needs.
2. Processes fault constantly. To service each fault the OS must evict some page — often a page another (or the same) process will need again immediately, so it just faults back in.
3. Because everyone is blocked waiting for the disk, CPU utilization drops toward zero. The disk, meanwhile, is saturated with page-in and page-out traffic.
4. A scheduler that judges health by CPU utilization sees the idle CPU and admits even more processes to "use it up".
5. Frames are split even thinner, the fault rate climbs higher, and throughput collapses. The spiral tightens until almost no useful work is done.

The classic picture is a curve: as you raise the degree of multiprogramming (how many processes you admit), CPU utilization climbs nicely at first, peaks, and then falls off a cliff. Past the peak, every extra process you admit makes the whole machine slower, because the marginal process steals frames from everyone and tips the system over the edge. The job of the OS is to keep you at the top of that curve, not past it.

Why locality is the way out

Thrashing would be unavoidable if programs touched their pages at random, but real programs do not. They obey locality of reference: over any short stretch of time, a process touches only a small, slowly-shifting cluster of pages — the inner loop's code, the array it is scanning, the few variables on its stack. As the program moves from one phase to another (say, finishing a loop and entering a new function), that cluster drifts to a new set of pages, but at any instant it is small.

This is the loophole that saves us. If we can give each process just enough frames to hold its current cluster, it will fault only briefly while shifting from one phase to the next, then run fault-free until the next shift. The trouble begins when a process gets fewer frames than its cluster needs — then it cannot hold even its active pages, so it faults endlessly. Thrashing, in one sentence, is the system trying to run more locality clusters at once than it has frames to hold.

Cure one: the working-set model

The first cure turns locality into a number we can measure. Pick a window — the last delta references a process made (say, the most recent 10,000 page accesses). The working set of that process is simply the set of distinct pages it touched within that window. Because of locality, this set is small and fairly stable, and it is a good estimate of the pages the process needs to hold right now to avoid faulting. The window size delta is the one knob: too small and you miss pages the process really needs; too large and you keep stale pages around.

Window delta = 10 most-recent references.
Reference string (page numbers touched, in order):

  ... 2 6 1 5 7 7 7 5 1 6 | 2 3 4 4 4 3 4 3 4 4 ...
      \___ window here ___/

  Working set in this window = { 1, 2, 5, 6, 7 }  -> needs 5 frames

Sum the working-set sizes of ALL processes:

  total demand  D = WSS_1 + WSS_2 + ... + WSS_n

  if  D <= total frames available  -> safe, run them all
  if  D >  total frames available  -> overcommitted: suspend a process

Here is the elegant part. The OS adds up the working-set sizes of all processes to get the total frame demand D. If D fits within the available frames, the system is safe and every process can hold its working set. But if D exceeds the frame supply, the OS knows thrashing is imminent and acts decisively: it suspends one process entirely, swapping it out and freeing all its frames for the rest. The suspended process waits, the survivors each get to keep their working sets, and the spiral never starts. Later, when demand falls, the suspended process is resumed. This is why the model pairs naturally with local replacement — keeping one process's faults from stealing another's frames.

Cure two: page-fault-frequency control

The working-set model is principled but a bit indirect — you measure pages to predict faults. The second cure, page-fault frequency (PFF), skips the prediction and measures the symptom we actually care about: the fault rate itself. The reasoning is simple. A high fault rate means a process has too few frames for its current locality; a very low fault rate means it has more frames than it needs and could lend some out. So we steer directly on the thing we want to control.

Concretely, the OS sets an upper and a lower bound on the acceptable fault rate for each process and watches it over time. If a process's fault rate rises above the upper bound, it is frame-starved, so the OS gives it more frames. If its fault rate drops below the lower bound, it is over-supplied, so the OS reclaims some of its frames for others. It is a thermostat: heat (faults) too high, add frames; too low, take frames away. The one escape hatch is when fault rates are high everywhere and there are no spare frames left to hand out — then, exactly as in the working-set scheme, the OS must suspend a process to relieve the whole system.

Both cures, in the end, converge on the same insight: the only real way out of thrashing is to reduce the number of competing localities until they fit. You can do it preventively by summing working sets, or reactively by watching fault rates, but either way the lever is admission and allocation — how many processes run, and how many frames each holds. That closes the loop of this whole rung: we asked who gets evicted, learned which policy evicts wisely, learned how to split frames across processes, and now we see what happens when the split is impossible — and how to keep it from happening.