Evicting the page whose next use is furthest away is optimal for any known sequence of references, and it is unimplementable, because it needs the sequence in advance. That is what makes it a bound rather than a policy. The lab checks the bound against a search over every eviction decision a cache of that size could make, and then sweeps FIFO from one slot to six on a trace where more cache means fewer hits.
Core ideas
Three ideas: what demand paging leaves to decide, why an unimplementable policy is still the right yardstick, and why more cache is not automatically more hits.
Under demand paging a referenced page that is absent is loaded, always, and nothing is loaded speculatively. So a policy is entirely determined by its eviction rule, and comparing policies is comparing eviction rules on the same trace with the same cache size. Every figure on this page is a hit count under that model.
Farthest-in-future evicts the page whose next reference is latest, which requires knowing the references that have not happened. No real cache can do it. It is still exactly the right thing to measure against, because it is optimal among all policies including the ones nobody can run: if LRU reaches 2 hits where the bound is 5, no cleverness in an online policy can recover more than 3, and the shortfall is attributable to not knowing the future rather than to LRU.
The intuition that a bigger cache cannot hurt is false for FIFO, and the panel sweeps it rather than saying so. On the opening trace FIFO gets 3 hits with three slots and 2 with four. The extra slot changes which pages are resident when each reference arrives, and FIFO's eviction order does not respect what is about to be used, so the change can go the wrong way.
The material
The model, the three eviction rules, the proof that farthest-in-future is optimal, the independent search that confirms it, and the sweep where a bigger cache loses.
A cache holds k pages. A trace is a sequence of page references. A reference to a resident page is a hit; a reference to an absent page is a miss, and the page is loaded, evicting one resident page if the cache is full. A policy is the rule for choosing which.
The lab opens on the trace 1 2 3 4 1 2 5 1 2 3 4 5 with three slots: twelve references over five distinct pages. FIFO evicts the page that has been resident longest and gets 3 hits, a rate of 1/4. LRU evicts the page unused for longest and gets 2, a rate of 1/6. Farthest-in-future gets 5, a rate of 5/12.
LRU doing worse than FIFO here is worth a moment. LRU is the better policy on most workloads and it is not a theorem; on this trace, which was built to embarrass FIFO's cache-size behaviour, LRU happens to lose by one hit. Two measurements on one trace, and neither is a ranking.
On a miss with a full cache, evict the resident page whose next reference is latest in the remaining trace; a page never referenced again is evicted first. This requires the whole trace in advance, so it is an offline policy.
For every trace and every cache size, no policy — online or offline — achieves more hits than farthest-in-future under demand paging.
The proof is an exchange argument of exactly the shape performed earlier on this course. Take any optimal schedule of evictions and the first point at which it differs from farthest-in-future; show that its choice can be replaced by farthest-in-future's without losing a hit, by tracking the two caches, which differ in at most one page, until they coincide again. Repeating drives the first difference forward, and the schedule becomes farthest-in-future's.
The lab does not run that argument. It does something stronger for the instance on screen: it searches every eviction decision a cache of this size could make, memoised on the pair of position and cache contents, and reports the maximum hits reachable. On the opening trace that search visits 43 distinct states and returns 5, which is what farthest-in-future got. So the optimality claim is checked here rather than cited, by a search that knows nothing about looking ahead.
On the thirteen-reference trace 1 2 3 1 4 1 2 5 1 2 3 4 5 with three slots, FIFO and LRU both get 4 hits and farthest-in-future gets 6, confirmed by a search over 44 states. On the loop 1 2 3 4 repeated three times with three slots, FIFO and LRU both get 0 — each evicts precisely the page about to be used — while the offline optimum is 6 of 12, because on every miss it discards the page whose turn comes last rather than the one whose turn comes next.
The panel sweeps FIFO from one slot to six on whatever trace is loaded and prints the hit count at each size. On the opening trace that row reads 0, 0, 3, 2, 7, 7: going from three slots to four costs a hit. On the thirteen-reference trace it reads 0, 1, 4, 3, 8, 8, and the same step loses a hit again. This is Belady's anomaly, and the reader sees the row rather than the citation.
The same sweep under LRU on those two traces reads 0, 0, 2, 4, 7, 7 and 0, 1, 4, 5, 8, 8: never falling. That is not luck. LRU is a stack policy — the pages resident with k slots are always a subset of those resident with k + 1 at the same point — and a stack policy cannot suffer the anomaly. FIFO is not a stack policy, and the two rows above are what that difference costs.
The sweep the panel draws is always FIFO's, whichever policy is selected for the chart, and the column that reads whether a bigger cache ever does worse is about FIFO alone. On two of the four shipped traces it reads no, and a reader who took that as a statement about caching in general would have generalised from a policy to a field.
The trace 1 2 1 3 1 4 1 5 1 6 1 7 with two slots is captioned as one where every policy keeps the hot page and the differences between them disappear. The table above it reads FIFO 3, LRU 5, farthest-in-future 5. FIFO does not keep the hot page: it evicts by arrival order, and page 1 is reloaded and then evicted again on every cycle. The difference between the policies on that trace is two hits out of twelve, which is the largest relative gap between FIFO and LRU on any of the four.
Measured on this page: 12 references, 3 slots, FIFO 3, LRU 2, farthest-in-future 5, offline optimum 5 over 43 states, and a FIFO sweep of 0, 0, 3, 2, 7, 7. Proved on this page: farthest-in-future is optimal on every trace and every cache size. Not proved anywhere in this library: any bound on how far an online policy can fall behind it, which is the competitive analysis this course names and does not develop.
Interactive
FIFO, LRU and farthest-in-future against a search over every eviction
Method
Four steps, and the fourth is the one that separates a policy comparison from a ranking.
A hit count means nothing without both. The same policy on the same trace gets 0 hits with three slots and 8 with four on the loop instance, and two policies compared at different sizes are not being compared at all.
FIFO and LRU are what a real cache can do. Farthest-in-future is what the trace permits. Recording them in that order keeps the bound in its place: it is the denominator of the comparison, not a candidate.
The panel searches every eviction decision, memoised on position and cache contents, and prints the number of states it visited. When that search agrees with farthest-in-future, optimality has been checked on this trace. When the trace is too long the panel refuses and says so.
One size is one data point, and the direction of the effect is not guaranteed. Read the whole row: three slots to four costs FIFO a hit on two of the four shipped traces, and nothing in the first three columns of either row would have warned you.
The trace is 1 2 3 4 1 2 5 1 2 3 4 5. Three slots. Each column below shows the cache after the reference, with a star marking a hit.
Farthest-in-future's first interesting move is at reference 4. Pages 1, 2 and 3 are resident and page 4 arrives; page 3's next use is at position 10 and pages 1 and 2 are needed at 5 and 6, so 3 goes. Every later eviction is the same calculation, and the two pages evicted at the end are ones the trace never mentions again.
The sweep is the row to stare at. FIFO's hit count goes 0, 0, 3, 2, 7, 7: three slots beat four. The reason is that FIFO's eviction order depends on when pages arrived, and adding a slot changes the arrival order of everything downstream, so the resident set at each reference is not a superset of the smaller cache's. LRU's resident set always is, which is why its row never falls.
For a faded rehearsal, work out the loop trace 1 2 3 4 1 2 3 4 1 2 3 4 with three slots before running it. The supplied first move is that after the first four references the cache holds 2, 3, 4 under both FIFO and LRU, and the next reference is 1. Say what FIFO and LRU each score, what the offline optimum is, and what happens to all three when the cache is given a fourth slot.
You should be able to replay FIFO, LRU and farthest-in-future by hand on a short trace, explain why an offline optimum is the right denominator, describe the exchange argument that proves the lookahead rule optimal, and say why LRU is immune to the anomaly and FIFO is not.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.