分頁置換（page replacement）

想像一張只能同時攤開六本書的小書桌。你正在讀書，需要第七本書，但桌面已經滿了。在你能放下新書之前，必須先從桌上六本當中挑一本放回書架。電腦記憶體運作的方式一模一樣：實體 RAM 只能容納固定數量的頁，而當某個行程存取到一個不在記憶體裡的頁（發生分頁錯誤），但每個頁框都已被佔用時，作業系統就必須挑出一個常駐的頁丟出去，讓想要的頁有地方放。這個挑選並逐出的步驟，就是分頁置換。

用平實的步驟說明它的機制。發生分頁錯誤，作業系統先找有沒有空閒的頁框。如果有，很好——把頁載入再繼續。如果沒有空閒的，作業系統就執行分頁置換演算法挑出一個犧牲頁。只有當犧牲頁曾被修改過，才把它寫回後備儲存（否則磁碟上的副本本來就是正確的，可以省下這次寫入），接著把犧牲頁的分頁表項目標記為無效，把想要的頁讀進剛空出的頁框，更新分頁表，最後重新執行造成錯誤的那道指令。所以最壞情況下，一次錯誤可能要付出兩次磁碟操作：一次把犧牲頁寫出、一次把新頁讀進。

為什麼重要：分頁置換是虛擬記憶體假裝機器擁有比實際更多 RAM 的核心。它之所以行得通，是因為程式具有區域性——它們會在一段時間內反覆使用一小組頁——因此好的演算法可以逐出最不可能很快用到的頁，而把忙碌的頁留在記憶體裡。整場遊戲就是要把這個猜測做好，因為每一次猜錯都是一趟昂貴的磁碟之旅。