Worked examples — Working set model, thrashing

Before anything, one reminder of the two quantities we juggle, in plain words:

---

The scenario matrix

Every question this topic can ask is one of these cells. The examples below are tagged with the cell they cover.

#	Cell (case class)	What makes it special	Example
C1	High locality (many repeats)	$\Vert W\Vert$ shrinks — few frames needed	Ex 1
C2	Low locality (all-distinct stream)	$\Vert W\Vert$ hits its ceiling $=\Delta$	Ex 2
C3	Phase change (locality set swaps)	$\Vert W\Vert$ spikes then re-settles	Ex 3
C4	$D<m$ (comfortable)	slack frames, no thrash, room to add load	Ex 4
C5	$D=m$ (exact break-even)	the boundary — thrash or not?	Ex 5
C6	$D>m$ (over-committed)	thrashing; must suspend	Ex 6
C7	Degenerate $\Delta$ ($\Delta =1$, or $\Delta \ge$ string length)	limiting behaviour of the window	Ex 7
C8	Real-world word problem	translate English → $D$ vs $m$	Ex 8
C9	Exam twist (PFF servo / low-CPU trap)	apply the feedback reasoning, not the raw formula	Ex 9

Read the "cliff" once more so C9 lands — the shape you must recognise:

---

C1 — High locality: repeats shrink the working set

Steps.

1. Locate the window at $t=4$. The last 4 references ending at position 4 are $4442$. Why this step? $W(t,\Delta )$ is defined as the distinct pages inside the last $\Delta$ accesses — so first we physically slice out those $\Delta$ accesses.
2. Count distinct pages. $\{4,2\}\Rightarrow |W(4,4)|=2$. Why? The three $4$s collapse to one page — the working set counts distinct pages, and repeats are exactly what locality produces.
3. Slide to $t=8$. Last 4 references: $4422\Rightarrow \{4,2\}\Rightarrow |W(8,4)|=2$. Why? Same two hot pages dominate the whole loop — high temporal locality keeps demand flat and small.

Verify: A window of width 4 can at most hold 4 distinct pages, and at least 1. We got 2, comfortably inside $[1,4]$. Sanity: the string only ever names pages 2 and 4, so $|W|$ can never exceed 2 anywhere. ✓ (Cell C1.)

---

C2 — Low locality: every page distinct

Steps.

1. Window at $t=4$: $1234\Rightarrow \{1,2,3,4\}\Rightarrow |W|=4$. Why this step? All four slots hold different pages — no collapsing happens.
2. Window at $t=6$: $3456\Rightarrow \{3,4,5,6\}\Rightarrow |W|=4$. Why? A pure streaming scan (array sweep, table scan) has no temporal locality — every reference is a brand-new page, so the window is always full of distinct pages.
3. Read the ceiling. $|W|=\Delta =4$: the working set saturates its window. Why it matters? This is the worst case for demand paging — the working set model over-predicts, and larger $\Delta$ would only pin more soon-dead pages (see the "bigger $\Delta$ isn't always better" mistake in the parent).

Verify: $|W|\le \Delta =4$ always; here it equals the bound, the theoretical maximum for a window of 4. ✓ (Cell C2.)

---

C3 — Phase change: the working set spikes, then re-settles

Steps.

1. $t=4$ (inside A): window $7788\Rightarrow \{7,8\}\Rightarrow |W|=2$. Why? Phase A is a tight loop over 2 pages — locality high, demand low.
2. $t=6$ (the seam): window $812\text{(refs 3–6: }812)$ — take last 4 ending at ref 6: refs 3,4,5,6 $=8812\Rightarrow \{8,1,2\}\Rightarrow |W|=3$. Why this step? The window still holds stale phase-A pages ($8$) and fresh phase-B pages ($1,2$) — during a transition both localities coexist, so demand temporarily rises.
3. $t=8$ (inside B): refs 5–8 $=1233\Rightarrow \{1,2,3\}\Rightarrow |W|=3$. Why? Once phase A pages age out of the window, only the new locality set remains.

Verify: Demand rose $2\to 3$ at the transition and held at $3$ — exactly the "spike at a phase change" the working set model is designed to catch. All counts lie in $[1,\Delta ]=[1,4]$. ✓ (Cell C3.)

---

C4 · C5 · C6 — Comfortable, break-even, over-committed

These three share one arithmetic: total demand $D={\sum }_i|W_i|$ versus frames $m$. We do all three signs at once so no case is left unshown.

1. Sum the demand: $D=3+4=7$. Why? Every runnable process needs its whole working set resident simultaneously, so demands add.
2. Compare to supply: $7<10\Rightarrow$ no thrashing, and $10-7=3$ frames are free. Why? Supply exceeds demand — everyone's live pages fit.
3. Consequence: the scheduler may safely raise the Multiprogramming Degree — 3 spare frames could host a small third process.

Verify: $D=7\le m=10$, slack $=3\ge 0$. ✓

1. Sum: $D=5+4=9$. Why? Same additive rule.
2. Compare: $9=9$. The thrashing condition is $D>m$ (strict), so $D=m$ is not thrashing — but there are zero spare frames. Why the strictness matters? At equality every working set just fits; nothing is evicted, so no fault-storm. But there is no margin: any tiny growth in one working set (a phase change) tips you straight into $D>m$.
3. Judgement: technically safe, operationally fragile — do not add load.

Verify: $D=9$, $m=9$, slack $=0$, and $D\ngtr m$, so no thrash by the definition. ✓

1. Sum: $D=5+4+6=15$. Why? Additive live demand.
2. Compare: $15>12\Rightarrow$ thrashing — supply short by $15-12=3$ frames. Why this means thrash? Three frames' worth of live pages have nowhere to sit; they get evicted, immediately re-faulted, and the machine trades compute for disk seeks.
3. Suspend the fix: drop $C$ ($|W_C|=6$). New $D=5+4=9\le 12$. Why $C$? It frees the most frames and lands $D$ comfortably below $m$ with $12-9=3$ slack — one suspension, problem solved.

Verify: before $15>12$ (thrash); after $9\le 12$ with slack $3$. Suspending $A$ instead would give $D=10\le 12$ (also works) but leaves only slack $2$; suspending $C$ maximises breathing room. ✓ (Cells C4/C5/C6.)

---

C7 — Degenerate windows: the limits of $\Delta$

1. (a) $\Delta =1$ — smallest window. The window is just the single current reference $\{6\}\Rightarrow |W|=1$. Why? One slot holds one page; a window of width 1 always gives $|W|=1$. This is the degenerate under-estimate — it forgets everything, so it thrashes on any real program.
2. (b) $\Delta =100$ — window bigger than the whole history. You can only look back at references that exist: all 6, i.e. $556566\Rightarrow \{5,6\}\Rightarrow |W|=2$. Why? When $\Delta \ge$ (number of references so far), the window becomes the entire reference history — $|W|$ equals the total distinct pages ever touched. This is the degenerate over-estimate: it never forgets, so it pins stale pages forever.
3. The takeaway on limits. As $\Delta :1\uparrow \infty$, $|W|$ climbs monotonically from $1$ up to (total distinct pages). The "right" $\Delta$ sits between these extremes, matched to the locality-phase length.

Verify: (a) $|W|=1$ (forced by $\Delta =1$). (b) distinct pages in whole string $=|\{5,6\}|=2$. Both inside $[1,\Delta ]$. ✓ (Cell C7.)

---

C8 — Real-world word problem

1. Frames available. Usable RAM $=6-1.5=4.5\text{ GiB}=4.5\times 2^{30}$ bytes. Divide by page size $4\text{ KiB}=4\times 2^{10}$: $m=\frac{4.5\times 2^{30}}{4\times 2^{10}}=\frac{4.5}{4}\times 2^{20}=1.125\times 1048576=1179648\text{frames}.$ Why this step? The thrashing test is in frames, so convert every byte figure into frames first (units must match).
2. Total demand. $D=6\times 200=1200$ frames. Why? All 6 workers are runnable together, so their working sets add.
3. Compare. $1200\ll 1179648\Rightarrow$ no thrashing — the box is enormously over-provisioned for this tiny working set.
4. How many workers fit? $\lfloor m/200\rfloor =\lfloor 1179648/200\rfloor =5898$ workers before $D$ would exceed $m$.

Verify: $D=1200$, $m=1179648$, $D\le m$ ✓. Max workers: $5898\times 200=1179600\le m$ and $5899\times 200=1179800>m$. ✓ (Cell C8.)

---

C9 — Exam twist: the low-CPU trap and the PFF servo

1. Test the working-set condition first. $D=3+3+4=10>8=m$. Why? Before trusting the CPU meter, check whether demand physically fits — it does not (short by $2$ frames).
2. Interpret the low CPU + high faults. Low utilization here means everyone is blocked on page faults, not that there is no work. Why this is the whole trick? The exam wants you to see that $f>U$ for the group is the cause of the idle CPU — the PFF law says "when everyone faults above $U$ and no free frames exist, suspend, don't add."
3. Wrong move (the trap): adding process 4 raises $D$ to $\ge 13>8$, shrinks each resident set, raises $f$ further, drives CPU below 15% — positive feedback into collapse.
4. Right move: suspend $C$. New $D=3+3=6\le 8$, slack $=2$; A and B stop faulting, CPU utilization recovers.

Verify: thrash before: $10>8$ ✓. After suspending $C$: $6\le 8$ with slack $2$ ✓. Adding a 4th (say $|W_D|\ge 3$) gives $D\ge 13>8$ — strictly worse ✓. (Cell C9.)

---

Active recall

Recall Why does

$|W|$ never exceed $\Delta$? Because the window holds exactly $\Delta$ references, and distinct pages $\le$ total references — repeats can only reduce the count. ::: So $1\le |W|\le \Delta$ always, with the ceiling hit only under zero temporal locality.