FIFO：就趕走最老的那個
從第 1 篇導覽你已經備齊了整個舞台：一條行程碰觸的分頁參考字串、固定數量的頁框，以及一個我們想盡量壓低的分數——分頁錯誤率。現在我們需要一條真正挑選犧牲者的規則。最簡單到不能再簡單的規則就是 FIFO，先進先出：當必須釋放一個頁框時，趕走「常駐最久」的那個分頁——也就是最早進來的那個。把它想成麵包店櫃台前的隊伍：等最久的那位客人先被招呼、先離開，不管他是誰。
FIFO 的吸引力在於它幾乎不花成本就能實作。作業系統把常駐的分頁排成一個簡單的佇列：每載入一個分頁，就接到隊尾；該驅逐時，從隊頭移除。不必盯著什麼位元、不必記時間戳、不必掃描——只要一個指向最老分頁的指標就好。這份廉價正是 FIFO 值得認識的全部理由。但廉價裡藏著代價：FIFO 只衡量一件事——「一個分頁是多久以前到的」——而對「這個分頁是不是還在被用」完全不聞不問。
那個盲點正是 FIFO 的致命傷。想想一個裝著程式核心迴圈的分頁，或一個被頻繁使用的全域變數：它幾乎每條指令都被碰到，但按 FIFO 的鐘來看，它就只是「老」。FIFO 會單純因為一個忙碌的分頁早早載入，就高高興興地把它趕走——然後緊接著的下一次參考又把它錯誤地拉回來。一個分頁可以一邊持續被使用、一邊反覆地被換出又換入，而這正是好策略必須避免的那種浪費。所以 FIFO 是個誠實的基準線：建起來輕而易舉，卻把「老」與「沒用」混為一談，而這兩者並不一樣。
用手追蹤一遍 FIFO
沒有什麼比親手走一遍參考字串更能讓策略變得具體，所以我們用 3 個頁框、在字串 7 0 1 2 0 3 0 4 上追蹤 FIFO。我們由左讀到右；每一步，已常駐的分頁是命中，而未常駐的分頁是錯誤、會載入該分頁，若三個頁框都已滿了就趕走最老的。一邊走一邊把這個事實記在腦裡：常駐裡最老的那個分頁，就是 FIFO 下次會趕走的對象。
- 參考 7、0、1（第 1 到 3 步）：三個頁框一開始是空的，所以每個新分頁都只是錯誤地載入、佔一個格子。頁框現在裝著 {7, 0, 1}，其中 7 最老。目前三次錯誤。
- 參考 2（第 4 步）：一次錯誤，而且頁框全滿。FIFO 趕走最老的，也就是 7，由 2 接手。頁框現在 {2, 0, 1}，其中 0 最老。四次錯誤。
- 參考 0（第 5 步）：分頁 0 仍然常駐，所以這是一次命中——整條字串上我們唯一的一次。沒有載入、也沒有驅逐。
- 參考 3（第 6 步）：一次錯誤。此時最老的是 0，所以 FIFO 趕走 0，儘管它在第 5 步才剛用過。頁框現在 {2, 3, 1}。五次錯誤。
- 參考 0 然後 4（第 7、8 步）：0 剛被丟出去，所以它馬上又錯誤地載入回來（趕走 1）；接著 4 也出錯。0 那趟白白浪費的來回——第 6 步出去、第 7 步回來——正是 FIFO「只看年紀」規則在造成傷害。最終計數：8 次參考裡 7 次錯誤。
OPT：拿未來作弊的那套策略
一套策略到底「能」有多好？要回答這個問題，我們需要一把沒有任何真實策略能超越的尺，而這樣的尺剛好只有一把：最佳演算法，通常寫作 OPT（或 MIN）。它的規則說起來簡單得令人屏息——當你必須驅逐時，丟掉「未來最久之後才會再被需要」的那個分頁。往參考字串的前方看，找出哪個常駐分頁「下一次」被用到離現在最遠（或永遠不會再用到），就趕走那一個。直覺上這顯然是對的：你最快會用到的分頁，正是你最想留住的。
我們在同一條字串 7 0 1 2 0 3 0 4、3 個頁框上跑 OPT，來比一比。前三次參考填滿頁框（3 次錯誤），就跟剛才一樣。到第 4 步，分頁 2 出錯，頁框裝著 {7, 0, 1}；往前看——7 之後再也不會用到，0 下一次在第 5 步用到，1 之後再也不會用到。7 和 1 都是「再也不會」，所以哪個當犧牲者都行；趕走 7。第 5 步（0）是命中。到第 6 步，分頁 3 出錯，頁框是 {2, 0, 1}；往前看，0 在第 7 步還會再用到，而 2 和 1 之後都不會用到——所以趕走 2 或 1，別動 0。關鍵就在 OPT 留住了 0，於是第 7 步（0）現在是命中。在完全相同的字串上，OPT 是 5 次錯誤，FIFO 是 7 次。
貝拉迪異常：當更多記憶體反而有害
第 1 篇導覽預告了一個驚奇，現在它來了。常識說頁框越多錯誤越少：給一個行程更多空間，它應該能裝下更多自己的分頁，所以應該錯得更少。對大多數策略而言這成立。但對 FIFO 來說它可能徹底失靈——加一個頁框反而可能讓錯誤次數「上升」。這就是貝拉迪異常，由 László Bélády 於 1969 年發現，它感覺不可能是真的，直到你親眼看著它發生。
Belady's anomaly with FIFO string: 1 2 3 4 1 2 5 1 2 3 4 5 --- 3 frames --- --- 4 frames --- ref frames F/H ref frames F/H 1 1 F 1 1 F 2 1 2 F 2 1 2 F 3 1 2 3 F 3 1 2 3 F 4 2 3 4 F 4 1 2 3 4 F 1 3 4 1 F 1 1 2 3 4 H 2 4 1 2 F 2 1 2 3 4 H 5 1 2 5 F 5 2 3 4 5 F 1 1 2 5 H 1 3 4 5 1 F 2 1 2 5 H 2 4 5 1 2 F 3 2 5 3 F 3 5 1 2 3 F 4 5 3 4 F 4 1 2 3 4 F 5 3 4 5 F 5 2 3 4 5 F 3 frames -> 9 faults 4 frames -> 10 faults (!)
數一數 F：3 個頁框時 FIFO 錯 9 次，但 4 個頁框時錯 10 次。更多記憶體把它弄得更糟。為什麼會這樣？因為 FIFO 的犧牲者選擇取決於「到達順序」，而改變頁框數會把那個順序整個重新洗牌——4 個頁框時某一刻常駐的分頁集合，並不只是「3 個頁框的那個集合再加一個」。這兩種配置會做出真正不同的驅逐決定，而 FIFO 沒有任何規則逼大的那個必須是小的那個的超集合。於是大的池子有可能正好在某一頁即將被需要之前把它趕走，而小的池子卻沒有。
FIFO 與 OPT 教會我們的事
退一步看，這兩套策略從下方和上方把整個問題框了起來。OPT 是錯誤的地板——在一條給定字串上任何策略所能達到的最佳——但它做不出來，因為它需要未來。FIFO 是「至少能運作」裡最便宜的——實作起來輕而易舉——但它可能很差，更糟的是，它還可能鬧出貝拉迪異常。每一套切合實際的分頁置換策略都活在這兩者之間的縫隙裡，而那道工程問題永遠是同一個：只用我們真正握有的資訊，我們能逼近 OPT 到什麼程度？
決定性的線索在於「每套策略看的是什麼」。OPT 看未來（不可能）。FIFO 看到達順序（便宜，但和「一個分頁是否仍有用」毫不相干）。缺的那味是「最近的使用」——而最近的使用之所以是這麼好的指引，靠的是你在需求分頁那個階段遇過的「參考的區域性」：一個最近碰過某分頁的程式，極可能很快又會碰它。換句話說，過去是對「不遠的未來」一份便宜、且通常誠實的預測。這一個洞見，就是通往下一篇導覽的橋。
於是第 3 篇導覽的計畫自己就寫好了：用「回看過去」來逼近 OPT 的「展望未來」——趕走「最久沒被用到」的那個分頁，這套策略叫做 LRU。我們會看到，真正的 LRU 能比得上 OPT 的好脾氣（沒有貝拉迪異常），卻昂貴到無法在硬體裡精確實作，這逼著我們走向聰明又便宜的近似法：老化，以及那個悄悄把 FIFO 那些忙碌分頁從驅逐邊緣救回來的第二次機會（時鐘）演算法。FIFO 與 OPT 是兩個極端；一切實用的東西，都活在中間。