CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 3 of 7 · 3 min read

Thrashing

Think of it this way. A cook with a tiny counter must keep fetching ingredients from the store room. Each trip puts something on the counter and pushes something off, and the next step needs the thing just pushed off. The cook does more walking than cooking. Thrashing is this state for a process, or for a whole machine.

In plain words: First, one process. In the experiment below, a process uses a locality of 20 pages at a time (a set of pages that it uses heavily for a period, then moves to another set), out of 200 pages in all. The script ran 60,000 references with LRU (page 8) and counted the faults at several frame counts:

Frames Faults Fault rate
4 48,035 0.8006
8 36,107 0.6018
12 24,353 0.4059
16 12,486 0.2081
18 6,504 0.1084
20 643 0.0107
22 432 0.0072
40 382 0.0064

The curve is not a gentle slope. From 20 frames up, the fault rate is near 0.01, and at 18 frames, only two frames fewer, the rate is ten times higher. The cliff sits at the size of the locality (20 pages). Below it, the process cannot hold the pages it is using now, so each reference tends to remove a page that will be needed again soon. Extra frames above 20 help little.

Now the whole machine. The second experiment shares 100 frames among n processes, each with a locality of 20 pages. A fault takes 200 times as long as a reference (made up). The model: a process spends 1 time unit on each reference and 200 more on each fault, so one process keeps the CPU busy for 1/(1 + 200 × p) of the time, with p its fault rate, and n processes together keep it busy for n/(1 + 200 × p), at most 1.

Processes Frames each Fault rate CPU utilisation
1 100 0.0046 0.52
2 50 0.0062 0.90
3 33 0.0067 1.00
4 25 0.0070 1.00
5 20 0.0105 1.00
6 16 0.2064 0.14
8 12 0.4031 0.10
10 10 0.5017 0.10

Up to 5 processes, more processes mean more CPU use, because while one process waits for a fault, another runs. At 6 processes, each gets only 16 frames, below the 20 that its locality needs. Faults jump, the CPU waits for the disk most of the time, and the use of the CPU falls from 1.00 to 0.14. A scheduler that sees low CPU use may then start even more processes, which makes it worse. That feedback is the danger of thrashing.

Thrashing

Thrashing is the state in which processes spend more time handling page faults than doing useful work, because the frames they have are too few to hold the pages they are using, and adding more processes makes the CPU use fall further.

Example: in the table, going from 5 to 6 processes drops the CPU use from 1.00 to 0.14, since each process now has 16 frames and needs 20.

Common mistake

Low CPU use does not always mean "start more work". If the cause is thrashing, more processes make it worse. Check the fault rate before adding load.

Check yourself: 1. Why does the fault rate jump when frames fall below the locality size? 2. In the table, why does the CPU use rise from 1 to 3 processes? 3. Why does a scheduler that reacts to low CPU use make thrashing worse?