Clock, Second Chance, and the Cost of Approximating LRU

Replacing the right page requires knowing the future. The optimal policy, described by Belady, evicts the page whose next use is furthest away, and it is unimplementable because the future is not available. Least-recently-used is the best implementable approximation when accesses are independent and the past predicts the future, and it too is unimplementable in its exact form, because it requires ordering every page by last use and updating that order on every memory reference.

What remains is a family of approximations that use one bit of hardware and a circular list. The family is worth understanding because the approximation’s failure modes are not the same as LRU’s, and because the way the kernel chooses a victim is entangled with how it writes pages back to storage and how it decides that the machine is under pressure.

The Reference Bit

The hardware maintains, per page-table entry, a bit that is set by the processor when the page is read or written and is not cleared by the processor. It is cleared only when software writes a zero to it. This is the entire input to the policy: one bit per page, saying whether the page has been touched since the last time the kernel looked.

The bit is cheap because the hardware sets it as a side effect of translation. There is no per-access trap and no counter to update. The kernel clears the bits in bulk and later reads them, which turns “was this page used recently” into a sampling question: used since the last sweep. The sweep interval is the resolution of the policy, and it is chosen as a trade between accuracy and the cost of clearing bits across the entire resident set.

Reading the bit is also not free in a system with a translation cache, since the bit lives in the page-table entry rather than in the cached translation. Clearing a reference bit requires invalidating the corresponding translation so that the next access re-sets it, or requires that the processor set the bit in memory on every access regardless of the cached entry. Architectures differ on this. Some handle it in hardware so that the cached entry carries the bit and writes it back on eviction; others require software to flush the translation. The former makes clock cheap; the latter makes it expensive enough that kernels batch the operation.

The Circular Scan

The clock algorithm arranges all resident pages in a circle with a hand pointing at one of them. When a frame is needed, the hand advances. If the page under the hand has its reference bit set, the bit is cleared and the hand advances past it: the page has had a second chance. If the bit is clear, the page is chosen as the victim, and the hand advances to the next page.

/* One step of the clock hand over a circular frame list. */
static struct frame *find_victim(struct frame_list *fl)
{
    for (;;) {
        struct frame *f = fl->hand;
        fl->hand = f->next;              /* advance first, so we never stall */

        if (f->pinned || f->dirty_and_writing)
            continue;                    /* cannot evict; skip without clearing */

        if (f->referenced) {
            f->referenced = 0;           /* second chance: clear and move on */
            continue;
        }
        return f;
    }
}

The loop terminates as long as at least one frame is evictable. If every frame has its reference bit set on the first pass, the hand clears them all and the second pass finds a victim at the first frame it examines, so the worst case is two revolutions over the resident set. That bound is the reason the algorithm is attractive: the work per eviction is proportional to the resident set size but with a small constant, and the constant is the cost of reading and conditionally writing one bit per frame.

The policy that results is not LRU. A page touched once between two sweeps and a page touched a thousand times between the same sweeps are indistinguishable; both have the bit set and both survive one pass. A page that is touched exactly once per sweep may survive indefinitely if the hand happens to pass it shortly after each touch. This is a coarse approximation, and it is deliberately coarse, because the hardware provides exactly one bit and the alternative is a software-maintained list updated on every access, which no system does.

The Dirty Bit and the Write-Back Decision

A victim that has been written to must be written back before its frame can be reused. The hardware provides a dirty bit for this, set on the first write, and the kernel can choose to clean pages proactively rather than at eviction time.

Cleaning ahead of eviction moves the write-back cost off the critical path. When a page is found dirty but its reference bit is set, a common strategy is to start the write and leave the page in place; if it is touched again before the write completes, the write may be redundant but the page stays resident. If it is not touched, the next pass finds it clean and can evict it without I/O. This is the same second-chance idea applied to the dirty bit rather than the reference bit, and it converts a synchronous write at eviction into an asynchronous write at a moment when the disk is otherwise idle.

The cost is redundant I/O. A page that is written, cleaned, written again, and cleaned again generates two writes for one final content. Under a write-heavy workload the redundancy can be substantial, and kernels balance it by limiting how often a page is cleaned before it is simply evicted dirty when the hand next reaches it.

What the Scan Rate Tells the Kernel

The hand’s speed is not fixed. It is driven by demand: the kernel scans only when it needs a free frame, so the scan rate is a direct measure of how quickly the free-frame pool is being consumed. A machine with plenty of free memory scans slowly or not at all, and pages accumulate reference bits over long intervals, which makes the sampling fine-grained in effect because the interval is long.

As free memory shrinks, the hand turns faster, the interval between sweeps shortens, and the policy becomes more aggressive: fewer pages get a second chance because fewer have been touched since the last sweep. This is the mechanism by which the replacement policy degrades gracefully under pressure. It is also the mechanism that produces the pathological case: when the resident set of the running workload exceeds physical memory, every page is evicted before it is reused, every access faults, and the machine spends its time in I/O. The hand spins, the fault rate rises, and no amount of scanning helps because the working set does not fit.

Kernels detect this state by watching the relationship between scan rate and fault rate. A rising scan rate with a flat fault rate means the kernel is successfully reclaiming unused memory. A rising scan rate with a rising fault rate means the workload’s working set has exceeded the machine, and the response is to reduce the number of runnable processes rather than to scan harder. The distinction matters because scanning harder in the second case makes things worse: it evicts pages that are about to be used again.

Where the Approximation Fails

Three patterns break clock’s assumptions.

Sequential streaming defeats it entirely. A program reading a large file once touches each page once, and every page has its reference bit set when the hand arrives. The hand clears the bit, moves on, and returns a full revolution later to find the page unreferenced, by which time the program has moved past it. The pages are evicted only after they have been carried for a full revolution, so the effective resident set for a stream is the whole stream rather than the window in use. Kernels mitigate this by detecting sequential access and either using a small circular buffer for streamed pages or evicting them out of hand.

Loops larger than memory produce the worst case. Each iteration touches every page, so every page is referenced between sweeps, so no page is a good victim, and the hand must clear bits and go around again. The policy degenerates to evicting whatever the hand reaches first after clearing, which is close to random, and random is worse than LRU for a cyclic pattern because LRU would at least retain the pages about to be reused at the start of the next cycle.

Pages with very different reuse distances coexist badly. A page touched every millisecond and a page touched every hour both have their bit set at sweep time if the sweep interval is longer than an hour, and both survive. The policy has no way to distinguish them without more state, which is why later algorithms add a second dimension: frequency of reference, or the time since the page entered the resident set. The clock algorithm with two hands, or with a queue of pages that have been referenced more than once, is a step in that direction, and the general family is constrained by reverse mapping and page migration, where the kernel’s need to find every mapping of a frame constrains what a replacement policy can afford to do.

The honest summary is that clock buys a bounded, predictable amount of work per eviction and pays for it with an accuracy loss that is invisible for workloads with a stable working set and severe for workloads at the edge of capacity. That trade is why it survives: the alternative policies are better on some traces and worse on the ones that matter, and none of them removes the fundamental problem that the kernel is guessing.