Page Replacement
Give a program more memory and it should fault less. That is not a rule of thumb, it is what everybody means by memory, and for the rules with the inclusion property, least-recently-used among them, it is a theorem. For the obvious rule it is false, and the obvious rule is to evict whatever has been resident longest. Belady, Nelson and Shedler printed the counterexample in 1969: twelve references, nine page faults with three frames, ten with four. This page runs their string, then searches every string shorter than it to show that none of them can do the same.
New to paging? Start here
A program's memory is cut into equal pages, and the machine holds only some of them at a time in slots called page frames. Touch a page that is not in a frame and it has to be fetched from somewhere slower, which is a page fault. That is the cost this page counts, and Page Fault is where the mechanism is.
When every frame is full and another page is wanted, something has to go. Which one goes is the replacement rule, and the obvious rule is to evict whatever has been sitting there longest, first in and first out. It has to remember the order they arrived in, and nothing else: a hit costs it no work at all, which is why it was the obvious rule.
The thing worth knowing before you start: everybody, including the people who built these machines, expected that giving a program more frames could only help. This page is about the year that turned out to be false, and about which rules it is false for.
What a processor actually does
A processor fetches an instruction, works out what it says, does that one small thing, and moves to the next. Add these two numbers. Put this number there. If that number is zero, carry on somewhere else. That is the job, and it repeats a few billion times a second.
Everything that looks like cleverness is arrangement around that loop: keeping the next instruction ready before it is asked for, keeping recently used numbers close by, letting a slow part and a fast part work at once. The machines here are those arrangements, and most of them exist because one part of the machine is thousands of times slower than another.
The machine for this idea on its own is Stored Program, if you would rather press it than read about it.
Machines here that come first: Page Fault, CPU Cache.
One string, two store sizes, and the fault count going the wrong way
1 One reference string, one replacement rule, and the frames you give it
A program touches pages in some order. The store holds a few of them at a time, and when a page is wanted that is not there, it has to be fetched. Count the fetches.
Page numbers 1 to 13, in the order the program touches them, up to twenty-four of them. This one is the string Belady, Nelson and Shedler print on page 350.
The offline optimum evicts whichever resident page is next wanted furthest away, which it can only know by reading the rest of the string first. It is a yardstick, not a rule a machine could run.
- pages fetched
- 9 of 12
The last column is in the order the rule keeps them in. First in, first out keeps arrival order, so the leftmost page is the one that goes next. Least recently used keeps them in the order they were last touched, and that reordering on a hit is the whole difference between the two. The optimum keeps arrival order and ignores it, because it decides by looking forward.
| step | page | outcome | evicted | frames hold |
|---|---|---|---|---|
| 1 | 1 | fault | — | 1 |
| 2 | 2 | fault | — | 1 2 |
| 3 | 3 | fault | — | 1 2 3 |
| 4 | 4 | fault | 1 | 2 3 4 |
| 5 | 1 | fault | 2 | 3 4 1 |
| 6 | 2 | fault | 3 | 4 1 2 |
| 7 | 5 | fault | 4 | 1 2 5 |
| 8 | 1 | hit | — | 1 2 5 |
| 9 | 2 | hit | — | 1 2 5 |
| 10 | 3 | fault | 1 | 2 5 3 |
| 11 | 4 | fault | 2 | 5 3 4 |
| 12 | 5 | hit | — | 5 3 4 |
9 of the 12 references had to be fetched. Everything on this page is counted; nothing is timed, and no clock would make the argument any better.
2 The same string with one more frame, and the fault count going up
Now sweep the frame count and leave everything else alone. The expected shape is a curve that only ever falls: more room, fewer fetches.
| frames | faults | hit rate | note |
|---|---|---|---|
| 1 | 12 | 0.0000 | |
| 2 | 12 | 0.0000 | |
| 3 | 9 | 0.2500 | |
| 4 | 10 | 0.1667 | up |
| 5 | 5 | 0.5833 | |
| 6 | 5 | 0.5833 |
At 3 frames it faults 9 times and at 4 it faults 10. The string did not change and the algorithm did not change. Only the memory did, and it went up.
Mattson and others drew this curve as a hit rate in 1970, for the 1969 string under FIFO. Read off their figure the six points sit at 0.00, 0.00, 0.25, 0.17, 0.58, 0.58, read off the plot to within 0.01, and dipping at four frames. This browser just computed 0.0000, 0.0000, 0.2500, 0.1667, 0.5833, 0.5833, and it dips at four frames. That is the experiment selected above.
3 Every string shorter than it, searched, and what the search was allowed to see
One string proves the thing can happen. It does not say whether the string is rare, or contrived, or the shortest of its kind. Those are finite questions, so ask them by counting rather than by trying.
A reference string is enumerated in canonical form: the first page named is 1, the next new one 2, and so on. Renaming pages cannot change a fault count, so one string per naming class is the whole space rather than a sample of it.
- strings searched
- 3,845
- strings there are, from the sums
- 3,845
- anomalous
- 0
| string | smaller store | larger store |
|---|---|---|
| none at this length | ||
3,845 strings of 8 references searched and not one is anomalous. The sums say there are 3,845 of them and the search saw 3,845, so nothing was skipped.
4 What least-recently-used holds that first-in-first-out does not
Mattson and his colleagues gave the reason in 1970, and it is one sentence. Some rules always hold, in a small store, a subset of what they hold in a bigger one. If that is true at every instant, then every hit in the small store is a hit in the big one, and faults cannot rise. They called it the inclusion property.
| reference | 1 frame | 2 frames | 3 frames | 4 frames |
|---|---|---|---|---|
| 1: 1 | 1 | 1 | 1 | 1 |
| 2: 2 | 2 | 1 2 | 1 2 | 1 2 |
| 3: 3 | 3 | 2 3 | 1 2 3 | 1 2 3 |
| 4: 4 | 4 | 3 4 | 2 3 4 | 1 2 3 4 |
| 5: 1 | 1 | 4 1 | 3 4 1 | 1 2 3 4 |
| 6: 2 | 2 | 1 2 | 4 1 2 | 1 2 3 4 |
| 7: 5 | 5 | 2 5 | 1 2 5 | 2 3 4 5 |
| 8: 1 | 1 | 5 1 | 1 2 5 | 3 4 5 1 |
| 9: 2 | 2 | 1 2 | 1 2 5 | 4 5 1 2 |
| 10: 3 | 3 | 2 3 | 2 5 3 | 5 1 2 3 |
| 11: 4 | 4 | 3 4 | 5 3 4 | 1 2 3 4 |
| 12: 5 | 5 | 4 5 | 5 3 4 | 2 3 4 5 |
At reference 7, comparing 3 frames against 4: the 3-frame store holds 1, 2, 5 and the 4-frame store is missing 1. Once that is true the smaller store can hit where the larger one misses, and the anomaly is possible.
How far it can go. The 1969 paper ends by conjecturing that the larger store can never fault more than twice as often as the smaller. Fornai and Ivanyi built a string in 2010 that does, and this is it.
- faults, six frames against five
- 161 against 78, a ratio of 2.064
Over two. The 1969 paper conjectured that the larger store could never fault more than twice as often, and this 181-reference string is the one Fornai and Ivanyi used to say otherwise.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| FIFO on the twelve-reference string: 9 faults with three frames, 10 with four | yes | one more frame, one more fault, on the same string |
| the same string under LRU (10 then 8) and OPT (7 then 6) gets better, not worse | yes | the string is not pathological; FIFO is |
| no string of eleven references or fewer is anomalous at any pair of frame counts: 820,987 searched, 0 found | yes | every canonical string up to length eleven, which is what the Bell numbers say there are |
| FIFO stops holding a superset at reference 7; LRU and OPT never do | yes | with 3 frames it holds 1, 2, 5 and with 4 it does not hold 1 |
| the search enumerates 4,140 strings of length eight and 3,845 of them use five pages or fewer, which is what the sums say | yes | counted by the enumerator and again from the Stirling numbers, which share no code |
| the census's arithmetic and the arithmetic that draws the trace agree on all 8,280 fault counts they both compute | yes | one algorithm written twice for two different jobs, compared over every canonical string of eight references |
| all 3 published figures this page checks itself against reproduce exactly | yes | a 1970 IBM figure, a 2010 counterexample and the 1969 paper's own closed forms |
| no algorithm here ever beats OPT, at any frame count | yes | OPT is a floor, and a floor nothing crosses is evidence the implementation is the optimum it claims to be |
| over every pair of frame counts up to six, LRU and OPT have no pair where more frames cost more | yes | 0 found |
What is real here, and what is not
Nothing here is timed, and no clock would help
Every measurement on this page is a count of page fetches. That is the same stance CPU Cache and The TLB take, and it is not modesty about the browser: the anomaly is a statement about how many faults a reference string induces, and a fault count is exact. A millisecond figure would add a number nobody could reproduce and settle nothing. Other numbers are printed and they are all derived from counting: how many references there were, how many strings a search examined, and the hit rate a fetch count implies. The one exception is the elapsed time of a search you asked for, which describes how fast this page is and says nothing about the phenomenon.
The twelve-reference string is the paper's, not a textbook's
It is printed on page 350 of the 1969 paper, in the paragraph beginning “taking the numerals 1, 2, 3, 4, 5 as the set of symbols corresponding to page names, a possible program can then be represented by the following string”. The archived scan is what this page was written from. The paper's trace ends in the state 5 3 4 at three frames, which is what the engine here computes, and it lists the four-frame store as 4 5 2 3 in physical frame order rather than arrival order, which is the same set written a different way.
A figure can be read for its shape and not for its fourth decimal place
The hit-rate curve in this panel is compared against figure 9 of the 1970 paper, and the comparison is made at the precision a printed plot can actually be read at, which is a hundredth, rather than at the precision this page computes to. What the figure settles exactly is its shape: it dips at four frames, and a dip is something a plot can be read for with no tolerance at all. An earlier draft of this page stored the exact values as if they had been read off the journal page, which would have been a claim about a scan that no scan can support.
The search's bound is part of its answer
The census enumerates strings in canonical form and caps how many distinct pages they may use, and that cap changes the result: at twelve references there is one anomalous string if the search may use five pages, six if it may use six, and eight if it may use seven. They are not one anomaly relabelled, because canonical form has already taken renaming out and these use five, six and seven distinct pages between them. What they share is the shape: every one faults nine times at three frames and ten at four, and every one has the same first eight references. The extra pages buy the last four references more ways to differ without changing what happens. But a page that printed the first number alone would have published the limits of its own sweep as a fact about the algorithm. The cap is a control for exactly that reason.
One inequality the scan could not settle, and how it was settled
Page 351 gives a production rule for building anomalous strings and states the constraint it holds under. The scan's OCR renders the last inequality as a tilde, so it could have been a < 2s or a ≤ 2s, and the closed forms it predicts are wrong under one reading. Running the rule over every candidate answered it first: the paper's own algebra reproduces exactly for all 84 parameter sets with a < 2s and fails for all 35 with a = 2s. Then page 351 was rendered at 300 dots per inch and read by eye, and it prints s < l < a < 2s. The computation and the page agree, and the page would not have been trusted alone.
What the census has not looked at
Strings longer than thirteen references. The census you can drive also stops at seven distinct pages, and both limits are a matter of time rather than of principle. Neither is the limit of what has been checked. The claim this page makes runs every time it loads, uncapped: over every canonical string of every length up to eleven, at every pair of frame counts, nothing is anomalous, so the shortest is twelve. Longer than thirteen is the part nobody here has searched.
Two to one is a theorem one way and was a conjecture the other
The 1969 paper proves that a ratio arbitrarily close to two to one can be reached, and separately conjectures that it can never be exceeded. The conjecture is false: Fornai and Ivanyi published a construction in 2010 whose ratio passes two and tends to three, and their string is the one behind the last control on this page. Their paper's title is FIFO anomaly is unbounded. It is a common mistake to report the proved half and the conjectured half as one result.
The optimum is offline, not impossible
Belady's 1966 paper names it, in the words “let us call it MIN”, and is careful about what is wrong with it: at the moment a page must be pushed out “nothing is known about the subsequent block references”, and the sequence “can be supplied by a pre-run of the program”, which is “impractical for most applications”. So it is a yardstick you can compute afterwards, not a policy you can run. Mattson's 1970 paper describes an algorithm it calls OPT which computes the same fault count and which it proves is a stack algorithm; this page implements that rule and labels it the offline optimum.
The name came later and this page does not claim to know who coined it
None of the three papers this page cites says “Belady's anomaly”. The 1969 paper says “the anomaly”; Mattson calls it “A peculiarity of FIFO”. He published as L. A. Belady, without the accents his name carries in Hungarian, and the citations here keep the byline as printed.
This is not the collapse The TLB shows, and the difference matters
The TLB holds one capacity fixed and changes the policy: least-recently-used loses to random replacement on a sequential scan. This page holds the policy fixed and changes the capacity: first-in-first-out loses to itself. The two are opposite experiments and they point at different things, and least-recently-used, the loser there, is exactly the rule that cannot lose here.
The measurement that started it cannot be reproduced
The 1969 paper opens with a real observation: a test load on an IBM M44/44X induced 170 page fetches with 48 pages of store and 202 with 52. That is a 1966 FORTRAN compile load on a machine that no longer exists and a trace nobody has. It is the reason anyone looked, and this page cannot check it. Everything else here is recomputed from scratch in the browser.
Sound: no
Asked and answered, so it does not have to be asked again. The measurement here is a count of fetches, and a tone per fault would carry the same count worse than the number does. The rule this studio uses is whether the sound is the measurement or a decoration of it; a click per page fault is a decoration.
Sources
- L. A. Belady, R. A. Nelson and G. S. Shedler, An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine, Communications of the ACM 12(6):349-353, June 1969. The anomaly, the twelve-reference string on page 350, the production rules and the two-to-one conjecture all come from here. An open scan of the printed pages; the ACM's own copy is behind a login and is cited below as the record.
- The same paper at its DOI, which is the citation of record. It resolves to a cookie wall rather than to the paper, so it was not the copy read.
- L. A. Belady, A study of replacement algorithms for a virtual-storage computer, IBM Systems Journal 5(2):78-101, 1966. Where MIN is defined and named, and where its unrealisability is stated precisely enough to quote.
- R. L. Mattson, J. Gecsei, D. R. Slutz and I. L. Traiger, Evaluation techniques for storage hierarchies, IBM Systems Journal 9(2):78-117, 1970. Stack algorithms, the inclusion property, and figure 9, which is the fault curve on this page drawn as a hit rate.
- P. Fornai and A. Ivanyi, FIFO anomaly is unbounded, 2010. The counterexample to the 1969 conjecture, and the string the last control on this page runs.
- Logical Art, the studio this belongs to.