§22.7–22.12Implementing Historical Algorithms … Summary

LRU wins on quality — now the bill. To implement it perfectly, some structure must move the accessed page to the MRU position on every single memory reference. Even with hardware stamping per-page time fields, eviction means scanning them all: a 4GB machine with 4KB pages has a million pages to examine. Which begs the question: do we need the absolute oldest page — or will close-enough do?

22.8 Approximating LRU

Yes — and it’s what modern systems do. The hardware contribution is one use bit use bit The hardware bit set to 1 whenever a page is referenced (a.k.a. the reference bit; first in Atlas) — hardware sets, the OS clears. The raw material from which clock and every LRU approximation is built. defined in ch. 22 — open in glossary per page (a.k.a. the reference bit; first appearing in the Atlas): set to 1 by hardware whenever the page is referenced, cleared only by the OS. From that single bit, Corbató’s clock algorithm clock algorithm Corbató's LRU approximation: pages in a circle, a hand sweeping — use bit 1? clear it, advance; use bit 0? victim found. Cheap, scan-bounded, and commonly extended to prefer clean over dirty victims. defined in ch. 22 — open in glossary conjures an LRU approximation:

(The clock is one arrangement among many: any scheme that periodically clears use bits and prefers use=0 victims approximates LRU. The clock’s charm is never rescanning all of memory.) How good is the approximation? Run it against the field:

22.9 Considering Dirty Pages

The StepThrough’s last frame already gave it away: eviction cost is not uniform. A dirty (modified) page must be written back to disk before its frame is free; a clean page’s eviction is free — the disk copy is already current. The hardware dirty bit (set on any write) feeds this into the policy: scan for unused-and-clean first, unused-and-dirty second.

22.10 Other VM Policies

Replacement isn’t the only decision. Page selection (Denning’s term) governs when pages come in: for most pages, demand paging demand paging The default page-selection policy: bring a page into memory only when it's accessed — on demand — rather than ahead of time. defined in ch. 22 — open in glossary — load on first access; plus prefetching prefetching Guessing a page will be needed and loading it early (e.g. code page P arrives → fetch P+1) — worthwhile only when the guess has a reasonable chance of being right. defined in ch. 22 — open in glossary when the odds are good (code page P just arrived → P+1 is likely next). And on the way out, clustering clustering Collecting pending page writes and issuing them as one large disk write — disks do one big write far more efficiently than many small ones (the swap daemon's favorite trick). defined in ch. 22 — open in glossary : gather pending writes and issue them as one large disk write — disks do one big write far more efficiently than many small ones.

22.11 Thrashing

What if demand simply exceeds physical memory — every policy’s nightmare? The system pages constantly and accomplishes little: thrashing thrashing The state where memory demand exceeds physical memory and the system pages constantly, making little progress — met historically with admission control, and in Linux with the out-of-memory killer. defined in ch. 22 — open in glossary . The classic answer is admission control admission control Fighting thrashing by refusing to run some processes so the remainder's working sets fit — sometimes it's better to do less work well than everything at once poorly. defined in ch. 22 — open in glossary : refuse to run some processes, hoping the survivors’ working sets working set The set of pages a process is actively using (Denning). If the running processes' working sets fit in memory, progress happens; if not, thrashing. defined in ch. 22 — open in glossary — the pages they actively use — fit in memory. Better to do less work well than everything at once poorly (a lesson with applications beyond paging, sadly). Some modern systems are blunter: versions of Linux run an out-of-memory killer that picks a memory-intensive process and terminates it — effective, if unsubtle, and occasionally it shoots the X server and takes the whole display down with it.

22.12 Summary

The full policy toolkit: optimal as the yardstick; FIFO and Random as cheap baselines; LRU as locality’s champion; clock and its dirty-bit variant as the affordable approximations modern systems actually run. Newer algorithms add scan resistance (ARC, among others) to dodge LRU’s looping-sequential worst case — the evolution continues. And a closing dose of humility: as the memory/disk gap has widened, paging of any kind has become so costly that the best fix for a thrashing system is often the intellectually unsatisfying one — buy more memory.