深入理解緩存算法中的 Belady 異常：為什麼增加緩存容量反而導致命中率下降？

前言

在作業系統的缺頁置換算法中，FIFO（先進先出）算法存在一個著名的反直觀現象：當分配的物理頁框數量增加時，缺頁次數不減反增。這種異常現象被稱為 Belady Anomaly（Belady 異常）。雖然這個概念源於虛擬記憶體管理，但在實際的緩存系統設計中，同樣會遇到「增加緩存容量，緩存命中率反而下降」的情況。本文將通過具體例子、詳細分析及理論結論，帶你徹底搞懂這一現象的成因與避免之道。

一、直觀例子：頁面置換模擬

假設頁面訪問序列為 dcbadcedcbae，採用 FIFO 算法，分別模擬 3 個頁框與 4 個頁框的情況：

從圖中可以清晰看到：3 個頁框時發生 9 次缺頁，而增加到 4 個頁框後，缺頁次數反而變成了 10 次。這就是典型的 Belady 異常。

二、深度分析：為什麼會發生這種情況？

關鍵在於兩種容量下的內存頁面集合之間不再保持子集關係。

• 時刻 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 也出現了相同的集合關係逆轉。

FIFO 算法在淘汰最老頁面時，無法保證大容量緩存的內容始終包含小容量緩存的所有內容，導致「包含關係」破裂，從而引發異常。

三、理論結論：Stack Algorithm 與 Belady 異常

如果一種置換算法滿足：任意時刻，較小容量的內存頁面集合始終是較大容量內存頁面集合的子集，則該算法稱為 Stack Algorithm（棧算法）。

• 可以證明：Stack Algorithm 永不會出現 Belady 異常（如 LRU、OPT）。
• FIFO 不是 Stack Algorithm，因此會出現 Belady 異常。

在實際工程中，應優先選擇 LRU 等棧類算法，或在使用 FIFO 時謹慎評估容量變更的影響。

四、參考文獻

1. Belady's Anomaly - 原始論文與經典教材說明