Second Chance and Clock Replacement

Introduction

Second Chance and Clock page replacement algorithms exist because exact LRU is useful but expensive. Exact LRU needs recency tracking on almost every memory access, which can create heavy overhead.

These algorithms keep the main idea of LRU: avoid evicting recently used pages. Instead of exact timestamps or lists, they use a simple reference bit to make a cheaper replacement decision.

Why Second Chance and Clock Are Needed

LRU works well because recently used pages are often likely to be used again soon. The problem is implementation cost. Tracking exact recency may require timestamps, stacks, lists, or frequent metadata updates.

Second Chance and Clock ask a practical question: can the system get LRU-like behavior using only a small hardware-supported signal? That signal is the reference bit.

• Reference bit: A bit associated with a page or frame.

• Set on access: Hardware sets it to 1 when the page is referenced.

• Used by OS: The operating system checks it during replacement.

• Main benefit: It avoids full exact-LRU tracking.

Second Chance Page Replacement

Second Chance starts with FIFO order, but it does not blindly remove the oldest page. Before eviction, it checks whether the oldest page was recently used.

If the reference bit is 0, the page has not been used recently, so it can be evicted. If the reference bit is 1, the page is given another chance: the bit is cleared to 0, and the algorithm moves to the next page.

This means a page that was recently used is protected once. If it is not used again before the algorithm returns to it, its bit remains 0, and it may be evicted later.

Clock Page Replacement

Clock is an efficient implementation of the Second Chance idea. Instead of moving pages around in a queue, it arranges frames in a circular list and uses a clock hand to scan them.

The clock hand points to the next candidate for replacement. When a page fault occurs and all frames are full, the hand moves until it finds a frame whose reference bit is 0.

The basic flow is:

• If current bit is 1: Clear it to 0 and move the hand forward.

• If current bit is 0: Evict that page.

• After loading new page: Set its reference bit to 1.

• After replacement: Move the hand to the next candidate.

Clock keeps the useful “second chance” behavior without physically moving pages through a FIFO queue.

Clock Worked Example

Consider this setup:

• Reference string: 1, 2, 3, 2, 4, 1, 2, 5

• Number of frames: 3

• Initial memory: Empty

• Reference bit rule: Set the bit to 1 on load or hit.

• Hand rule: After each load or replacement, the hand points to the next candidate.

At step 5, all reference bits are 1, so the hand clears them while moving and then evicts the first frame it reaches again with bit 0. Page 1 is replaced by page 4.

For this trace, the Clock algorithm produces 7 page faults and 1 page hit out of 8 total page references. Therefore, the page fault rate is 7 / 8.

Dirty Bit and Practical Cost

The dirty bit tells whether a page has been modified after being loaded into memory. This matters because replacing a dirty page is more expensive than replacing a clean page.

Some Clock variants prefer pages with R = 0 and D = 0, meaning not recently used and clean. This reduces write-back cost, because a clean page can be evicted faster than a dirty page.

So practical page replacement is not only about counting page faults. Dirty-page writebacks also affect total I/O cost and system performance.

Strengths and Limitations

Second Chance and Clock are useful because they give recently used pages some protection without exact LRU overhead. They are simple, practical, and depend on a reference bit that hardware can help maintain.

Their limitation is that they are approximations. A page with bit 1 only means it was referenced since the bit was last cleared; it does not show exact recency or frequency. Because of this, Clock can behave differently from true LRU.

Summary

Second Chance and Clock page replacement algorithms approximate LRU using a reference bit. A page with reference bit 1 is treated as recently used, so the bit is cleared and the page gets another chance instead of being evicted immediately.

Clock implements Second Chance efficiently with a circular frame list and a moving hand. It is cheaper than exact LRU, but still only an approximation, and practical variants may also use the dirty bit to avoid costly writebacks.