Visual walkthrough — Working set model, thrashing
We will earn every symbol before we use it. By the end you'll be able to draw the whole story on a napkin.
Step 1 — What is a "page reference"?
WHAT. A running program is, from memory's point of view, just a long stream of addresses it touches: fetch this instruction, read that array element, write this variable. Memory is chopped into fixed-size blocks called pages. Every touch lands in some page. So the program produces a sequence of page numbers — a reference string.
WHY start here. Everything downstream is counted in these touches. If we don't nail down "one touch = one entry in the string," the symbols we introduce later (the current position, and the window we slide) have nothing to stand on. (See Demand Paging for how a touch to an absent page becomes a fault.)
PICTURE. Read the string left to right. Each colored tick is one memory reference; the number below it is the page that reference landed in.
- ::: the page touched at the -th access
- ::: virtual time = how many accesses have happened so far
Step 2 — The sliding window
WHAT. Pick a whole number (say ). At any moment , look backward at the last references — the reference at and the before it — that's the window. It slides right by one every time a new reference arrives.
WHY a window, and why backward? We cannot see the future, so we use the recent past as a forecast. Locality of Reference promises "recently used ⇒ soon used again," so the last few touches are a cheap crystal ball. Backward-looking = it uses only data we already have.
PICTURE. The orange box is the window (). Watch it slide: at it covers references ; at it slides to cover , dropping the oldest and admitting the newest.
Step 3 — From window to working set: count distinct pages
WHAT. Inside the window, cross out repeats. What remains — the set of distinct page numbers — is the working set . Its size is how many frames the process needs right now.
WHY distinct? A page already in RAM costs nothing to touch again. Only different pages compete for frames. So the thing that stresses memory is the count of distinct pages in the window, not the raw number of touches.
PICTURE. Same window as before, but now duplicates are greyed out and the survivors are boxed. Count the boxes — that number is .
Worked trace with on the string (positions –):
| positions | window | distinct pages | ||
|---|---|---|---|---|
| 5 | 1–5 | 2 6 1 5 7 | {2,6,1,5,7} | 5 |
| 7 | 3–7 | 1 5 7 7 7 | {1,5,7} | 3 |
| 11 | 7–11 | 7 5 1 6 2 | {7,5,1,6,2} | 5 |
(At the full window is positions – = pages — five distinct pages, so .)
Step 4 — Why breathes: locality in action
WHAT. Watch over time. When the program loops (the run of s), distinct-page count drops. When the program changes phase and streams in fresh pages (the tail), climbs.
WHY it matters. This breathing is locality made visible. Low = tight loop, few frames needed. Rising = phase change, the program is asking for more memory. The OS can literally watch this number to decide how many frames to hand over.
PICTURE. Plot against : a valley during the loop, a rise at the phase change. The shaded band is one locality "phase."
Step 5 — Add up the demands: vs
WHAT. Run several processes at once (Multiprogramming Degree). Each has its own working-set size . Stack them into a single bar — total demand . Compare that bar against the fixed height = number of physical frames.
WHY sum them? Every process must have its working set resident to run smoothly. Frames are shared, finite, and non-overlapping — process A's frame is unavailable to B. So the pressures simply add.
PICTURE. Three stacked demand blocks (A, B, C) on the left; the RAM ceiling drawn as a horizontal red line. Two panels: one where the stack fits under , one where it pokes through.
Step 6 — The thrashing condition, forced by geometry
WHAT. If the stacked bar exceeds the ceiling , there is no legal placement: some process's live page has nowhere to sit. That page gets evicted, is touched again almost immediately, faults back in, evicts someone else's live page — a swap-storm. That is thrashing.
WHY it's forced, not likely. This is pigeonhole, not probability. You cannot fit pigeons into holes when . At least one needed page is always out on disk, and because it's needed it's re-requested at once. Disk is – slower than RAM, so the CPU stalls (see Page Fault Handling).
PICTURE. The over-full stack: the overflow slice is painted red and shown ping-ponging between RAM and disk with a two-way arrow labelled "fault → evict → refault."
Step 7 — The fix, and the trap
WHAT. To escape, suspend one whole process: swap all of it out. Its leaves the stack, dropping below , and the survivors run cleanly. Suspended work resumes later when a working set fits.
WHY suspend a whole one (not shave a bit off everyone)? Shaving frames off every process shrinks each below its working set — now everybody faults. Better to run some processes fast than all at a crawl. This is exactly what Page Replacement Algorithms cannot fix on their own: no eviction policy helps when the total simply doesn't fit.
THE TRAP. When thrashing, CPU utilization is low (everyone's blocked on disk). A naive scheduler reads "idle CPU" as "add more work," which steals more frames and deepens the collapse — positive feedback into the cliff.
PICTURE. Left: over-full stack with C highlighted. Right: C removed, stack now under , arrow labelled "suspend → D drops → runs clean."
The one-picture summary
Everything on one canvas: reference string → sliding window → distinct count → stack the demands → compare to → thrash or fix.
Recall Feynman: the whole walkthrough in plain words
A program only reads from a stream of memory touches. Slide a little box over the last few touches and count how many different pages it holds — that's how much desk space (RAM frames) it needs right this second, its working set. When it loops, that count shrinks; when it starts a new task, it grows. Now put several programs on the same desk: stack up how much space each one needs. If the stack is taller than the desk, at least one needed sheet is always on the floor — you spend all day picking it up and dropping someone else's. That's thrashing, and it's guaranteed by pigeonhole, not bad luck. The cure isn't to trim everyone (then all of them fumble); it's to send one whole program away so the rest can actually work. And beware: a busy-looking-but-idle CPU during heavy paging means too much load, never too little — so you remove a program, you never add one.