CEUC301 · Unit 6 of 9
Virtual Memory &
Page Replacement Design
Chapter 5 ended on an open problem: paging doubles every memory access, since the CPU has to look up the page table in memory before it can look up the data itself. This chapter opens with the hardware fix, then asks the harder question paging raises the moment physical memory fills up — when something has to go, what decides what it is, and what happens when the whole system starts making the wrong choice constantly.
The spine. WriteWell renders a document by touching a handful of pages over and over as the user scrolls and edits: the title block, an embedded image, the footer, the table of contents. Which of those pages physical memory actually holds at any instant — and which one gets evicted the moment a new one is needed — is this entire chapter, traced through one small, concrete sequence of page touches from beginning to end.
TLB Design & Performance
Paging doubled every memory access. Can hardware buy that back?
Chapter 5's page table lookup happens in memory — meaning every single memory access a process makes actually costs two: one to read the page table entry, one to read the actual data. Doing this for literally every access would make paging's memory savings not worth the speed it costs.
The TLB: a cache for translations, not data
The Translation Lookaside Buffer (TLB) is a small, extremely fast piece of hardware that caches recent (page number → frame number) translations, sitting right next to the CPU. On a TLB hit, the frame number is available immediately, no memory access needed for the translation at all — only the one remaining access for the actual data. On a TLB miss, the CPU falls back to Chapter 5's full page-table walk in memory, then accesses the data — the original two-memory-access cost, plus the (small) time spent checking the TLB in the first place.
Worked example: what the TLB actually buys WriteWell
TLB access takes 20ns, main memory access takes 100ns, and WriteWell's working set gives a TLB hit ratio of 90%.
Figure 1 · EMAT as the hit ratio changes
Same TLB and memory speeds, varying locality
drag the sliderContext switches and the TLB: Chapter 1's callback, finished
Chapter 1's Section 1.4 mentioned, briefly, that Process-Context Identifiers (PCID) let TLB entries survive a process switch by tagging each entry with the address space it belongs to. Here's why that matters as much as it does: without tagging, a naive TLB has no way to tell "this cached translation belongs to the process that just got switched out" from "this translation is still valid" — so the safe, simple answer is to flush the entire TLB on every process switch. Every one of those flushed entries has to be re-learned the slow way, at the full miss cost, right when the newly-scheduled process starts running — a direct, compounding tax on top of the context-switch cost already measured in Chapter 1.
Pitfall
A TLB miss is two memory accesses, not one — the page table read and the
data read. Forgetting the page-table access and writing the miss path as just t + m
is the single most common EMAT calculation error, and it silently halves the miss penalty in the final
answer.
Practice 6.1
- TLB access takes 10ns, memory access takes 80ns, hit ratio is 95%. Compute EMAT.
Show solution
EMAT = 0.95×(10+80) + 0.05×(10+80+80) = 0.95×90 + 0.05×170 = 85.5 + 8.5 = 94ns.
- Variation. Using the same numbers, what hit ratio would be needed to bring EMAT down to
exactly 91ns?
Show solution
91 = p×90 + (1−p)×170 = 170 − 80p, so 80p = 79, p = 0.9875 — a 98.75% hit ratio.
- Interpretation. Two systems report the same EMAT. System A has a fast TLB and a low hit
ratio; System B has a slower TLB and a high hit ratio. Is this possible?
Show solution
Yes — EMAT is a single number produced by trading off several inputs at once (t, p, and implicitly m), so different combinations of TLB speed and hit ratio can land on the same final average. The same EMAT number does not mean the same underlying hardware or workload.
- Synthesis. Explain why a process with poor locality of reference (touching many
different pages, rarely repeating any) hurts EMAT even if the TLB hardware itself is unchanged.
Show solution
The TLB can only produce a hit if a translation it already cached gets reused; a process that keeps touching new pages it hasn't recently accessed drives the hit ratio down regardless of how fast or well-designed the TLB hardware is. EMAT depends on the workload's behaviour (Chapter 2's locality ideas, reused here) at least as much as on the hardware itself.
Page Replacement Algorithms
Memory is full. Something has to go. What decides what?
WriteWell can only keep 3 pages in physical memory at once for this example — a deliberately small number, to make every eviction decision visible. Every algorithm below answers the exact same question — which page currently in memory gets evicted to make room for the one just requested — with a different rule for what "the right one" means.
| Algorithm | Rule | Cost to implement |
|---|---|---|
| FIFO | Evict whichever page has been in memory the longest, regardless of how often it's used. | Trivial — just a queue. |
| LRU | Evict whichever page hasn't been touched for the longest time. | Needs exact recency tracking on every access — expensive in full generality; real systems use approximations (the clock/second-chance algorithm). |
| Optimal | Evict whichever page won't be needed again for the longest time in the future. | Requires knowing the future. Not implementable — exists purely as a theoretical best-case benchmark to measure real algorithms against. |
Figure 2 · one reference sequence, three algorithms, side by side
3 frames, 12 page references
step 1 of 12Final tally after all 12 references: FIFO 10 faults, LRU 9 faults, Optimal 7 faults — exactly the ranking the theory predicts, though as the next depth box shows, that ranking isn't a law.
Depth — LRU doesn't always beat FIFO on every string
Averaged over realistic workloads, LRU reliably outperforms FIFO — but "reliably, on average" is not "always." A different 12-reference sequence, verified the same way as Figure 2, produces FIFO 9 faults against LRU 10: title, img1, foot, toc, title, body, foot, title, body, img1, toc, foot. LRU's advantage is a strong empirical tendency grounded in locality of reference, not a per-string guarantee.
Belady's anomaly: more memory, more faults
It seems obvious that more physical memory should never make paging worse. FIFO breaks that intuition. On the reference string title, body, toc, img1, title, body, foot, title, body, toc, img1, foot:
| Frames | FIFO page faults |
|---|---|
| 3 | 9 |
| 4 | 10 |
Giving FIFO a fourth frame makes it fault more, not less. This is Bélády's
anomaly (László Bélády, 1969): FIFO's eviction choice depends only on arrival order, not on how the
reference pattern actually unfolds, so the specific set of pages held in a 3-frame system is not guaranteed to
be a subset of what a 4-frame system holds at the same instant — the two systems can diverge and end up
faulting on different things. LRU and Optimal are both stack algorithms (the set of
pages held with n frames is always a subset of what's held with n+1
frames), which is precisely what makes them immune to this anomaly — provably, not just empirically.
Pitfall
"Add more RAM" is not a universally safe fix for a paging performance problem if the system is using FIFO — Bélády's anomaly is a real, constructible counterexample, not a theoretical curiosity. It's also specifically a FIFO (and FIFO-like) problem: stating that Bélády's anomaly can happen under LRU is a common and incorrect exam answer.
Practice 6.2
- In Figure 2, at the reference to
meta(the tenth reference), why do FIFO and LRU choose different victims even though both currently hold the same three pages?Show solution
FIFO evicts whichever page has been resident longest, regardless of recent use; LRU evicts whichever page was least recently referenced. The two rules only coincide when arrival order and access-recency order happen to match, which they don't here — exactly why the two algorithms' frame contents start to diverge from this point onward in the trace.
- Variation. If Optimal's algorithm is run on a reference string where every page is
referenced exactly once, what does it degrade to?
Show solution
Any replacement rule at all — with no repeats, no page already in memory will ever be referenced again, so there is no "wrong" eviction choice to avoid, and Optimal, FIFO, and LRU all necessarily produce the same number of faults (one per reference).
- Interpretation. A report claims "we switched from FIFO to LRU and page faults went up."
Given this section, is that suspicious?
Show solution
Not necessarily suspicious on its own — the depth box above gives a verified example where LRU faults more than FIFO on a specific string. It would be worth checking the actual workload's reference pattern before assuming a bug, though it's also worth checking the LRU implementation, since exact LRU is expensive and many "LRU" implementations are really approximations that can behave differently from the ideal.
- Synthesis. Explain why Optimal's 7 faults in Figure 2 is a meaningful number to report
even though Optimal can never actually run in a real system.
Show solution
Optimal defines the best any algorithm could possibly do on that exact reference string, so it's the natural yardstick: FIFO's 10 and LRU's 9 are both meaningfully described as "3 more" and "2 more" faults than the theoretical floor, which says more than the raw counts alone. This is the same role Chapter 2's SRTF played as a provably-optimal-but-idealised benchmark for comparing real scheduling algorithms.
Thrashing & the Working Set Model
Adding another process should mean more gets done. Sometimes it means nothing does.
Run more processes and, up to a point, CPU utilisation climbs — more processes means more chances that someone is ready to run whenever another blocks on I/O (Chapter 2). Past that point, something breaks entirely.
Thrashing: spending more time paging than computing
Thrashing is what happens when the combined memory demands of all running processes exceed physical memory badly enough that the system spends most of its time servicing page faults — evicting a page one process needs, only to immediately fault it back in for another — instead of running anyone's actual code. Adding more processes at this point makes it worse, not better: each new process's memory demands shrink everyone else's already-insufficient share, driving the fault rate up further still.
Figure 3 · the curve every OS textbook draws, verified in shape
CPU utilization vs. degree of multiprogramming
illustrative curveThe working set model: measuring "what a process actually needs, right now"
Peter Denning's working set model (1968) gives a precise, computable definition of a
process's current memory needs: WS(t, Δ), the set of distinct pages referenced in
the most recent Δ references before time t. A process
thrashes specifically when the frames it's actually been given are smaller than its own working set —
not some fixed, universal number, but whatever it's been touching lately.
Worked example: WriteWell's working set, three points in time
Using Figure 2's exact reference sequence and a window of Δ=4:
| t | Last 4 references | |WS(t,4)| |
|---|---|---|
| 3 | title, img1, foot, toc | 4 |
| 7 | img1, foot, body, title | 4 |
| 11 | foot, meta, body, title | 4 |
Every window here happens to touch 4 distinct pages — and Figure 2 only gave this process 3 frames. That gap, working set size exceeding frame allocation, is thrashing's precise, checkable precondition, not just a vague "too many processes" intuition.
Using the model: two practical policies
Working-set-based admission control: before starting a new process, add its estimated working set size to the sum of everyone else's; refuse to start it if the total would exceed physical memory — preventing thrashing before it begins, at the cost of sometimes refusing to run something that would have fit most of the time. Page-fault-frequency (PFF) monitoring: watch each process's actual fault rate directly; give a process more frames if its rate is too high, reclaim frames if its rate is unusually low — reactive rather than predictive, and cheaper to implement than tracking exact working sets.
Pitfall
Thrashing is a property of the relationship between working set size and allocated frames, not of process count by itself. Ten processes with tiny working sets can coexist happily in memory that would thrash under two processes with enormous ones. "Too many processes" is the visible symptom in Figure 3, not the actual cause.
Practice 6.3
- A process is given 5 frames, and its working set size stays at 3 for its entire run. Is it at risk of
thrashing?
Show solution
No — its working set (3) fits comfortably within its allocation (5). Thrashing risk specifically requires working set size to exceed the frames actually given, which isn't the case here regardless of how many other processes are also running.
- Variation. If Δ were increased from 4 to 8 in the worked example, would the
computed working set sizes likely increase, decrease, or stay the same?
Show solution
Likely increase (or at worst stay the same) — a wider window captures more distinct pages referenced over a longer history, so |WS(t,Δ)| is non-decreasing in Δ. Choosing Δ itself is a real design trade-off: too small underestimates genuine current needs; too large overestimates them by counting pages the process has since moved on from.
- Interpretation. A system's CPU utilisation graph looks exactly like Figure 3, currently
sitting just past the peak. What's the most directly effective fix: add more processes, or reduce the
number running?
Show solution
Reduce the number running (or give the existing ones more memory). Figure 3's falling side means additional processes make the fault rate — and utilisation — worse, not better; the system needs less contention for physical memory, which is the opposite of what adding more processes provides.
- Synthesis. Explain why page-fault-frequency monitoring can respond to thrashing that's
already starting, while working-set-based admission control can only prevent thrashing that hasn't
happened yet.
Show solution
Admission control makes its one decision at process start, based on an estimated working set size, and has no further say once the process is running — if the process's actual behaviour changes later, admission control can't react. PFF monitoring watches the live fault rate continuously and adjusts frame allocations in response, making it the only one of the two capable of responding to a working set that grows mid-execution, exactly the scenario in Figure 3's already-collapsing right-hand side.
Cheat Sheet & Self-Test
Everything above, compressed to what you'd want on the way into an exam.
6.1 TLB
EMAT = p×(t+m) + (1−p)×(t+m+m). Miss path is TWO memory accesses, not one.
PCID/ASID tag TLB entries by address space, avoiding a full flush on every process switch (Ch1 callback).
6.2 Replacement algorithms
FIFO: oldest out. LRU: least-recently-used out (expensive exact; approximated in practice). Optimal: farthest-future-use out — unimplementable benchmark.
LRU/Optimal are stack algorithms — immune to Bélády's anomaly. FIFO is not: more frames can mean more faults.
6.3 Thrashing & working set
Thrashing: more time paging than computing. More processes past the peak makes it worse.
WS(t,Δ) = distinct pages touched in the last Δ references. Thrashing risk = WS size > frames allocated.
Fixes: working-set admission control (predictive) or page-fault-frequency monitoring (reactive).
Mixed self-test
Deliberately not grouped by section — your exam won't be either.
- TLB access is 15ns, memory access is 90ns, hit ratio is 85%. Compute EMAT.
Show solution
EMAT = 0.85×(15+90) + 0.15×(15+90+90) = 0.85×105 + 0.15×195 = 89.25 + 29.25 = 118.5ns. (6.1)
- Why is Bélády's anomaly specifically associated with FIFO and not with LRU or Optimal?
Show solution
LRU and Optimal are stack algorithms: the set of pages held with n frames is always a subset of what's held with n+1 frames, which makes more faults with more frames provably impossible. FIFO's eviction choice depends only on arrival order, not on this subset property, so no such guarantee holds. (6.2)
- A process's working set size is consistently 6, but it's only ever been allocated 4 frames. What should
be expected?
Show solution
Thrashing risk for this process specifically — its actual current needs (6) exceed its allocation (4), the precise precondition Section 6.3 defines, regardless of how many other processes are running. (6.3)
- Does enabling PCID/ASID tagging eliminate TLB misses entirely?
Show solution
No — it only avoids flushing the entire TLB on every process switch by letting entries from different address spaces coexist. Ordinary TLB misses from poor locality of reference, or from a process referencing a page for the first time, still happen exactly as before. (6.1, callback to Ch1)
- A system adds more physical memory, but its FIFO-based paging performance gets worse, not better. Is
this a bug?
Show solution
Not necessarily — this is exactly Bélády's anomaly, constructible and verified in Section 6.2, not a theoretical curiosity. It's a real, if uncommon, argument for preferring a stack-based algorithm (LRU or an approximation of it) if this behaviour is a genuine operational risk. (6.2)
- What's the key difference between working-set-based admission control and page-fault-frequency
monitoring?
Show solution
Admission control is predictive and acts once, at process start, based on an estimated working set; PFF monitoring is reactive and continuous, watching the actual fault rate and adjusting frame allocations while the process runs. (6.3)
- On a specific 12-reference string, LRU produces more page faults than FIFO. Does this contradict LRU's
reputation as generally better than FIFO?
Show solution
No — "generally better" describes an average tendency across realistic workloads, not a per-string guarantee. Section 6.2 verified exactly this kind of counter-example directly; LRU's advantage comes from typical locality of reference, not from a proof that it dominates FIFO on every possible input. (6.2)
- Why does a TLB need to be small and extremely fast, rather than just being a bigger, slightly slower
cache that could hold more translations?
Show solution
The TLB sits on the critical path of every single memory access a process makes; any speed sacrificed for size directly inflates the hit-path term (t) in the EMAT formula, for every access, not just the ones that would have missed anyway. A bigger but slower TLB could easily raise EMAT even while improving the hit ratio, since Section 6.1's formula charges the TLB's own access time on every single request, hit or miss. (6.1)
Further reading
- Stallings, Operating Systems: Internals and Design Principles, 9th ed., Ch. 8. This course's primary text; closest match to this chapter's structure across all three sections.
- Silberschatz, Galvin & Gagne, Operating System Concepts, 10th ed., Ch. 10. The standard reference treatment of TLBs, page replacement, and thrashing.
- Bélády, L.A., "A Study of Replacement Algorithms for a Virtual-Storage Computer," IBM Systems Journal, 1966. The original paper behind Section 6.2's Optimal algorithm and the stack-algorithm property.
- Denning, P.J., "The Working Set Model for Program Behavior," CACM, 1968. The original paper behind Section 6.3's working set model, still the clearest primary source.
Before this chapter — Chapter 1 (the PCID/context-switch material Section 6.1 completed) and Chapter 5 (the page-table-in-memory cost this entire chapter exists to manage, first in hardware via the TLB, then in policy via replacement and admission control).
Where this goes next — Unit 7, File System Design and Performance: how the OS organises what's actually sitting on disk once it's not in memory at all — file system abstractions, journaling versus log-structured designs, free space management, and the security considerations that come with letting a file outlive the process that wrote it.