CLOCK caches: revisit pages through reference bits

Last updated: 5 Oct 20269 min read

tutorial

A CLOCK cache stores page frames in a circular array, a reference bit beside each frame, and a map from page ID to frame position. A hit sets that page's bit. On a full-cache insertion, the hand inspects one frame at a time: a set bit is cleared and skipped, while the first clear bit identifies the victim. The hand then advances beyond the replacement. Newly inserted pages begin with a clear bit in this explicit policy; they have entered the cache but have not received a later hit. This approximates recency without moving a linked-list node on every hit. It does not preserve exact least-recently-used order. A page with a set bit can still be evicted after the hand clears it and completes another cycle.

Operational case

Three page frames hold incident pages 47, 19, and 61. A read of 47 sets its reference bit. When page 83 arrives, the hand gives 47 a second chance, then replaces 19 because that page's bit is clear. Residents are 47, 61, and 83. An insertion into a free frame does not evict another page. Updating an existing page replaces its payload in place and marks it referenced. Missing reads raise an error rather than inserting placeholder data. The return value of put names the evicted page, if any, so a caller can distinguish a replacement from an update or unused-frame fill.

Working Python program

class ClockPageCache:
    def __init__(self, capacity):
        if capacity < 1:
            raise ValueError("capacity must be positive")
        self.frames = [None] * capacity
        self.referenced = [False] * capacity
        self.positions = {}
        self.hand = 0
        self.used = 0

    def get(self, page_id):
        position = self.positions[page_id]
        self.referenced[position] = True
        return self.frames[position][1]

    def put(self, page_id, payload):
        if page_id in self.positions:
            position = self.positions[page_id]
            self.frames[position] = (page_id, payload)
            self.referenced[position] = True
            return None
        if self.used < len(self.frames):
            position = self.used
            self.used += 1
        else:
            while self.referenced[self.hand]:
                self.referenced[self.hand] = False
                self.hand = (self.hand + 1) % len(self.frames)
            position = self.hand
        victim = self.frames[position]
        if victim is not None:
            del self.positions[victim[0]]
        self.frames[position] = (page_id, payload)
        self.positions[page_id] = position
        self.referenced[position] = False
        self.hand = (position + 1) % len(self.frames)
        return None if victim is None else victim[0]


pages = ClockPageCache(3)
for page_id in (47, 19, 61):
    pages.put(page_id, f"page-{page_id}")
pages.get(47)
evicted = pages.put(83, "page-83")
print("evicted=", evicted, " resident=", sorted(pages.positions), sep="")

Output

evicted=19 resident=[47, 61, 83]

Time, space, and tradeoff

A hit uses expected O(1) dictionary lookup and one bit update. A full insertion can inspect at most two complete passes over C frames: the first clears set bits and the second finds a clear bit, so its worst-case time is O(C). Frame storage, bits, and the position map each use O(C) space. Across many replacements the hand spreads scans, but this Python example makes no measured amortized or hardware-cache claim. There is no removal API, dirty-page handling, concurrent access control, or write-back callback. The reference bit is only a one-bit history sample, not a timestamp.

Common Mistakes

Do not claim that CLOCK implements exact LRU order.
Do not forget to remove an evicted page from the position map.
Do not leave the hand on the replaced frame after insertion.
Do not treat a set reference bit as permanent immunity from eviction.

Connected lessons

Compare retention and timing contracts with Segmented LRU: separate probation from protected reuse, Frequency admission: compare an arrival with an eviction victim, Hashed timing wheels: bucket incident expiries by tick, then run the policy audit and contract quiz.

data structures

range-query-structures