8. Simulating LRU: The Aging Algorithm

1. The Limitation of Simple Second-Chance

While the Clock algorithm (second-chance) avoids the heavy overhead of strict LRU, it is relatively coarse-grained. It only remembers whether a page was referenced during the current sweep cycle (R = 1 or R = 0). It cannot distinguish between a page referenced 10 instructions ago versus one referenced 10,000 instructions ago.

2. The Aging Algorithm Solution & The Referenced (R) Bit

To capture more precise access history without full LRU matrix overhead, operating systems use the Aging Algorithm. Each physical page frame is assigned a fixed-width binary history register (typically 8 bits wide, corresponding to 8 consecutive clock ticks).

The foundation of aging relies on the hardware Referenced (R) bit. Whenever the CPU accesses a virtual address, the memory management unit (MMU) automatically sets the page's R bit to $1$. Because the MMU never clears this bit on its own, the OS uses periodic clock ticks to read, shift, and reset it.

• Clock Tick Interception: At regular hardware clock intervals, the OS interrupts execution and performs a right-shift operation on every page's counter: R_i \to R_i \gg 1.
• MSB Injection (R \to MSB): During the shift, the current hardware Referenced (R) bit is inserted into the most significant bit (MSB, position 7) of the register: R₇ = R.
• Eviction Policy: When a page fault occurs, the kernel scans all frame registers as unsigned integers. The page with the lowest numerical value is chosen as the victim (indicating it has not been referenced for the longest sequence of ticks).