Least-recently-used is expensive: it needs a full timestamp on every page. The clock keeps one bit per page and a hand that sweeps a circle. A referenced page gets a second chance — its bit is cleared, not its frame; only a page found already-clear is evicted. With a single bit it approximates LRU: on the string below it faults 7 — exactly LRU's count — and beats FIFO's 9. Terms go in, the hand turns, faults come out. Blue builds it; red breaks it.
source F. J. Corbató, A Paging Experiment with the Multics System, MIT Project MAC report MAC-M-384 (1968) — multicians.org/paging-experiment.pdf. AMBER: the report gives the parametric FIFO↔LRU pager; the name "clock" and the circular-hand picture are the later shorthand for its use-bit scheme. Rendered, not quoted.
Frames sit in a circle; a hand points at one. Each frame carries a reference bit. Four rules, and validity falls out of them:
R1 a use sets the page's reference bit to 1. R2 a freshly loaded page starts with its bit set. R3 on a fault the hand advances; a frame with bit 1 is spared — its bit is cleared to 0 (a second chance) — and the hand moves on. R4 the first frame found with bit 0 is evicted; the new page lands there.
Live frames — page & reference bit at the current step:
| frame | page | ref bit | hand |
|---|
The neighbour sphere the-page-replacement proves LRU optimal-ish but costly: true recency wants a clock tick or a stack move on every access.
The clock is that idea on a budget — LRU approximated with a single reference bit and a moving hand. It never knows the exact order, only touched-since-the-hand-last-passed. That one bit is the page daemon real kernels run (Multics, BSD, Linux's active/inactive lists). Each sphere is the next one's premise.
The blue team's live check: re-run the pager over the whole string and confirm clock = LRU < FIFO and that the hand always finds a victim within two sweeps. If red tampers, this badge is where it shows.
A stream of page requests feeds the pager, which holds only 3 frames of physical memory. Five distinct pages compete for three frames:
Each page carries exactly one reference bit, set on use. The pager sees the requests one at a time — no lookahead, no timestamps. That single bit of history is all the clock gets to spend.
Fault count by policy on the full string (computed live, not looked up):
Watch the hand: a page with its bit set is spared and cleared; the first clear page is evicted. Nothing is looked up — the hand turns on the spot.
What the machine proves, discretely: on this string the clock faults 7 — exactly LRU's 7 — and beats FIFO's 9, using one bit where LRU needs a full timestamp. And the hand always terminates: after one sweep every bit is clear, so a victim is found in at most two full sweeps (observed max: 3 steps ≤ 2·3).
The blue witness (left) confirms these numbers live; the red team (right) tries to make the hand spin forever.
Worse: if references arrive faster than the hand sweeps, every bit saturates to 1, the first sweep clears them all, and the clock degrades to plain FIFO. It only approximates LRU while the bits stay informative — which is why real kernels add a second bit (dirty), multiple hands, or aging counters. The clock is not LRU; it is LRU you can afford.
"Clock is just LRU." Cut. It is an approximation — it matches LRU here (7=7) but can differ; it only knows "used since the hand last passed," one bit of history, not true order.
"Clock always beats FIFO." Cut. When every bit is set it is FIFO — it ties, never strictly worse, but not always better. The win is 9→7 on this string, not a theorem for all.
"A spared page is safe." Kept, corrected. A second chance only clears the bit. If the hand returns before the page is used again, it is evicted next pass — one reprieve, not immunity.
The red team's move: make the hand never clear the reference bit — grant every page a second chance, always. Now no bit ever reaches 0, the hand finds no victim, and it spins forever. The blue witness (window 7) is watching for exactly this.
Disable the bit-clearing and the two-sweep termination bound breaks: the witness recomputes, sees the hand loop past 2·F steps, and turns red. Nothing is faked; the attack is real and it is caught.