Learning Objectives
- 追蹤 FIFO、LRU、OPT 的置換過程，算出分頁錯誤次數
- 說明 Belady 異常，以及為什麼 LRU 不會有這個問題
- 說明真正的 LRU 為什麼太貴，用 Clock 近似它，並寫出來
- 解釋髒頁為什麼讓換出的代價不一樣
- 解釋顛簸怎麼發生，用工作集說明要怎麼避免
記憶體不夠時要請誰離開
上一課說過，每個行程看到的位址空間遠比實體記憶體大，用到的頁加起來也可能超過實體記憶體。這時核心要挑一些頁請出去：
- 內容來自檔案、又沒被改過的頁（程式碼、頁快取）：直接丟掉，要用再從檔案讀回來。
malloc來的匿名頁、改過的頁：要先寫到磁碟的交換空間（swap）才能騰出來。
被請出去的頁再被用到時，就是 major fault：行程阻塞，等磁碟把資料讀回來。記憶體存取以奈秒計，磁碟 I/O 動輒微秒到毫秒，差好幾個數量級。所以置換演算法挑錯一頁，代價非常高，核心值得花心思挑。
衡量的標準很簡單：給定一串記憶體參照（reference string，只看頁號），分頁錯誤越少越好。
FIFO、LRU、OPT
| 演算法 | 換出誰 | 特性 |
|---|---|---|
| FIFO | 最早載入的頁 | 最好寫，但不管它是不是一直在用 |
| LRU | 最久沒被用過的頁 | 用過去預測未來，有區域性時效果好 |
| OPT | 下一次使用最晚的頁（之後不再用的優先） | 理論最佳，但要知道未來，只能當比較基準 |
用 Python 寫 LRU 只要幾行，和第 13 課的 TLB 完全相同的結構：
一步一步跑 LRU
注意第 4 個參照：第 1 頁又被用了一次，搬到最後面。所以第 5 個參照（第 4 頁）進來時，被換出的是第 2 頁，不是最早進來的第 1 頁。
Belady 異常：多一點記憶體，反而更多錯誤
剛才的 FIFO 跑出了違反直覺的結果：3 個頁框錯 9 次，4 個頁框反而錯 10 次。記憶體變多，表現卻變差。用程式再跑一次，看 frames 裡的內容怎麼走到不同的路上。
FIFO 的異常
同一串參照，4 個頁框的錯誤比 3 個多。這個現象由 Belady、Nelson 和 Shedler 在 1969 年發表，後來就叫 Belady 異常。
為什麼 LRU 和 OPT 不會有這個問題
LRU 和 OPT 有一個性質：n 個頁框裡的頁，一定是 n＋1 個頁框裡的頁的子集。LRU 留下的永遠是「最近用過的 n 頁」，多一個頁框只是多留一頁，所以錯誤次數不可能變多。這類演算法叫堆疊演算法（stack algorithm）。
FIFO 留下的是「最近載入的 n 頁」，頁框數不同時載入的順序也不同，這個包含關係不成立。
真正的 LRU 太貴
LRU 看起來簡單，但真正實作要在每一次記憶體存取時更新順序：一支程式每秒做幾億次存取，全部都要多做一次串列搬移，硬體和軟體都負擔不起。
硬體實際提供的是便宜得多的東西：第 13 課講過的頁表項裡，有一個 Accessed 位元（參考位元），CPU 存取這一頁時自動設成 1。
只有一個位元，無法排出順序，但可以回答「這頁最近有沒有被用過」。Clock（時鐘，也叫第二次機會，second chance）就只用這個位元來近似 LRU：
- 頁框排成一圈，有一根指針。
- 要換頁時看指針指的那一頁： - R＝1：最近用過，給它第二次機會，R 清成 0，指針往下。 - R＝0：一輪繞回來都沒人用，換出它。
- 命中時只需要硬體把 R 設成 1，什麼串列都不用動。
用得越頻繁的頁，R 越常被設回 1，越不容易被換掉。沒有 LRU 精確，但每次存取幾乎沒有額外成本。Clock 不是堆疊演算法，所以和 FIFO 一樣可能出現 Belady 異常；頁框很少、R 幾乎全是 1 時，它的行為就和 FIFO 相同。
髒頁：換出的代價不一樣
頁表項裡還有一個硬體自動設定的 Dirty 位元：這一頁被寫過就設成 1。
- 乾淨的頁（D＝0）：磁碟上的內容和記憶體一樣，換出時直接丟掉。
- 髒頁（D＝1）：要先寫回磁碟才能騰出頁框，多一次 I/O。
所以真實的系統偏好先換出乾淨的頁，並在背景定期把髒頁寫回，讓需要騰空間時已經有乾淨的頁可以用。下面的工具也畫出了 D 位元。
實作：寫出 Clock，和工具對答案
補完 clock。規則和工具一樣：命中時把 R 設成 1，指針不動；未命中時，指針指到空框或 R＝0 就放進去（R 設成 1，指針前進），指到 R＝1 就清成 0、指針前進。
這幾組輸入都是工具裡的預設情境，比較表上的 Clock 欄就是答案。最後兩行會看到 Clock 也有 Belady 異常。
顛簸：大家都在等磁碟
早期的系統會這樣調度：CPU 使用率低，就多放一個程式進來，好讓 CPU 不要閒著。
這個直覺在記憶體不夠時會翻車：
- 程式太多，每個人分到的頁框少於它正在用的頁。
- 分頁錯誤暴增，大家都阻塞著排隊等磁碟。
- CPU 閒下來了，調度器一看，再放更多程式進來。
- 每個人分到的頁框更少，回到第 1 步。
這叫顛簸（thrashing）：系統把幾乎所有時間花在搬頁面，什麼事都做不完。你的電腦開太多東西時，硬碟燈狂閃、滑鼠都不太動，就是這個狀況。
工作集
Peter Denning 在 1968 年提出工作集（working set）的概念：一個行程在最近一段時間內實際用到的頁。因為區域性，這個集合通常遠小於行程的全部記憶體，而且相對穩定，一段時間換一批。
由此得到的規則很簡單：一個行程的工作集要全部放得進記憶體，它才跑得動；放不下就不要讓它跑。所有工作集加起來超過實體記憶體時，正確的做法是暫停一些行程（把它們整個換出去），而不是讓大家一起搶。
下面這個工具的分頁錯誤率是用 LRU 實際跑出來的，CPU 使用率用等候網路公式算；時間參數是示意值，所以看形狀，不要看絕對數字。
Linux 怎麼處理
Linux 的回收比上面的演算法複雜（依 Linux 核心文件）：
- 背景的
kswapd在可用記憶體低於水位時開始回收，再低就由要記憶體的行程自己同步回收，這時它會被卡住。 - 回收的對象主要是頁快取和匿名頁；乾淨的檔案頁直接丟，髒的寫回，匿名頁寫到 swap。
- 真的回收不出來時，OOM killer（Out Of Memory killer）選一個行程殺掉，讓系統活下去。
一台 Linux 機器上的實際狀態：
MemTotal: 16079072 kB
MemAvailable: 14295692 kB
Cached: 7069036 kB
SwapTotal: 0 kB
SwapFree: 0 kB
Dirty: 2772 kB
/proc/sys/vm/swappiness: 60
/proc/sys/vm/overcommit_memory: 0
/proc/self/oom_score: 666
在真正的 Linux 上實際執行的結果（Compiler Explorer 的 Linux x86-64 環境，gcc 13.3，2026-11-04）。
SwapTotal是 0：這台機器沒有 swap，匿名頁無處可換，記憶體用完就只能靠 OOM killer。很多雲端主機和容器是這樣設定的。Cached佔了不少：頁快取是用來放檔案內容的「閒置記憶體」，需要時可以回收，所以MemAvailable遠大於真正什麼都沒放的量。overcommit_memory是 0：預設的樂觀配置，也就是第 14 課malloc成功卻不保證有記憶體的原因。oom_score：OOM killer 參考的分數，越高越容易被選中。
看到行程無故消失、dmesg 裡出現 Out of memory: Killed process，就是 OOM killer 做的。
確認一下
參照串 1,2,3,1,4，3 個頁框，用 LRU。第 4 頁進來時換出哪一頁？
把 LRU 的頁框從 3 個加到 4 個，分頁錯誤次數可能變多嗎？
作業系統為什麼普遍用 Clock 這類近似方法，而不是真正的 LRU？
一台伺服器 CPU 使用率只有 5%，磁碟一直是滿載，回應非常慢。下面哪個做法最可能有幫助？
置換時有兩頁都可以選，一頁 D＝0，一頁 D＝1。為什麼常常先換 D＝0 的？
重點整理
- FIFO 最簡單但不看使用情況；LRU 用過去預測未來；OPT 是看得到未來的比較基準。
- FIFO 有 Belady 異常（多一個頁框反而更多錯誤）；LRU、OPT 是堆疊演算法，不會有。
- 真正的 LRU 每次存取都要更新，太貴。Clock 只用硬體的參考位元近似它：R＝1 給第二次機會，R＝0 換出。
- 髒頁換出要多寫一次磁碟，所以系統偏好換乾淨的頁，並在背景把髒頁寫回。
- 工作集放不下記憶體時發生顛簸：CPU 閒著、磁碟滿載。此時要減少同時跑的行程，不是加更多。Linux 記憶體真的用完時有 OOM killer。
延伸閱讀：OSTEP 的 Beyond Physical Memory: Policies。
下一課離開記憶體，看 I/O：CPU 怎麼和磁碟、其他裝置打交道，磁碟排程又在排什麼。