前言
在使用FIFO算法作為缺頁置換算法時，分配的缺頁增多，但缺頁率反而提高，這樣的異常現象稱為belady Anomaly。
雖然這種現象說明的場景是缺頁置換，但在運用FIFO算法作為緩存算法時，同樣也是會遇到，增加緩存容量，但緩存命中率也會下降的情況。這也是我在學習緩存算法時遇到的概念，雖總結歸納之。
一、舉例
假設我們有字符串"dcbadcedcbae",頁面置換算法采用FIFO算法，現在有兩個內存，一個是3頁，一個是4頁。結果如下
由圖可以清楚的看到，前者缺頁數是9，而增加後的缺頁數反而是10.
二、分析
讓我們仔細看看在每個時刻在內存的頁數。比如在時刻3,3頁內存的頁數是 a、c、b, 4頁內存的頁數是d、c、b、a，3頁內存是4頁內存的子集，所以此時如果3不缺頁，4肯定不缺頁。
但是，比如在時刻6,3頁內存為e、d、c，4頁內存為e、c、b、a，3頁內存不是4頁內存的子集，那就意味著，4出現缺頁時，3反而不一定出現缺頁。時刻7和時刻10是同樣的道理。
三、結論
如果內存中頁數更小的集合是內存頁數更大的集合的子集，這個算法被稱為stack algorithm。可以證明stack algorithm(如LRU)不會出現belady現象，FIFO會出現。
四、參考文獻
1、Belady’s Anomaly
