The Clock Algorithm

Exact Least Recently Used (LRU) replacement requires a total order on all resident pages by time of last access, updated on every memory reference. Maintaining that order — via a doubly linked list touched on every read or write — is too expensive for hardware to do transparently, and too expensive for software to do on every instruction. The Clock algorithm, invented as a practical approximation of LRU, abandons the total order and instead maintains, for each frame, a single reference bit $R$ that hardware sets to 1 automatically whenever the page is accessed (read or written). The frames of physical memory are arranged conceptually in a circular list, and a single pointer called the clock hand sweeps around this circle. When a page fault occurs and a frame must be freed, the hand examines the frame it currently points to. If that frame's reference bit is 0, it is evicted immediately — it has not been used since the last sweep passed it. If the bit is 1, the algorithm gives the page a second chance: it clears the bit to 0 and advances the hand, without evicting, continuing until it finds a frame with $R=0$. This is why the base algorithm is also called the second-chance algorithm. The Enhanced Clock algorithm (used in Mach, VMS-derived systems, and described in Silberschatz's treatment of replacement algorithms) extends this with the modify bit (dirty bit) $M$, which hardware sets when a page is written. This produces four classes of pages, ordered by preference for eviction:

A $(0,0)$ page is both unused and clean — the ideal victim, since evicting it costs nothing beyond dropping the frame. A $(0,1)$ page is unused but dirty, requiring a costly write-back to disk before reuse. A $(1,0)$ page was recently used but is clean. A $(1,1)$ page was recently used and is dirty — the worst candidate, evicted only as a last resort. Enhanced Clock sweeps multiple times, first hunting for class $(0,0)$, then $(0,1)$ (clearing R bits as it goes), converging on a victim that minimizes both the chance of reuse and the cost of write-back.

The core data structure is an array (or circular doubly linked list) of frame descriptors, each holding a page identifier, a reference bit, and — for Enhanced Clock — a dirty bit. A single integer `hand` indexes the current frame under examination.

Second-chance (basic Clock) proceeds as follows on every page fault: ``` // Frame table: circular array of size N // frame[i].page = resident page (or EMPTY) // frame[i].ref = reference bit, set by hardware on access // hand = index of the clock's current position function CLOCK_REPLACE(new_page): loop forever: f = frame[hand] if f.page == EMPTY: frame[hand] = { page: new_page, ref: 1 } hand = (hand + 1) mod N return hand_position_used if f.ref == 0: // victim found: evict it evicted_page = f.page if f.page is loaded from disk before use, flush if dirty // basic version: assume clean or write-through frame[hand] = { page: new_page, ref: 1 } hand = (hand + 1) mod N return evicted_page else: // f.ref == 1 f.ref = 0 // give a second chance hand = (hand + 1) mod N // continue loop; do not evict yet // Hardware side, on every memory access to page p resident in frame i: on_access(i): frame[i].ref = 1 ``` The crucial invariant is that the hand only ever advances forward, and every frame it passes either gets its bit cleared (if it was 1) or gets evicted (if it was already 0). Since there are only $N$ frames, after at most $N$ steps of "clear and advance," the hand must encounter a frame whose bit is already 0 — either one it cleared on a previous full lap, or one that was never referenced. Termination is therefore guaranteed within at most $2N$ examinations in the worst case (one lap to clear everything, a second lap to find a zero), though in practice it terminates far sooner because most working sets are smaller than $N$.

Enhanced Clock replaces the single-bit test with a class search, sweeping up to twice through the circle: ``` function ENHANCED_CLOCK_REPLACE(new_page): // Phase 1: look for (ref=0, dirty=0) without modifying bits, // but clear ref bits of (1, *) pages as we pass them. // Phase 2: if no (0,0) found, look for (ref=0, dirty=1). // At most two full sweeps of the circle are needed in total. start = hand target_class = (0, 0) // phase 1 target: unused & clean cleared_any = false for pass in {1, 2}: i = hand repeat: f = frame[i] if (f.ref, f.dirty) == target_class: evict f, place new_page in frame[i], set ref=1 hand = (i + 1) mod N return if f.ref == 1: f.ref = 0 // demote toward class (0, dirty) cleared_any = true i = (i + 1) mod N until i == start target_class = (0, 1) // phase 2: unused but dirty allowed // note: ref bits are already cleared from phase 1, // so phase 2 only needs to check dirty bits now // Guaranteed to succeed by end of phase 2: every frame now has ref=0, // so either (0,0) or (0,1) must match every remaining frame. unreachable ``` The key correctness fact for Enhanced Clock: by the end of the first full sweep, every reference bit in the circle has been cleared to 0 (either because it was already 0, or because the algorithm cleared it while passing). Therefore the second sweep is guaranteed to find a match in class $(0,0)$ or $(0,1)$ — every frame now satisfies $R=0$. This bounds Enhanced Clock to at most two full sweeps, i.e. $O(N)$ frame examinations per fault in the worst case, same asymptotic order as basic Clock.

Time complexity. Each individual page fault triggers a scan that, in the worst case, visits every frame twice: once to clear all reference bits down to 0, and once more to find a frame that already has $R=0$ (for Enhanced Clock, up to two full sweeps for the two classes, so up to $4N$ examinations). This gives a worst-case cost of $O(N)$ per fault, where $N$ is the number of physical frames. However, this worst case is misleading in isolation. Consider the total work done across a sequence of $F$ faults. Each time the hand passes over a frame and clears its bit, that frame cannot be cleared again until it is referenced afresh (setting $R=1$) — and references are driven by the running program, not by the replacement algorithm. In the amortized sense, if we charge each bit-clearing operation to the memory access that most recently set that bit to 1, then each memory access is charged for at most one clear. Combined with the fact that a fault always terminates in the frame it evicts, the amortized cost per fault is $O(1)$ in typical workloads where the total number of "clear" operations is bounded by the total number of memory accesses, not by $N$ alone. In the pathological case where a workload has no locality at all and every bit is constantly re-set, the algorithm degrades toward $O(N)$ per fault, matching the theoretical worst case — but this is precisely the regime where any replacement policy performs poorly, foreshadowing the discussion of Thrashing.

Space complexity is $O(N)$: one reference bit and (for Enhanced Clock) one dirty bit per physical frame, plus the single hand pointer — a dramatic improvement over exact LRU's need for either a full access-time stamp per page ($O(N)$ words) or a linked list with pointer updates on every reference.

Correctness argument — why Clock approximates LRU. The claim to prove is not that Clock evicts the exact least-recently-used page, but that it evicts a page that has not been referenced during the most recent full sweep of the hand — a bounded window of accesses, playing the role of an approximate recency threshold. Invariant: At any point after the hand has completed a full lap without finding a victim, every frame's reference bit reflects whether that page was accessed since the hand last passed it (because passing clears the bit to 0, and any subsequent access sets it back to 1). Argument: Suppose the hand is examining frame $f$. If $R(f) = 0$, this means no access to $f$'s page has occurred since the hand last visited $f$ and cleared its bit (or since $f$ was loaded, if never visited). This is exactly the property LRU wants: a page unused for a "long time" (one full sweep) is evicted. If $R(f) = 1$, the page has been used since the last sweep, so evicting it would be a mistake under an LRU-like policy — hence Clock correctly grants it a second chance rather than evicting it blindly. Termination: The hand advances monotonically and clears every 1-bit it encounters. Since there are finitely many frames ($N$) and no new 1-bits can appear on a frame without a genuine memory access (an external event, not caused by the algorithm), within one full lap every previously-1 bit becomes 0, and the next pass is guaranteed to find at least one frame with $R=0$ unless every single frame was re-referenced during the very lap that cleared it — a case handled correctly by simply continuing the sweep, at worst costing another full lap.

Honest tradeoff. Clock is not exact LRU: it can evict a page referenced two accesses ago but not since the hand's last pass, while retaining one referenced long ago but touched once, coincidentally, just before the hand arrived. It sacrifices strict recency ordering for O(1) amortized bookkeeping — a tradeoff that is almost always worth it, because the bookkeeping savings on every memory access dwarf the marginal replacement-quality loss measured in cache-hit-rate studies (Clock typically comes within a few percentage points of exact LRU on realistic workloads).

Take a system with 4 frames, all initially holding pages A, B, C, D (loaded in that order, so all reference bits start at 1 after their initial load), and hand starting at frame 0 (page A). Suppose the reference string of subsequent accesses, before the next fault, is:

where E is a new page not currently resident, forcing a fault. Reference bits before the fault, reflecting the accesses to B and D (E is not yet resident so its access is the fault):

All four bits happen to be 1 — a deliberately non-trivial case where the first lap finds no immediate victim. Hand is at frame 0 when the fault for E occurs. Trace:

The hand takes a full lap (4 steps) clearing every bit, then on the second pass immediately evicts frame 0 (page A) because its bit is now 0 — nobody touched A during the lap. Note this matches intuition: A was the only page in the set never re-referenced (B and D were touched, C was untouched too but happened to sit later in the sweep order). Had C been checked before A on the second lap, the outcome would depend on hand position — this is precisely the source of Clock's approximation error relative to exact LRU, which would need to distinguish "A untouched longer" from "C untouched," a distinction Clock's single bit cannot make.

Enhanced Clock variant of the same scenario. Now suppose D is dirty (written to) and A, B, C are clean. Enhanced Clock's phase 1 seeks $(R{=}0, M{=}0)$:

Enhanced Clock reaches the same eviction choice here, but critically, if D had instead been the only untouched page, Enhanced Clock would skip past it (since $(0,1)$ is a worse class than $(0,0)$) to find a clean victim first, avoiding an unnecessary disk write-back — a distinction basic Clock cannot make since it has no dirty bit.

The reference-bit approximation to LRU emerged from the practical constraints of early time-sharing and virtual memory systems, where hardware could cheaply provide a single "was I touched" bit per page but not a full access-time log.

Nearly every production operating system kernel uses a Clock-derived algorithm rather than exact LRU, because the hardware reference bit is universally available on modern MMUs while exact per-access timestamping is not. Linux uses a two-list "active/inactive" LRU approximation heavily influenced by Clock-style periodic bit inspection, scanning pages during memory pressure (`kswapd`) rather than on every fault. FreeBSD implements an explicit Clock-based page daemon with active, inactive, and cache queues. Windows uses a working-set-based variant that also relies on hardware access bits rather than exact recency lists. Beyond OS kernels, the same reference-bit idea appears in database buffer pool managers (e.g., PostgreSQL's clock-sweep buffer replacement policy, used instead of exact LRU precisely to avoid lock contention on a shared recency list under concurrent access), and in CPU cache replacement approximations where full LRU is too expensive to implement exactly beyond a handful of ways. The general principle — approximate an expensive-to-maintain ordering with a cheap, hardware-supported bit sampled lazily — recurs anywhere systems must balance replacement quality against bookkeeping cost, directly motivating the deeper question of how much memory a process truly needs, which leads into Thrashing and the Working Set model.

Ask the tutor: How does the Enhanced Clock algorithm's four-class priority scheme change under heavy write-mostly workloads compared to read-mostly ones?