堆疊演算法（stack algorithm）

假設你把同一個程式跑兩次：一次允許它三個記憶體頁框，一次允許四個。你也許會希望四頁框那一次始終把三頁框那一次留在記憶體裡的一切都留著，再加一個頁——也就是較大的記憶體是較小的超集。一個對每一串參考字串、每一個時間點都永遠成立此性質的演算法，就稱為堆疊演算法。它用較多頁框所持有的頁集合，永遠包含它用較少頁框時會持有的集合。

更精確地說，堆疊演算法具有包含性質：在任何參考字串的每一步，它用 n 個頁框會留下的那 n 個頁，都是它用 n+1 個頁框會留下的那 n+1 個頁的子集。LRU 與最佳法都具備這個性質——LRU 是因為它的選擇只取決於使用的新近程度（最近使用的前 n 個頁永遠落在最近使用的前 n+1 個之內），最佳法是因為它的選擇只取決於未來的使用順序。FIFO 不具備它，因為多加一個頁框會以一種破壞巢狀關係的方式打亂哪些頁最老。

為什麼重要：堆疊性質正是某些演算法無法遭遇貝雷迪異常的確切原因。如果較大的記憶體永遠包含較小記憶體所持有的一切，那麼每個在 n 個頁框下命中的頁，在 n+1 個頁框下仍然常駐，於是加頁框絕不會把命中變成失誤——錯誤只會持平或下降。所以當你聽到「LRU 對貝雷迪異常免疫」時，底層原因就只是「LRU 是堆疊演算法」。這個性質還讓我們能在對參考字串的一次掃描中，算出所有記憶體大小的錯誤數。