A repeatable string of requests for Belady's Anomaly

Alec Jacobson

January 07, 2010

weblog/

My friend and I were looking at Belady's Anomaly today. The anomaly occurs when using a First In First Out algorithm for page replacement in computer storage. The basic idea is that for certain, specific cases it's possibly to generate more page faults with a higher number of page frames than a lower number. Having 3 frames may give 9 faults and strangely having 4 frames may give 10 faults. In classes and online, the common example looks like this:

 012301401234  page requests
-------------
 mmmmmmmhhmmh  hit or miss
_012301444233  frame 1
__01230111422  frame 2
___0123000144  frame 3

-------------
 mmmmhhmmmmmm  hit or miss
 012333401234  frame 1 
 _01222340123  frame 2
 __0111234012  frame 3
 ___000123401  frame 4

As you can see in the above example the page system with 3 frames has 9 misses or faults and the one with 4 frames has 10 misses. My friend and I were wondering if this pattern can be repeated. Meaning, could we make a finite string of requests and such that if we repeated it k times we'd get k more misses in the 4 frames system than the 3 frame system. Here's a simple modification of the string above that allows such a repetition:

     start loop       end loop
     |                |
 5678|0123014012345678|...  page requests
------------------------------
 mmmm|mmmmmmmhhmmhmmmm|     hit or miss
_5678|0123014442335678|     frame 1
__567|8012301114223567|     frame 2
___56|7801230001443256|     frame 3

------------------------------
 mmmm|mmmmhhmmmmmmmmmm|     hit or miss
_5678|0123334012345678|     frame 1
__567|8012223401234567|     frame 2
___56|7801112340123456|     frame 3
____5|6780001234012345|     frame 4

So the string a="5678012301401234" is a repeatable string of requests generating one more miss on the four-framer, per occurrence of a. I broke a up a little differently above to show that the stacks are the same on both framers at the start and end of each loop through a. I'm curious about how this relates to rational and irrational numbers if at all. It would be cool for example if you could show for a 3-framer and 4-framer that reading the digits of pi you get more misses with a 4-framer.