Chapter 31 of 38

Thrashing

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: m frames and n processes, each gets m / n.

  • Proportional allocation: each process gets frames in proportion to its size: ai = (si / S) × m, where S is 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):

  1. A timer interrupts every T references (or every few milliseconds).

  2. On each interrupt, the OS copies each page's reference bit into a few history bits kept in memory, then clears the reference bit.

  3. 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 3
procs -----------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/memory
some 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.