Exercises — Page replacement — FIFO, LRU, Clock, Optimal

(a) FIFO — it uses arrival time only. (b) LRU — it uses last-access time. (c) Optimal (OPT) — it looks into the future; unrealizable, used as a benchmark. Why: the distinguishing word is arrival vs last-access vs future. That single word is the whole policy.

The bit is the reference bit R. Hardware sets $R\leftarrow 1$ on every access to that page. When the sweeping hand lands on a frame with $R=1$, it does not evict; it gives a second chance by setting $R\leftarrow 0$ and advancing. It evicts only when it finds $R=0$.

False. OPT guarantees faults(OPT) $\le$ faults(any policy) — it is a lower bound, so it can tie. On 7 0 1 2 0 3 0 4 with 3 frames both score 6 (shown in the parent note).

Track the queue oldest→newest. A * marks a fault.

Faults = 9. (This is the famous Belady string — remember 3 frames → 9.)

Faults = 10. More frames → more faults. That is Belady's Anomaly (Belady's Anomaly), and 2.1 vs 2.2 is its canonical demonstration.

List frames LRU→MRU (leftmost is the eviction candidate). On a hit we move the page to the MRU (right) end.

Faults = 7.

Frames are a 3-slot ring; hand ↓ marks the current position. (R) is the reference bit. On a hit we set that frame's $R=1$. On a fault the hand sweeps: $R=1$→clear to 0 and advance; $R=0$→evict here, load new page with $R=1$, advance hand one past.

Faults = 8. Note Clock (8) did worse than LRU (7) here — it approximates recency, it does not reproduce it.

They diverge at the second 0 (step 7 of the parent's tables). By step 6, both had to evict a page. FIFO's queue made 0 the oldest, so FIFO evicted 0 at step 6 and had to reload it (fault) at step 7. LRU had just used 0 at step 5, so 0 was Most-Recently-Used — LRU evicted 1 instead and still held 0 at step 7 → hit. Why LRU wins: FIFO judges by age; but age is a bad proxy for future use when a page is old and still hot. LRU judges by recent use, which — under Locality of Reference — predicts near-future use.

OPT is the benchmark / lower bound. For any realizable policy $\pi$ on the same string and frame count: $\text{faults}(\text{OPT})\le \text{faults}(\pi ).$ So OPT tells you the best possible fault count. If LRU is close to OPT on your workload, you know LRU is essentially as good as any policy could be — no point chasing a fancier algorithm. That is the whole value of an unachievable optimum: it bounds how much room for improvement exists.

A policy is a stack algorithm if, for every prefix of the reference string, the set of pages it holds with $k$ frames is always a subset of the set it holds with $k+1$ frames: $S_k\subseteq S_{k+1}.$ LRU and OPT satisfy this: with more frames you keep a superset of pages, so any page present with $k$ frames is present with $k+1$ — you can never fault more with more memory. Hence faults are monotonically non-increasing in $F$; no anomaly. FIFO is not a stack algorithm: its victim depends on insertion order, and a different queue length reorders evictions so $S_k⊈S_{k+1}$. That broken inclusion is exactly what lets adding a frame increase faults (see 2.1 vs 2.2, Belady's Anomaly).

Use 1 2 3 4 1.

Faults = 5. FIFO evicted 1 (oldest) at ref 4, then the very next reference needed 1 again. LRU would also fault on 4 and 1 here, so this short string is the essence of the trap, not yet a win for LRU — but it isolates the mechanism: eviction by age ignores that 1 was about to be reused.

Use 1 2 3 1 4 1 2.

FIFO (old→new):

FIFO faults = 6.

LRU (LRU→MRU):

LRU faults = 5.

Why LRU wins: at ref 4, FIFO's oldest frame is 1 (arrived first) so FIFO evicts 1 — but 1 was just used at ref 4-position-4 and is needed again next. LRU sees 1 as MRU and evicts 2 instead, keeping 1 for its reuse. Age vs recency, made to bite.

Use 1 2 3 2 1.

OPT ($F=2$): at ref 3 (frames [1,2]), look ahead — 2 used at position 4, 1 at position 5. 1 is used furthest, so evict 1.

OPT faults = 4.

LRU ($F=2$):

LRU faults = 4. They tie — confirming OPT is $\le$, not $<$.

Proof. A frame can only contain a page that was previously loaded into it, and a page is loaded only on a fault (demand paging — nothing is prefetched). The first time a page $p$ is referenced, it has never been loaded, so it cannot be in any frame; that reference is necessarily a fault. Distinct pages have distinct first appearances, and no reference can be the first appearance of two pages. Hence there are at least (number of distinct pages) faults, giving the bound. $■$

Application. Distinct pages in 7 0 1 2 0 3 0 4 are $\{7,0,1,2,3,4\}$ = 6. So every policy — even OPT — faults at least 6 times. Since OPT achieves exactly 6 (parent note), 6 is unavoidable and OPT is tight here. These 6 are the compulsory / cold-start faults (Thrashing & Working Set Model calls them cold misses).

Invariant. After processing any prefix, LRU with $k$ frames holds exactly the $k$ most recently used distinct pages of that prefix (with fewer if fewer distinct pages have appeared).

Why the invariant holds: LRU only ever evicts the least recently used page and always keeps the just-referenced page as most-recently-used, so the retained set is precisely the top-$k$ by recency. (Induct on prefix length: the base is trivial; each new reference either is a hit — recency order updates, top-$k$ still the $k$ most recent — or a fault that inserts the new page as most-recent and drops the least-recent, again leaving the $k$ most recent.)

Conclusion: the "$k$ most recent distinct pages" is, by definition, a subset of the "$k+1$ most recent distinct pages." Therefore $S_k\subseteq S_{k+1}$, LRU is a stack algorithm, and by Exercise 3.3's reasoning its fault count is monotone non-increasing in $F$ — no Belady's Anomaly. $■$

There are $8$ references. $\text{fault rate}=\frac{\#\text{faults}}{8}.$

• FIFO: $7/8=0.875=87.5\%$.
• LRU: $6/8=0.75=75\%$.
• OPT: $6/8=0.75=75\%$.

Relative overhead of FIFO over OPT: $\frac{7-6}{6}=\frac{1}{6}\approx 0.1667=16.67\%.$ So FIFO does $16.67\%$ more faults than the theoretical best on this string, while LRU matches OPT exactly.