Imagine a student preparing for exams at a tiny desk that fits only three books. The chapter she is studying needs five books open at once. So she keeps putting one book back on the shelf to make room for another, and a minute later she needs the book she just put away. She spends the whole evening walking to the shelf and almost no time reading.
An operating system can get into exactly the same situation with memory. When processes do not have enough frames to hold the pages they are actively using, they keep evicting pages they will need again almost immediately. The CPU then spends most of its time waiting for the disk, and almost no useful work gets done.
Thrashing is a condition in which a system spends more time servicing page faults (moving pages between memory and disk) than executing processes. It happens when processes do not have enough frames to hold the pages they are actively using.
In the previous chapters, Virtual Memory & Demand Paging and Page Replacement Algorithms, we saw how a page fault is handled and how the OS chooses a victim page. This chapter answers a bigger question: what happens when page faults stop being rare events and become the normal case, and how does the OS detect and prevent that?
Why a Page Fault Is So Expensive
To understand thrashing, you first need to feel how slow a page fault is compared with a normal memory access. Recall the effective access time (EAT) formula from Virtual Memory & Demand Paging:
EAT = (1 - p) × memory access time + p × page fault service time
p = probability that a memory reference causes a page fault
Let us take round numbers: a memory access takes 100 ns, and servicing a page fault from a disk takes about 8 ms (8,000,000 ns). That is 80,000 times slower.
Page fault rate p | EAT | Slowdown vs no faults |
|---|---|---|
0 | 100 ns | 1x |
1 in 1,000,000 | about 108 ns | 1.08x |
1 in 100,000 | about 180 ns | 1.8x |
1 in 10,000 | about 900 ns | 9x |
1 in 1,000 | about 8,100 ns | 81x |
1 in 100 | about 80,100 ns | 801x |
Even one fault in a thousand references makes the machine about 80 times slower. To keep the slowdown below 10%, we need:
(1 - p) × 100 + p × 8,000,000 < 110
p × 7,999,900 < 10
p < about 1 in 800,000
So a healthy system must fault extremely rarely. Thrashing is what happens when the fault rate climbs to something like "one fault every few references". At that point the CPU is essentially idle and the paging disk is the bottleneck.
A page fault is so much slower than a memory access that even a small fault rate dominates performance. Thrashing is the extreme case where faults happen almost all the time.
Why Too Few Frames Causes a Cliff, Not a Slope
You might expect performance to fall gently as a process gets fewer frames. Often it does not. It falls off a cliff.
Consider a process running a loop that touches pages 1, 2, 3, 4, 5 again and again. Here is the reference string for four iterations (20 references), with LRU replacement:
Frames given | Page faults (out of 20 references) |
|---|---|
3 | 20 |
4 | 20 |
5 | 5 (only the first-time faults) |
6 | 5 |
With 5 frames the loop fits, so only the five cold-start faults happen. With 4 frames, every single reference faults. Why? Trace it with 4 frames:
Ref In memory after the reference Fault?
1 {1} F
2 {1, 2} F
3 {1, 2, 3} F
4 {1, 2, 3, 4} F
5 {2, 3, 4, 5} (evict 1) F
1 {3, 4, 5, 1} (evict 2) F
2 {4, 5, 1, 2} (evict 3) F
3 {5, 1, 2, 3} (evict 4) F
... every reference keeps faulting
When 5 is needed, LRU evicts 1 (least recently used).
The very next reference is 1, which was just evicted.
To bring 1 back, LRU evicts 2, which is needed next... and so on.
LRU always throws out exactly the page that the loop needs soonest. FIFO behaves the same way here (we checked: 20 faults with 4 frames, 5 faults with 5 frames). The lesson is important:
If a process has even one frame fewer than the set of pages it is actively looping over, its fault rate can jump from almost zero to almost 100%.
The set of pages a process is actively using is called its locality, and it is the key idea for the rest of this chapter.
The Locality Model
Programs do not touch memory randomly. At any moment they work on a small group of pages, then move to another group.
A locality is a set of pages that are actively used together. As a program runs, it moves from one locality to another.
Examples:
When a function is called, its code page, its stack frame and the global variables it uses form a locality. When it returns, the program moves to a different locality.
A loop that scans an array keeps reusing the loop's code page and walks through the array's pages.
A database query works on a few index pages and data pages, then moves on.
Time →
|--- locality A: {1,2,3,4} ---|--- locality B: {7,8,9} ---|--- locality C ...
Locality is why demand paging works at all: a process needs only its current locality in memory, not its whole address space. It is also why thrashing happens:
Frames ≥ size of current locality → faults only when moving to a new locality. Fine.
Frames < size of current locality → the process faults constantly inside the same locality. Thrashing.
How Thrashing Starts: The Vicious Cycle
Early operating systems had a long-term scheduler that watched CPU utilization. If the CPU was underused, it admitted more processes to raise the degree of multiprogramming. That sounds sensible, but with global page replacement it can trigger a disaster:
1. Processes need more frames than are available
↓
2. They start faulting and take frames from each other
↓
3. Faulting processes wait in the queue for the paging disk
↓
4. Ready queue empties, CPU utilization drops
↓
5. Scheduler sees low CPU use → admits MORE processes
↓
6. Even fewer frames per process → even more faults
↓
back to step 2 (it gets worse every round)
The OS reacts to the symptom (idle CPU) with exactly the wrong medicine (more processes). This is a positive feedback loop.
The Classic Curve
CPU
utilization
100% | ***
| *** *
| *** *
| ** *
| ** * ← thrashing region
| ** **
| * ***********
+------------------------------------→
degree of multiprogramming
As we add processes, utilization rises because there is always someone ready to run while others do I/O. Past a certain point the processes' localities no longer fit in memory together, and utilization crashes.
A Small Simulation
To see this with real numbers, we wrote a small Python simulation (a toy model, not a real kernel). Settings:
20 physical frames shared by all processes, global LRU replacement.
Each process loops over its own 5 pages, using 1 CPU time unit per memory reference.
After every 10 references a process does ordinary I/O for 30 time units.
A page fault takes 20 time units on a single paging disk (one fault served at a time).
Processes (N) | Total pages needed | CPU utilization | Page faults per reference |
|---|---|---|---|
1 | 5 | 25.0% | 0.00 |
2 | 10 | 49.8% | 0.00 |
3 | 15 | 74.6% | 0.00 |
4 | 20 | 99.3% | 0.00 |
5 | 25 | 58.5% | 0.09 |
6 | 30 | 10.0% | 1.00 |
8 | 40 | 10.0% | 1.00 |
(In this model the page-fault trap itself also costs 1 CPU unit. So the 10% that remains at N = 6 and above is half page-fault handling and only half useful work: about 5% of the CPU is doing real computation.)
Up to 4 processes, all localities fit in 20 frames and adding a process adds about 25% utilization. The fifth process needs 25 frames in total and the system starts to struggle. From 6 processes onward every reference faults and the CPU sits mostly idle while the paging disk works flat out. Adding processes now makes things worse, never better.
How Frames Are Shared: Allocation and Replacement Scope
Whether thrashing spreads depends on how the OS divides frames among processes.
Frame Allocation
Every process needs a minimum number of frames, decided by the hardware: one instruction may touch several pages (the instruction itself, a source operand and a destination operand, possibly each crossing a page boundary). If a process gets fewer frames than that minimum, a single instruction can never complete.
Above the minimum, two simple policies exist:
Equal allocation:
mframes andnprocesses, each getsm / n.Proportional allocation: each process gets frames in proportion to its size:
ai = (si / S) × m, whereSis the total size.
Example: 100 free frames and three processes of 20, 60 and 120 pages (S = 200):
P1: (20 / 200) × 100 = 10 frames
P2: (60 / 200) × 100 = 30 frames
P3: (120 / 200) × 100 = 60 frames
Notice that neither policy looks at what the process is actually using right now. A large process may be working on a tiny locality, and a small one on a large locality. That is why we need the working-set idea below.
Global vs Local Replacement
Global replacement | Local replacement | |
|---|---|---|
Victim chosen from | All frames in the system | Only the faulting process's own frames |
Frames per process | Changes over time | Fixed (changes only when the OS re-allocates) |
Throughput | Usually higher, memory flows to whoever needs it | Can waste frames held by idle processes |
Effect on thrashing | One thrashing process steals frames and can drag others into thrashing | Thrashing is contained to the process, but it still slows the shared paging disk for everyone |
Local replacement limits the damage but does not solve the problem: the thrashing process still has too few frames, and its long queue at the paging disk increases the fault service time of every other process. The real fix is to give each process enough frames for its current locality, or to not run it at all for now.
The Working-Set Model
The working-set model, proposed by Peter Denning, gives the OS a practical way to estimate a process's current locality.
The working set of a process at time t, written WS(t, Δ), is the set of distinct pages referenced in the most recent Δ memory references. Δ is called the working-set window.
If a page has been used in the last Δ references, it is in the working set. If it has not been used for Δ references, it drops out.
Worked Example
Reference string (20 references) and window Δ = 5:
t: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
ref: 1 2 3 2 1 4 2 1 3 2 7 8 9 7 8 9 8 7 9 8
The working set at time t contains the pages in references t-4 to t:
t | Last 5 references | WS(t, 5) | Size |
|---|---|---|---|
5 | 1 2 3 2 1 | {1, 2, 3} | 3 |
10 | 4 2 1 3 2 | {1, 2, 3, 4} | 4 |
12 | 1 3 2 7 8 | {1, 2, 3, 7, 8} | 5 |
13 | 3 2 7 8 9 | {2, 3, 7, 8, 9} | 5 |
15 | 7 8 9 7 8 | {7, 8, 9} | 3 |
20 | 9 8 7 9 8 | {7, 8, 9} | 3 |
Look at what the numbers tell us:
From t = 1 to 10 the program is in locality {1, 2, 3, 4}.
Around t = 11 to 13 it is moving to a new locality, so the working set briefly contains pages from both (size 5).
From t = 15 onward it has settled into locality {7, 8, 9}, and the old pages have dropped out.
So the working set grows during a transition and shrinks once the program settles. That is exactly the behaviour we want an allocation policy to follow.
Using the Working Set to Prevent Thrashing
Let WSSi be the working-set size of process i, and let m be the number of frames available.
D = Σ WSS_i (total demand for frames)
If D ≤ m → everyone's locality fits. OK.
If there is spare memory, the OS may admit another process.
If D > m → thrashing will occur.
The OS suspends (swaps out) one or more processes
and gives their frames to the rest.
This flips the old, broken rule. Instead of "CPU idle → add processes", the OS says "memory demand too high → remove processes". The degree of multiprogramming is kept as high as possible without exceeding memory.
Choosing Δ
Δ too small: the window does not cover the whole locality. Pages still in use drop out, and the process faults.
Δ too large: the window overlaps several old localities. The process is credited with pages it no longer needs, wasting frames.
Δ = ∞: the working set becomes every page the process has ever touched.
How Can the OS Track It Cheaply?
Recording the exact last Δ references would need work on every memory access, which is far too expensive. Real systems approximate it with the reference bit (the same bit used by the clock/second-chance algorithm in Page Replacement Algorithms):
A timer interrupts every T references (or every few milliseconds).
On each interrupt, the OS copies each page's reference bit into a few history bits kept in memory, then clears the reference bit.
A page whose reference bit or any history bit is 1 was used recently, so it is considered in the working set.
More history bits and more frequent interrupts give a more accurate estimate at a higher cost.
Page-Fault Frequency (PFF)
The working-set model is somewhat indirect. The real problem is a high fault rate, so a simpler strategy is to measure the fault rate directly.
Page-Fault Frequency (PFF) control sets an upper and a lower bound on each process's acceptable page-fault rate, and gives or takes away frames to keep the rate between them.
page-fault
rate
| \
| \
|----\---------------- upper bound → above: give the process more frames
| \
| \___
|----------\_____------ lower bound → below: take frames away
| \______
+-----------------------------→ number of frames
Fault rate above the upper bound: the process needs more frames. Allocate one.
Fault rate below the lower bound: the process has more frames than it needs. Take one back.
If a process needs more frames and none are free, the OS suspends a process and frees its frames.
Working-Set Model | Page-Fault Frequency | |
|---|---|---|
What it measures | Which pages were used in the last Δ references | How often the process faults |
Main parameter | Window Δ | Upper and lower fault-rate bounds |
Cost | Needs reference-bit sampling | Just count faults per time interval |
Behaviour at locality change | Working set temporarily grows | Fault rate spikes, then process gets more frames |
Programs Can Cause (or Avoid) Thrashing Too
Locality also depends on how you write code. Consider a C array of 1024 x 1024 ints with 4 KB pages. An int is 4 bytes, so each row (1024 × 4 = 4096 bytes) fills exactly one page. C stores arrays in row-major order.
int a[1024][1024];
/* Version 1: row by row (matches memory layout) */
for (int i = 0; i < 1024; i++)
for (int j = 0; j < 1024; j++)
a[i][j] = 0;
/* Version 2: column by column */
for (int j = 0; j < 1024; j++)
for (int i = 0; i < 1024; i++)
a[i][j] = 0;
We simulated both with LRU (counting only the array's pages):
Frames for the array | Version 1 (row-wise) faults | Version 2 (column-wise) faults |
|---|---|---|
1 | 1,024 | 1,048,576 |
100 | 1,024 | 1,048,576 |
1,024 | 1,024 | 1,024 |
Version 1 finishes one page completely before moving on, so it faults once per page. Version 2 touches all 1024 pages for every single column, so unless the whole array fits in memory, every access faults: 1024 × 1024 = 1,048,576 faults. Same result, one thousand times more faults. Good data layout and access order keep the locality small. (The same effect also matters for CPU caches, even when there is no paging at all.)
Thrashing on Modern Systems
The classic long-term scheduler is mostly gone from desktop and server OSes, but thrashing is very much alive. On a Linux machine that runs out of RAM you see the system become unresponsive, the disk light stays on, and the mouse barely moves.
What modern systems do about it:
Swap and the page cache: Linux reclaims memory both by evicting file-backed pages (they can simply be re-read from the file) and by writing anonymous pages to swap. Heavy, continuous swapping in and out is the modern form of thrashing.
Out-of-memory (OOM) killer: if memory truly cannot be reclaimed, Linux kills a process to free memory. This is a harsh version of "suspend a process".
Memory limits per group: cgroups (used by containers) cap how much memory a group of processes can use, so one runaway job cannot push the whole machine into thrashing.
Mobile OSes: Android and iOS kill background apps when memory is low rather than letting the device thrash. Android's low-memory killer daemon (lmkd) does this.
SSDs and compressed RAM (for example zram on Linux, memory compression on Windows and macOS) make a page fault cheaper, which softens thrashing but does not remove it.
How to Spot It on Linux
The vmstat command shows swap activity in the si (swapped in) and so (swapped out) columns. This is real output from a healthy WSL Linux machine:
vmstat 1 3procs -----------memory---------- ---swap-- -----io---- -system-- -------cpu-------
r b swpd free buff cache si so bi bo in cs us sy id wa st gu
0 0 0 10064336 49784 1105976 0 0 5517 4232 2695 4 1 1 98 1 0 0
0 0 0 10067552 49784 1105912 0 0 0 260 722 689 0 0 100 0 0 0
0 0 0 10068900 49784 1105912 0 0 0 0 789 851 0 0 100 0 0 0
Here si and so are 0 and plenty of memory is free. (The first line shows averages since boot, the later lines show each one-second interval.) On a thrashing machine you would see large, steady si/so values, a high wa (CPU waiting for I/O), and low us (useful user work).
Since Linux 4.20 there is also Pressure Stall Information (PSI), which reports the share of time tasks were stalled waiting for memory:
cat /proc/pressure/memorysome avg10=0.00 avg60=0.00 avg300=0.00 total=0
full avg10=0.00 avg60=0.00 avg300=0.00 total=0
some is the percentage of time at least one task was stalled on memory, and full is the percentage of time all non-idle tasks were stalled at once. On a thrashing system these numbers climb steeply. This is a modern, direct measurement of the same idea as page-fault frequency.
How to Fix or Prevent Thrashing
Remedy | Why it works |
|---|---|
Reduce the degree of multiprogramming (suspend or swap out processes) | Fewer processes means more frames for each remaining one |
Working-set or PFF based allocation | Gives each process enough frames for its current locality |
Local replacement | Stops one thrashing process from stealing everyone's frames |
Add more RAM | Larger m, so more localities fit at once |
Improve program locality | Smaller working sets (data layout, access order) |
Faster backing store (SSD, compressed RAM) | Cheaper faults; does not fix the cause |
Common Mistakes
"Thrashing means many page faults." Not exactly. A program starting up has many cold faults and is not thrashing. Thrashing means the system spends most of its time paging, so useful work collapses.
"Add more processes to raise CPU utilization." During thrashing, low CPU use is a symptom of too many processes, not too few.
"A better replacement algorithm fixes thrashing." No algorithm can help when the locality simply does not fit. With 4 frames and a 5-page loop, both LRU and FIFO fault on every reference.
"Local replacement eliminates thrashing." It only isolates it. The thrashing process still overloads the shared paging device.
Confusing working set with resident set. The resident set is what is in memory now. The working set is what the process has recently used (what it needs).
Mixing up Δ. Δ is a window of references (or time), not a number of frames.
Interview Questions
What is thrashing?
A state where processes do not have enough frames for their active pages, so they fault constantly. The system spends most of its time paging and very little executing useful instructions.
What is the main cause of thrashing?
The total size of the processes' current localities (working sets) exceeds the available physical memory, usually because the degree of multiprogramming is too high.
Why does CPU utilization drop during thrashing?
Almost every process is blocked waiting for the paging disk, so the ready queue is empty most of the time.
What is the working set?
The set of distinct pages a process referenced in the most recent Δ references. It approximates the process's current locality.
How does the working-set model prevent thrashing?
It computes D = sum of all working-set sizes. If D exceeds available frames, it suspends processes until the rest fit. If memory is spare, it can admit new processes.
What is page-fault frequency control?
The OS keeps each process's fault rate between an upper and a lower bound by adding frames when it is too high and removing them when it is too low. If no frames are free, a process is suspended.
Global or local replacement: which handles thrashing better?
Local replacement contains thrashing to the offending process, but does not cure it. Global replacement gives better throughput but lets thrashing spread.
How do you detect thrashing on Linux?
Look for sustained high swap-in/swap-out (vmstat si/so), high I/O wait, low user CPU, and high memory pressure in /proc/pressure/memory.
The Main Idea
Thrashing happens when processes do not have enough frames for the pages they are actively using.
Too many processes for the memory
↓
Frames per process < locality size
↓
Page faults on almost every reference
↓
Everyone waits for the paging disk, CPU idle
↓
Fix: give each process its working set, or run fewer processes
Key facts to remember:
Cause → Σ working-set sizes > available frames
Symptom → high paging, low CPU utilization, unresponsive system
Working set → pages used in the last Δ references
PFF → keep fault rate between upper and lower bounds
Cure → reduce multiprogramming / allocate by locality / more RAM
A process needs its whole current locality in memory. Give it less and it does not run slower; it barely runs at all.
This chapter completes our study of memory management. In the next chapter, File Systems, we move from memory to long-term storage and see how the OS organises data into files.