Thrashing is what happens when a computer spends most of its time moving memory pages between RAM and storage and very little time running programs. Disks or SSDs are busy, CPUs are mostly idle, and every program is painfully slow. It’s an interview favourite because the cause is counter-intuitive: the system doesn’t degrade gradually as memory runs short. It holds up fine and then falls off a cliff, and the usual reflex of adding more work to use the idle CPU makes it worse.
The working set, not the allocation
Peter Denning defined a process’s working set in 1968 as the set of pages it referenced during the most recent window of time. The point of the definition is that what a program uses matters more than what it has. A JVM might reserve an 8 GB heap and a database might map a 200 GB file, while the pages each touches in any given minute fit in a few hundred megabytes.
As long as every running process’s working set fits in RAM together, page faults are rare: some first-touch faults, some cold data read once. Memory can even be overcommitted on paper without harm, because pages nobody touches can sit in swap or never be allocated at all. The trouble starts when the sum of active pages exceeds physical memory. Then every page brought in pushes out a page someone will need again soon.
Measuring a working set directly is harder than measuring RSS. On Linux, /proc/<pid>/smaps reports Referenced pages per mapping, which you can reset and re-read to see what was touched in an interval, and the kernel’s idle page tracking does the same more precisely. Most people approximate it from behaviour: if a process’s major fault rate jumps when you squeeze its memory, you’ve gone below its working set.
The cliff: one frame short
Page replacement policies decide which page to evict. Least recently used (LRU) is the classic choice, and real kernels use cheaper approximations of it, such as clock algorithms and Linux’s active and inactive lists. LRU works well when recently used pages are likely to be used again, and fails dramatically when they aren’t.
This simulation counts LRU faults for two access traces: a job sweeping the same 100 pages in a loop 50 times, and a job where 90% of accesses hit 20 hot pages and 10% hit any of 980 cold ones:
from collections import OrderedDict
import random
def lru_faults(trace, frames):
cache, faults = OrderedDict(), 0
for page in trace:
if page in cache:
cache.move_to_end(page)
else:
faults += 1
if len(cache) >= frames:
cache.popitem(last=False) # evict the least recently used page
cache[page] = True
return faults
WORKING_SET = 100
loop = list(range(WORKING_SET)) * 50 # a job sweeping 100 pages, 50 times
rng = random.Random(1)
hot_cold = [rng.randrange(20) if rng.random() < 0.9 else rng.randrange(20, 1000) for _ in range(5000)]frames loop-of-100 faults 90%-hot-20 faults
120 100 ( 2.0%) 465 ( 9.3%)
101 100 ( 2.0%) 471 ( 9.4%)
100 100 ( 2.0%) 471 ( 9.4%)
99 5000 (100.0%) 471 ( 9.4%)
90 5000 (100.0%) 475 ( 9.5%)
50 5000 (100.0%) 494 ( 9.9%)
20 5000 (100.0%) 1324 ( 26.5%)With 100 or more frames, the looping job takes exactly 100 faults, one per page on the first sweep, and none after. With 99 frames, every single access faults. Each time the job needs page 0 again, LRU has just evicted it, because page 0 was the least recently used; loading it evicts page 1, which is needed next, and so on around the loop. One frame short of the working set turns a 2% fault rate into 100%.
The hot-and-cold job degrades gently instead: its 10% of cold accesses miss no matter what, and its fault rate only climbs steeply once memory drops toward its 20 hot pages. Real programs mix both patterns, which is why a server can look fine at 90% memory use and collapse at 95%.
Why a few faults are a big slowdown
The arithmetic makes the cliff worse. If a memory access takes about 100 ns and a page fault costs time t, the effective access time with fault rate p is roughly (1 - p) × 100 ns + p × t.
On this M1, reading a file page in from the SSD through a major fault measured about 32 µs per 16 KiB page in a sequential test, and random reads cost 150 µs or more. Take 100 µs as a round figure: a fault rate of just 0.1% makes the average access about 200 ns, twice as slow; 1% makes it about 1.1 µs, eleven times slower. On a spinning disk at 10 ms per fault, 0.1% alone means 10 µs per access, a hundredfold slowdown. Nothing has to be “broken” for a program to crawl.
Thrashing at the system level
With several processes, the effect feeds itself. Process A faults and blocks on I/O, so the scheduler runs B. B faults on a page that was evicted to make room for A’s page, and blocks. C runs and evicts some of A’s and B’s pages. CPU utilisation drops because everyone is waiting for storage. Early batch systems famously responded to low CPU utilisation by admitting more jobs, which added more working sets and made the thrashing worse.
The symptoms are distinctive: a high major fault rate and swap-in rate, storage queues full of page reads, CPUs idle or in I/O wait, and very little useful work. On Linux, the pressure stall information file /proc/pressure/memory reports the share of time tasks were stalled waiting on memory, which is the most direct thrashing signal; vmstat 1 shows swap-ins and swap-outs in its si and so columns. I didn’t run Linux here.
The M1 used for these experiments, which has 8 GB of RAM, was itself under real memory pressure at the time. sysctl vm.swapusage reported used = 5104.81M of a 6 GB swap file, and vm_stat showed 896,252 pages (about 13.7 GiB) held in the compressor, squeezed into 202,652 pages of RAM. macOS compresses inactive pages before swapping them, which buys a lot of headroom since compressing and decompressing is far faster than storage I/O. The pressure was visible in experiments too: in one run of a page-fault test, pages touched once faulted again on the second pass because the kernel had compressed them in between.
Getting out of it
Thrashing is fixed by reducing demand for memory or adding memory. Adding CPU doesn’t help, and adding work makes it worse.
- Run less at once. Fewer worker processes, smaller batch sizes, or admission control that schedules jobs by memory need rather than idle CPU. Classic operating systems did this with load control: suspend whole processes until the rest fit.
- Cap and isolate. cgroup memory limits keep one service’s growth from evicting another’s working set. Setting
memory.highbelowmemory.maxmakes the kernel reclaim aggressively within the group before anything is killed. - Kill early. Linux’s OOM killer acts only when memory is completely exhausted, often long after the system became unusable.
systemd-oomdwatches pressure stall information and kills a culprit while the machine is still responsive. - Improve locality. Process data in blocks that fit in memory, use compact data structures, and avoid access patterns that sweep a huge data set repeatedly.
Swap still has a role: it lets the kernel move genuinely idle pages out of the way so active ones get RAM. It just can’t hold a working set. For latency-sensitive services, many teams run with little or no swap so memory exhaustion fails fast instead of slowly.
Interview exercise: two more workers, 80% less throughput
A batch host with 64 GB of RAM runs eight worker processes, each with a working set of about 7 GB. Throughput is good, and CPU sits at 60%. To use the idle CPU, someone raises the worker count to ten. Total throughput drops by about 80%. Explain what happened and what you’d do.
Answer
Eight workers need about 56 GB of active memory, which fits in 64 GB with room for the kernel and page cache. Ten workers need about 70 GB, more than the machine has. Once the combined working sets exceed RAM, each worker’s pages are evicted to make room for another’s, and every worker spends most of its time waiting for page-ins instead of computing. As the LRU simulation shows, the collapse isn’t proportional to the 9% shortfall; a looping access pattern goes from almost no faults to faulting constantly. CPU utilisation would actually fall, which is the giveaway that the bottleneck moved from CPU to memory.
To confirm, check the major fault and swap-in rates and memory pressure stall time before and after the change: they should jump from near zero to very high.
The immediate fix is to go back to eight workers. The lasting fix is to schedule by memory, not CPU: give each worker a cgroup memory limit, and let the job runner admit a new worker only when enough memory is free for its working set. If more throughput is needed, reduce each worker’s working set (smaller in-memory batches, more compact data), or add memory or hosts. Idle CPU on a memory-bound machine is not spare capacity.
Related memory and swap notes
- Operating Systems interview questions
- Operating Systems MCQs
- Paging, Page Faults and Memory Access
- Operating Systems: Swap and Thrashing
- OSTEP, Beyond Physical Memory: Policies, covering LRU, clock approximations and thrashing