A replacement policy is judged by the hits it gets on a reference string, not by how sensible its rule sounds. Farthest-in-future is the offline optimum and therefore the bound; the three runnable policies fall short of it by different amounts on different traces. And FIFO can miss more often with a larger cache, which is Belady’s anomaly and is measured here rather than asserted.
Core ideas
A policy is a rule for choosing a victim. Three of these can be run by a cache; the fourth cannot, and that is what makes it useful.
Give a policy a reference string and a number of slots and it produces a definite number of hits. FIFO evicts the oldest arrival, LRU the least recently used, LFU the least frequently used. On 1 2 3 4 1 2 5 1 2 3 4 5 with three slots those give 1/4, 1/6 and 1/6 — and FIFO, the policy nobody defends, wins.
The offline optimum evicts the resident key whose next use is furthest ahead in the trace. It needs the rest of the trace, so no cache can execute it, and that is precisely why it is useful: no online policy beats it, so the gap between it and LRU is the most any policy change could possibly buy. On this trace with three slots it gets 5/12 against LRU’s 1/6.
LRU and farthest-in-future are stack algorithms: a cache of k+1 slots always contains everything a cache of k slots would, so their miss counts cannot rise when the cache grows. FIFO has no such property, and on this trace it misses 9 times with three slots and 10 times with four.
The material
What each rule does, who proves the optimum is optimal, and the trace on which more memory costs hits.
A reference string is the sequence of keys a cache is asked for. A replacement policy is the rule that chooses which resident key to evict when a miss arrives at a full cache of k slots. Its hit rate on that string is hits divided by references.
The first reference to each key must miss whatever the policy and whatever k: those are the compulsory misses, and on a trace of five distinct keys there are five of them.
Farthest-in-future — also called Belady’s algorithm, or OPT — minimises misses over every possible policy on a given trace. It is offline: it reads the rest of the request sequence to choose a victim, which no cache can do. So it is not a policy anyone runs; it is a ceiling against which the policies people do run are measured.
That it is optimal is a theorem, proved by an exchange argument, and the proof is not this course’s. It is Algorithms, in “Greedy Algorithms and Matroids”, in the lesson “Optimal Offline Caching” — algorithms/greedy-algorithms-and-matroids/optimal-caching — which also draws the offline/online distinction properly. What this lesson does with the theorem is use it: the bound turns “our hit rate is 1/6” into “the best any policy could have done on this trace is 5/12, and we are getting 1/6”.
On 1 2 3 4 1 2 5 1 2 3 4 5 with k = 3: farthest-in-future gets 5 hits (5/12), FIFO gets 3 (1/4), LRU gets 2 (1/6) and LFU gets 2 (1/6). The gap between the bound and LRU is 1/4 of all references, which is the most that a better online policy could have recovered — and no online policy can recover all of it, because the bound reads the future.
Now give the same trace four slots instead of three. LRU improves from 2 hits to 4, LFU from 2 to 4, the optimum from 5 to 6. FIFO goes from 3 hits to 2: its miss count rises from 9 to 10. A larger cache made it worse.
A policy is a stack algorithm if, at every point of every trace, the contents of a k-slot cache are a subset of the contents of a (k+1)-slot cache. For such a policy every hit at k is a hit at k+1, so the miss count is non-increasing in the cache size.
LRU and farthest-in-future are stack algorithms; FIFO is not, because its eviction order depends on insertion times that change when the cache size changes. Having no such guarantee is not the same as always failing — FIFO is well behaved on most traces — but it means no trace is safe.
This is the misconception the lesson exists to kill, and it is a belief people genuinely hold: that adding memory to a cache can be neutral at worst. It cannot, unless you know which policy you are running and that it is a stack algorithm. The lab scans every cache size from 1 to 6 for all four policies on your own trace and reports where any of their miss counts rises, so the anomaly arrives as a measurement rather than as a claim.
Two limits on what a trace can tell you. A hit count on twelve references is a fact about twelve references and not about your system; policies are separated by workloads, and a trace with a hot key ranks them differently from a round robin. And nothing here is about cost: LRU needs bookkeeping that FIFO does not, and whether that is worth two per cent of hit rate is an implementation question this course leaves to Algorithms.
Interactive
FIFO, LRU, LFU and the offline bound, at two cache sizes
Method
Two cache sizes, always. One size tells you which policy won a coin toss.
The distinct count is the compulsory misses, the floor every policy shares. A comparison that does not subtract them exaggerates how close the policies are: on twelve references with five distinct keys, five of the misses were never anyone’s fault.
Farthest-in-future gives you the ceiling before you have any attachment to a policy. If the gap between the bound and your current policy is small, no replacement change will help and the answer is a bigger cache or a different workload.
FIFO, LRU and LFU at k and at k+1. Two sizes, because a single size is one sample and because the second size is where an anomaly becomes visible. Compare hit counts, not hit rates, if the traces differ in length.
If a policy misses more with more slots, you have found Belady’s anomaly and you have learned something about the policy rather than about the trace. LRU and the optimum cannot do this; FIFO and LFU carry no such guarantee.
Twelve references over five keys. The four-slot run is the one that matters, and it is the one most people would not bother with.
Two results, and they point in different directions. At three slots FIFO beats LRU on this trace, which is a fact about this trace. At four slots FIFO gets worse than it was at three, which is a fact about FIFO: it is not a stack algorithm and has no guarantee to break.
For a faded rehearsal, run A B C A B D A B C D at k = 3 and k = 4. The supplied first move is that the optimum gets 5 hits at three slots; find LRU and FIFO at both sizes, and then say which policy’s ranking changed between the two cache sizes and whether any miss count rose. Report what that trace does and does not show about the anomaly.
The lab replays your own trace through all four policies, steps through the cache contents reference by reference so you can watch a policy make the eviction it is about to regret, and scans every cache size from one to six looking for a rise. It reports which policies it found one for and which it did not.
You should be able to replay a short reference string through FIFO, LRU, LFU and farthest-in-future, count hits at two cache sizes, identify the compulsory misses, quote the bound as a bound, and recognise a rising miss count as Belady’s anomaly rather than as a mistake.
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.