Search Knowledge

© 2026 LIBREUNI PROJECT

Page 15 of 29

Replacement, Working Sets, and Thrashing

Analyze page-replacement policies from reference traces, prove the stack-property boundary, and diagnose when aggregate working-set demand turns reclaim into thrashing.

Lesson briefVirtual memory · 5 h 30 min · 4 outcomes

Required knowledge

  • Demand paging, page faults, physical frames, and file/anonymous backing
  • Sets, sequences, recency order, and basic proof by induction
  • Latency, throughput, and queueing as distinct performance measures

Learning outcomes

  • Execute FIFO, exact LRU, OPT, and CLOCK-style replacement traces with explicit victim and dirty-page costs.
  • Use the stack property to explain why LRU avoids Bélády's anomaly while FIFO does not.
  • Compute a process working set over a reference window and diagnose system-wide thrashing from demand exceeding available frames.
  • Design a reclaim experiment that separates policy quality, workload locality, writeback cost, and memory-allocation scope.

Assessment target

Given an unseen multi-process reference trace with clean and dirty pages, execute competing replacement policies, prove or refute monotonicity as frames change, estimate working sets, identify the onset of thrashing, and defend a recovery policy with measurable evidence.

Scope boundary

  • Swap-device implementation, compressed memory, NUMA balancing, huge-page reclaim, and Linux Multi-Gen LRU internals beyond its documented model are not implemented.
  • The interactive trace uses exact LRU and a single global frame pool; production kernels use approximations, multiple page classes, and resource-control boundaries.

Demand paging can admit more virtual memory than physical memory. Once every free frame is occupied, satisfying one not-present fault requires reclaiming or evicting something else. A poor victim may be referenced again immediately, causing another fault that evicts another hot page. Under sufficient pressure, CPUs spend their time servicing faults and storage traffic while application throughput collapses.

Replacement is not “choose the oldest page.” It is an online decision under incomplete knowledge. The kernel must estimate which resident page has the lowest future value while accounting for dirty writeback, sharing, fairness, and the allocation domain from which the victim may be taken.

Reclaim objective. Free enough usable memory while minimizing future stall cost and preserving allocation isolation. A policy must be evaluated against a reference workload and cost model, not by its name.

Reference strings make policy claims falsifiable

Let a reference string r1,r2,…,rnr_1,r_2,\ldots,r_n record virtual page numbers in access order. A resident set RtR_t is the set of pages occupying the assessed frames after reference tt A reference is a hit if rt∈Rt−1r_t \in R_{t-1} and a fault otherwise. On a fault with no free frame, the policy selects a victim v∈Rt−1v \in R_{t-1}

The small trace model assumes:

  • every reference accesses one page;
  • all pages have equal size;
  • any evicted page can later be restored;
  • replacement decision time is ignored;
  • faults are counted equally unless dirty cost is introduced explicitly; and
  • prefetching, sharing, NUMA, and concurrent references are absent.

These assumptions isolate victim choice. They do not model end-to-end program time.

Four comparison policies

PolicyVictim ruleKnowledge requiredPrincipal boundary
FIFOpage loaded earliestarrival ordercan evict a frequently used old page
exact LRUpage referenced least recentlytotal recency ordermetadata/coordination cost is high
OPT/MINpage whose next use is farthest in the futurefuture traceoffline lower bound, not deployable online
CLOCK/second chancefirst candidate whose reference bit is clearapproximate recent-use bitscan rate and bit sampling affect quality

OPT is useful because it separates “the workload inherently needs many faults” from “the online policy chose poorly.” It is not an implementation proposal.

Retrieval — recover the online boundary. Why can OPT be used in an evaluation even though a kernel cannot implement it for an arbitrary future workload?

Reveal the diagnostic answerExpand

An offline experiment already has the complete recorded trace, so it can compute the minimum achievable fault count for that trace and frame capacity. The gap between an online policy and OPT is evidence about victim decisions. Deploying OPT would require knowledge of future references that the running kernel does not possess.

FIFO can get worse when memory increases

Consider the reference string

1 2 3 4 1 2 5 1 2 3 4 5

Worked trace: FIFO with three frames

The queue is written oldest→newest.

RefFrames/queue after accessResultEvictedFaults
11fault—1
21 2fault—2
31 2 3fault—3
42 3 4fault14
13 4 1fault25
24 1 2fault36
51 2 5fault47
11 2 5hit—7
21 2 5hit—7
32 5 3fault18
45 3 4fault29
55 3 4hit—9

With four frames, FIFO faults 10 times on the same trace. The larger resident set changes queue order so that pages 1–5 repeatedly displace one another near the end. This is Bélády’s anomaly: increasing allocated frames can increase faults for a non-stack policy.

Stack property. A replacement algorithm has the stack property if, after every common reference prefix, the resident set with kk frames is a subset of the resident set with k+1k+1 frames.

Exact LRU has this property. Maintain all referenced pages in one recency order. The kk-frame resident set is the first kk pages of that order; the (k+1)(k+1)-frame set is the first k+1k+1 Therefore every hit with kk frames is also a hit with k+1k+1 so adding a frame cannot increase exact-LRU faults. FIFO’s resident sets are not prefixes of one shared order, so the proof does not apply.

Page replacement and stack properties

0 / 4 answered

Evaluate each statement regarding page replacement policies, stack properties, and thrashing:

Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.

1
The CLOCK second-chance algorithm uses hardware accessed bits to approximate LRU with bounded pointer traversal cost.
2
Thrashing can be resolved entirely by switching the local replacement algorithm without reducing active workload demand.
3
FIFO page replacement is guaranteed to be monotonic because older loaded pages are strictly less likely to be used.
4
Replacement algorithms satisfying the stack property guarantee that increasing physical frames cannot increase faults.

Experiment: force a non-monotonic fault curve

The simulator implements FIFO, exact LRU, and offline OPT for fixed reference strings. It counts all faults equally, assumes clean pages, and uses two to five frames in one global pool. Its “changing working set” and “cyclic scan” traces are deterministic examples, not workload measurements.

Prediction — write the number before moving the frame control. For the Bélády trace under FIFO, will four frames produce fewer, equal, or more faults than three? State which invariant would rule out your answer for exact LRU.

Interactive exploration

Run a page-replacement policy against locality

Change frame capacity, policy, and reference pattern. Scrub the trace to inspect every victim choice; use the Belady trace to test whether adding memory can increase FIFO faults.

6 faults in 12 references
Frames after 12 references
frame 01
frame 12
frame 23

Fault: evicted page 5

123214125213
cumulative faultsreferences

OPT looks into the future and is not implementable online; it supplies a comparison bound. LRU here is exact, while production kernels approximate recency and also consider dirty pages, sharing, I/O cost, cgroups, and reclaim pressure.

Run a page-replacement policy against locality
Frames after 12 references
frame 05
frame 13
frame 24

Hit: frame contents unchanged

123412512345
cumulative faultsreferences

Static state: FIFO with three frames on the Belady trace produces 9 faults. Compare four frames interactively; stack algorithms such as LRU do not exhibit this anomaly.

Transfer — construct a policy challenge. Select the cyclic scan and compare exact LRU with OPT at two and five frames. Explain why recency performs poorly even though its stack property still holds. Then describe one trace shape where LRU should approach OPT.

Reveal the reasoning targetExpand

For the prediction, FIFO rises from 9 faults with three frames to 10 with four; exact LRU’s stack property rules out such an increase. On the six-page cyclic scan, exact LRU faults 12 times at both two and five frames. OPT faults 10 times at two frames and 7 times at five. With five frames, LRU’s least-recent page is the one needed next after the current insertion, so every reference misses even though adding capacity has not made the count worse. A trace with a compact repeatedly reused set plus rare one-time pages gives recency useful evidence and can make LRU approach OPT.

Locality produces a working-set demand

Programs usually move through phases: a loop touches a compact set of code and data; a later phase touches another set. A working set estimates the pages in active use over a recent window. For window length Δ\Delta references,

W(t,Δ)={ri∣t−Δ<i≤t},w(t,Δ)=∣W(t,Δ)∣.W(t,\Delta)=\{r_i \mid t-\Delta < i \le t\}, \qquad w(t,\Delta)=|W(t,\Delta)|.

The window is a model parameter. Too small a Δ\Delta omits pages whose reuse interval is slightly longer; too large a Δ\Delta mixes phases and overestimates current demand.

Worked trace: a phase boundary

Use references

1 2 1 3 2 1  |  8 9 8 10 9 8

At t=6t=6 with Δ=5\Delta=5 the window is 2 1 3 2 1, so W(6,5)={1,2,3}W(6,5)=\{1,2,3\} and w=3w=3 At t=9t=9 the window is 2 1 8 9 8, so W(9,5)={1,2,8,9}W(9,5)=\{1,2,8,9\} and w=4w=4 the window straddles the transition. At t=12t=12 the window is 9 8 10 9 8, so W(12,5)={8,9,10}W(12,5)=\{8,9,10\} and w=3w=3

Allocating only two frames to either steady phase forces recurrent faults. Allocating four because of the transient boundary may be reasonable if phase changes are frequent, but it is not evidence that every phase needs four.

Application — compare windows. For the same trace at t=12t=12 compute W(t,3)W(t,3) and W(t,8)W(t,8) Which estimate responds faster to a phase change, and which retains stale pages longer?

Reveal the sets and interpretationExpand

The final three references are 10 9 8, so W(12,3)={8,9,10}W(12,3)=\{8,9,10\} The final eight are 2 1 8 9 8 10 9 8, so W(12,8)={1,2,8,9,10}W(12,8)=\{1,2,8,9,10\} The shorter window adapts faster but may miss a page with a reuse distance greater than three; the longer window retains pages 1 and 2 from the old phase and therefore reacts more slowly.

Thrashing is a system state, not a large fault count alone

Suppose mm processes have estimated working-set sizes wi(t,Δ)w_i(t,\Delta) and the allocation domain has FF usable frames. If

D(t,Δ)=∑i=1mwi(t,Δ)>F,D(t,\Delta)=\sum_{i=1}^{m} w_i(t,\Delta) > F,

the domain cannot keep all estimated working sets resident. Repeatedly stealing a needed page from one process to satisfy another can create a positive feedback loop: faults increase, blocked processes release CPUs, runnable processes touch more nonresident pages, and I/O queues grow.

This inequality is a diagnostic model, not a universal threshold. Shared pages may reduce physical demand; inaccurate windows distort DD clean file pages and dirty anonymous pages have different reclaim costs. The key signal is loss of useful progress per unit of fault/reclaim work.

Code
title "Thrashing feedback and intervention points"
rectangle "active working-set demand\nexceeds usable frames" as PRESSURE
rectangle "evict a page still in active use" as EVICT
rectangle "near-future reference faults" as FAULT
rectangle "storage / zero-fill / copy work\nand blocked execution" as COST
rectangle "lower application throughput\nwith continued memory demand" as DROP
rectangle "intervene: reduce admission,\nprotect a working set, or add memory" as CONTROL
PRESSURE --> EVICT
EVICT --> FAULT
FAULT --> COST
COST --> DROP
DROP --> EVICT : pressure persists
PRESSURE --> CONTROL
CONTROL --> PRESSURE : reduce demand below capacity
Thrashing feedback and intervention pointsThrashing feedback and intervention pointsactive working-set demandexceeds usable framesevict a page still in active usenear-future reference faultsstorage / zero-fill / copy workand blocked executionlower application throughputwith continued memory demandintervene: reduce admission,protect a working set, or addmemorypressure persistsreduce demand belowcapacity

Worked diagnosis: multiprogramming overload

Three jobs have stable working-set estimates of 40, 35, and 30 frames. The cgroup has 90 usable frames. Their combined demand is 105. Equal allocation gives 30 frames each: the third job fits, while the first two continually lose ten and five active pages. Giving 40/35/15 protects two jobs but makes the third fault heavily. No replacement ordering creates 15 missing frames.

Admitting only the first two jobs uses 75 frames and leaves 15 for kernel/reclaim variation. Throughput may increase even though fewer jobs run concurrently. The defensible claim is not “suspend the largest process”; it is “reduce simultaneous working-set demand below measured capacity, then compare completed work and tail latency.”

Transfer — distinguish pressure from thrashing. Name two measurements that show productive progress and two that show reclaim cost. Explain why CPU utilization alone is ambiguous.

Reveal an evidence setExpand

Productive measures include completed transactions, retired application work units, or useful bytes processed. Cost measures include major/minor fault rate, reclaim scans, swap/file reads, dirty writeback, and time blocked on faults. CPU utilization can stay high because kernel reclaim and fault handling consume CPU even while application throughput falls; it can also fall because tasks block on storage. A diagnosis needs both progress and cost over the same interval.

CLOCK approximates recency with bounded metadata

Exact LRU needs a total recency update on every reference, which is expensive on multicore systems. CLOCK arranges candidate frames in a circle and maintains an accessed/reference bit A:

  1. inspect the frame under the hand;
  2. if A=1, clear it and advance, granting a second chance;
  3. if A=0 and the page is eligible, select it;
  4. if the page is dirty, either schedule writeback and continue or account for its higher cost;
  5. advance the hand after selection.

RISC-V permits implementation-dependent A/D update schemes within architectural rules; a kernel must follow the architecture’s contract when sampling or clearing those bits. A software-managed bit or fault-assisted scheme can replace hardware updates, but it changes overhead.

Worked trace: second chances and dirty cost

Four frames under the hand contain:

FramePageADirtyEligible
071noyes
120yesyes
290nono, pinned for I/O
340noyes

Starting at frame 0, CLOCK clears page 7’s A and advances. Page 2 is unreferenced but dirty. If the policy minimizes immediate stall, it can schedule page 2 for writeback and continue. Page 9 is ineligible. Page 4 is clean, unreferenced, and eligible, so it is the immediate victim. A later pass may reclaim page 2 after writeback completes.

Calling page 2 “the correct victim” from recency alone ignores the assessed objective. If clean and dirty evictions have different latency, policy needs a cost rule in addition to recency.

Application — mutate one bit. If page 4 has A=1 instead, trace the hand until a victim is found under the rule “schedule dirty writeback but do not block on it; pinned pages are skipped.”

Reveal the traceExpand

Frame 0: clear page 7 and advance. Frame 1: schedule page 2 writeback and advance. Frame 2: skip pinned page 9. Frame 3: clear page 4 and advance. On the next revolution, page 7 now has A=0, is clean and eligible, so page 7 is selected—unless a real reference set its bit again before the hand returned. Omitting that concurrency caveat treats CLOCK as a fixed-reference batch algorithm.

Production reclaim adds allocation and page classes

Real kernels cannot place every page in one undifferentiated queue:

  • anonymous pages may require swap before eviction;
  • clean file-cache pages can often be discarded and reread;
  • dirty file pages require writeback and ordering;
  • shared pages serve several mappings;
  • pinned or unevictable pages are not candidates;
  • memory cgroups and NUMA nodes constrain where reclaim occurs; and
  • refault observations can reveal that recently evicted pages were still hot.

Linux’s documented Multi-Gen LRU groups pages by estimated recency generations and provides working-set/refault-oriented controls. Its existence is evidence that production reclaim is an adaptive subsystem, not evidence that one named policy is universally optimal.

Counterexample: global efficiency can violate isolation

A global policy may evict pages from a latency-sensitive service because a batch job generates more faults. Total faults might fall while the service misses its latency objective. A local or cgroup-bounded policy can preserve allocation isolation at some cost to global utilization. The correct scope follows the resource contract and workload objective.

Section Exercises

Deep Practice

Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.

Exercise 4.4.1: Tracing Belady's Anomaly Under FIFO Replacement

Verificationapplication

Consider the classic reference sequence σ=1,2,3,4,1,2,5,1,2,3,4,5\sigma = 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

  1. Compute the total page fault count under FIFO replacement with 3 physical frames.
  2. Compute the total page fault count under FIFO replacement with 4 physical frames.
  3. State the formal definition of Belady’s anomaly demonstrated by this reference trace.
HintExpand

Step through arrival orders in a FIFO queue. With 3 frames, faults occur 9 times; with 4 frames, faults occur 10 times.

Worked solutionExpand
  1. FIFO with 3 frames: Tracing the queue (oldest to newest):

    • Ref 1: [1], Fault 1.
    • Ref 2: [1, 2], Fault 2.
    • Ref 3: [1, 2, 3], Fault 3.
    • Ref 4: [2, 3, 4], Fault 4 (evicts 1).
    • Ref 1: [3, 4, 1], Fault 5 (evicts 2).
    • Ref 2: [4, 1, 2], Fault 6 (evicts 3).
    • Ref 5: [1, 2, 5], Fault 7 (evicts 4).
    • Ref 1: [1, 2, 5], Hit (1 resident).
    • Ref 2: [1, 2, 5], Hit (2 resident).
    • Ref 3: [2, 5, 3], Fault 8 (evicts 1).
    • Ref 4: [5, 3, 4], Fault 9 (evicts 2).
    • Ref 5: [5, 3, 4], Hit (5 resident). Total faults with 3 frames = 9.
  2. FIFO with 4 frames:

    • Ref 1: [1], Fault 1.
    • Ref 2: [1, 2], Fault 2.
    • Ref 3: [1, 2, 3], Fault 3.
    • Ref 4: [1, 2, 3, 4], Fault 4.
    • Ref 1: [1, 2, 3, 4], Hit.
    • Ref 2: [1, 2, 3, 4], Hit.
    • Ref 5: [2, 3, 4, 5], Fault 5 (evicts 1).
    • Ref 1: [3, 4, 5, 1], Fault 6 (evicts 2).
    • Ref 2: [4, 5, 1, 2], Fault 7 (evicts 3).
    • Ref 3: [5, 1, 2, 3], Fault 8 (evicts 4).
    • Ref 4: [1, 2, 3, 4], Fault 9 (evicts 5).
    • Ref 5: [2, 3, 4, 5], Fault 10 (evicts 1). Total faults with 4 frames = 10.
  3. Belady’s anomaly definition: Belady’s anomaly is the counter-intuitive phenomenon whereby increasing the physical page frame allocation for a given reference string results in a strictly greater number of page faults under a non-stack replacement algorithm.

Exercise 4.4.2: Proving Stack Inclusion and Anomaly Immunity for Exact LRU

Proofsynthesis

Let Rk(t)R_k(t) denote the resident set of pages in physical memory after reference tt using exact Least Recently Used (LRU) with kk frames.

  1. Prove by induction on tt that Rk(t)⊆Rk+1(t)R_k(t) \subseteq R_{k+1}(t) for all t≥1t \ge 1 (the inclusion / stack property).
  2. Deduce that exact LRU can never exhibit Belady’s anomaly for any reference string or capacity.
HintExpand

Express R_k(t) as the set of the k most recently referenced unique pages.

Worked solutionExpand
  1. Proof of the stack inclusion property: At any time tt let S(t)=⟨p1,p2,…,pu⟩S(t) = \langle p_1, p_2, \dots, p_u \rangle be the sequence of unique pages referenced up to time tt ordered strictly by decreasing recency of their most recent reference (so p1=rtp_1 = r_t is the most recently referenced page). By definition of exact LRU:

    • For a memory of capacity kk the resident set consists of the first min⁡(k,u)\min(k, u) elements of S(t)S(t) Rk(t)={p1,p2,…,pmin⁡(k,u)}.R_k(t) = \{p_1, p_2, \dots, p_{\min(k, u)}\}.
    • For a memory of capacity k+1k+1 the resident set consists of the first min⁡(k+1,u)\min(k+1, u) elements of S(t)S(t) Rk+1(t)={p1,p2,…,pmin⁡(k+1,u)}.R_{k+1}(t) = \{p_1, p_2, \dots, p_{\min(k+1, u)}\}.

    Since min⁡(k,u)≤min⁡(k+1,u)\min(k, u) \le \min(k+1, u) it follows immediately from the definition of subset that:

    Rk(t)⊆Rk+1(t)for all t≥1.R_k(t) \subseteq R_{k+1}(t) \quad \text{for all } t \ge 1.
  2. Deduction of anomaly immunity: Suppose page reference rtr_t results in a cache hit under kk frames. Then rt∈Rk(t−1)r_t \in R_k(t-1) By the inclusion property proved above, Rk(t−1)⊆Rk+1(t−1)R_k(t-1) \subseteq R_{k+1}(t-1) which immediately implies rt∈Rk+1(t−1)r_t \in R_{k+1}(t-1) Thus, any reference that is a hit with kk frames is guaranteed to also be a hit with k+1k+1 frames. The total fault count with k+1k+1 frames must therefore be less than or equal to the fault count with kk frames Fk+1≤FkF_{k+1} \le F_k Consequently, exact LRU can never suffer Belady’s anomaly.

Exercise 4.4.3: Simulating CLOCK Hand Traversals with Dirty Page Writeback

Constructionapplication

A circular buffer of 4 frames contains pages P=[7,2,9,4]P = [7, 2, 9, 4] at indices 0,1,2,30, 1, 2, 3 The CLOCK pointer currently points to index 0. The hardware access AA and dirty DD bits are:

  • Index 0 (page 7): A=1,D=0A=1, D=0
  • Index 1 (page 2): A=0,D=1A=0, D=1
  • Index 2 (page 9): A=1,D=1A=1, D=1 (pinned for active DMA).
  • Index 3 (page 4): A=0,D=0A=0, D=0

Trace the CLOCK algorithm to select a victim to satisfy an incoming fault for page 5 under the policy: “advance hand, clear accessed bits, do not evict pinned pages, schedule dirty pages for writeback without blocking, and evict the first clean unreferenced eligible page.”

HintExpand

Check each frame in order from the current hand position.

Worked solutionExpand
  1. Index 0 (page 7): A=1A=1 The algorithm clears the accessed bit A←0A \leftarrow 0 and advances hand to index 1.
  2. Index 1 (page 2): A=0,D=1A=0, D=1 The page has not been recently accessed, but it is dirty. Under the non-blocking policy, the kernel issues an asynchronous disk writeback request for page 2 and advances the hand to index 2 (without immediately stalling on writeback).
  3. Index 2 (page 9): Pinned for active DMA. The algorithm skips pinned frames and advances hand to index 3.
  4. Index 3 (page 4): A=0,D=0A=0, D=0 unpinned. The page has A=0A=0 and is clean D=0D=0 The algorithm selects page 4 as the immediate victim frame. The pointer is left pointing to index 0 (circular advance: (3+1) mod 4=0(3 + 1) \bmod 4 = 0 and page 5 is loaded into frame 3 with A=1,D=0A=1, D=0

Exercise 4.4.4: Computing Denning Working-Set Sizes Across Reference Windows

Constructiontransfer

Let an operating system process reference virtual pages according to the sequence:

σ=⟨1,2,1,3,4,1,2,3,2,4,5,1⟩.\sigma = \langle 1, 2, 1, 3, 4, 1, 2, 3, 2, 4, 5, 1 \rangle.
  1. Using Denning’s working-set model with window size Δ=4\Delta = 4 compute the working set W(t,4)W(t, 4) and its cardinality ∣W(t,4)∣|W(t, 4)| for time steps t=4,8,12t = 4, 8, 12
  2. If the operating system allocates only 2 physical frames to this process during the interval t∈[8,12]t \in [8, 12] explain why thrashing is inevitable.
HintExpand

The working set W(t, Delta) is the set of distinct pages referenced in the interval [t - Delta + 1, t].

Worked solutionExpand
  1. Working-set evaluations:
    • At t=4t = 4 the window is the last 4 references (indices 1 to 4): {1,2,1,3}\{1, 2, 1, 3\} The distinct pages are W(4,4)={1,2,3}W(4, 4) = \{1, 2, 3\} so ∣W(4,4)∣=3|W(4, 4)| = 3
    • At t=8t = 8 the window is references at indices 5 to 8: {4,1,2,3}\{4, 1, 2, 3\} The distinct pages are W(8,4)={1,2,3,4}W(8, 4) = \{1, 2, 3, 4\} so ∣W(8,4)∣=4|W(8, 4)| = 4
    • At t=12t = 12 the window is references at indices 9 to 12: {2,4,5,1}\{2, 4, 5, 1\} The distinct pages are W(12,4)={1,2,4,5}W(12, 4) = \{1, 2, 4, 5\} so ∣W(12,4)∣=4|W(12, 4)| = 4
  2. Thrashing onset: During t∈[8,12]t \in [8, 12] the process actively demands 4 distinct pages ∣W(t,4)∣=4|W(t, 4)| = 4 to execute its phase loop. If the OS allocates only 2 frames M=2<4M = 2 < 4 every memory access requiring one of the unrepresented working-set pages triggers a page fault. Every fault necessarily evicts a page that will be demanded again within the next 1–3 instructions. The process spends virtually 100% of its execution time waiting on storage I/O, which is the exact definition of thrashing.

Exercise 4.4.5: Diagnosing System-Wide Thrashing and Sizing Allocation Domains

Descriptionsynthesis

Explain why aggregate working-set overload ∑i=1N∣Wi(t,Δ)∣>Mtotal\sum_{i=1}^N |W_i(t, \Delta)| > M_{\text{total}} causes a sudden cliff in system throughput rather than a gradual linear degradation. Describe how memory cgroups and process suspension (swapping) restore equilibrium.

HintExpand

Consider the feedback loop between page-fault handling latency, queue buildup, and CPU utilization collapse.

Worked solutionExpand
  • The non-linear thrashing cliff: When ∑∣Wi∣≤Mtotal\sum |W_i| \le M_{\text{total}} page fault rates are low, and the swap/storage device queue is largely idle. When aggregate working-set demand crosses the physical threshold MtotalM_{\text{total}} processes continuously evict each other’s active working-set pages. Each evicted page triggers a synchronous disk read latency 50 μs50\ \mu\text{s} to 10 ms10\text{ ms} Because threads block waiting on I/O, the operating system scheduler attempts to compensate by dispatching other runnable threads, which immediately fault as well. Storage request queues explode, I/O latency compounds, and CPU utilization collapses to near zero. Throughput drops precipitously from near 100% to near 0% across a tiny increase in working-set demand.
  • Remediation mechanisms:
    1. Admission control / suspension: The kernel suspends one or more processes entirely (moving their active threads to swapped state) until ∑active∣Wi∣≤Mtotal\sum_{\text{active}} |W_i| \le M_{\text{total}} The remaining processes run to completion at full speed without thrashing, after which suspended tasks are resumed.
    2. Memory cgroups (resource isolation): By placing processes into bounded cgroups with memory.max and memory.high thresholds, the kernel isolates memory pressure. A runaway batch job thrashes only within its own private quota without evicting pages belonging to critical interactive or production services.

References & Further Reading