偷未來的點子：LRU 為什麼有用
在上一篇導覽裡你認識了最佳演算法：當記憶體滿了，趕走「最久之後才會再被用到」的那一頁。它在任何參考字串上都產生可能的最少錯誤，這正是為什麼它是衡量其他所有策略的基準。但它有個致命缺陷——它需要知道未來，而沒有任何真實的作業系統能看見一個程式明天會碰哪些分頁。所以 OPT 是無法實現的；它只活在模擬器裡，當一把尺。
LRU——最近最少使用（Least Recently Used）——就是那個聰明的變通辦法。既然我們無法向前看，那就向後看：趕走「最久沒被碰過」的那一頁。這背後的賭注是參考局部性，也就是「程式並非隨機地碰記憶體」這個深刻的觀察。一個剛剛用過的分頁，很可能很快會再被用到（迴圈變數、堆疊頂端），而一個很久沒被碰的分頁大概已經用完了。所以LRU拿最近的過去，當作對近未來一個便宜的預測——過去是面鏡子，OPT 用不起，LRU 卻用得起。
一個附帶好處：LRU 永不受貝拉迪異常之害
回想第二篇導覽裡那個令人不安的意外：用 FIFO，給一個行程更多頁框，有時反而會讓它錯得更多，這個結果叫做貝拉迪異常。LRU 可被證明對此免疫。原因是一個整潔的性質，叫做堆疊性質：用 LRU，「k 個頁框時會常駐的那組分頁」永遠是「k+1 個頁框時會常駐的那組分頁」的子集。多加一個頁框，絕不會丟掉一個較小記憶體本來會留住的分頁。
擁有這個性質的策略叫做堆疊演算法，而 LRU 與 OPT 都是其中一員。對任何堆疊演算法，更多頁框只會減少錯誤或維持不變——絕不會增加。這是工程師選 LRU 風格策略而非 FIFO 的一個真實、實際的理由：LRU 不只通常錯得更少，它的行為還是單調的，所以「容量規劃的直覺」（買更多 RAM、錯得更少）真的成立。FIFO 不是堆疊演算法，這正是它會出怪招的原因。
陷阱：精確的 LRU 太貴，造不起
如果 LRU 這麼好，為什麼幾乎沒有真實的作業系統「精確地」實作它？因為「最近最少使用」需要追蹤分頁被碰觸的「順序」，而這個順序在「每一次記憶體存取」時都會改變——不只在出錯時。要精確地做，你要嘛替每次存取蓋一個時間戳記（這樣驅逐時就掃描找最舊的戳記），要嘛維護一個雙向鏈結串列、每次參考就把那一頁搬到最前面。不論哪種，硬體都得為 CPU 執行的「每一次」載入與儲存做真正的記帳工作——每秒數十億次。
一言以蔽之，這就是那個取捨：讓驅逐決策變聰明，代價落在「每一次存取」上，而那正是你最付不起的地方。沒有任何主流的記憶體管理單元會在硬體裡為每一頁維護更新中的時間戳記，而用軟體來做則意味著在每一次參考時都陷入核心——慢到荒謬。所以精確的 LRU 是人人都想要、卻沒人付得起的策略。實際的做法是「放棄精確的順序」，退而求其次接受一個粗略、便宜的訊號，它只說：「這一頁最近被碰過、還是沒有？」——而結果證明，這個問題硬體幾乎免費就能回答。
參考位元與「第二次機會」的點子
幾乎每個記憶體管理單元都在髒位元旁邊提供一個免費的幫手：每個分頁表項目裡的一個參考位元（又叫存取位元或使用位元）。規則很簡單——每當硬體碰到一頁，無論是讀或寫，它就自動把那一頁的參考位元設成 1。作業系統永遠不必盯著個別的存取；它只要稍後讀這些位元就好。參考位元正是我們想要的那個粗略訊號：1 代表「自我上次看以來被用過」，0 代表「在那段窗口裡沒被用過」。它無法告訴你碰觸的「順序」，只能給你「最近與否」這個大略的事實。
第二次機會演算法就用這一個位元，造出一個近似 LRU 的策略。執行樸素的 FIFO，但在你真正趕走最老的那一頁之前，先偷看它的參考位元。如果位元是 0，這一頁最近確實沒被用過——趕走它，就像 FIFO 會做的。如果位元是 1，這一頁最近被用過，所以還不該死：給它第二次機會。把它的參考位元清成 0，再往下一個次老的分頁前進，重複同樣的測試。一個位元被設起的分頁會一直存活，直到它「整整繞過一圈都沒被碰」為止。
請注意這個優雅的效果：一個不斷被使用的分頁，會在每次掃描之間被硬體一再重設它的位元，於是它一再贏得第二次機會、繼續常駐——正是 LRU 想要的行為。一個沒人碰的分頁，終究會以 0 位元迎上指針而被趕走。我們用單單一個免費位元加上一個 FIFO 順序，就重建了 LRU 的精神，完全不需要任何「每次存取」的記帳。
時鐘：把第二次機會畫成一個圓圈
第二次機會有個彆扭的實作細節：一個真正的佇列會逼你在一頁存活時，把它「實體地」從前面搬到後面，這很瑣碎。時鐘演算法是同一個點子，配上漂亮的包裝。把所有頁框排成一個圓圈，像鐘面上的數字，並保有一根指針——時鐘指針——指著其中之一。指針永遠只往前走，一圈又一圈地掃；什麼都不必重排。時鐘就是這麼回事：把佇列彎成一個環的第二次機會，讓存活者不需要任何搬動。
find_victim(): # frames arranged in a ring; 'hand' points at one
loop forever:
page = frame_at(hand)
if reference_bit(page) == 0:
evict page # found the victim; this frame is reused
advance hand one step # leave hand just past the new page
return page
else:
reference_bit(page) = 0 # clear bit: this is its "second chance"
advance hand one step # keep sweeping
# A burst of all-1 bits is impossible to loop on forever: each pass
# clears bits, so within at most one full revolution some bit is 0.兩個誠實的邊角情況。第一，如果出錯來臨時「每一頁」的參考位元都被設起，指針會繞完整整一圈、把每個位元都清成 0，然後趕走它一開始所在的那一頁——所以在那個最壞情況下，時鐘恰好退化成 FIFO。第二，一個更精細的版本會把參考位元和髒位元一起權衡，傾向在「沒用過但髒」的分頁之前，先趕走「既沒用過又乾淨」（不需寫回）的分頁——這正是第一篇導覽的便宜驅逐技巧，被直接摺進掃描裡。真實的核心常跑好幾根指針或好幾個優先級類別，但核心永遠是這個「一位元、不重排」的迴圈。
老化：用更多位元，榨出更多近期資訊
樸素的參考位元有一個弱點：它只有一個位元，所以它分不出兩個「在上一次掃描裡的某個時刻」都被用過的分頁——它沒有「多久以前」的概念。老化演算法靠著給每一頁一個小計數器（比方說 8 個位元）來修正這點，並在固定的計時器滴答上更新它。每一次滴答，把每一頁的計數器右移一位，再把那一頁當下的參考位元放進剛空出來的最高位元，然後清掉參考位元。這個計數器就成了一段簡短的歷史：高位的一個 1 代表「最近用過」，低位的一個 1 代表「不久前用過」，全部是零代表「冷」。
因為較新的參考落在高位、較舊的往下走並掉出去，這個計數器當成一個二進位數來讀時，幾乎是依真正 LRU 的方式替分頁排名：趕走計數器最小的那一頁。老化仍然是一種近似——它的解析度是計時器的間隔，而計數器會忘掉比它位元寬度更久的一切——但用區區幾個位元，它追蹤近期資訊就比單一位元細緻太多，以「每滴答」（而非「每存取」）一份微小、固定的代價，逼近精確的 LRU。
小心別把老化和計數式策略（LFU/MFU）搞混了，後者數的是一頁被用得「多頻繁」，而不是「多近期」。計數頻率很誘人卻很脆弱：一個在啟動期間被大量使用的分頁，可能囤積一個巨大的計數，之後就算再也不被碰，也賴著不走。近期性——LRU 與老化所追蹤的東西——通常比原始的頻率更能預測近未來；這正是為什麼真實系統倚靠的是 LRU 這一家族，並用時鐘與老化來近似它。