Working set model, thrashing: Question bank — Coding deep dive

This page assumes the vocabulary from the parent Working Set Model & Thrashing. If any word feels shaky, rebuild it there first. Prerequisite ideas live in Locality of Reference, Demand Paging, Page Fault Handling, Page Replacement Algorithms, Multiprogramming Degree, and TLB and Caches.

Symbol reminder (read before the traps)

Every symbol used on this page, in plain words. Nothing below is used before it appears here.

Definition The cast of symbols

$t$ — the current virtual time, i.e. the position in the stream of memory accesses. Access number 1, 2, 3, … Not clock time.
$Δ$ (delta) — the window size: how many of the most recent memory accesses we look back over. Counted in accesses, never seconds.
$W (t, Δ)$ — the working set: the set of distinct pages touched during the last $Δ$ accesses ending at time $t$ . It is a set of page-numbers, e.g. ${2, 6, 1}$ .
$∣ W (t, Δ) ∣$ (or just $∣ W ∣$ when $t, Δ$ are obvious) — the size of that set = how many distinct pages, hence how many frames the process needs right now. The bars $∣ \cdot ∣$ mean "count of elements".
$m$ — the number of physical frames (page-sized slots in RAM) the machine has to hand out.
$D$ — total demand $= \sum_{i} ∣ W_{i} ∣$ , the working-set sizes of all runnable processes added up. If $D > m$ the demands cannot all fit.
$f$ — a process's measured page-fault rate (faults per unit of accesses).
$L$ , $U$ — the lower and upper fault-rate bounds used by Page-Fault-Frequency control. Keep $f$ between $L$ and $U$ .

A trap caught in the act — minimal walk-through

Worked example The scheduler's fatal "helpful" move

Frames $m = 12$ . Two processes are running with $∣ W_{A} ∣ = 5$ , $∣ W_{B} ∣ = 4$ , so $D = 9 \leq 12$ — healthy, CPU busy. Now the scheduler notices CPU dipping during an I/O burst and, believing the CPU is under-loaded, admits process $C$ with $∣ W_{C} ∣ = 6$ .

Step 1 — new demand: $D = 5 + 4 + 6 = 15$ .
Step 2 — compare to supply: $15 > 12$ , so the three working sets cannot all be resident.
Step 3 — the collapse: some live pages get evicted, are re-referenced immediately, and fault straight back from disk. All three processes now spend most of their time in Page Fault Handling rather than executing.
Step 4 — the trap closes: CPU utilization drops further, the scheduler reads that as "still under-loaded", and is tempted to add a fourth process — exactly the wrong move.

The escape: detect $D > m$ (or fault rate above $U$ ) and suspend $C$ . Then $D = 9 \leq 12$ and A, B run cleanly. The lesson every trap below re-tests: low CPU during heavy paging is over-load, not under-load.

True or false — justify

Every prompt is a claim. Decide true/false and give the one-line reason.

Δ

is measured in milliseconds."

False —

Δ

counts memory references (virtual time

t

), so the working-set behaviour is identical on a fast or slow CPU. See Locality of Reference.

"A larger window

Δ

always gives better performance."

False — too large keeps stale pages resident (over-estimates

∣ W ∣

), wasting frames and lowering the Multiprogramming Degree;

Δ

must match the locality phase length.

"If

D = \sum_{i} ∣ W_{i} ∣

equals

m

exactly, the system is thrashing."

False — thrashing needs

D > m

; at

D = m

every working set just fits, so processes run without constant re-faulting (though with zero slack).

"Thrashing means the CPU is overloaded with computation."

False — the CPU is nearly idle; it is stalled waiting on disk for page faults, not busy computing. Low utilization is the symptom.

"The working set is a fixed set of pages chosen once when the process starts."

False — it is a sliding window: as new references arrive and old ones fall out of the last

Δ

accesses, the set continuously changes.

"Adding more processes when CPU utilization is low always improves throughput."

False — only when the system is not thrashing. Under thrashing, low CPU use is caused by faulting, so more processes steal frames and worsen the collapse.

"Page-Fault-Frequency (PFF) control computes the exact working set each interval."

False — PFF avoids enumerating

W (t, Δ)

; it servo-controls the measured fault rate

f

between bounds

L

and

U

, which converges toward the right frame count indirectly.

"Locality of reference is an assumption we hope holds; the working set model breaks if a program is truly random-access."

True — with no locality (uniform random access) the recent past predicts nothing,

∣ W ∣

balloons, and the model gives no benefit. See Locality of Reference.

"Thrashing can happen even with a single process."

True — if that one process's working set alone exceeds

m

(i.e.

∣ W ∣ > m

), it faults on nearly every access with no other process to blame.

Spot the error

Each line contains a subtly broken statement. The reveal names the flaw and fixes it.

"To fix thrashing, evict a few pages from each process evenly."

Wrong — shrinking everyone's resident set below their working set makes all of them fault more; the fix is to suspend one whole process so the rest keep their full

W (t, Δ)

∣ W (t, Δ) ∣

counts every reference in the window, so it grows with

Δ

regardless of repeats."

Wrong — it counts distinct pages, so repeated references (a run of the same page) do not increase it; high locality keeps

∣ W ∣

small even for large

Δ

"Increasing the multiprogramming degree always increases CPU utilization."

Wrong — utilization rises only up to a critical point; past it, working sets no longer fit and utilization falls off the cliff. See Multiprogramming Degree.

"The thrashing condition is

\sum_{i} ∣ W_{i} ∣ < m

Wrong — that is the safe condition; thrashing is

\sum_{i} ∣ W_{i} ∣ > m

, i.e.

D > m

(demand exceeds supply).

"Because disk is slow, we should page in more pages per fault to amortise the cost — that eliminates thrashing."

Wrong — prefetching helps latency per fault but does not change the fact that total demand

D

exceeds

m

; thrashing is a capacity problem, not a per-fault-cost problem.

"A high TLB miss rate is the same thing as thrashing."

Wrong — a TLB and Caches miss just re-walks the page table (often still in RAM); thrashing is about page faults hitting disk. Different layer, different cost.

Why questions

Answer with the mechanism, not a definition.

Why is the window

Δ

measured in references and not seconds?

So the working-set behaviour is a property of the program's access pattern alone, independent of CPU speed, scheduling, or how long the process happened to be swapped out.

Why does the scheduler's natural reaction make thrashing worse?

Seeing low CPU utilization, it adds processes to "use the idle CPU"; each new process steals frames, raising everyone's fault rate

f

and dropping utilization further — a positive-feedback collapse.

Why does a run of repeated references shrink

∣ W ∣

Repeats add no new distinct pages while old distinct pages age out of the window, so the count of live pages drops — a numerical signature of high temporal locality.

Why suspend an entire process rather than trim frames globally?

A resident set below the working set causes near-constant faulting, so half-served processes are worthless; removing one entirely restores full working sets for the survivors and drops

D

below

m

Why can PFF control replace exact working-set computation?

The fault rate

f

is a cheap, directly-measurable proxy: too many frames ⇒

f

low (below

L

), too few ⇒

f

high (above

U

), so keeping

f \in [L, U]

drives the frame count to "just enough" — which is the working set.

Why does spatial locality justify demand-paging whole pages instead of single bytes?

Touching address

x

predicts soon touching

x + 1

, so loading the containing page pays one fault to serve many nearby future accesses. See Demand Paging.

Edge cases

Boundary and degenerate scenarios the model must still handle.

What is

∣ W (t, Δ) ∣

when

Δ = 1

Exactly

1

— the window holds only the current reference, so the working set is the single page just touched (a maximally short-sighted, thrash-prone estimate).

What happens to

∣ W ∣

at a phase change (program switches to a new region of memory)?

It temporarily spikes: old pages still in the window plus a burst of new ones both count, over-estimating need until old pages age out.

Δ

exceeds the whole program's lifetime of references, what does

W (t, Δ)

become?

The set of all pages the process ever touched — no forecasting value, since nothing is ever forgotten from the window.

Two processes each with

∣ W_{i} ∣ = m

and only

m

frames total — thrash or not?

Thrash —

D = 2 m > m

. Each alone fits, but together they cannot, so co-scheduling them forces eviction and re-faulting; run one at a time.

A process references only one page forever — is thrashing possible?

No —

∣ W ∣ = 1

, which fits in any non-trivial

m

; with no other demand there is nothing to evict, so the fault rate

f

is essentially zero after the first fault.

What if two processes' working sets overlap (they share pages, e.g. a shared library)?

Naïve

D = \sum_{i} ∣ W_{i} ∣

over-counts the shared pages; true demand is the size of the union, so the simple sum can falsely predict thrashing when shared frames make the real footprint smaller.

D = m

exactly, what is the cost of one more runnable page reference to a new page?

With zero slack, admitting any new page forces an eviction of a live page, tipping the system into faulting —

D = m

is the razor's edge, not a comfortable operating point.

Recall One-line closure

A trap answered with the right yes/no but the wrong reason ::: is a trap you will fall into next time — always rehearse the mechanism.