Belady's Anomaly

Belady's Anomaly : As the name suggests, in this scheme, the page that is removed from the memory is the one that entered it first. Assuming the some pages reference string as shown in fig.1, the states of various frames and page faults after each page reference. As it is clear from the fig., 15page faults result.

FIFO algorithm- Belady's anomaly

Belady's anomaly algorithm is easy to understand and to program.The first three columns are self explanatory. In the fourth reference of page 3, a page fault results and FIFO algorithm throws out page 8 because it was the first one to be brought in. The fifth page reference does not cause a page fault in both OPT( optimal) ad FIFO algorithms as page 1 already in the memory. The sixth page reference is for page 4. Here, FIFO will throw out page 1, because it came in earlier than the remaining two pagesat that time, viz. pages 3 and 2. Page 1 has been there the longest. Notice that OPT had close page 2 for throwing out.

FIFO algorithm- Belady's anomaly

The FIFO algorithm has one anomaly known as Belady's anomaly, named after the one who discovered it first.

Normally, if the physical memory size and therefore, the number of pages frames available increases, the number of page faults should decrease. This should enhance the performance. But this is not necessarily the case if we use FIFO as the page replacement policy. This, in essence, in Belady's anomaly. 

Let us, for example, take a reference string 2,3,4,5,2,3,6,2,3,4,5,6. Figure 2 shows that with 3 page frames, FIFO gives 9 page faults. However fig.3 shows us that if we increase the number of page frames from 3 to 4, the number of page faults increases and comes 10 

FIFO algorithm- Belady's anomaly

This clearly is anomalous. From these figures, we notice the page faults increases because in the case represented by figure 3, the page is referenced as soon as it is evicted in this specific reference string. Fortunately the anomalous behavior is rare and can be found only for specific types of page refrence string.FIFO is still fairly goof algorithm.

 Note :This phenomenon is commonly experienced when using the First in First Out (FIFO) page replacement algorithm. László Bélády demonstrated this in 1969.