貝雷迪異常（Belady's anomaly）
/ BEL-ah-dee /
常識會說，給程式更多記憶體只可能有幫助——更多頁框肯定永遠不會產生更多分頁錯誤。對大多數演算法來說，這個直覺是對的。但在 1969 年，László Bélády 發現了一個驚人的例外：用 FIFO 置換，在某些參考字串上，增加頁框數反而會增加錯誤數。這個倒反、看似不可能卻真實的結果，就是貝雷迪異常。
它之所以發生，是因為 FIFO 純粹依年齡逐出，而多加一個頁框會改變每一步裡哪些頁恰好是最老的——其改變方式無法保證讓較大集合的內容始終是較小集合的超集。三個頁框時，一個有用的頁也許靠運氣存活了；四個頁框時，同一個頁卻可能在最糟的時刻被擠出去，造成一次三頁框版本所避開的後續錯誤。教科書字串 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 就是經典示範：FIFO 三個頁框產生 9 次錯誤，四個頁框卻產生 10 次。
為什麼重要：這個異常告訴你一件關於「什麼讓置換演算法表現良好」的深刻道理。屬於堆疊演算法的那些——也就是用 n 個頁框所持有的頁，永遠是用 n+1 個頁框所持有的頁的子集——可以被證明不會遭遇它；LRU 與最佳法都是堆疊演算法，所以對它們而言，更多頁框絕不會意味更多錯誤。FIFO 不是堆疊演算法，這正是它脆弱的原因。這個異常在實務上罕見、多出來的錯誤通常也不多，但它是一個著名的警告：別只因為一個演算法簡單，就假設它的行為是單調的。
字串 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。三個頁框時，FIFO 錯 9 次。加一個頁框變成四個，FIFO 卻錯 10 次——記憶體更多，錯誤反而多一次。這就是一行字寫完的貝雷迪異常。
更多頁框、更多錯誤——只有在 FIFO 不是堆疊演算法時才可能發生。
貝雷迪異常專屬於像 FIFO 這種非堆疊演算法。LRU 與最佳法是堆疊演算法、可被證明免疫——對它們而言，加頁框只會讓錯誤持平或減少，絕不會增加。