Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 22, Arpaci-Dusseau & Arpaci-Dusseau

Beyond Physical Memory: Policies

When free memory is plentiful, a page fault is easy: take a frame from the free list. Under memory pressure, the OS must evict pages to make room. Which page? That is the replacement policy.

Crux: how decide which page(s) to evict? What principles? What corner-case tweaks?

Mechanisms first

Assumes swap, present bit, and page faults (Ch. 21). Main memory is a cache for pages that may live on disk.

Cache management and AMAT

Physical memory caches a subset of all virtual pages. Goal: minimize misses (disk fetches) / maximize hits.

Average memory access time:

AMAT = TM + (P_miss · TD)

You always pay memory; on a miss you also pay disk. Example: TM = 100 ns, TD = 10 ms, P_miss = 0.1 → AMAT ≈ 1 ms. At P_miss = 0.001, AMAT ≈ 10.1 µs (~100× faster). Tiny miss rates dominate when disk is slow.

Optimal (Belady / MIN)

Evict the page that will be used furthest in the future [B66]. Fewest misses possible — but needs the future, so not deployable. Still invaluable as a comparison point.

Trace 0,1,2,0,1,3,0,3,1,2,1, cache size 3: first three accesses are compulsory (cold) misses; on page 3, OPT evicts 2; later miss on 2 may evict 3. Hit rate 6/11 ≈ 54.5% (higher if you ignore compulsory misses).

Compare against optimal

An 80% hit rate is meaningless alone; “OPT is 82%” shows you are close — and when to stop optimizing [AD03].

Three C’s of misses

Compulsory (cold), capacity (cache too small), conflict (set-associativity limits). OS page caches are fully associative — no conflict misses in that sense [H87].

FIFO

Pages enter a queue; replace the first-in. Simple. On the same trace, FIFO does worse (~36% hits): it may evict a hot page just because it arrived earliest.

Belady’s anomaly

For FIFO, a larger cache can hurt hit rate on some streams (e.g. 1,2,3,4,1,2,5,1,2,3,4,5 at size 3 vs 4) [BNS69]. LRU has the stack property [M+70]: size N+1 contains size N, so hit rate never worsens when the cache grows.

Random

Pick a random victim. Easy; quality depends on luck. Over many seeds it sometimes matches OPT and sometimes does poorly.

Using history: LRU (and LFU)

Locality [D70]: recent (or frequent) pages are likely needed again.

• LRU — replace least-recently-used
• LFU — replace least-frequently-used

On the cooked chapter trace, LRU matches OPT. Opposites MRU/MFU usually ignore locality and do poorly.

Spatial locality: nearby pages. Temporal locality: re-use of recent pages. Not a law — some workloads are random.

Workloads (intuition)

Workload	Behavior
No locality	LRU ≈ FIFO ≈ RAND; hit rate ≈ cache / working-set size
80–20	Hot pages; LRU beats FIFO/RAND; OPT still better
Looping sequential	Scan of N pages with cache N−1 → LRU/FIFO ≈ 0%; RAND less pathological

Implementing history (and approximating LRU)

Perfect LRU updates a structure on every memory reference — expensive. Hardware can stamp a time field per page, but scanning a million pages to find the oldest is too slow.

Crux: approximate LRU.

Use (reference) bit per page: hardware sets to 1 on access; OS clears. Clock [C69]: circular list + hand. If use=1, clear and advance; if use=0, evict. Approximates LRU without a full scan.

Dirty (modified) bit: prefer evicting clean pages (no writeback) over dirty ones — often folded into Clock variants.

Quiz

Rank the sequence

1 / 1

Order the steps the Clock algorithm takes when scanning for a victim page (top = first).

OrderDrag the handle to rearrange — top should be first.

1. ⋮⋮1Advance the hand to the next page
2. ⋮⋮2Evict the page under the clock hand
3. ⋮⋮3Clear the use bit to 0
4. ⋮⋮4Check the use bit of the page under the hand

Drag items into the correct order (or use ↑↓), then check.

Other VM policies

• Page selection: usually demand paging; optional prefetch (e.g. bring P+1 with P) when the guess is good
• Writes: cluster/group dirty pages for efficient disk I/O

Thrashing

When the aggregate working set exceeds RAM, the system pages constantly [D70]. Responses: admission control (run fewer jobs well), or drastic measures (e.g. Linux OOM killer). Often the practical fix: buy more memory — disk is so slow that frequent paging is untenable.

Modern policies add tweaks (e.g. scan resistance / ARC [MM03]) to avoid LRU’s looping-scan failure mode.

Interactive

Try: Optimal · FIFO · LRU on the chapter trace · Clock use-bit walk.

Check your understanding

Quiz

Page replacement policies

1 / 6

AMAT = TM + Pmiss · TD. If disk is ~100,000× slower than memory, a small miss rate…

Pick an answer to see if you are right.

Coding challenges

Homework lab: paging-policy.py

Use the OSTEP paging-policy homework (paging-policy.py).

Lab

Homework: paging-policy.py

0/4 started

Loading lab…

Summary

Policy	Idea	Watch-out
OPT	Furthest future use	Needs oracle
FIFO	Oldest arrival	Can evict hot pages; Belady anomaly
RAND	Random victim	Variable; sometimes escapes LRU traps
LRU / LFU	Recency / frequency	Costly if exact; looping scans hurt LRU
Clock	Use bit + hand	Practical LRU approx; prefer clean pages

Previous: Beyond Physical Memory — Mechanisms

Next: Complete Virtual Memory Systems — VAX/VMS and Linux as full designs.

Further Reading

• Remzi & Andrea Arpaci-Dusseau — Operating Systems: Three Easy Pieces Ch. 22
• OSTEP vm-beyondphys-policy PDF
• OSTEP beyond-physical homework
• Belady [B66]; Corbató Clock [C69]; Denning survey [D70]; ARC [MM03]