10. The WSClock Page Replacement Algorithm

Tanenbaum Section 3.4.6 (Fig. 3-20): Combining the simplicity of Clock with the thrashing-resistance of the Working Set model.

1. Why Simple Working Set Is Too Expensive

While the theoretical Working Set model prevents thrashing by ensuring a process's active pages (w(k, t)) remain resident in RAM, implementing it naively is impractical. In a basic working set algorithm, every single page fault triggers a linear scan across all allocated page table entries to evaluate whether their age exceeds \tau. On systems with gigabytes of RAM and hundreds of thousands of frames, this O(N) traversal consumes an unacceptable number of CPU cycles.

2. The WSClock Innovation: Circular List with Asynchronous Flushing

To solve this problem, Carr and Hennessy formulated WSClock. Like the standard Clock algorithm, all allocated page frames are linked in a circular ring traversed by a single moving hand. When a page fault occurs, the hand examines the page pointed to and evaluates four specific criteria:

WSClock Decision Logic per Frame:
Let Tcurrent be the process's current virtual execution time, and let \tau be the working set age threshold.
1. If R = 1: The page was referenced recently. Clear R ← 0, update Time of Last Use ← Tcurrent, and advance the hand.
2. If R = 0 and (Tcurrent - Time) ≤ \tau: The page is still within the active working set window. Do not evict; advance the hand.
3. If R = 0 and (Tcurrent - Time) > \tau and M = 0: The page is cold and clean. Immediate Victim! Evict this page, claim the frame, and finish.
4. If R = 0 and (Tcurrent - Time) > \tau and M = 1: The page is cold but dirty. To avoid blocking the CPU, schedule an asynchronous disk write and keep advancing the hand in search of a clean candidate.
Figure 2: WSClock Per-Frame Decision Pipeline Page Fault Hand points to Frame R == 1? Yes Clear R ← 0, Time ← T_curr Advance Hand → Next Frame No Age ≤ τ? (In WS?) Yes Keep in Working Set Advance Hand → Next Frame No M == 0? (Clean?) Yes EVICT VICTIM! Claim frame, exit fault handler No Schedule Async Write Keep hand advancing (non-blocking)

3. Handling Full Hand Sweeps

If the clock hand completes a full 360-degree rotation without finding an evicted clean page:

  • If at least one write was scheduled: The hand continues advancing until the first scheduled write completes, allowing that newly clean frame to be reclaimed.
  • If no writes were scheduled: All resident pages have R=1 or are within the working set \tau. The process is genuinely thrashing under severe memory pressure, so the OS picks the first clean page it encounters or falls back to standard Clock.
Figure 3-20: The WSClock Ring Architecture (Tanenbaum) WSClock Circular Frame Ring Structure Circular buffer of physical frames evaluating R-bit, Modified-bit, and Age delta (Current Time - Last Use) Frame 0 (Page A) R=1 | M=0 | T=2184 Frame 1 (Page B) R=0 | M=1 | T=1020 Frame 2 (Page C) R=0 | M=0 | T=850 Frame 3 (Page D) R=0 | M=0 | T=2140 HAND Victim Evicted! R=0, Age > τ (1350 > 400), M=0
Scenario 1 (Step 1 of 3) Interactive Decision Tracer
1. Hand at Frame 0: Evaluating Gate 1
1. Active Decision Tree Branch Branch Active
Page Fault Hand → Frame R == 1? Yes R ← 0, Time ← T_curr Advance Hand → No Age ≤ τ? (In WS?) Yes In Working Set Advance Hand → No M == 0? (Clean?) Yes EVICT VICTIM! Claim frame now No Schedule Async Write Advance Hand →
2. Circular Frame Ring State Hand: Frame 0
Frame 0 (Page A) R=1 | M=0 | T=2180 Frame 1 (Page B) R=0 | M=0 | T=1950 Frame 2 (Page C) R=0 | M=0 | T=1600 Frame 3 (Page D) R=0 | M=1 | T=1500 HAND

Part 3: Interactive WSClock Ring Simulator

Simulate reference streams, dirty write flushes, and observe real-time clock hand sweeps.

How the Simulator Works & What to Observe:
1. Read or Write Pages Type a page letter (A-F) and choose Read (R=1) or Write (M=1). Notice how the page's last used timestamp refreshes to current virtual time.
2. Set Age Threshold (τ) Adjust the slider to control the working set window size. Pages older than τ become candidates for eviction or asynchronous flushing.
3. Trigger Page Faults Click Trigger Page Fault to advance the clock hand. Watch the terminal trace calculate the exact age delta ((Tcurr - Tlast)) for each frame.
Suggested Experiment: Mark a page Dirty using Write Page, slide τ down to 100 ticks, and trigger a fault. Watch the algorithm schedule an asynchronous flush rather than evicting it immediately!
400 ticks Time: 2200
Clock Hand Index: Frame 0 Total Faults: 0 Dirty Writes Queued: 0 Clean Evictions: 0
Circular Buffer Frames
FramePageRMLast UsedAgeStatus
Kernel WSClock Execution Trace