線上分頁與快取（online paging and caching）

你的電腦有一塊小而快的記憶體（快取，或 RAM 的頁），只能裝 k 個項目，而你可能想要的資料住在一個巨大而慢的儲存裡。當程式要求一個已在快取裡的項目，那是「命中」，基本上免費。當它要求一個不在裡面的項目，那是「未命中」：你得把它取進來（慢），而且若快取已滿，就得丟掉 k 個項目之一來騰位子。整場遊戲就是一次又一次地選「該逐出哪一個」，而你不知道下一個會被要求什麼。這就是分頁，它本質上就是線上的。

由於逐出不可撤回、未來又被遮住，我們用「對抗 OPT 的競爭比」來評快取規則，OPT 是知道整串請求序列的離線最佳解。OPT 有一條著名而簡單的規則（Belady 規則）：未命中時，逐出「下次被用到最遠的未來」的那個項目。我們無法線上執行 OPT——它需要未來——但它是標尺。自然的線上規則是 LRU（最近最少使用）：逐出閒置最久的項目，賭「最近的過去能預測不久的未來」。一條漂亮的定理說 LRU（與 FIFO）恰好是 k-競爭的：在任何序列上它的未命中數最多約為 OPT 的 k 倍，而沒有確定性線上規則能保證好過 k。證明的想法是分階段論證：把序列切成若干階段，每階段含 k+1 個相異頁；OPT 每階段至少未命中一次，而 LRU 每階段最多未命中 k 次。

分頁是最早也最具影響力的線上問題，它解釋了為什麼你的 CPU、瀏覽器、資料庫都採用類 LRU 的策略。它也教了一個令人謙卑的道理：k-競爭聽起來很糟（LRU 可能比全知最佳解多未命中 k 倍），但那個因子只出現在「特意設計來打敗它」的對抗序列上；在有區域性（locality）的真實工作負載上，LRU 表現極佳。誠實的提醒：k-競爭界是最壞情況，隨機化策略（如 MARKER）能把期望比值改善到約 2*ln(k)，而「逐出最近最少使用者」是對未來的啟發式猜測，不是對它的保證。