How to use the cache replacement policy simulator
- Enter the reference sequence: the pages, blocks or keys that are asked for, in order, separated by spaces or commas.
- Set the cache size in frames, from 1 to 12.
- Choose which policy's steps to show in the detailed table. The summary table always compares all five.
- Read the hits, misses and evictions for each policy, then follow the step table to see what is in the cache after every reference.
Formula
hit: the page is already in a frame, nothing changes except its use count and time
miss: the page takes an empty frame, or the frame of the victim the policy picks
FIFO victim = oldest loaded; LRU = longest unused; LFU = fewest uses, ties by LRU; Clock = first page with bit 0; Optimal = used farthest in the future
The hit rate is hits divided by the number of references. Optimal needs to see the future, so it is a floor to compare against, not a policy a real system can use.
A textbook sequence with 3 frames
The 20 references 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames give 15 misses under FIFO, 12 under LRU, 11 under LFU, 14 under Clock and 9 under Optimal. Optimal has 11 hits, a hit rate of 55%.
The sequence 1 2 3 4 1 2 5 1 2 3 4 5 shows Belady's anomaly: FIFO has 9 misses with 3 frames but 10 misses with 4 frames, so more memory made it worse. LRU and Optimal can never behave that way.
How the policies differ
FIFO ignores how a page was used and so can throw out a page that is needed constantly. LRU assumes the recent past predicts the near future, which often holds. LFU favors pages used many times, but a page that was popular long ago can stay far too long. Clock approximates LRU cheaply with one reference bit per page: a page gets a second chance if it was used since the hand last passed.
The same ideas run browsers, databases, processors and content networks. To see how keys spread over several cache nodes, use the Consistent Hash Ring Simulator, and for queues in general the Little's Law Calculator.
Rules for ties and starts
Empty frames fill from the first one. If two pages tie on the policy's measure, the rule is stated in the formula: LFU breaks ties by least recent use and Optimal evicts the page loaded longest ago when several are never used again. A loaded or hit page gets the Clock bit 1, and the hand moves on past the frame it fills.
Assumptions and limits
- References are compared as text, so 7 and 07 are different pages.
- Each reference is one page and the cache holds distinct pages only.
- LFU counts uses only while a page is in the cache; the count starts again when it is loaded.
- There is no cost to a miss other than the count, and write-back and prefetching are not modeled.
- At most 200 references of up to 12 characters each are accepted.
Frequently asked questions
Why can the optimal policy never lose?
It always removes the page that will not be needed for the longest time. No other choice can leave a better cache, which the tests confirm by searching every possible choice on short sequences.
What is the Belady anomaly?
It is a case where a larger cache gives more misses. FIFO can show it, as the second preset does, but LRU and Optimal cannot.
Why does the Clock count differ from LRU?
Clock only knows whether a page was used since the hand last looked, not when, so it picks a victim less precisely. Its answer is usually between FIFO and LRU.
Does a bigger cache always help?
For LRU and Optimal, never hurts. For FIFO it usually helps, but the anomaly shows it is not guaranteed.