Thrashing and the Working Set

Thrashing is a degenerate steady state of a paging system in which processes fault so frequently that the CPU spends nearly all its time servicing page faults — reading and writing pages to backing store — rather than executing instructions. CPU utilization, which normally increases as more processes are added (more processes means more chances that someone is ready to run when another blocks), instead collapses once the sum of processes' memory demands outstrips physical memory. Every process's resident set is squeezed until pages needed in the immediate future are evicted before they are used again, forcing another fault almost immediately. The system oscillates between fault-servicing and starvation. The explanation rests on locality of reference: at any point in a program's execution, references cluster around a relatively small, slowly changing set of pages — the current function's code, its local variables, the data structure it is traversing. A program moves through a sequence of localities as execution proceeds (entering a new function, starting a new loop, switching data structures), but within a locality the active page set is compact. This is an empirical property of real programs (loops, sequential array scans, hot code paths), not a mathematical guarantee, and it is the reason virtual memory works at all: without locality, no small resident set would ever suffice, and paging would always be catastrophic. The working-set model (Denning, 1968) formalizes locality into an operational definition. Fix a window size Δ, measured in number of memory references (or, in some implementations, elapsed virtual time). The working set WS(t, Δ) is the set of distinct pages referenced in the interval of the process's most recent Δ references, ending at virtual time t. Its size, WSS(t, Δ) = |WS(t, Δ)|, is a function of Δ: too small a Δ misses part of the current locality (thrashing risk even with "enough" memory), too large a Δ blends together multiple localities (wasting memory on pages no longer needed). The working-set model's central claim is a memory-allocation policy: give each process at least WSS(t, Δ) frames, so its full current locality stays resident, and admit new processes only while there remain enough free frames to satisfy everyone's working set simultaneously — this is the origin of controlling the degree of multiprogramming, the number of processes concurrently competing for memory.

Page-fault-frequency (PFF) control is a pragmatic alternative that measures the symptom (fault rate) directly rather than the cause (working-set size), sidestepping the need to track exact reference windows. It keeps each process's observed fault rate inside a target band by dynamically growing or shrinking its frame allocation, and throttles multiprogramming when frames run out globally.

Step 1 — Detecting the problem in the large. A kernel monitors global CPU utilization and global paging rate. If utilization is falling while the paging rate is rising, and free-frame count is low, the system is on the thrashing side of the curve.

Step 2 — Working-set tracking (per process). Every process maintains, conceptually, the sliding window of its last Δ page references. Maintaining this exactly is expensive, so real systems approximate it using the reference bits already exploited by the Clock Algorithm (or a variant), sampled periodically.

Step 3 — Frame allocation from working-set sizes. The kernel sums working-set sizes across resident processes. If the sum exceeds the number of physical frames, it must reduce the multiprogramming degree — suspend (swap out entirely) one or more processes — rather than let every process's allocation shrink below its working set, which would only induce more faulting.

Step 4 — Page-fault-frequency control (the operational alternative). Rather than estimating WSS directly, the kernel measures each process's fault rate F = faults / time since its last frame-count adjustment. It compares F against a target band [lower, upper]:

• If F is above `upper`, the process is faulting too much for its current allocation — give it more frames (if available).
• If F is below `lower`, the process has more frames than its locality needs — reclaim some (they can be given to another process or freed).
• If F stays above `upper` and no frames are available to give, some process must be suspended (multiprogramming degree reduced) to free frames globally.

Both mechanisms are feedback controllers: they sample a signal (working-set size or fault rate), compare it to a target, and adjust an allocation. This is why they are robust to workload variation — they do not require a priori knowledge of a program's memory needs, only continual observation. ```pseudocode

# ---------- Working-set estimation (approximate, clock-based) ----------

# Each process p keeps: reference bits per resident page, sampled on a timer.

# WS_estimate(p) approximates WS(t, Δ) using T recent timer samples

# instead of exact reference counts (Δ ≈ T * sampling_interval). structure PageEntry: page_id ref_bit # hardware-set on access, cleared by us last_seen_tick # last timer tick at which ref_bit was found set function SAMPLE_WORKING_SET(process p, current_tick, window_ticks): active = {} for entry in p.resident_pages: if entry.ref_bit == 1: entry.last_seen_tick = current_tick entry.ref_bit = 0 # clear for next interval if current_tick - entry.last_seen_tick <= window_ticks: active.add(entry.page_id) p.working_set_estimate = active return |active| # WSS estimate

# Called by the kernel's periodic memory-management interrupt handler: function WORKING_SET_POLICY(all_processes, total_frames, window_ticks, tick): total_wss = 0 for p in all_processes: wss_p = SAMPLE_WORKING_SET(p, tick, window_ticks) total_wss += wss_p if total_wss > total_frames:

# Overcommitted: must reduce degree of multiprogramming victim = SELECT_SUSPEND_VICTIM(all_processes) # e.g., lowest priority,

# largest WSS, or longest idle SUSPEND(victim) # swap all its frames out elif total_frames - total_wss >= MIN_WSS_TO_ADMIT: candidate = NEXT_WAITING_PROCESS() if candidate exists: ADMIT(candidate) # raise multiprogramming degree ``` ```pseudocode

# ---------- Page-Fault-Frequency (PFF) control ----------

# Simpler to implement than exact WS: only needs a per-process fault counter

# and a periodic timer; no reference-bit scanning required. structure ProcessMemState: frames_allocated faults_since_last_check last_check_time function PFF_CONTROL(p, current_time, lower_thresh, upper_thresh, free_frames): interval = current_time - p.last_check_time if interval <= 0: return # avoid divide-by-zero on first call fault_rate = p.faults_since_last_check / interval if fault_rate > upper_thresh: needed = ESTIMATE_FRAMES_NEEDED(fault_rate, upper_thresh, p.frames_allocated) if free_frames >= needed: GIVE_FRAMES(p, needed) free_frames -= needed else:

# No frames to give: this process (or another) must be suspended REQUEST_SUSPEND(SELECT_VICTIM(all_processes)) elif fault_rate < lower_thresh: surplus = ESTIMATE_SURPLUS(fault_rate, lower_thresh, p.frames_allocated) RECLAIM_FRAMES(p, surplus) free_frames += surplus p.faults_since_last_check = 0 p.last_check_time = current_time

# Invoked on every page fault, incrementing the counter that PFF_CONTROL reads: function ON_PAGE_FAULT(p): p.faults_since_last_check += 1 HANDLE_FAULT_NORMALLY(p) # ordinary demand-paging fault service ```

Working-set estimation cost. Exact WS(t, Δ) tracking would require logging every memory reference — infeasible at hardware speed. The clock-based approximation instead scans each process's resident page table entries once per timer sample. If a process holds `f` resident frames and the kernel samples every `s` timer ticks, the per-process cost is O(f) per sample, and O(f / s) amortized per unit time. Summing over `n` processes with total resident frames F (≤ physical memory size M), the global cost per sample interval is O(F) = O(M), independent of `n` for fixed total memory — the work scales with memory size, not process count, which is why the approximation is practical even under heavy multiprogramming.

PFF control cost. Each page fault increments one counter: O(1) per fault, no scanning required. The periodic check per process is O(1) (a few arithmetic comparisons), so the global periodic cost is O(n) per control interval — cheaper than working-set sampling, at the price of reacting only to the symptom (fault rate) rather than directly to the cause (which pages are hot).

Why this prevents thrashing — the invariant. Define the system invariant we want to maintain:

where M is the number of physical frames available for user pages. This is the working-set balance invariant. As long as it holds, every resident process has enough frames to retain its current locality, so — assuming the locality assumption itself holds for the workload — very few pages needed in the near future have been evicted, and the aggregate fault rate stays low. Thrashing is precisely the violation of this invariant: when

frames must be shared out below what each process's locality requires. Any replacement algorithm, however good, is forced to evict pages that will be referenced again imminently, since there is provably not enough room for everyone's locality — this is not a policy failure but an information-theoretic impossibility given the memory budget. The working-set admission rule enforces the invariant directly: a new process is admitted only if

which by induction keeps the sum below M at every admission step, provided the estimate is accurate and Δ is chosen well.

PFF's correctness argument is indirect but sound. There is a monotone (empirically, not proven in full generality) relationship between a process's allocated frame count and its fault rate — the fault-rate/allocation curve, decreasing as frames increase, flattening once allocation covers the working set (this is the operational content of the locality assumption). PFF's target band brackets the flat region of this curve: below `lower_thresh` the process has surplus frames it is not using (safe to reclaim, no effect on fault rate); above `upper_thresh` the process is in the steep declining part of the curve (each frame reclaimed would sharply worsen faulting, and each frame added meaningfully helps). By hill-climbing along this curve per process, and freeing global memory pressure by suspending a process when no frames remain to hand out, PFF drives the system toward the same invariant, without ever explicitly computing WSS.

Honest tradeoffs.

• Both mechanisms depend on locality holding; a workload with no locality (e.g., pure random access over a huge address space) cannot be rescued by any allocation policy — the fault rate is intrinsic to the working set, not to the algorithm.
• Choosing Δ (working-set model) or the [lower, upper] band (PFF) is a tuning problem: too tight and the system oscillates admitting/suspending processes; too loose and either memory is wasted (Δ too large) or thrashing still occurs (Δ too small, or band too wide).
• Suspending a process to free memory has its own cost — writing its entire resident set out — so the controller must avoid thrashing on suspension decisions themselves (flapping a process in and out repeatedly), typically by adding hysteresis (different thresholds for admit vs. suspend, or a cooldown timer).
• PFF is cheaper but reactive: by the time fault rate crosses the upper threshold, some damage (extra I/O, latency) has already occurred; the working-set model is proactive but harder to measure precisely.

Consider a system with M = 100 physical frames available for user pages, and four processes admitted in sequence, each entering a new locality phase over time. We track working-set size (estimated with Δ corresponding to a fixed sampling window) and the resulting decision at each admission point.

Reading the trace: at t2, the system is already near saturation (only 10 free frames) but still under the invariant, so it is fragile — one process entering a bigger locality (t4, P1 jumping from 25 to 40 pages, e.g., starting a large matrix multiply) pushes ΣWSS to 102, violating the invariant by 2 frames. Even this small violation is enough to start degrading P3 specifically, because P3 has the smallest margin. The PFF controller (t5) detects P3's elevated fault rate — the operational symptom of the invariant violation — and suspends it, since no frames are free to give it. This restores the invariant (t6: ΣWSS = 70 ≤ 100) at the cost of P3 making zero progress until it is resumed. Only once P1 shrinks back down (t7, finishing its large loop) is there enough slack to admit the waiting P4 (t8) without re-violating the invariant. This trace illustrates the key qualitative behavior: thrashing is a sum condition, not a per-process one — no single process was greedy, but their combined footprint at t4 exceeded memory, and the system's only correct response was to remove one process entirely (suspend), not to shrink everyone's allocation equally (which would have pushed multiple processes below their working sets simultaneously, spreading the thrashing instead of containing it).

Modern operating-system kernels rarely implement the textbook working-set algorithm verbatim (exact reference-window tracking is too costly), but nearly every production virtual-memory subsystem implements some feedback loop with the same goal: measure demand, and throttle admission or reclaim memory before global thrashing sets in. Linux's page reclaim and OOM (out-of-memory) killer, and its `vm.swappiness` and pressure-stall information (`PSI`) metrics, are direct descendants of PFF-style monitoring — PSI literally reports the fraction of time processes spend stalled waiting on memory, a modern proxy for the fault-rate signal PFF used. Windows' working-set trimmer explicitly tracks each process's resident set and adjusts it under memory pressure, using terminology inherited directly from Denning's model. In virtualization, hypervisors face an amplified version of the same problem across guest VMs instead of processes: ballooning drivers inflate inside a guest to reclaim pages the hypervisor can hand to another VM, functioning as an externally triggered working-set squeeze, while VMware's ESXi and similar platforms monitor per-VM "active memory" (an operational analogue of WSS) to decide how much physical RAM each VM truly needs versus merely holds. Container orchestrators (Kubernetes' memory limits and eviction manager) apply the same admission-control philosophy at a coarser grain — refusing to schedule a new pod onto a node whose aggregate memory demand would exceed capacity, echoing the working-set admission rule directly. Database buffer-pool managers and JVM garbage collectors apply locality-driven sizing internally as well, treating "hot" data or object sets much as the kernel treats a process's working set.

Ask the tutor: How would you design a hysteresis rule for the admit/suspend decision to avoid flapping a process in and out of memory?