subroute.
Intermediate9 min readlive prototype

Clock

Second Chance done efficiently: pages stay in a ring and a hand sweeps for a victim. The LRU approximation operating systems and buffer pools really ship.

Overview

What this concept solves

Clock is Second Chance made efficient. It makes exactly the same eviction decisions, but instead of shuffling pages around a queue, it leaves them fixed in a circular buffer and moves a single pointer — the 'clock hand' — around the ring. No list surgery, just an advancing index.

Picture the frames arranged in a circle, like numbers on a clock face. Each frame has a reference bit. The hand points at the next candidate for eviction. When you need to evict, the hand sweeps clockwise: if the frame it's pointing at has its bit set, it clears the bit and moves on (that page got a second chance); if the bit is already clear, that's the victim. The hand stops one past the slot it just filled, ready for next time.

Because the data never moves, every operation is O(1) amortized and touches only a bit and a pointer. That efficiency is why Clock — not exact LRU, not Second Chance — is the algorithm real operating systems and database buffer pools actually run.

Mechanics

How it works

The rule, step by step

  1. Page already in a slot? Hit. Set its reference bit to 1. The hand does not move.
  2. Not in memory, an empty slot exists? Place the page there with bit = 1 and advance the hand past it.
  3. Not in memory, all slots full? Sweep clockwise from the hand: if the current slot's bit is 1, clear it to 0 and advance; if it's 0, evict that page, load the new one there with bit = 1, and leave the hand one slot ahead.

Why the hand can't spin forever

Each step of the sweep either finds a 0 (and stops) or clears a 1 to 0. In the worst case — every bit set — the hand clears all of them in one full revolution and then evicts the slot it started on, now reading 0. So a sweep visits at most every slot once or twice; it always terminates, and worst-case behavior is plain FIFO. The prototype's Full sweep preset shows the hand going all the way around.

Clock's quality matches Second Chance's, and so it inherits the same limit: a single bit of history. Real kernels extend the idea — combining the reference bit with the dirty (modified) bit (see NRU), or using a counter instead of one bit (see Aging) — to make finer decisions. But the bare Clock is the foundation under all of them.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

About this simulation

The same logic as Second Chance, but pages stay put in a ring and a hand does the scanning. A hit sets the page's reference bit to 1 (green). On a fault the purple hand sweeps clockwise: a slot with bit 1 gets its bit cleared and the hand advances; the first slot with bit 0 is evicted and the new page loaded there. Watch the hand rotate and clear bits as it hunts for a victim.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Watch the hand clear bits and evict

Load the Classic textbook preset and step to a fault on a full ring. Follow the purple hand: each slot with a green '1' gets cleared to '0' as the hand passes (a second chance), until the hand lands on a '0' slot — that page is evicted and the new one loaded there. The hand ends one slot past the new page.

try 02

Protect a hot page

Run the Hot page protected preset. The repeatedly-referenced page keeps getting its bit re-set to 1 on each hit, so whenever the hand reaches it, the bit is cleared but the page survives that pass — and gets re-set before the hand comes around again. It's never evicted, just like a hot page under LRU.

try 03

Confirm Clock = Second Chance

Note Clock's total faults on the Belady example preset, then open the Second Chance prototype and run the identical string and frame count. The fault totals match exactly — proof they're the same algorithm. The only difference is that Clock moved a pointer where Second Chance moved pages.

In practice

When to use it — and what you give up

Where Clock is the right answer

  • Operating system page replacement — Clock and its variants are the standard. They get most of LRU's quality at FIFO-like cost.
  • Database buffer pools — PostgreSQL's buffer manager uses a clock-sweep variant (with a small counter per buffer) to pick eviction victims.
  • Any cache where exact LRU is too expensive — Clock is the go-to approximation when you can't afford a metadata update on every access.
  • When the MMU gives you an accessed bit — Clock is designed precisely around the single reference bit that page-table hardware already maintains.

Clock in the wild

PostgreSQL uses 'clock sweep' over its shared buffers, with a usage counter that the hand decrements instead of a single bit. Classic Unix systems used a two-handed clock (the 'page daemon') where a leading hand clears bits and a trailing hand evicts. The Linux page reclaim has evolved well beyond a basic clock into multiple LRU lists and, more recently, the Multi-Gen LRU — but the reference-bit-and-sweep heritage is still visible.

Pros

  • O(1) amortized, no data movement — just a bit flip and a pointer advance.
  • LRU-like quality — same decisions as Second Chance, far better than FIFO.
  • Uses the MMU's accessed bit — little or no extra metadata.
  • The real-world standard — what operating systems and buffer pools actually ship.

Cons

  • Only one bit of history — coarser than true LRU; can't tell heavily-used from barely-used.
  • Worst case is FIFO — when every bit is set, the sweep clears them and evicts the oldest.
  • Needs extensions for nuance — respecting dirty pages or finer recency requires NRU/Aging-style additions.
  • Sweep cost spikes occasionally — a sweep that clears many bits before finding a victim does more work that one step.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

clock.ts
// Clock: Second Chance with a fixed ring and a moving hand.
interface Slot { page: number; ref: 0 | 1; }

class Clock {
  private slots: (Slot | null)[];
  private hand = 0;
  faults = 0; hits = 0;

  constructor(frames: number) { this.slots = Array(frames).fill(null); }

  access(page: number): "hit" | "fault" {
    const hit = this.slots.find((s) => s?.page === page);
    if (hit) { hit.ref = 1; this.hits++; return "hit"; } // set bit, hand stays
    this.faults++;
    // sweep clockwise: clear set bits, evict the first cleared one
    while (this.slots[this.hand] && this.slots[this.hand]!.ref === 1) {
      this.slots[this.hand]!.ref = 0;          // second chance
      this.hand = (this.hand + 1) % this.slots.length;
    }
    this.slots[this.hand] = { page, ref: 1 };  // evict here (was null or ref 0)
    this.hand = (this.hand + 1) % this.slots.length;
    return "fault";
  }
}

References & further reading

5 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

What does the clock hand do when it points at a slot whose reference bit is 1?

question 02 / 03

How does Clock relate to Second Chance?

question 03 / 03

Why is Clock guaranteed to terminate its sweep and not spin forever?

0/3 answered

Was this concept helpful?

Tell us what worked, or what to improve. We read every note.

Back to Page Replacement