When a page fault occurs and NO free frame exists, one resident page must be evicted. The choice determines the fault rate, which (from the previous topic) dominates performance. If the victim is DIRTY it must be written to disk first — doubling the cost. Hence the DIRTY BIT: prefer a clean victim, because discarding it is free. FRAME ALLOCATION POLICIES: EQUAL each of n processes gets frames/n PROPORTIONAL each gets frames × (its size / total size) PRIORITY higher-priority processes get more LOCAL replacement a process may only evict its OWN pages → its fault rate depends only on itself GLOBAL replacement a process may evict ANY process's page → better overall utilisation, but a process's performance now depends on others' behaviour, so it is unpredictable Most systems use global replacement, accepting the unpredictability for the better throughput.

REFERENCE STRING (the standard textbook example, 20 refs): 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 All results below were COMPUTED, not estimated. ──────── WITH 3 FRAMES ──────── algorithm faults hit rate FIFO 15 25.0% OPTIMAL 9 55.0% LRU 12 40.0% CLOCK 14 30.0% ──────── WITH 4 FRAMES ──────── algorithm faults hit rate FIFO 10 50.0% OPTIMAL 8 60.0% LRU 8 60.0% CLOCK 9 55.0% 1. FIFO — evict the OLDEST page · a simple queue; the page that arrived first leaves first ✔ trivial to implement — one pointer ✗ WORST performance here (15 faults with 3 frames) ✗ ignores usage entirely: a heavily used page is evicted just because it is old ✗ suffers BELADY'S ANOMALY (below) 2. OPTIMAL (OPT / MIN) — evict the page that will not be used for the LONGEST TIME in the future ✔ provably the BEST possible: 9 faults, the theoretical minimum ✗ IMPOSSIBLE to implement — it requires knowing the future → its value is as a BENCHMARK. FIFO's 15 versus OPT's 9 tells you exactly how much room for improvement exists. 3. LRU — evict the LEAST RECENTLY USED page · uses the past as a prediction of the future, which works because of temporal locality ✔ good performance: 12 faults, much closer to OPT than FIFO ✔ NO Belady's anomaly (it is a "stack algorithm") ✗ EXPENSIVE to implement exactly: counter method — timestamp every page on every access stack method — move the page to the top of a stack on every access Both require work on EVERY MEMORY REFERENCE, which hardware will not do. 4. CLOCK (second-chance) — the practical LRU approximation · pages in a circular list, each with a REFERENCE BIT · to evict: examine the page at the hand ref = 0 → EVICT it ref = 1 → set ref = 0, advance, give it a second chance ✔ needs only ONE bit per page, set by hardware for free ✔ 14 faults with 3 frames — between FIFO (15) and LRU (12) ✔ this is what real operating systems use ENHANCED CLOCK uses the reference AND dirty bits, giving four classes and preferring (0,0) — not recently used and clean, so no write-back needed.

Intuition says more frames must mean fewer faults. For FIFO that is FALSE. REFERENCE STRING: 1 2 3 4 1 2 5 1 2 3 4 5 MEASURED: FIFO with 3 frames: 9 faults FIFO with 4 frames: 10 faults ← WORSE with MORE memory LRU with 3 frames: 10 faults LRU with 4 frames: 8 faults ← improves, as expected Adding a frame made FIFO worse. That is BELADY'S ANOMALY, and it is not a rounding artefact — it is a structural property of FIFO. WHY IT HAPPENS: FIFO's eviction choice ignores usage. With more frames, a page can survive long enough to be at the FRONT of the queue exactly when it is about to be needed again — so it is evicted at the worst possible moment. More memory changed the queue order for the worse. STACK ALGORITHMS are immune. An algorithm is a stack algorithm if the set of pages in n frames is always a SUBSET of the set in n+1 frames. LRU and OPT satisfy this; FIFO does not. For a stack algorithm, adding a frame can only ever help, because everything that was resident before is still resident. WHY THIS MATTERS BEYOND THE EXAM: it means you cannot tune a FIFO cache by simply making it bigger and measuring. The relationship is not monotonic, so a benchmark at one size does not predict another. LRU-family caches are safe to size by measurement; FIFO ones are not.

LFU (least frequently used) — evict the lowest access count ✗ a page used heavily once then never again keeps a high count forever ✗ a newly loaded page has a low count and is evicted immediately, even if it is about to be used FIX: AGING — periodically halve all counters, so old activity decays. MFU (most frequently used) — evict the highest count, arguing that a low-count page has just arrived and will be used ✗ performs poorly in practice; mainly of theoretical interest SECOND-CHANCE / CLOCK — described above, what real systems use ENHANCED SECOND CHANCE — reference and dirty bits together: (0,0) not referenced, not modified → BEST victim (0,1) not referenced, modified → must write out (1,0) referenced, not modified → likely reused (1,1) referenced and modified → WORST victim Scan for class (0,0) first; if none, scan again clearing reference bits. WORKING SET / WSCLOCK — evict pages outside the working set, combining replacement with the thrashing control from the swapping topic. THE PRACTICAL SUMMARY: OPTIMAL the benchmark — unimplementable LRU the goal — too expensive exactly CLOCK the compromise that ships FIFO only when simplicity outweighs everything And the reason approximation is acceptable: the difference between CLOCK (14) and LRU (12) is much smaller than the difference between FIFO (15) and LRU (12), so one cheap bit recovers most of the benefit. That is a very common shape in systems design — the first approximation captures most of the value.