How Does the Clock Algorithm Approximate LRU?

The Clock page replacement algorithm, also known as the second-chance algorithm, is a widely used operating system memory management technique that approximates Least Recently Used eviction without the high overhead of maintaining a strict recency list. By organizing page frames into a circular buffer and tracking a single reference bit per page, the Clock algorithm achieves near-LRU hit rates with constant-time overhead on memory accesses.

Why Exact LRU Is Expensive

In an ideal Least Recently Used (LRU) policy, the operating system evicts the page that has gone the longest without being accessed. Implementing exact LRU in hardware or software requires updating a data structure—such as a doubly linked list or a timestamp counter—on every single memory reference.

Because modern processors execute billions of memory accesses per second, updating a linked list or sorting timestamps on every read or write is prohibitively slow. Even with hardware support, maintaining a total ordering across \(N\) page frames requires \(O(\log N)\) or \(O(N)\) work or complex associative hardware, which does not scale well to large physical memories.

How the Clock Algorithm Works

The Clock algorithm replaces exact recency ordering with a coarse, two-state approximation using a circular buffer (the "clock face") and a pointer (the "clock hand").

Each page frame \(i\) in physical memory has a single hardware-managed reference bit \(R_i \in \{0, 1\}\):

  • Whenever a page is accessed (read or written), the Memory Management Unit (MMU) sets its reference bit to \(1\).
  • The operating system maintains a clock hand pointing to the next candidate frame to inspect.

When a page fault occurs and a frame must be evicted, the operating system advances the clock hand:

  1. If the frame at the hand has \(R_i = 0\), the page has not been accessed since the hand last passed it. It is evicted, the new page is loaded into that frame, its reference bit is set to \(1\), and the hand advances to the next frame.
  2. If the frame at the hand has \(R_i = 1\), the page gets a "second chance." The operating system clears its reference bit (\(R_i \leftarrow 0\)) and advances the hand to the next frame, repeating the check.

Why It Approximates LRU

The Clock algorithm divides pages into two rough categories: recently used (\(R_i = 1\)) and not recently used (\(R_i = 0\)). A page that is frequently accessed will repeatedly have its reference bit set back to \(1\) by the MMU before the clock hand completes a full revolution, keeping it resident in memory. Conversely, a page that has not been used for at least one full sweep of the clock hand will have \(R_i = 0\) when the hand returns, making it eligible for eviction.

In the worst case, if all \(N\) pages have \(R_i = 1\), the clock hand sweeps through all \(N\) frames, clearing every bit, and evicts the original frame—taking \(O(N)\) steps for that single fault. However, across a sequence of \(k\) page faults, the amortized cost per eviction remains \(O(1)\) as long as a reasonable fraction of pages are inactive, while normal memory hits require zero operating system intervention.

Common Variants

Several practical extensions improve the Clock algorithm's accuracy:

  • Enhanced Second-Chance (Clock-Pro / Two-Bit Clock): Uses both the reference bit \(R\) and the dirty (modified) bit \(M\). Pages with \((R=0, M=0)\) are evicted first because they require no disk writeback, followed by \((R=0, M=1)\), preferring to keep clean or recently used pages.
  • Two-Handed Clock: Uses a leading hand to clear reference bits and a trailing hand (separated by a fixed angular distance) to evict pages whose bits are still \(0\). This bounds how long a page can remain unreferenced before eviction, which is useful when physical memory is very large.