CLOCK page replacement

Keep page frames in a circular list with a reference bit and a scanning hand. Clear set reference bits while scanning; choose the first eligible page frame with a clear reference bit. This second chance approximates LRU replacement with cheaper tracking. When hardware reference flags are absent, revoking a mapping and handling its first later page fault can supply a software reference observation.

For the page-reference trace, number the three page frames 1–3 and initially point the hand at 1. Every access sets the referenced page frame's reference bit to 1. On a miss, scan from the hand: stop at an empty page frame or a resident one with reference bit 0; otherwise clear its reference bit and advance cyclically. Install the requested memory page with reference bit 1 and advance the hand to the next page frame. Hits leave the hand where it is. This fixes a particular variant; clean-victim preference is excluded.^[ref]

After the first three accesses, all reference bits are 1 and the hand is back at page frame 1. Access 4 clears all three reference bits, returns to page frame 1, evicts memory page 1, installs memory page 4, and leaves the hand at page frame 2 with reference bits $(1,0,0)$. This variant gives nine misses for three page frames and ten for four on the displayed sequence. Approximating LRU replacement therefore does not inherit the LRU stack property.

// Destination: computer-science.bigb