Memory thrashing

Why does a computer that is only slightly short of memory crawl to a halt rather than slowing a little?

Most shortages are proportionate. A machine five per cent short of disk space is five per cent short; a slightly slower processor runs slightly slower. So the naive expectation for memory is a gentle slope: overshoot by a little, pay a little.

That is emphatically not what happens. A machine comfortably inside its memory and one slightly outside are not two points on the same line — the second can be a thousand times slower, unresponsive, apparently broken. What is different about memory that turns a small shortfall into a cliff?

Start with the arrangement that makes the shortfall survivable at all. A program addresses memory that need not physically exist; the operating system keeps the pages in use in physical frames and parks the rest on a backing store. Touch a page that is not resident and the hardware raises a page fault: the process stops, the page is fetched, it resumes. Nothing here is a failure — this is the design working, and it is why you can run more than fits.

So the cost of being short is the cost of faults, and the question becomes arithmetic. A read from RAM is on the order of a hundred nanoseconds. A seek and read on a spinning disk is a few milliseconds — call it five million nanoseconds. The ratio is about fifty thousand to one.

Now weight it. If one access in a hundred thousand faults, the average costs a hundred nanoseconds of memory plus fifty of amortised fault: about a hundred and fifty, so the machine runs at two-thirds speed and nobody notices. Take the fault rate to one in ten thousand and the average is six hundred — six times slower. One in a thousand gives five thousand: fifty times slower, visibly dying. Those follow from the two figures above, and the pattern is the point: because one term is fifty thousand times the other, the average is governed almost entirely by the rare term, and a hundredfold change in something rare changes everything a hundredfold.

But that only relocates the puzzle. Why should a small shortfall produce a hundredfold rise in fault rate? Ask what those hit rates rested on: locality. Programs revisit what they touched recently, and Denning's working set names the pages a process has actually referenced in the recent past. Give a process its working set and almost every reference is a hit. Give it slightly less, and the pages it evicts are not idle spares; they are pages it will reference again shortly, because the working set is by definition what it keeps coming back to. It faults, brings the page in, evicts another page it also needs, then needs that one. The hit rate does not decline proportionally — the reuse that produced it stops working, and it falls off the plateau.

Let us test whether we have the whole cause. The textbook account adds a real feedback loop: when every process is blocked waiting for pages, the processor looks idle, so a naive scheduler concludes it has spare capacity and admits more work — which needs frames, shrinking everyone's allocation and raising the fault rate further. But is it the cause? A single process alone on a machine, with a working set five per cent too large, thrashes anyway, with no scheduler and no competitors involved. So the feedback is an amplifier, historically important and now largely designed out by load control, not the mechanism itself.

Try one more falsification, of my own account this time. If the cliff's steepness comes from the size of that outlying term, shrinking the outlier should flatten the cliff. It does. Swapping to a solid-state drive replaces five milliseconds with nearer a hundred microseconds, and the same shortfall that once froze a machine merely makes it sluggish. That is the prediction the account makes, and it holds.

This is the mirror image of the case for caching. There, a small fast store buys nearly all of a large fast store's benefit because locality makes hit rates high and the average access time collapses toward the fast term. Here the same arithmetic runs backwards: once locality no longer fits, the average is dragged toward the slow term instead. The hierarchy is spectacular when the bet pays and catastrophic when it does not, with very little in between — and that narrowness is the whole phenomenon.

A modern clarification matters too, because people conclude that turning swap off prevents thrashing. It does not. Much of a machine's memory holds clean file-backed pages, including the executable code of every running program, and those can be dropped with no swap file at all, since they can be re-read from the original file. Under pressure the kernel drops them, then must re-read a program's instructions in order to execute them, faulting on the code path itself. A swapless machine thrashes through the page cache instead, so disabling swap changes the symptom rather than removing it.

And nothing tunes away the ratio between RAM and storage. The interventions that work either reduce demand — a smaller working set, a better layout, fewer resident processes — or refuse the overcommitment beforehand, which is what admission control and the out-of-memory killer are for. Killing a process is crude and is also the only move that acts on the actual variable. Where to place that threshold, and how aggressively to act on early pressure signals, remains a live engineering argument.

• Why the out-of-memory killer must guess which process to end, and how badly that goes.
• How a database managing its own buffer pool sidesteps the operating system's paging.

Every term the collection defines is gathered in the glossary.