What is the Clock (Second-Chance) Page Replacement Algorithm?
Learn how the clock / second-chance page replacement algorithm approximates LRU with a reference bit, with OS interview questions.
Expected Interview Answer
The Clock algorithm, also called second-chance, approximates LRU cheaply by arranging resident pages in a circular list with a single reference bit each, sweeping a pointer around the circle and giving any page whose reference bit is set one more chance before eviction instead of tracking exact access order.
Every page frame carries a hardware-maintained reference bit that is set to 1 whenever the page is accessed. When a page fault requires a victim, the clock hand examines the page it currently points to: if its reference bit is 0, that page is evicted immediately and the new page takes its frame; if the bit is 1, the algorithm clears it to 0, giving the page a “second chance,” and advances the hand to the next page in the circle, repeating until it finds a page with a 0 bit. This means a page must survive one full sweep without being re-referenced before it becomes eligible for eviction, which approximates recency using only a single bit per page instead of exact ordering. Clock is dramatically cheaper than exact LRU — updates on reference are just a bit set, done in hardware, with all the real work deferred to eviction time — while still capturing most of LRU’s benefit, which is why it (or its enhanced variant using both reference and dirty bits) is the algorithm actually used in most production operating systems.
- Approximates LRU using only one reference bit per page, not a full ordering
- O(1) hardware cost per memory access — the bit is set automatically
- Amortized low cost per eviction despite occasionally sweeping past several pages
- The algorithm actually implemented in most real-world kernels (Linux, Windows variants)
AI Mentor Explanation
Clock replacement is like a groundstaff supervisor walking a circular row of equipment lockers, checking a small flag on each: if a locker’s flag is down, that locker is cleared out immediately for a new player; if the flag is up (meaning a player used it recently), the flag is lowered and the supervisor moves to the next locker instead of clearing it right away. A locker only gets cleared once a full lap passes without its flag being raised again. This mirrors clock’s cheap, single-bit approximation of recency instead of tracking exact last-use times.
Step-by-Step Explanation
Step 1
Reference bit set on access
Hardware sets a page’s reference bit to 1 automatically whenever it is accessed, with no software overhead per reference.
Step 2
Fault requires a victim
On a page fault with no free frame, the clock hand examines the page it currently points to.
Step 3
Check and possibly clear the bit
If the reference bit is 0, evict that page. If it is 1, clear it to 0 (second chance) and advance the hand to the next page.
Step 4
Repeat until a 0 bit is found
The hand keeps sweeping the circular list, clearing bits along the way, until it lands on a page with a 0 bit, which becomes the victim.
What Interviewer Expects
- A definition tied to a circular list, a hand pointer, and a per-page reference bit
- Understanding of the “second chance” mechanic — bit cleared, page skipped once
- Recognition that this is a cheap approximation of LRU, not exact LRU
- Awareness that real kernels use enhanced clock (reference + dirty bits) in practice
Common Mistakes
- Confusing clock with exact LRU — clock only approximates recency with one bit
- Forgetting that the reference bit is cleared (not left set) when a page gets a second chance
- Not knowing that clock is what most production operating systems actually use
- Thinking the clock hand resets to the start after every fault (it persists between faults)
Best Answer (HR Friendly)
“Clock, or second-chance, replacement is a cheap and practical way to approximate “least recently used” without the overhead of tracking exact access order. Every page has a simple on/off flag that gets set when it is touched, and a pointer sweeps around all the pages like a clock hand — a page with its flag off gets evicted, but a page with its flag on gets one more chance and has its flag cleared instead. This is why nearly every real operating system uses some version of clock rather than true LRU.”
Code Example
struct frame { int page_id; int ref_bit; };
struct frame frames[NUM_FRAMES];
int hand = 0; /* the clock hand, persists across calls */
int clock_evict(void) {
for (;;) {
if (frames[hand].ref_bit == 0) {
int victim = hand;
hand = (hand + 1) % NUM_FRAMES; /* advance hand past the victim */
return victim;
}
frames[hand].ref_bit = 0; /* give it a second chance */
hand = (hand + 1) % NUM_FRAMES;
}
}
void on_page_access(int frame_idx) {
frames[frame_idx].ref_bit = 1; /* hardware-style set on access */
}Follow-up Questions
- How does enhanced (second-chance) clock use both the reference and dirty bits together?
- Why is clock cheaper per-access than exact LRU, and what does that cost show up as instead?
- Can the clock hand sweep past the same page more than once in one eviction? Why or why not for a bounded number of frames?
- How does Linux’s actual page-replacement (active/inactive LRU lists) relate to the classic clock idea?
MCQ Practice
1. In the clock algorithm, what happens when the hand lands on a page with reference bit = 1?
A set reference bit means the page was recently used, so it gets a second chance: the bit is cleared and the hand moves on without evicting it.
2. What is the main advantage of clock over exact LRU?
Clock avoids the expensive list-reordering exact LRU needs by using one cheap reference bit per page, checked only at eviction time.
3. What sets a page’s reference bit to 1?
Hardware automatically sets the reference bit whenever the page is accessed, requiring no software intervention on the fast path.
Flash Cards
What structure does clock replacement use? — A circular list of pages with a moving hand pointer and one reference bit per page.
What happens on ref bit = 1 during a sweep? — The bit is cleared to 0 (second chance) and the hand advances without evicting.
What happens on ref bit = 0 during a sweep? — That page is evicted immediately.
Why is clock preferred over exact LRU in real kernels? — It approximates recency with O(1) hardware-set bits instead of costly per-access reordering.