Exercises — Working set model, thrashing

WHAT we do: take the last $\Delta =4$ references and count the distinct pages. The window: $\{3,3,3,3\}$. The four touches are all page $3$. Distinct pages: just $\{3\}$. $|W(t,4)|=1$ WHY: the working set counts which pages, not how many touches. Repeats collapse. This is exactly the "run of 7s" behaviour from the parent trace — high temporal locality ⇒ tiny working set.

(a) $\Delta$ → memory references (virtual time). It must be speed-independent so the same code has the same working-set behaviour on any CPU. (b) $f$ = faults per reference (or per unit time as a rate) — a frequency, faults divided by references. The core insight to keep: $\Delta$ is a count, not a clock.

Method: at each $t$, slide a window over the last 4 references and count distinct pages. The string, indexed: pos1=4, pos2=5, pos3=6, pos4=4, pos5=5, pos6=6, pos7=7, pos8=7, pos9=5, pos10=4.

WHY it stays at 3: the double-$7$ (temporal locality) keeps the distinct count below the window width of 4. At $t=10$ page 6 falls off the back and page 4 enters the front — count holds. See the sliding-window picture:

Step 1 — total demand. Sum the live demands: $D=6+5+7+4=22.$ Step 2 — compare with supply. $D=22>20=m\Rightarrow \text{thrashing}.$ WHY: every process needs its whole working set resident to run without constant faulting. Demanding 22 frames when only 20 exist means at least 2 live pages get evicted and immediately re-faulted — the swap-storm begins.

WHAT happens as we add processes: each new process adds its $|W_i|$ to the total demand $D$. While $D\le m$, every working set fits, faults are rare, and overlapping I/O keeps CPU busy → utilization climbs. The tipping point: the moment $D$ crosses $m$, you cannot fit all working sets. Now evicting one live page causes a fault, whose service evicts another live page, which faults... The fault rate does not drift up linearly — it compounds, because each process's shrunken resident set makes it fault more, and every fault steals service time from everyone. Why a cliff, not a slope: below $m$ the fault rate is near zero; the marginal page still fits. Just above $m$ the marginal page does not fit, and its absence triggers a chain of mutual eviction (positive feedback). A threshold with feedback past it = a cliff. The scheduler's fatal reflex: it sees low CPU use, misreads it as "idle CPU", and adds a process — pushing $D$ even further above $m$. The feedback tips the graph off the edge.

Indexed: pos1=1,2,1,2,1,2(pos6),8(pos7),9(pos8),8(pos9),9(pos10).

The bump: during pure phase P the count sits at 2. At the boundary ($t=7,8$) the window straddles both phases — it still remembers old pages $\{1,2\}$ while new pages $\{8,9\}$ stream in, so the count temporarily rises to 3. Once the window has fully moved into phase Q ($t=9$), the stale pages drop off and it settles at 2 again. WHY this matters: the working set transiently over-estimates at every phase boundary. This is exactly why $\Delta$ must roughly match the phase length — too large a $\Delta$ makes the "bump" permanent, wasting frames on dead pages.

(a) $D=5+4+6=15>12=m$ ⇒ thrashing. (b) Test each suspension — compute the surviving demand and the slack $m-D_{\text{new}}$:

Choose $C$. Suspending the largest working set frees the most frames, giving the most slack ($3$ frames). A and B run cleanly; C resumes when a working set fits. WHY prefer maximum slack: headroom absorbs the transient bumps at phase boundaries (Exercise 3.2) without re-triggering thrashing.

Decision 1: $f_B>U$ and a free frame exists → PFF grants $B$ one frame. Now $B$ holds $5$ frames. Effect: more of $B$'s working set is resident → its fault rate falls. Given: now $L<f_B<U$. Decision 2: $f_B$ sits in the dead band $[L,U]$ → PFF does nothing. Neither $f_B>U$ (would grant) nor $f_B<L$ (would revoke) fires. WHY the dead band exists: it prevents oscillation — without a gap between $L$ and $U$, the controller would grant a frame, drop below threshold, revoke it, fault again, grant again... forever. The band $[L,U]$ is hysteresis that servo-controls the resident set toward "just enough" ≈ the working set, without ever enumerating $W$.

(a) $D=10+9+8+11=38>32=m$. Overcommitted by $38-32=6$ frames ⇒ thrashing. (b) We must shed at least $6$ frames of demand. Sort working sets descending: $D(11),A(10),B(9),C(8)$.

• Suspend one: the biggest is $D=11\ge 6$. That alone works. New $D=10+9+8=27$, slack $=32-27=5$. ✓
• Could a smaller single suspension work? Need the freed amount $\ge 6$. $C=8\ge 6$ works too but gives less slack ($D=30$, slack $2$). $B=9$ → slack $4$; $A=10$ → slack $5$ (tie with D by count but D frees most). Best single suspension: suspend $D$ (or $A$) — freeing $11$ (resp. $10$) frames. Suspending $D$ gives new $D=27$, slack $5$, the largest headroom while removing only one process. (c) Why suspend whole processes rather than shrink everyone: if you cut every process below its working-set size, each one now faults on its own live pages — you convert one over-committed system into four permanently-faulting ones. Utilization collapses for all. Suspending one process keeps the survivors' working sets intact, so they run at full speed while the suspended one waits its turn. Better to run some processes fast than all at a crawl — the parent note's core allocation principle.

(a) $\Delta =50$ (far too small): the window sees only a fraction of the current phase, so it under-estimates $|W|$ — some genuinely-live pages fall outside the window, get evicted, and are re-faulted almost immediately. Result: thrashing within a phase. (b) $\Delta =5000$ (far too large): the window spans roughly ten phases at once, so it keeps stale pages from long-finished phases resident. This over-estimates $|W|$, wastes frames, and lowers the multiprogramming degree (fewer processes fit). (c) $\Delta \approx 500$ (matched): the window covers one phase, dropping old pages just as new ones enter (the "bump" from Exercise 3.2 stays brief). This tracks the true working set — enough to avoid faults, no more. Tune $\Delta$ to the phase length.