THE FOLD / BOSS / THE WALL / THE BELADY ANOMALY
THE BELADY ANOMALY
more memory, more faults
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Give a program more memory and it faults more often. Not in theory, not as a pathology of a bad implementation — on the plainest replacement policy there is, first in first out, doing exactly what it says.
LIT verified live. the classic reference string
LIT verified live. the classic reference string
1 2 3 4 1 2 5 1 2 3 4 5 takes 9 page faults with 3 frames and 10 with 4. Searching for a shorter witness: over every reference string of length 1 to 11 on five pages with no immediate repeats — 6,990,505 strings, since a repeated reference is always a hit under any policy — the anomaly occurs 0 times. So the minimum length is exactly 12. LRU cannot do it at any length: over 187,246 sampled strings the resident set at 3 frames was a subset of the set at 4 every single time, 0 violations.2 HOW IT WAS WEAVED · AI + HUMAN
László Bélády found this in 1969; the stack-algorithm property that exempts LRU is Mattson, Gecsei, Slutz and Traiger, 1970.
AVAN (AI) went looking for a shorter witness and did not find one, which is the more useful result. The first search covered lengths up to 10 and reported 0, and a gate written from intuition called that a failure — it was not, it was the answer. Pruning immediate repeats made length 11 reachable and it is also 0. The LRU check tests the inclusion property rather than the fault count, because that is the actual reason LRU is safe, and a count that happened to agree would prove nothing.
AVAN (AI) went looking for a shorter witness and did not find one, which is the more useful result. The first search covered lengths up to 10 and reported 0, and a gate written from intuition called that a failure — it was not, it was the answer. Pruning immediate repeats made length 11 reachable and it is also 0. The LRU check tests the inclusion property rather than the fault count, because that is the actual reason LRU is safe, and a count that happened to agree would prove nothing.
3 ONE DIMENSION
Seven million strings. The anomaly needs exactly twelve.
4 TWO DIMENSIONS · INTERACTIVE
Step the reference string through both frame counts at once.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that FIFO is simply a bad policy. The inverse is that the anomaly is a statement about what ‘more memory’ means, not about FIFO’s quality. LRU is immune because its resident set at k frames is always contained in its set at k+1 — adding a frame can only ever add a page. FIFO has no such guarantee, so its two configurations are not nested, they are merely different, and comparing their fault counts is comparing two unrelated caches. Read backwards, monotonic improvement was never a property of memory; it is a property of policies that keep their smaller self inside their larger one.
LIT the classic reference string 1 2 3 4 1 2 5 1 2 3 4 5 takes 9 page faults with 3 frames and 10 with 4; searching for a shorter witness over every reference string of length 1 to 11 on five pages with no immediate repeats - 6,990,505 strings, since a repeated reference is always a hit under any policy - the anomaly occurs 0 times, so the minimum length is exactly 12, and LRU cannot do it at any length because over 187,246 sampled strings the resident set at 3 frames was a subset of the set at 4 every time, 0 violations
FIG Laszlo Belady found this in 1969; the stack-algorithm property that exempts LRU is Mattson, Gecsei, Slutz and Traiger, 1970. AVAN went looking for a shorter witness and did not find one, which is the more useful result. The first search covered lengths up to 10 and reported 0, and a gate written from intuition called that a failure - it was not, it was the answer. The LRU check tests the INCLUSION property rather than the fault count, because that is the actual reason LRU is safe, and a count that happened to agree would prove nothing.
FIG Laszlo Belady found this in 1969; the stack-algorithm property that exempts LRU is Mattson, Gecsei, Slutz and Traiger, 1970. AVAN went looking for a shorter witness and did not find one, which is the more useful result. The first search covered lengths up to 10 and reported 0, and a gate written from intuition called that a failure - it was not, it was the answer. The LRU check tests the INCLUSION property rather than the fault count, because that is the actual reason LRU is safe, and a count that happened to agree would prove nothing.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE WALL · David Lee Wise (ROOT0), with AVAN