7. Page Replacement: The Clock Algorithm

Tanenbaum Section 3.4.4 (Fig. 3-16): Second-chance circular FIFO replacement, R-bit clearing sweeps, and live page fault handling.

1. The Need for Page Replacement

When a page fault occurs and all physical memory frames are occupied, the operating system kernel must choose an existing page to evict from physical RAM. If the evicted page was modified while in memory (M = 1), it must be written back to disk; if unmodified, the incoming page overwrites the frame directly.

While the Least Recently Used (LRU) policy is theoretically optimal among practical algorithms, recording an exact LRU sequence in hardware requires updating a counter or moving a linked-list node on every single memory reference, introducing severe memory bus latency.

2. Second-Chance and the Clock Optimization

A practical approximation of LRU is the Second-Chance replacement policy. The OS examines the Referenced (R) bit in the hardware page table entry:

  • If R = 0: The page is old and has not been referenced recently. It is evicted immediately.
  • If R = 1: The page was recently referenced. The OS clears R o 0, grants it a second chance, and inspects the next candidate.
Tanenbaum's Clock Optimization (Fig. 3-16):
Second-chance requires moving unreferenced pages to the tail of a linked list, which is unnecessarily slow. The Clock Algorithm eliminates this list-shuffling overhead by arranging all page frames into a circular buffer governed by a single rotating clock hand.
Figure 3-16: The Clock Page Replacement Algorithm (Before and After Page Fault at Time 20) (a) State before page fault occurs A, R=1 B, R=0 C, R=0 D, R=1 E, R=1 F, R=0 G, R=1 Hand → A (b) Page B evicted → Page I loaded, Hand advances A, R=0 I, R=1 C, R=0 D, R=1 E, R=1 F, R=0 G, R=1 Hand → C
Step 1 of 4 Interactive Clock Hand Stepper
1. Incoming Page Fault: Requesting Page 'I'

Part 3: Interactive Clock Algorithm Sandbox

Issue page references, inspect the circular pointer sweep, and toggle referenced bits on the live canvas.

How to Use the Sandbox & Observable Rules
1. Access a Page Type any page letter (e.g. H) in the input box and click Access Page. If resident → Hit (R o 1, hand stays put). If absent → Fault (hand sweeps to find and evict an R=0 victim).
2. Toggle R-Bits Click directly on any frame square in the circular SVG canvas or click Toggle R in the table to manually change referenced bits.
3. Periodic Timer Tick Click Periodic Timer Tick to simulate an OS interrupt clearing all R bits across every frame to 0 simultaneously.
Suggested Experiment: Click Reset Frames to load Tanenbaum Figure 3-16. Enter absent page I and click Access Page. Watch the animated sweep step through Frame 0 (giving a second chance: R=1 o 0) and evict Frame 1 (where R=0).
Total Accesses: 0 Hits: 0 Faults: 0 Hit Rate: 0.0%
Circular Frame Array
FramePageR BitPointerAction
Kernel Replacement Log