= CLOCK page replacement
{c}
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.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others/Beyond Physical Memory: Policies>[Section 22.8, p. 12: reference bits and the circular-hand algorithm; section 22.9, p. 13: dirty-page preference is an additional modification]{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
Back to article page
