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 record virtual page numbers in access order. A resident set is the set of pages occupying the assessed frames after reference A reference is a hit if and a fault otherwise. On a fault with no free frame, the policy selects a victim
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
| Policy | Victim rule | Knowledge required | Principal boundary |
|---|---|---|---|
| FIFO | page loaded earliest | arrival order | can evict a frequently used old page |
| exact LRU | page referenced least recently | total recency order | metadata/coordination cost is high |
| OPT/MIN | page whose next use is farthest in the future | future trace | offline lower bound, not deployable online |
| CLOCK/second chance | first candidate whose reference bit is clear | approximate recent-use bit | scan 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 answerExpandCollapse
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.
| Ref | Frames/queue after access | Result | Evicted | Faults |
|---|---|---|---|---|
| 1 | 1 | fault | — | 1 |
| 2 | 1 2 | fault | — | 2 |
| 3 | 1 2 3 | fault | — | 3 |
| 4 | 2 3 4 | fault | 1 | 4 |
| 1 | 3 4 1 | fault | 2 | 5 |
| 2 | 4 1 2 | fault | 3 | 6 |
| 5 | 1 2 5 | fault | 4 | 7 |
| 1 | 1 2 5 | hit | — | 7 |
| 2 | 1 2 5 | hit | — | 7 |
| 3 | 2 5 3 | fault | 1 | 8 |
| 4 | 5 3 4 | fault | 2 | 9 |
| 5 | 5 3 4 | hit | — | 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 frames is a subset of the resident set with frames.
Exact LRU has this property. Maintain all referenced pages in one recency order. The -frame resident set is the first pages of that order; the -frame set is the first Therefore every hit with frames is also a hit with 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
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.
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.
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.
Fault: evicted page 5
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.
Hit: frame contents unchanged
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 targetExpandCollapse
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 references,
The window is a model parameter. Too small a omits pages whose reuse interval is slightly longer; too large a 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 with the window is 2 1 3 2 1, so and At the window is 2 1 8 9 8, so and the window straddles the transition. At the window is 9 8 10 9 8, so and
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 compute and Which estimate responds faster to a phase change, and which retains stale pages longer?
Reveal the sets and interpretationExpandCollapse
The final three references are 10 9 8, so The final eight are 2 1 8 9 8 10 9 8, so 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 processes have estimated working-set sizes and the allocation domain has usable frames. If
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 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.
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 setExpandCollapse
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:
- inspect the frame under the hand;
- if
A=1, clear it and advance, granting a second chance; - if
A=0and the page is eligible, select it; - if the page is dirty, either schedule writeback and continue or account for its higher cost;
- 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:
| Frame | Page | A | Dirty | Eligible |
|---|---|---|---|---|
| 0 | 7 | 1 | no | yes |
| 1 | 2 | 0 | yes | yes |
| 2 | 9 | 0 | no | no, pinned for I/O |
| 3 | 4 | 0 | no | yes |
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 traceExpandCollapse
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.
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
Consider the classic reference sequence
- Compute the total page fault count under FIFO replacement with 3 physical frames.
- Compute the total page fault count under FIFO replacement with 4 physical frames.
- State the formal definition of Belady’s anomaly demonstrated by this reference trace.
HintExpandCollapse
Step through arrival orders in a FIFO queue. With 3 frames, faults occur 9 times; with 4 frames, faults occur 10 times.
Worked solutionExpandCollapse
-
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.
-
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.
-
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
Let denote the resident set of pages in physical memory after reference using exact Least Recently Used (LRU) with frames.
- Prove by induction on that for all (the inclusion / stack property).
- Deduce that exact LRU can never exhibit Belady’s anomaly for any reference string or capacity.
HintExpandCollapse
Express R_k(t) as the set of the k most recently referenced unique pages.
Worked solutionExpandCollapse
-
Proof of the stack inclusion property: At any time let be the sequence of unique pages referenced up to time ordered strictly by decreasing recency of their most recent reference (so is the most recently referenced page). By definition of exact LRU:
- For a memory of capacity the resident set consists of the first elements of
- For a memory of capacity the resident set consists of the first elements of
Since it follows immediately from the definition of subset that:
-
Deduction of anomaly immunity: Suppose page reference results in a cache hit under frames. Then By the inclusion property proved above, which immediately implies Thus, any reference that is a hit with frames is guaranteed to also be a hit with frames. The total fault count with frames must therefore be less than or equal to the fault count with frames Consequently, exact LRU can never suffer Belady’s anomaly.
Exercise 4.4.3: Simulating CLOCK Hand Traversals with Dirty Page Writeback
A circular buffer of 4 frames contains pages at indices The CLOCK pointer currently points to index 0. The hardware access and dirty bits are:
- Index 0 (page 7):
- Index 1 (page 2):
- Index 2 (page 9): (pinned for active DMA).
- Index 3 (page 4):
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.”
HintExpandCollapse
Check each frame in order from the current hand position.
Worked solutionExpandCollapse
- Index 0 (page 7): The algorithm clears the accessed bit and advances hand to index 1.
- Index 1 (page 2): 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).
- Index 2 (page 9): Pinned for active DMA. The algorithm skips pinned frames and advances hand to index 3.
- Index 3 (page 4): unpinned. The page has and is clean The algorithm selects page 4 as the immediate victim frame. The pointer is left pointing to index 0 (circular advance: and page 5 is loaded into frame 3 with
Exercise 4.4.4: Computing Denning Working-Set Sizes Across Reference Windows
Let an operating system process reference virtual pages according to the sequence:
- Using Denning’s working-set model with window size compute the working set and its cardinality for time steps
- If the operating system allocates only 2 physical frames to this process during the interval explain why thrashing is inevitable.
HintExpandCollapse
The working set W(t, Delta) is the set of distinct pages referenced in the interval [t - Delta + 1, t].
Worked solutionExpandCollapse
- Working-set evaluations:
- At the window is the last 4 references (indices 1 to 4): The distinct pages are so
- At the window is references at indices 5 to 8: The distinct pages are so
- At the window is references at indices 9 to 12: The distinct pages are so
- Thrashing onset: During the process actively demands 4 distinct pages to execute its phase loop. If the OS allocates only 2 frames 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
Explain why aggregate working-set overload causes a sudden cliff in system throughput rather than a gradual linear degradation. Describe how memory cgroups and process suspension (swapping) restore equilibrium.
HintExpandCollapse
Consider the feedback loop between page-fault handling latency, queue buildup, and CPU utilization collapse.
Worked solutionExpandCollapse
- The non-linear thrashing cliff: When page fault rates are low, and the swap/storage device queue is largely idle. When aggregate working-set demand crosses the physical threshold processes continuously evict each other’s active working-set pages. Each evicted page triggers a synchronous disk read latency to 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:
- Admission control / suspension: The kernel suspends one or more processes entirely (moving their active threads to swapped state) until The remaining processes run to completion at full speed without thrashing, after which suspended tasks are resumed.
- Memory cgroups (resource isolation): By placing processes into bounded cgroups with
memory.maxandmemory.highthresholds, 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
- L. A. Bélády, R. A. Nelson, and G. S. Shedler, “An anomaly in space-time characteristics of certain programs running in a paging machine” (1969)
- Peter J. Denning, “The Working Set Model for Program Behavior” (1968)
- Peter J. Denning, working-set primary-publication index
- Linux kernel documentation: Multi-Gen LRU
- RISC-V Privileged Architecture: accessed and dirty PTE state