4.2 分頁置換演算法（FIFO、LRU、Clock 與理論上界）#

置換問題：快取的宿命#

當分頁錯誤需要載入新頁而實體記憶體已滿，作業系統必須挑選一個「犧牲頁」（victim）逐出。挑得好不好，直接決定缺頁率（page fault rate），而一次缺頁要付出一次磁碟 I/O（數毫秒），是一次記憶體存取（約 100 奈秒）的一萬倍。設存取序列中缺頁率為 \(f\) ，則有效存取時間（EMAT）近似：

\[ \text{EMAT} \approx (1-f) \cdot t_{mem} + f \cdot t_{disk} \]

代入 \(t_{mem}=100\text{ns}\) 、 \(t_{disk}=5\text{ms}\) ：即使 \(f\) 只有 1%，EMAT 也膨脹到約 50 微秒——慢了 500 倍。置換演算法因此是記憶體管理的效率命脈。

置換問題本質上是快取替換問題：把實體記憶體視為虛擬位址空間的快取。這使它與 CPU 快取、資料庫緩衝池、CDN 快取共享同一套理論。歷史上，Belady（1966）在 IBM 的研究建立了此問題的科學框架，並以 Belady 反例證明一個反直覺現象：FIFO 在某些存取序列下，框架越多缺頁反而越多（Anomaly）——這證明 FIFO 不是「棧演算法」（stack algorithm），也促使研究者尋找有理論保證的演算法。

OPT：不可能實作的天花板#

最佳置換（OPT / Belady's MIN，Belady 1966）：逐出未來最久不會被使用的那頁。它需要預知未來，無法實作，但作為理論下界無可取代：任何線上演算法的缺頁數都以 OPT 為標竿。競賽分析中，LRU 對 OPT 的競爭比為 \(k\) （快取大小），這一結果由 Sleator 与 Tarjan（1985）的線上演算法理論嚴格化——LRU 是「從過去推未來」的啟發式中最接近 OPT 的，因為它依賴時間局部性這一真實程式行為。

範例：存取序列 1 2 3 4 1 2 5 1 2 3 4 5，3 個框架：

演算法	缺頁次數	註記
OPT	7	逐出未來最遠者
LRU	10	逐出過去最久未用
FIFO	9	逐出最早進入
FIFO（4 框架）	10	Belady 反例：框架多反而更差

FIFO 與 LRU：兩個極端#

FIFO#

維護進入順序佇列，逐出最早進入者。優點：實作 O(1)、無需硬體支援（不用存取位元）。缺點：它記錄的是「到達時間」而非「使用時間」，與局部性無關——經常被用的頁可能因「來得早」被逐出（如存放關鍵程式碼的那頁）。加上 Belady 反例，FIFO 是反面教材的常客，但注意：Linux 在 2.6.33（2010）之後的 split LRU 中確實包含 FIFO 式的「unevictable/unreclaimable」分級思想，簡單演算法未必一無是處。

LRU（Least Recently Used）#

逐出最久未被存取的頁。理論上：LRU 是棧演算法（無 Belady 反例），且在時間局部性強的工作負載下近似 OPT。實作的殘酷之處在每次記憶體存取都要更新「最近使用」資訊——由硬體在每次存取時自動完成才可行。兩種硬體支援：

計數器法：每頁配一個 time-of-use 暫存器，每次存取寫入全域時鐘；逐出時掃描取最小。需要 \(O(n)\) 掃描與大量計數器暫存器，硬體昂貴。
矩陣法 / 堆疊法：理論教材常見，實務罕用。

真正的工程答案是：完全精確的 LRU 從不在 CPU 的分頁硬體中實作。作業系統採用的是「近似 LRU」——以極小的硬體成本換取接近 LRU 的行為。

Clock 演算法：第二次機會#

參考位元（reference bit）#

硬體只需一個便宜的機制：每個 PTE 一個 R 位元（referenced/accessed bit），CPU 存取該頁時硬體自動置 1（TLB 命中時置在 TLB、回寫時落到 PTE），核心週期性清 0。這一個位元就是全部的硬體需求。

Clock（FIFO + R 位元 = 第二次機會）#

Second Chance / Clock（FIFO 的改良，教科書通行版本；工程原型可追溯至 Multics 與 1969 年後的 VMS 前身）把所有候選頁排成一個環，一個時針指針掃描：

struct pte { bool valid, referenced, dirty; int pfn; };

int clock_replace(pte_t *table, int n, int *hand) {
    while (true) {
        pte_t *p = &table[*hand];
        if (p->referenced) {
            p->referenced = 0;     // 給它第二次機會
            *hand = (*hand + 1) % n;
        } else {
            return *hand;          // R=0：選它犧牲
        }
    }
}

語意：R=1 表示「最近被用過」→ 清零、跳過（給第二次機會）；R=0 表示「一整圈都沒人碰」→ 逐出。最壞情況退化為 FIFO（全體 R=1 時掃兩圈），常見情況近似 LRU。一次位元、一個指針，買到 LRU 的八成效果——這是「近似」哲學的代表作。

變體：LFU、MFU 與改進 Clock#

LFU（最不常用）：逐出計數最小者；被一次性掃過的歷史污染，實務少用。
改進 Clock：同時看 R 與 D（dirty，髒位元），優先逐出「乾淨且未用」的頁——逐出乾淨頁不用寫回磁碟，省一次 I/O。此思路在 Linux 的「先掃檔案頁、後掃匿名頁」分層回收中延續。

真實系統：從 VMS 的分段 FIFO 到 Linux 的 multigenerational LRU#

VMS（DEC，1977–）：用「全域 FIFO＋FREELIST」的簡單機制取得優異表現——被逐出的頁先進 free list 尾端觀察幾秒（延遲重用），若期間又被存取則「軟錯誤」直接拿回，避免真 I/O。這個「逐出≠立即失效」的緩衝思想影響深遠。

Linux 的 split LRU：把頁分為「檔案頁（可從檔案重讀，clean 便宜）」與「匿名頁（必須寫 swap，貴）」，各配 active/inactive 兩個鏈結串列，以近似 Clock 的方式在鏈上掃描、降級、升級，並依記憶體壓力權衡兩類的回收比例（swappiness）。2022 年起核心合入 MGLRU（multigenerational LRU，Yu Zhao），以「世代（generation）」分層取代二元 active/inactive，用大批次掃描降低大型伺服器（數百 GB 記憶體）上回收的 CPU 開銷——演算法隨硬體尺度演化的最新實例。

反向思想：不置換——即記憶體超額承諾（overcommit）＋ OOM killer：Linux 預設不把 swap 當主要手段，記憶體真不夠時挑一個行程直接殺掉（OOM score 選犧牲者）。這是「與其低效抖動，不如快速失敗」的工程取捨，也是雲端容器 OOMKilled 事件的機制根源。

置換策略的比較總表#

演算法	需要的硬體	Belady 反例	近似度	實作成本	用在哪
OPT	預知未來	無	最優	不可能	理論上界
FIFO	無	有	差	O(1)	教學、特例
LRU	每存取更新	無	好（局部性強時）	硬體太貴	資料庫緩衝池（軟體模擬）
Clock	R 位元	無	接近 LRU	極低	幾乎所有 OS
改進 Clock	R＋D 位元	無	更好＋省 I/O	低	進階核心

理論視角：競爭分析與 Bélády 之後#

置換是線上演算法（online algorithm）的典型問題：決策當下看不到未來。Sleator-Tarjan（1985）證明 LRU 的競爭比為 \(k\) 且是確定性演算法中的最優；Borodin-El-Yaniv 的教科書將其體系化。隨機化方向上，MARKING／Random 演算法可達 \(O(\log k)\) 競爭比（Fiat 等人 1991）——「隨機逐出」在對抗性存取序列下遠優於任何確定性策略，這解釋了為何某些系統偏好隨機置換（也自然免疫於 Belady 式病態序列）。這條理論線如今延伸到 BDW/Flash 快取與 CDN 的 AdaptiveTTL、LRB（learning-augmented，2018 前後將機器學習預測接入置換決策）——OPT 的「預知未來」正在被 ML 模型近似，半個世紀前的理論天花板成為今日的工程方向。

與編譯器/虛擬機的關聯#

軟體管理的快取：JVM 的分代 GC 在「老年代回收」時面臨與分頁置換完全同構的問題（哪些物件該被搬走/回收），其 card table、remembered set 即是「R 位元＋dirty 追蹤」的 Java 版。
緩衝池置換：資料庫（InnoDB、PostgreSQL）在應用層重新實作 Clock/LRU 變體，因為 OS 分頁快取對「誰是熱頁」缺乏語意理解——在正確的層放正確的快取是系統設計的永恆課題。
編譯器的暫存器配置：圖著色暫存器配置（Chaitin，1981）本質上是「有限快速資源（暫存器）的置換問題」的編譯期版本；spill（溢出）即「逐出到記憶體」。OS 的分頁置換與編譯器的暫存器溢出，是同一數學問題在執行期與編譯期的兩次求解。

重點整理#

置換演算法的效率以缺頁率計，一次缺頁 ≈ 一萬次記憶體存取，EMAT 公式量化其代價。
OPT 是不可實作的理論下界；FIFO 有 Belady 反例；LRU 理論佳但硬體不可行。
Clock 演算法用一個 R 位元近似 LRU，是「以微小硬體換近似最優」的典範，統治了所有現代 OS。
競爭分析（Sleator-Tarjan 1985）為置換提供理論地圖；MGLRU 與 LRB 顯示該領域仍在活躍演化。