Question bank — Page replacement — FIFO, LRU, Clock, Optimal

False for FIFO — this is Belady's Anomaly; a bigger queue can retain a "wrong" page and evict a needed one. True only for stack algorithms (LRU, OPT).

True — they do often disagree because "oldest" means different things: FIFO uses arrival time, LRU uses last-access time. A page loaded long ago but touched recently is old to FIFO, fresh to LRU.

False — OPT is a lower bound ($\le$ every policy), so it can tie. On 7 0 1 2 0 3 0 4 with 3 frames both score 6.

False — the verdict fails because there exist strings where Clock's second-chance sparing keeps a page FIFO would have dropped, and that page then triggers extra faults later; Clock and FIFO are different policies with no ordering guarantee, so neither dominates the other. (In the degenerate case where no page ever earns a second chance, Clock merely matches FIFO — matching is not the same as never-worse.)

True — the first reference to each distinct page must fault regardless of policy, since no policy can hold a page it has never seen. Only the later evictions differ.

False — if distinct pages exceed frames, at minimum every distinct page's first touch faults, so some faults are unavoidable and a $100\%$ hit run is impossible.

True — recency must be refreshed on every access (hit or miss), which is exactly why exact LRU is expensive and Clock exists as a cheap approximation.

Error — FIFO never reorders on a hit; a hit changes nothing about age. Moving-to-newest-on-hit is LRU's behaviour, not FIFO's.

Error — Clock evicts the first page it finds with $R=0$. A page with $R=1$ gets its bit cleared and is spared (second chance), then the hand advances.

Error — that describes LRU. OPT looks forward and evicts the page whose next use is furthest in the future.

Error — the anomaly is specific to FIFO (and non-stack policies). LRU is a stack algorithm and is immune.

Error — only when all frames are full. If a free frame exists, the page is simply inserted with no eviction.

Error — the denominator is the total number of references, not distinct pages, because every reference is one hit-or-fault trial.

Error — Clock needs only one reference bit $R$ per frame; that single-bit cost is its whole selling point over LRU's timestamps.

Because FIFO's victim choice ignores usage entirely — it picks by arrival order, so a heavily-used but early-arriving page can be thrown out right before its next reference.

LRU bets that the recent past predicts the near future (Locality of Reference). This bet holds for real programs but can be defeated by adversarial or looping access patterns that violate temporal locality.

It gives an unbeatable benchmark / lower bound — the fewest possible faults for a string and frame count — so you can measure how far a real policy is from perfect.

Clearing $R$ records "I checked you once"; a page truly in use will have its $R$ re-set to 1 by hardware before the hand returns, letting genuinely active pages survive while stale ones eventually meet the hand with $R=0$.

Because the set of pages held in $k$ frames is always a subset of the set held in $k+1$ frames; adding a frame can only add pages, never displace a page that would have been kept — so faults never go up as $k$ grows.

A single disk access costs roughly $10^5\times$ a RAM access; each avoided fault saves millions of cycles, so the cost is dominated by fault count, not by the bookkeeping of evictions.

Exactly the number of distinct pages (all compulsory cold-start faults). Once every page is loaded, nothing is ever evicted, so all four policies tie.

Every single reference is a fault — with no slots the page can never be resident, so there is nothing to keep and nothing to compare policies on; fault rate is $100\%$ for all of them.

No — with one frame every fault evicts the only resident page, so all three make identical choices and produce identical fault counts.

The hand sweeps a full circle clearing all bits to 0, then evicts the page it started on — so a full loop of second chances collapses to picking the frame the hand first pointed at.

None — every reference is a compulsory fault for all policies, so FIFO, LRU, Clock, and OPT all fault on every reference and tie.

No — by definition OPT is optimal, so no policy can achieve fewer faults; any string that faults OPT faults every real policy at least as often.

Faults explode and the system spends most time swapping — this runaway state is thrashing, where too few frames hold too little of the active working set.