Working set model, thrashing
WHY does this concept even exist?
The problem: Physical RAM is finite, but virtual memory pretends it's infinite by paging stuff to disk. The OS decides which pages stay in RAM. If it guesses wrong, every memory access becomes a disk access (a page fault), and disk is ~–× slower than RAM.
The observation that saves us: programs don't touch all their memory uniformly. They obey the principle of locality:
- Temporal locality — a page used now is likely used again soon (loops, hot variables).
- Spatial locality — if you touch address , you'll soon touch (arrays, instruction streams).
So at any instant a program only needs a handful of pages "live". The working set model quantifies that handful so the OS can allocate frames intelligently.
WHAT is the working set?
- = the working-set window size (measured in memory references, not seconds).
- = the working set size = number of frames the process needs right now.
HOW do we compute ? — a worked trace
Reference string (each number = a page touched): Take (look back at the last 5 references including current).
| ref | last-5 window | |||
|---|---|---|---|---|
| 5 | 7 | 2 6 1 5 7 | {2,6,1,5,7} | 5 |
| 6 | 7 | 6 1 5 7 7 | {6,1,5,7} | 4 |
| 9 | 1 | 7 7 5 1 _ | {7,5,1} | 3 |
| 11 | 2 | 1 6 2 _ _ | {1,6,2} | 3 |
Why this step? When references repeat (the run of 7s), the count of distinct pages drops — locality is high, fewer frames needed. When new pages stream in (phase change at the end), climbs again.
The allocation rule (HOW the OS uses it)
Let = total demand = sum of working-set sizes over all runnable processes. Let = number of physical frames available.
WHAT is thrashing, precisely?
Page-Fault-Frequency (PFF): the practical control
Instead of computing exact working sets (expensive), bound the fault rate with two thresholds:
Worked example 2 — does this set thrash?
Three processes, frames . .
Step 1: . Why? Sum the live demands. Step 2: Compare: ⇒ thrashing. Why? Demand exceeds supply. Step 3 (fix): Suspend . New . Why ? Removing it frees the most and brings comfortably under , leaving slack for the others. System now runs A and B cleanly; C resumes when a working set fits.
Recall Feynman: explain it to a 12-year-old
Imagine you do homework at a tiny desk (RAM) but keep all your books on a shelf across the room (disk). You only need the few books for the chapter you're on right now — that's your working set. If you and your siblings crowd the desk so nobody's chapter-books fit, everyone keeps running back and forth to the shelf and no one actually writes anything. That endless running is thrashing. The smart move is for one kid to leave the desk so the rest can finally work.
Active Recall
What is the working set ?
What does represent?
In what units is the working-set window measured?
State the thrashing condition.
What principle makes the working set a good predictor?
Define thrashing.
Why does naively adding processes worsen thrashing?
What is the OS fix for thrashing?
What does the Page-Fault-Frequency (PFF) scheme do when ?
What does PFF do when ?
Why is too large bad?
Connections
- Demand Paging — working set decides which pages to keep resident.
- Page Replacement Algorithms — LRU/Clock approximate the working set.
- Locality of Reference — the empirical law the whole model rests on.
- Multiprogramming Degree — bounded by .
- TLB and Caches — same locality principle, smaller scale.
- Page Fault Handling — faults are the events PFF measures.
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Dekho, idea simple hai: ek program apni saari memory ek saath use nahi karta. Kisi bhi pal sirf thodi si pages "active" hoti hain — usko hum working set kehte hain. Yeh kaise pata chalta hai? Hum last memory references dekhte hain (window). Jo distinct pages us window mein touch hui, wahi working set. Iska size batata hai ki process ko abhi kitne frames chahiye RAM mein.
Ab thrashing kya hai? Maan lo bahut saare processes chal rahe hain. Har ek ka working set add karo: . Agar yeh total RAM ke frames se zyada ho gaya (), toh sabki active pages RAM mein fit hi nahi hongi. Phir har memory access pe page fault, disk se page lao, kisi aur ki page nikaalo, wo bhi turant fault... CPU bas swapping mein laga rehta hai, kaam kuch nahi hota. Yahi thrashing hai — disk RAM se lakhon guna slow hai, isliye system reng-reng ke chalta hai.
Sabse khatarnaak baat: jab thrashing hoti hai toh CPU idle dikhta hai (sab fault wait kar rahe). Naive scheduler sochta hai "CPU khaali hai, ek aur process daal do" — aur cheez aur kharaab ho jaati hai! Yeh positive feedback loop graph mein "cliff" banata hai. Sahi fix ulta hai: ek process ko suspend kar do, taaki ho jaaye, baaki tezi se chalein.
Exam/coding tip: seconds mein nahi, references mein hota hai. Aur PFF (page-fault-frequency) scheme practical hai — fault rate ho toh frame do, ho toh frame waapas lo. Bas itna yaad rakho: "D > m matlab DOOM."