Page-replacement benchmarks

Measuring eviction-policy trade-offs in a demand-paged Pintos kernel — part of unix-kernel-subsystem.

The kernel pages on demand and chooses its eviction policy at boot (-evict=clock|fifo|random). These numbers are the kernel's own KSTAT counters over 10 seeds per configuration, collected by scripts/bench.sh and summarised by analyze.py. Design rationale is in ADR-003.

2.9×fewer evictions under clock than FIFO on page-parallel (4 MB)

3pages swapped back in under clock vs 320 under FIFO — clock keeps the hot set

∞FIFO thrashes page-merge-par past the time budget; clock finishes in ~3 s

Watch it run

A replay of the kernel's real output: a fork bomb contained, a CPU hog killed at its budget, a well-behaved process still finishing on time beside both, and demand-paged VM swapping a working set larger than RAM.

Recorded kernel output, replayed. Click to pause/resume.

Policy comparison at a fixed memory budget (4 MB)

At 4 MB every workload pages heavily, so the policy alone decides how much I/O the system does for the same program. Fewer swap-ins is better — a swap-in is a page the policy evicted and the program immediately needed back.

evictions and swap-ins by policy — Eviction work by policy. Clock (blue, highlighted) uses the accessed bit to keep pages still in use; FIFO and random pay far more swap traffic.

workload	policy	ok	evictions	swap-ins	swap-outs	page-faults	ticks
page-merge-par	`clock`	10/10	334	179	331	732	283±8
page-merge-par	`fifo`	0/5	—	—	—	—	—
page-merge-par	`random`	5/5	301±15	147±15	299±15	699±15	286±13
page-parallel	`clock`	10/10	164±1	3	159±1	1050	118±5
page-parallel	`fifo`	5/5	480	320	479	1365	179±9
page-parallel	`random`	5/5	470±100	284±93	462±98	1333±95	175±23

Paging curve: clock vs physical RAM

Holding the policy at clock and growing RAM shows the working set starting to fit — eviction collapses to zero once it is resident.

evictions vs physical RAM — Evictions fall to zero by 6 MB as the working set becomes resident.

workload	RAM (MB)	ok	evictions	swap-ins	page-faults
page-merge-par	4	10/10	334	179	732
page-merge-par	5	5/5	30	3	556
page-merge-par	6	5/5	0	0	550
page-parallel	4	10/10	164±1	3	1050
page-parallel	5	5/5	35±1	3	1050
page-parallel	6	5/5	0	0	1044

Running this curve originally surfaced two concurrency bugs in the paging code — a free-before-read race in swap_in and a load-during-eviction window — that only the benchmark's parallel stress triggered. Both are fixed; every memory size now passes. Write-up: BUGS-FOUND.md.

Theory: simulation against Belady's optimal

A trace-driven simulator (simulate.py) runs the same reference strings under FIFO, LRU, CLOCK and OPT (Belady's optimal, the unbeatable lower bound). It reproduces Belady's anomaly — FIFO faulting more with more frames — which LRU and OPT, as stack algorithms, never do.

page faults vs frames per policy — OPT is the floor; the gap above it is the cost of not knowing the future. Full tables in SIMULATION.md.

Generated by analysis/build_site.py from measured data. Source: sumitparmar19/unix-kernel-subsystem · raw benchmark write-up. Kernel work after the course submission was AI-assisted (Claude); see the repository README.