Lesson 6 · Memory management

Clock Page Replacement: Second Chance

Arrange the frames in a circle and sweep. A page whose reference bit is set gets one more revolution to prove itself; the first page with a clear bit is evicted.

What the Second Chance Algorithm Is

The second chance page replacement algorithm, implemented as clock, is FIFO with one piece of hardware attached. Frames are arranged in a circular buffer and a hand points at the next eviction candidate. Each frame carries a reference bit that the MMU sets to 1 automatically whenever the page is accessed.

Arrange the frames in a circle with a hand pointing at the current candidate.
On a reference to a resident page, the MMU sets that frame's reference bit to 1 the OS does nothing.
On a fault, examine the frame under the hand.
If its reference bit is 1, clear it to 0, advance the hand, and examine the next frame the page gets a second chance.
If its reference bit is 0, evict that page, load the new one in its place with the bit set to 1, and advance the hand.
The sweep always terminates: if every bit is set, the first pass clears them all and the hand evicts the page it started on.

When a victim is needed, the hand inspects the frame it points at. If the reference bit is 0, that page has not been touched since the hand last passed, and it is evicted. If the bit is 1, the page has been used recently — the algorithm clears the bit to 0 and advances the hand without evicting anything. That reprieve is the second chance.

The insight is that the reference bit costs nothing. The MMU already sets it as part of address translation, so the operating system gets a coarse recency signal for free — no timestamp writes, no linked-list updates, nothing on the fast path. Clock page replacement turns that free bit into a decent approximation of LRU.

It cannot rank pages the way exact LRU does; the bit distinguishes only used since the last sweep from not used. That single bit of resolution turns out to be enough — on the standard reference string clock matches exact LRU fault for fault.

Decision rule: evict the first page found with a clear reference bit
A set bit buys one full revolution of grace
The reference bit is set by hardware at no software cost
Guaranteed to terminate within two revolutions

Clock Page Replacement Algorithm Example

This clock page replacement algorithm example runs 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 through three frames. Frames are numbered 0, 1, 2 around the circle; the hand starts at frame 0. Write each state as page values plus reference bits.

The first three references fill the empty frames, each loaded with R=1, leaving frames [7, 0, 1] with bits [1, 1, 1] and the hand back at frame 0.

Reference 2 — fault, and every bit is set. The hand sweeps the whole circle: frame 0 (page 7, R=1) is cleared and spared, frame 1 (page 0) cleared and spared, frame 2 (page 1) cleared and spared. Now back at frame 0, page 7 has R=0 and is evicted. This is the guaranteed-termination case: a full revolution clears every bit, so the second pass must find a victim. Frames [2, 0, 1], bits [1, 0, 0], hand at frame 1.

Reference 0 — hit. The MMU sets frame 1's bit back to 1. No sweep, no OS involvement at all.

Reference 3 — fault. The hand is at frame 1 (page 0, R=1): cleared and spared. Frame 2 (page 1, R=0): evicted. Frames [2, 0, 3]. Page 0 survived precisely because it had been used — the second chance doing its job, and the same page LRU spared here too.

Reference 0 — hit again, vindicating that decision. The run continues to a total of 9 faults, 4 hits — exactly matching LRU, for a fraction of the implementation cost. FIFO, which is clock without the bit, takes 10.

Clock on 7,0,1,2,0,3,0,4,2,3,0,3,2 with 3 frames — bits shown as [f0 f1 f2]
Ref	Frames after	Bits after	Event
7	7 – –	1 0 0	fault — empty frame
0	7 0 –	1 1 0	fault — empty frame
1	7 0 1	1 1 1	fault — empty frame
2	2 0 1	1 0 0	sweep clears all three, then evicts 7
0	2 0 1	1 1 0	hit — MMU sets the bit
3	2 0 3	1 0 1	spares 0 (R=1), evicts 1
0	2 0 3	1 1 1	hit — the spare paid off
4	4 0 3	1 0 0	sweep spares 2, 0, 3, then evicts 2
2	4 2 3	1 1 0	evicts 0 (R=0)
3	4 2 3	1 1 1	hit
0	4 2 0	0 0 1	sweep spares 3, 4, 2, then evicts 3
3	3 2 0	1 0 1	evicts 4 (R=0)
2	3 2 0	1 1 1	hit
Total	—	—	9 faults — identical to LRU

9 faults, 4 hits — matches exact LRU on this string
Two evictions required a full clearing sweep first
Page 0 was spared twice by its reference bit and hit both times
FIFO, the same algorithm without the bit, takes 10

Key reference

Terms, operations, and practical uses

The rule

DecisionEvict the first page the hand finds with a clear reference bit.
Second chanceA set bit is cleared and the page spared for one revolution.
Reference bitSet by the MMU on every access, at no software cost.
TerminationA full revolution clears every bit, so a victim always exists.

Enhanced clock

(0, 0)Unused and clean — the best victim, no write-back needed.
(0, 1)Unused but dirty — evictable at the cost of a write.
(1, 0) and (1, 1)Used recently — spared, reference bit cleared.
Dirty bitA modified page must be written back before its frame is reused.

In real kernels

9 faultsOn the standard string — identical to exact LRU here.
Cost modelWork happens on faults, never on the memory-access path.
LinuxActive and inactive lists; two references needed for promotion.
No hardware bitSome architectures simulate it via deliberate faults.

Implementation

Clock (second chance) on the standard reference string

def clock(refs, frames):
    """Clock (second chance) page replacement. Returns (faults, hits).

    Frames sit in a circular buffer. On a fault the hand advances past any page
    whose reference bit is set, clearing it on the way -- that is the second
    chance -- and evicts the first page it finds with a clear bit.
    """
    pages = [None] * frames
    referenced = [False] * frames
    hand = faults = hits = 0

    for page in refs:
        if page in pages:
            hits += 1
            referenced[pages.index(page)] = True  # the MMU does this in hardware
            continue

        faults += 1
        # Sweep. A full revolution clears every bit, so this always terminates.
        while pages[hand] is not None and referenced[hand]:
            referenced[hand] = False
            hand = (hand + 1) % frames

        pages[hand] = page
        referenced[hand] = True
        hand = (hand + 1) % frames

    return faults, hits


refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
print(clock(refs, 3))  # (9, 4) -- identical to exact LRU

#include <iostream>
#include <vector>
// Clock (second chance): a circular buffer of frames and a hand. A set
// reference bit buys the page one more revolution instead of eviction.
int clockReplace(const std::vector<int>& refs, int frames, int& hits) {
    std::vector<int> pages(frames, -1);
    std::vector<bool> referenced(frames, false);
    int hand = 0;
    int faults = 0;
    hits = 0;
    for (int page : refs) {
        bool resident = false;
        for (int i = 0; i < frames; ++i) {
            if (pages[i] == page) {
                ++hits;
                referenced[i] = true; // set by the MMU on a real machine
                resident = true;
                break;
            }
        }
        if (resident) {
            continue;
        }
        ++faults;
        // A full revolution clears every bit, so the sweep always terminates.
        while (pages[hand] != -1 && referenced[hand]) {
            referenced[hand] = false;
            hand = (hand + 1) % frames;
        }
        pages[hand] = page;
        referenced[hand] = true;
        hand = (hand + 1) % frames;
    }
    return faults;
}
int main() {
    std::vector<int> refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
    int hits = 0;
    std::cout << clockReplace(refs, 3, hits) << " faults, " << hits << " hits\n";
    return 0;
}

import java.util.Arrays;
public class ClockPageReplacement {
    /**
    * Clock (second chance). The hand sweeps a circular buffer, clearing set
    * reference bits and evicting the first page whose bit is already clear.
    */
    static int clock(int[] refs, int frames) {
        int[] pages = new int[frames];
        boolean[] referenced = new boolean[frames];
        Arrays.fill(pages, -1);
        int hand = 0;
        int faults = 0;
        for (int page : refs) {
            int slot = -1;
            for (int i = 0; i < frames; i++) {
                if (pages[i] == page) {
                    slot = i;
                    break;
                }
            }
            if (slot >= 0) {
                referenced[slot] = true; // hardware sets this on a real machine
                continue;
            }
            faults++;
            // One full revolution clears every bit, so this terminates.
            while (pages[hand] != -1 && referenced[hand]) {
                referenced[hand] = false;
                hand = (hand + 1) % frames;
            }
            pages[hand] = page;
            referenced[hand] = true;
            hand = (hand + 1) % frames;
        }
        return faults;
    }
    public static void main(String[] args) {
        int[] refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
        System.out.println(clock(refs, 3) + " faults");
    }
}

Watch it run

Step through it

Running on refs 7,0,1,2,0,3,0,4,2,3,0,3,2 · 3 frames, hand at frame 0

Output

Enhanced Clock: Adding the Dirty Bit

Not all victims cost the same. A clean page — unmodified since it was read in — can be dropped instantly, because an identical copy already exists on disk. A dirty page must be written back before its frame can be reused, costing a disk write on the fault path with the process blocked.

Enhanced clock therefore reads two bits per frame, the reference bit R and the dirty bit M, giving four classes. The hand makes up to three passes, preferring the cheapest available victim: (0, 0) is unused and clean, the ideal target; (0, 1) is unused but dirty, evictable at the price of a write; (1, 0) and (1, 1) have been used recently and are spared, with their reference bits cleared as the hand passes.

The first pass looks for (0, 0) without modifying anything. Failing that, a second pass takes the first (0, 1) it finds, scheduling the write-back, and clears reference bits as it goes. By the third pass the earlier clearing guarantees a candidate exists.

The gain is that a clean page is preferred over a dirty one of similar age, so the common case avoids a synchronous write entirely. This is close to what production kernels run, alongside background flushing that writes dirty pages out early precisely so that clean victims are available when the hand comes round.

Enhanced clock — the four classes in preference order
R	M	Meaning	Action
0	0	Not used recently, clean	Best victim — evict immediately, no write
0	1	Not used recently, dirty	Evict, but a write-back is required first
1	0	Used recently, clean	Spare — clear R and move on
1	1	Used recently, dirty	Worst victim — spare, and schedule a background write

Dirty pages cost an extra disk write before the frame is reusable
Preference order: (0,0), then (0,1); the R=1 classes are spared
Up to three passes, with the first pass modifying nothing
Background flushers keep clean pages available for the hand

Why Real Kernels Use Clock

Every practical operating system approximates LRU rather than implementing it, and the clock page replacement algorithm in OS design is the approximation they converge on. The reason is the cost model: exact LRU pays on every memory access, whereas clock pays only on a fault, when the process is already blocked and a few microseconds of sweeping is invisible against a disk read.

The quality gap is small. Clock cannot order pages within the used since last sweep group, but that group is exactly the working set, and the pages outside it — the ones with clear bits — are the pages LRU would also have chosen. On the string traced above the two policies produce the same 9 faults.

Linux extends the idea with active and inactive lists, where a page must be referenced twice to reach the active list. That defends against the sequential-scan pathology that ruins naive LRU: a one-pass scan cycles through the inactive list without displacing the active working set. BSD runs a two-handed clock, with a leading hand clearing bits and a trailing hand evicting, which lets the sweep rate adapt to memory pressure.

The bit itself is not always available. Some architectures — notably early ARM and MIPS — provide no hardware reference bit, so the kernel simulates one by marking pages temporarily invalid and setting the bit in the resulting fault handler. It works, but it converts a free signal into a costly one, which is a good illustration of how much clock depends on that single bit of hardware support.

Cost falls on faults, not on every memory access
Matches LRU's fault count on typical workloads
Linux's active/inactive lists require two references for promotion
Where no reference bit exists, it must be simulated via faults