LRU Approximations: Clock and Enhanced Clock

The cost of true LRU

True LRU requires updating a data structure on every memory access. Options:

• Timestamp per page: on every access, write the current time to the page’s timestamp. On eviction, scan for the smallest timestamp. This is $O(n)$ eviction with a costly write on every access.
• Stack: maintain a doubly-linked list of pages in recency order. On access, remove the page from its current position and push it to the top. This is $O(1)$ per access but requires pointer updates that are impractical for hardware-managed page tables.

Neither is feasible for a general-purpose OS. Practical systems use approximations based on the A (Accessed) bit, which the MMU sets automatically and the OS clears periodically.

The Clock (Second-Chance) algorithm

Maintain a circular list of pages (a “clock”). A pointer (the clock hand) sweeps through the list. When a victim is needed:

1. Advance the clock hand to the next page.
2. If A = 0: this page has not been accessed since the hand’s last visit. Evict it.
3. If A = 1: give it a second chance. Clear the A bit and advance the hand. When the hand returns to this page later, if A is still 0 (not accessed in the interval), evict it.

Clock is an approximation of LRU: pages accessed recently (A = 1) get a second chance; idle pages (A = 0) are evicted. The approximation is crude — “recently” is defined by the hand’s rotation period — but it is cheap (no timestamps, just testing and clearing one bit) and reasonably effective.

Enhanced Clock (using D bit)

The enhanced second-chance algorithm uses both the A and D bits to prioritise eviction:

A	D	Description	Priority
0	0	Not recently used, clean	Evict first (no writeback needed)
0	1	Not recently used, dirty	Evict second (must writeback)
1	0	Recently used, clean	Give second chance
1	1	Recently used, dirty	Give second chance (worst to evict — recently used AND requires writeback)

The hand sweeps the clock, preferring to evict (0,0) pages. If none exist, it falls back to (0,1). If none, it clears A bits and tries again (giving all pages one more lap).

By preferring clean pages, enhanced clock minimises the number of disk writes, which are the dominant cost of page replacement.

Emulating reference and dirty bits (2024 Paper 2 Q4)

What if the hardware lacks A and D bits? The OS can emulate them using the page-table’s permission bits and page-fault handling:

Emulating the reference bit (A):

1. Initially, mark all pages as not present in the page table (even though they are in memory).
2. On the first access, the MMU raises a page fault. The kernel’s handler records “this page was accessed”, sets the P bit to 1 (really present), and sets the software reference bit.
3. Periodically, the kernel resets all pages to not-present to re-detect accesses. Between sweeps, any accessed page causes exactly one page fault, which records the reference. The overhead is one extra fault per accessed page per sweep interval.

Emulating the dirty bit (D):

1. Mark all pages as read-only in the page table (even though writes should be permitted).
2. On the first write, the MMU raises a protection fault. The kernel records “this page is dirty”, sets the R/W bit to 1, and resumes.
3. The overhead is one extra fault per written page until the bits are reset.

This technique is called software-referenced bits or paging-hardware emulation and was used by early versions of various OSes on hardware without A/D bits.

Summary

• Clock approximates LRU using only the A bit and a circular sweep; it is cheap but coarse.
• Enhanced clock uses A and D bits to prefer clean idle pages, reducing writeback cost.
• If hardware lacks A/D bits, the OS can emulate them by trapping on first access (A bit) or first write (D bit) using present/read-only tricks — at the cost of extra page faults per sweep.