FOR FREE CONTENT

Belady's Anomaly

Disadvantage of FIFO page replacement algorithm:

Generally, we know if we increase the number of frames then page fault will reduce. So, the number of frames and page faults are reversely proportionate.

But unlike all page replacement algorithms, FIFO has a disadvantage that for some page reference strings, page faults increases when the number of frames increases. This is called Belady's Anomaly.

Example of Belady’s anomaly

For some reference strings, FIFO behaves abnormally because page faults abnormally increase and decrease as the page frames increase. 

Some page reference like: 

(i) 5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5

(ii) 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

(iii) 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4

Now, we evaluate page fault with the number of frames 3 and 4 using Optimal, LIFO, and FIFO for page references: 5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5. 

Optimal:

Page references: 5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5 and number of frame = 3

So, number of page fault = 8

Page references: 5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5 and number of frame = 4

So, the number of page fault = 6

LRU

Page references: 5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5 and number of frame = 3

So, the number of page fault = 11

Page references: 5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5 and number of frame = 4.

So, the number of page fault = 9

Note: Now, it is clear that for optimal and LRU, every time when we increase the number of frames, the page fault decrease (Both are inversely proportional) 

FIFO:

Page references: 5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5 and number of frame = 3.

So, the number of page fault = 10

Page references: 5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5 and number of frame = 4.

So, the number of page fault= 11

Now, using FIFO policy page faults with 3 frames = 10

FIFO policy page faults with 4 frames = 11

# So, here page fault increases when we increase the number of frames.

Note: But not every time page fault increases when we increase frame by a number, it may be increased or decreased the page fault for a certain number of frames. 

So, Belady’s anomaly only happened with FIFO, not any page replacement algorithm.

Now, what is the reason for Belady’s anomaly which only occurs at the FIFO page replacement algorithm?

Please visit Stack Property.