So Belady's Anomaly states that when using a FIFO page replacement policy, when adding more page space we'll have more page faults.
My intuition says that we should less or at most, the same number of page faults as we add more page space.
If we think of a FIFO queue as a pipe, adding more page space is like making the pipe bigger:
____
O____O size 4 ________
O________O size 8So, why would you get more page faults? My intuition says that with a longer pipe, you'd take a bit longer to start having page faults (so, with an infinite pipe you'd have no page faults) and then you'd have just as many page faults and just as often as with a smaller pipe.
What is wrong with my reasoning?
55 Answers
The reason that when using FIFO, increasing the number of pages can increase the fault rate in some access patterns, is because when you have more pages, recently requested pages can remain at the bottom of the FIFO queue longer.
Consider the third time that "3" is requested in the wikipedia example here:
Page faults are marked with an "f".
1:
Page Requests 3 2 1 0 3 2 4 3 2 1 0 4
Newest Page 3f 2f 1f 0f 3f 2f 4f 4 4 1f 0f 0 3 2 1 0 3 2 2 2 4 1 1
Oldest Page 3 2 1 0 3 3 3 2 4 42:
Page Requests 3 2 1 0 3 2 4 3 2 1 0 4
Newest Page 3f 2f 1f 0f 0 0 4f 3f 2f 1f 0f 4f 3 2 1 1 1 0 4 3 2 1 0 3 2 2 2 1 0 4 3 2 1
Oldest Page 3 3 3 2 1 0 4 3 2In the first example (with fewer pages), there are 9 page faults.
In the second example (with more pages), there are 10 page faults.
When using FIFO, increasing the size of the cache changes the order in which items are removed. Which in some cases, can increase the fault rate.
Belady's Anomaly does not state anything about the general trend of fault rates with respect to cache size. So your reasoning (about viewing the cache as a pipe), in the general case is not wrong.
In summary: Belady's Anomaly points out that it is possible to exploit the fact that larger cache sizes can cause items in the cache to be raised in the FIFO queue later than smaller cache sizes, in order to cause larger cache sizes to have a higher fault rate under a particular (and possibly rare) access pattern.
5This statement is wrong because it is overgeneralized:
Belady's Anomaly states that when using a FIFO page replacement policy, when adding more page space we'll have more page faults
This is a corrected version:
"Belady's Anomaly states that when using a FIFO page replacement policy, when adding more page space, some memory access patterns will actually result in more page faults."
In other words... whether the anomaly is observed depends on the actual memory access pattern.
4Belady's anomaly occurs in page replacement algorithm do not follow stack algorithm.That is the pages when frames were less should be a subset of pages when frame are more.On increasing page frame,the page frames which were present before has to be there.This can occur in FIFO sometimes,even random page replacement but not LRU or optimal.
I could not understand belady anomaly even after reading the Wikipedia article and accepted answer. After writing the trace I kind of got it. Here I’d like to share my understanding.
Keys to understanding belady anomaly.
- Unlike LRU, FIFO just pushes out the oldest elements regardless of frequency. So staying in FIFO longer means falling victim to eviction.
From here, I refer to 3 and 4 pages FIFO queue as FIFO3 and FIFO4.
To understand Wikipedia example, I divided it into 2 parts. When FIFO3 catches up with FIFO4 and when FIFO3 overtakes FIFO4.
How FIFO3 catch up with FIFO4 on 9th
Look at 3 in both FIFOs. In FIFO3, 3 is evicted on 4th and came back on 5th. So it was still there on 8th and cache hit happened. In FIFO4, 3 is HIT on 5th, but this cache hit made 3 stays longer and evicted on 7th, right before next 3 on 8th.
2 is the same as 3. Second 2(6th) is MISS on FIFO3 and HIT on FIFO4, but third 2(9th) is HIT on FIFO3, and MISS on FIFO4. It might help to think like this. On FIFO3, 3 was updated on 5th so stayed longer until 8th. On FIFO4 3 was old and evicted on 7th, right before next 3 comes.
How FIFO3 overtakes FIFO4
Because there are 2 cache misses on 8, 9th for FIFO4, 4 is pushed down and evicted on 11th in FIFO4. FIFO3 still retains 4 on 12th because there are cache hit on 8, 9th, so 4 was not pushed down. I think this is why Wikipedia's aritcle says "Penny Wise, Pound Foolish"
Conclusion
FIFO is a simple and naive algorithm that does not take frequency into account. You might get a better understanding by applying LRU(Least Recently Used) to Wikipedia’s example. In LRU, 4 is better than 3.
Belady's anomaly happens in a FIFO scheme only when the page that is currently being referred is the page that was removed last from the main memory. only in this case even though you increase more page space, you'll have more page faults.
1
