Learning Objectives
- 說明作業系統為什麼要管理記憶體：很多行程共用記憶體，又要彼此保護
- 把邏輯位址拆成頁號與偏移，透過頁表轉換成實體位址
- 說明虛擬記憶體與分頁錯誤：只把用到的頁放在記憶體，其餘留在磁碟
- 用 FIFO、LRU、OPT 計算分頁錯誤次數，說明 Belady 異常與輾轉現象
記憶體不夠時，電腦為什麼會變慢
你可能遇過：瀏覽器開了幾十個分頁，再開一個影片剪輯軟體，整台電腦突然變得很卡，硬碟燈一直閃； 或是手機切回一個 App，它要重新載入。這些都和記憶體管理有關。
記憶體（RAM）裡同時放著很多行程的程式碼與資料，作業系統要處理三個問題：
| 問題 | 例子 |
|---|---|
| 配置：每個行程放在哪裡？ | 瀏覽器、音樂播放器、作業系統本身都要一塊記憶體 |
| 保護：怎麼避免互相干擾？ | 一個有錯的程式不能改到別的程式的資料，更不能改到核心 |
| 不夠用時怎麼辦？ | 所有程式加起來需要的記憶體，比實際裝的還多 |
這一課的答案是分頁（paging）與虛擬記憶體（virtual memory）。今天的 Windows、macOS、Linux、Android、iOS 都使用這套機制。
分頁：把記憶體切成一樣大的格子
早期的做法是替每個程式找一段連續的記憶體。程式來來去去之後，空的地方變成很多零碎的小洞， 加起來夠大，卻沒有一段連續的空間放得下新程式，這叫外部碎片（external fragmentation）。
分頁換了一個想法：
- 把實體記憶體切成固定大小的框（frame），常見的大小是 4 KB（4096 位元組）。
- 把每個行程看到的記憶體也切成同樣大小的頁（page）。
- 每一頁可以放進任何一個空的框，不必連續。作業系統替每個行程維護一張頁表（page table），記錄「第幾頁放在第幾框」。
程式裡用的位址叫邏輯位址（logical address，也叫虛擬位址），真正送到記憶體晶片的叫實體位址（physical address）。 轉換的方法：
頁號 ＝ 邏輯位址 ÷ 頁大小 的商
偏移 ＝ 邏輯位址 ÷ 頁大小 的餘數
實體位址 ＝ 頁表[頁號] × 頁大小 ＋ 偏移
頁大小是 2 的次方，所以用二進位看更簡單：4 KB＝2¹² 位元組，邏輯位址的最後 12 位元就是偏移，前面的位元就是頁號。 換成實體位址時，偏移原封不動，只把頁號換成框號。
這個轉換每存取一次記憶體就要做一次，所以由 CPU 裡的硬體（記憶體管理單元，MMU）負責， 並用一個小快取（TLB）記住最近查過的頁表項目。作業系統的工作是維護頁表。
每個行程有自己的頁表。兩個行程都用邏輯位址 0x1000，會被對到不同的框，所以誰也看不到、改不到對方的資料。
用 Python 做一次位址轉換
頁表 page_table 的第 i 格是第 i 頁所在的框號，None 代表這一頁不在記憶體。看 //（整數除法）算出頁號、%（餘數）算出偏移，再用頁號當索引查頁表。上方的 ▲ 標出正在查的那一格。
虛擬記憶體與分頁錯誤
程式不會同時用到它所有的頁：一個文書軟體有拼字檢查、列印、匯出 PDF 等功能，你這一刻只用到其中一小部分。 虛擬記憶體就是利用這一點：只把現在用得到的頁放在記憶體，其他的頁留在磁碟上（Windows 叫分頁檔，Linux 叫置換空間 swap）， 頁表裡標示「不在記憶體」。
程式存取一個不在記憶體的頁時：
- 硬體查頁表發現這一頁不在記憶體，發出分頁錯誤（page fault），程式暫停。
- 作業系統找一個空的框；沒有空框，就挑一頁換出去（如果它被改過，要先寫回磁碟）。
- 從磁碟把需要的頁讀進這個框，更新頁表。
- 讓程式重新執行剛才那一個指令。程式本身完全感覺不到，只是慢了一點。
「分頁錯誤」聽起來像出錯，其實是正常的機制：程式一啟動時，幾乎每一頁都是第一次用到，都會發生分頁錯誤。
真正的錯誤是存取根本不屬於自己的位址，這時作業系統會結束程式（Linux 上會看到 Segmentation fault）。
虛擬記憶體帶來的好處：
- 程式可以使用比實體記憶體還大的位址空間。
- 同時放得下更多程式，因為每個只需要一部分在記憶體裡。
- 每個程式都以為自己從位址 0 開始、獨占一大片記憶體，寫程式的人不用煩惱實際放在哪裡。
歷史上，英國曼徹斯特大學與 Ferranti 公司在 1962 年完成的 Atlas 電腦，是第一台用分頁實作虛擬記憶體的電腦，當時稱為「單層儲存」（one-level store）。
想一想：分頁與位址轉換
每一頁 4096 位元組。邏輯位址 5000 的頁號與偏移是多少？
瀏覽器與音樂播放器兩個行程，都在程式裡存取邏輯位址 0x1000。會發生什麼事？
下面哪一個情況會發生「分頁錯誤」（page fault），而且是完全正常、不會讓程式被結束的？
分頁置換：記憶體滿了，要換出哪一頁
發生分頁錯誤、又沒有空框時，作業系統要選一頁換出去。選錯了，剛換出去的頁馬上又要用，就得再讀一次磁碟。 衡量的方式是：給一串程式依序用到的頁（參考串列），看各種方法會發生幾次分頁錯誤。
| 演算法 | 換出哪一頁 | 說明 |
|---|---|---|
| FIFO（先進先出） | 最早載入的那一頁 | 簡單，但最早進來的頁可能正好是最常用的 |
| LRU（最近最少使用） | 最久沒有被使用的那一頁 | 用「過去」猜「未來」：最近用過的，很可能馬上又要用 |
| OPT（最佳置換） | 未來最晚才會再用到的那一頁 | 錯誤次數最少，但要知道未來，真實系統做不到，只用來當比較的標準 |
LRU 的想法來自區域性（locality）：程式通常在一段時間裡反覆用到同一小群位址，例如迴圈裡的程式碼、正在處理的陣列。 真實的作業系統很少完整實作 LRU（每次存取都要記時間太花成本），多半用它的近似做法。
直覺上，框越多，分頁錯誤應該越少。1969 年 IBM 的研究人員 Bélády、Nelson、Shedler 發表論文指出， FIFO 有時候框變多、分頁錯誤反而變多，後來稱為 Belady 異常（Bélády's anomaly）。下面的程式與模擬器用的就是常見的例子： 參考串列 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。
用 Python 數 FIFO 的分頁錯誤
frames 串列就是記憶體裡的 3 個框，最早進來的頁在最左邊。每次參考一頁：已經在裡面就是命中；不在裡面就是分頁錯誤，框滿了就把最左邊那一頁踢掉，新的頁放到最右邊。數數看最後一共錯了幾次，再到下面的模擬器把框數改成 4 比一比。
輾轉現象：一直在搬頁，沒時間做事
如果同時執行太多程式，每個行程分到的框少於它「最近經常用到」的頁（工作集，working set）， 就會不停發生分頁錯誤：剛換出去的頁馬上又要用，讀回來又擠掉另一頁。電腦把大部分時間花在搬頁上， CPU 反而閒著等磁碟。這叫輾轉（thrashing）。
症狀：程式都變得非常慢、硬碟（或 SSD）一直忙碌、CPU 使用率卻不高。
解決方式：
- 關掉一些程式，讓剩下的行程有足夠的框（作業系統也可能自己暫停或結束一些行程，手機切回 App 要重新載入就是這個原因）。
- 加裝記憶體。
- 用比較快的 SSD 當置換空間可以減輕，但讀 SSD 仍然比讀記憶體慢很多，不能取代記憶體。
想一想：分頁置換
把上面 FIFO 範例的 capacity 改成 4，最後會印出什麼？
3 個框，參考串列 1, 2, 3, 1, 4, 2。用 LRU 會發生幾次分頁錯誤？
同時開了太多大型程式，電腦非常慢、硬碟一直忙碌，但 CPU 使用率很低。最可能的原因是？
重點整理
- 記憶體管理要解決配置、保護、不夠用三個問題。
- 分頁把記憶體切成固定大小的框，行程的位址空間切成同樣大小的頁；頁表記錄每一頁在哪個框。
- 頁號＝邏輯位址 ÷ 頁大小的商，偏移＝餘數；實體位址＝框號 × 頁大小＋偏移。轉換由 MMU 硬體做，作業系統維護頁表。
- 虛擬記憶體只把用得到的頁放在記憶體；用到不在記憶體的頁時發生分頁錯誤，作業系統從磁碟讀進來。存取不屬於自己的位址才是真正的錯誤。
- 置換演算法：FIFO 換出最早進來的、LRU 換出最久沒用的、OPT 換出最晚才用到的（理論上最好，實際做不到）。FIFO 會有 Belady 異常。
- 同時執行太多程式、框不夠時會發生輾轉，電腦忙著搬頁而不是做事。
下一課看作業系統管理的另一個資源：磁碟上的檔案與目錄，以及刪掉的檔案為什麼有時候救得回來。