Thrashing
Thrashing is the pathological condition where an operating system spends most of its time swapping pages in and out of memory instead of executing processes; it is detected and controlled by working-set and page-fault–frequency ideas.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Thrashing directly reduces system throughput and increases response time: an engineer must recognise it in systems with virtual memory (paging/segmentation) and apply controls (reduce multiprogramming, change replacement/locality policies, use working-set or page-fault–frequency schemes). It appears when memory management (paging) cannot keep the active page sets of running processes resident.
Key ideas
Definition: Resident set — the set of pages of a process that are currently loaded in physical memory (frames) and available for immediate access.
Definition: Thrashing — a condition in a demand-paged system where the system (or a process) spends most of its time servicing page faults rather than doing useful work; symptoms include very high paging I/O, low CPU utilisation, and rapidly rising page-fault activity. It typically occurs when the sum of working sets exceeds available frames.
Definition: Working set (WSS) — Denning's formal definition: the working set WSS(t, Δ) of a process at time t with window size Δ is the set of distinct pages referenced by that process in the most recent Δ memory references before t (implementations may approximate a time-based window via periodic sampling of reference bits). It is a measure of the process’s current locality. Assumption: references are recorded (or approximated) for the chosen Δ.
- Property: WSS depends on Δ (the working-set window). If Δ is too small, WSS underestimates the needed locality; if Δ is too large, WSS may include pages not needed now.
Definition: Degree of multiprogramming (D) — the number of processes loaded and allowed to run concurrently (or at least resident in memory). It determines how total frames are shared.
Fundamental condition for thrashing (practical rule): if the sum of working sets of all processes exceeds the number of available physical frames, the system will likely thrash. Formally:
- Let N = total number of physical frames available for user processes (after OS reserve).
- Let W = sum over all processes i of WSS_i(t, Δ).
- If W > N then resident sets are too small; processes will incur many page faults and the system may thrash.
Page-fault–frequency (PFF) control: measure the page-fault frequency f of a process (faults per second; equivalently 1/mean time between faults). Maintain f within acceptable bounds [f_min, f_max]. If f > f_max, give the process additional frames (or reduce D). If f < f_min, consider reclaiming frames. PFF is an alternative to computing WSS explicitly; choose one unit (per second or per reference) and keep it consistent.
Local vs global replacement policies:
- Global replacement: any frame can be taken from any process. This can cause a process to lose too many frames when others demand more, producing thrashing.
- Local replacement: a process can only replace its own frames. This isolates processes’ locality but may be inefficient if some processes are idle.
Effective Access Time derivation (EAT): show how page-fault rate affects memory performance. Let p = probability of a page fault on a memory reference (page-fault rate). Let ma = memory access time, pf = page-fault service time (time to service a fault: trap, disk I/O to read page, update tables, resume). Then EAT = (1 − p)·ma + p·pf. As p increases even slightly, since pf ≫ ma, EAT grows large and CPU stalls on faults; this models why small increases in p can cause huge slowdowns and lead to thrashing.
Practical controls to avoid or recover from thrashing:
- Reduce degree of multiprogramming: suspend or swap out processes until W ≤ N.
- Increase available physical memory (add RAM) or adjust OS-reserve frames.
- Use better locality-preserving scheduling and allocation (load control, working-set-based allocation).
- Use PFF to dynamically assign frames.
- Prefer local replacement or per-process frame quotas when global replacement causes frequent contamination of resident sets.
Diagrams to draw (describe exactly):
- Working-set window diagram: draw a horizontal axis of memory references (or time). Mark current point t at the right end. Draw a window of the last Δ references ending at t (label t − Δ and t). Under the axis, write the sequence of page references inside the window, e.g. A B C A D B E A. Above the axis, enclose with a bracket the distinct pages (A,B,C,D,E) and label WSS(t, Δ) = 5.
- Resource-availability bar chart: draw a vertical bar labelled N (total frames). Next to it draw a stacked bar showing WSS1, WSS2, …, WSSk stacked to total W. If stacked total > N, draw a red cross and label “Thrashing likely (W > N)”.
- EAT vs page-fault rate plot: x-axis p from 0 to small value (0.0–0.001), y-axis EAT. Plot EAT = (1 − p)·ma + p·pf (show steep rise because pf ≫ ma). Label points showing ma and pf.
- CPU utilisation vs degree of multiprogramming (D) curve: x-axis D, y-axis CPU utilisation. Show initial increase, then a knee, followed by a sharp drop in utilisation in the thrashing region. Mark the region where reducing D recovers performance.
Notes on assumptions: these models assume uniform memory access time ma, a single type of page-fault service time pf (but pf varies in practice: cold page read vs clean page vs victim write), and stationarity for p (probability of fault per reference) and any measured fault frequency f (treated as steady over the analysis interval).
Formulas
EAT = (1 − p) · ma + p · pf where p = page-fault rate (dimensionless, faults per memory reference), ma = memory access time (seconds), pf = average page-fault service time (seconds). Applies when page faults are independent and service time pf is the average cost per fault.
WSS(t, Δ) = number of distinct pages referenced by the process in (t − Δ, t) where WSS is a count (pages), Δ is a working-set window measured in the number of most-recent memory references (dimensionless; many OSs approximate this with a time-based sampling window), t is current time.
W = Σ_i WSS_i(t, Δ) where W = total working-set size (pages) summed over all processes i.
Thrashing condition (practical inequality): If W > N then thrashing likely where N = total user frames (pages) available.
Page-fault–frequency decision rule (conceptual): if f_process > f_max then increase frames or reduce multiprogramming; if f_process < f_min then reclaim frames where f_process is measured in faults per second (choose one unit and keep it consistent).
Worked examples
Example 1 — Effective Access Time (numerical) Problem: Memory access time ma = 100 ns. Average page-fault service time pf = 8 ms. Page-fault rate p = 1 × 10^−6 (one fault per million references). Compute EAT. Steps:
- Convert pf to ns: pf = 8 ms = 8 × 10^6 ns.
- Use formula: EAT = (1 − p)·ma + p·pf.
- Substitute: EAT = (1 − 1e−6)·100 ns + (1e−6)·8,000,000 ns.
- Compute: (1 − 1e−6)·100 = 99.9999 ns. The fault term = 8,000,000 × 1e−6 = 8.0 ns.
- Sum: EAT = 99.9999 + 8.0 ≈ 107.9999 ns. Answer: EAT ≈ 108.0 ns. Notes: even a very small p increases EAT significantly because pf is millions of times larger than ma.
Example 2 — Working set and thrashing decision (theory/numerical) Problem: Physical frames available N = 40. There are three processes with measured working sets WSS1 = 10 pages, WSS2 = 15 pages, WSS3 = 20 pages for the current Δ window. Will the system thrash? Steps:
- Compute total W = 10 + 15 + 20 = 45 pages.
- Compare W to N: 45 > 40.
- Conclusion: since W > N, resident sets cannot accommodate all working sets; page faults will rise and thrashing is likely. Action (full-marks answer): reduce degree of multiprogramming: suspend or swap out one process (e.g., process with WSS3 = 20). After suspending, remaining W = 25 ≤ 40, so thrashing should stop. Answer: Yes, thrashing likely; reduce multiprogramming (e.g., suspend one process) to restore W ≤ N.
Example 3 — Page-fault frequency control (conceptual) Problem: You measure that process P has page-fault frequency f_P = 0.05 faults/sec. The OS parameter f_max allowed is 0.02 faults/sec. What should the OS do? Answer steps:
- f_P = 0.05 > f_max = 0.02.
- According to PFF policy, increase frames assigned to P (if free frames exist) or reduce degree of multiprogramming (swap out other processes) to lower f_P. If neither is possible, suspend P until more memory becomes available. Answer: Increase frames for P or reduce multiprogramming to bring f_P ≤ f_max.
Common mistakes
- Assuming more frames always reduce page faults in all replacement algorithms (Belady's anomaly exists for FIFO: more frames can increase faults for some workloads and algorithms; but thrashing is about insufficient aggregate frames for all working sets).
- Forgetting to convert units when computing EAT (mixing ns and ms).
- Misinterpreting WSS: using too-large Δ so WSS ≈ entire program size and losing the locality advantage.
For your exam
Kinds of questions:
- Definitions and short notes: define thrashing, working set, resident set, degree of multiprogramming.
- Derivations: show EAT formula from probabilities, explain how small p affects EAT numerically.
- Diagram questions: draw and label working-set window and show WSS count; draw stacked bars to illustrate W vs N; draw CPU utilisation vs degree of multiprogramming curve and indicate the thrashing region.
- Procedures: explain working-set based load control and page-fault–frequency scheme step-by-step.
- Numericals: compute EAT given ma, pf, p; decide thrashing given N and WSS values. What a full-marks answer includes:
- Precise definitions using the bold terms (thrashing, WSS, resident set).
- Clear statement of assumptions (demand paging, pf service time uniform mean value, choice of Δ).
- Correct formulae with units and numeric conversions shown, and stepwise substitution.
- Clear decision based on W vs N or p vs threshold for PFF with recommended remedial actions.
Quick check
- What is the working set WSS(t, Δ)?
- Write the EAT formula using p, ma and pf.
- If total WSS = 90 pages and available frames N = 80, what is the immediate conclusion?
Answers: WSS(t, Δ) is the number of distinct pages referenced by a process in the interval (t − Δ, t);
EAT = (1 − p)·ma + p·pf; since W > N (90 > 80) thrashing is likely — reduce multiprogramming or increase frames.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?