Learning Objectives
- 比較輪詢、中斷、DMA 讓 CPU 付出什麼代價，並判斷什麼情況下輪詢反而比較好
- 說明硬碟一次讀取的時間花在哪裡，為什麼請求的順序會影響效能
- 算出 FCFS、SSTF、SCAN、C-SCAN、LOOK 的總移動距離，說出 SSTF 為什麼會餓死請求
- 說明 SSD 為什麼不需要這些排程，以及寫入放大、TRIM、RAID、頁快取各解決什麼問題
CPU 等得起硬碟嗎
你在程式裡寫一行 read(fd, buf, 4096)，CPU 下一個指令要的資料如果還在硬碟上，得等磁頭移過去、等碟片轉過來。這段時間以毫秒計；同一段時間，CPU 可以執行數百萬個指令。
裝置和 CPU 的速度差這麼多，作業系統要回答兩個問題：
- 等裝置的時候，CPU 要做什麼？ 一直問「好了沒」，還是先去做別的？資料由誰搬？
- 很多請求排隊的時候，先做哪一個？ 硬碟的磁頭有物理位置，順序不同，總時間差很多。
這一課先看第一個問題，再看第二個，最後看 SSD 怎麼把第二個問題改掉。
裝置驅動程式：核心和硬體之間的翻譯
每個裝置對 CPU 來說就是幾個暫存器：狀態（好了沒、有沒有出錯）、命令（要做什麼）、資料（要搬的內容）。不同廠牌的網路卡、磁碟控制器，暫存器長得都不一樣。
裝置驅動程式（device driver）是核心裡專門對付某一種裝置的程式碼，對上提供統一的介面（第 1 課的 read、write），對下照這個裝置的規矩操作暫存器。驅動程式跑在核心模式，寫錯了可以弄垮整台機器，這也是核心裡程式碼量很大的一塊。
接下來的問題就是：驅動程式下完命令之後，要怎麼等？有三種做法：
| 方式 | 等待時 CPU 在做什麼 | 資料由誰搬 |
|---|---|---|
| 輪詢（polling） | 一直讀狀態暫存器 | CPU |
| 中斷（interrupt） | 跑其他程式，裝置好了會打斷它 | CPU |
| DMA（Direct Memory Access，直接記憶體存取） | 跑其他程式 | DMA 控制器，全部完成才打斷 CPU |
硬碟的一次讀取花在哪裡
傳統硬碟（HDD）有旋轉的碟片和會移動的磁頭。一次讀取分成三段：
| 階段 | 做什麼 | 量級 |
|---|---|---|
| 尋軌（seek） | 磁頭移到正確的磁軌 | 數毫秒，距離越遠越久 |
| 旋轉等待（rotational latency） | 等目標磁區轉到磁頭下方 | 7200 RPM 轉一圈 60000 ÷ 7200 ≈ 8.33 毫秒，平均等半圈約 4.17 毫秒 |
| 傳輸（transfer） | 資料真的被讀出來 | 很短 |
前兩段都是機械動作，傳輸相比之下幾乎可以忽略。所以硬碟讀連續的資料很快（不用移動），讀分散的資料很慢（每次都要移動）。作業系統能控制的就是移動距離：把排隊的請求重新排序，讓磁頭少走路。 這就是磁碟排程。
下面用磁區編號代表位置，比較的是總移動距離。
磁碟排程演算法
| 演算法 | 規則 | 優點 | 代價 |
|---|---|---|---|
| FCFS | 照到達順序 | 公平、簡單 | 磁頭來回跑 |
| SSTF（最短尋軌優先） | 每次挑離磁頭最近的 | 總距離常常很短 | 遠端的請求可能一直等不到 |
| SCAN（電梯演算法） | 往一個方向服務到盡頭，再回頭 | 不會餓死 | 兩端的請求平均等比較久 |
| C-SCAN | 只在一個方向服務，到盡頭跳回另一端 | 等待時間比較平均 | 回程不服務，總距離變長 |
| LOOK／C-LOOK | 和 SCAN／C-SCAN 一樣，但前面沒有請求就提早轉向或跳回 | 省下跑到盡頭的距離 | 仍要等一輪 |
SSTF 和第 5 課的 SJF 是同樣的想法：每一步都做眼前最划算的，整體通常不錯，但不保證最好，也會讓人等很久。
用 Python 走一次 SSTF
請求和上面的互動練習相同。注意每服務一個請求，都要把剩下的請求全部看一遍，找最近的那個。
實作：寫出 LOOK
補完 look：磁頭一開始往編號變大的方向走，先服務所有編號大於等於磁頭的請求（由小到大），再回頭服務其他請求（由大到小）。回傳服務順序與總移動距離。
寫完可以到上面的互動練習輸入同一組請求，對照 LOOK 那一列。
SSD 把問題換了一個
SSD 用快閃記憶體，沒有機械零件，讀任何位置的時間幾乎相同，所以上面的排程目標（少走路）不再適用。Linux 可以為每個裝置選擇 I/O 排程器，查看的位置是 /sys/block/<裝置>/queue/scheduler，kernel.org 文件的範例長這樣（方括號是目前使用的）：
[mq-deadline] kyber bfq none
none 就是不重新排序，常用在速度很快的 NVMe SSD 上。硬碟則還是能從排序得到好處。
SSD 換來的是另一組限制：
- 讀寫單位是頁，抹除單位是區塊：一個區塊包含很多頁，快閃記憶體不能直接覆寫，要先抹除，而且只能整個區塊一起抹除。
- 所以改一頁資料的做法是寫到新的頁，舊的頁標成無效，由 SSD 裡的 FTL（Flash Translation Layer，快閃轉換層）記下對應關係。這和第 13 課的頁表是同樣的想法：邏輯位置和實體位置分開。
- 垃圾回收與寫入放大：一個區塊裡無效的頁多了要回收，還有效的頁得先搬走。使用者只寫了一次，快閃記憶體實際被寫了好幾次，這個比例叫寫入放大（write amplification）。快閃記憶體每個區塊的抹除次數有限，所以寫入放大直接影響壽命。
- TRIM：檔案系統刪除檔案時只改 metadata，SSD 不知道那些頁已經沒用，回收時還會白白搬它們。TRIM 是作業系統告訴 SSD「這些位置不要了」的命令，可以減少無謂的搬移。
判斷時要問：裝置的成本結構是什麼？硬碟的成本在移動，所以重排請求；SSD 的成本在抹除與回收，所以關心寫入量。
RAID 與頁快取
RAID（Redundant Array of Independent Disks）把多顆磁碟組成一個邏輯裝置：
| 等級 | 作法 | 4 顆 1 TB 的可用容量 | 壞一顆 |
|---|---|---|---|
| RAID 0 | 資料切開輪流寫到每一顆（striping） | 4 TB | 全部資料都沒了 |
| RAID 1 | 每份資料寫兩顆以上（mirroring） | 2 TB（兩兩成對） | 另一顆還有 |
| RAID 5 | 切開寫，加一份同位元（parity），輪流放在不同顆 | 3 TB | 用其他顆算回來 |
RAID 5 的同位元就是 XOR：1010 XOR 0110 = 1100，壞掉哪一份，把其他的 XOR 起來就得到它。代價是每次小寫入都要連帶更新同位元。
RAID 擋的是硬碟故障，不是備份：誤刪檔案、程式寫壞資料，所有磁碟會一起照做。
頁快取（page cache）是核心用閒置的記憶體存放最近讀寫過的檔案內容：
- 讀取：同一份資料第二次讀，不用碰磁碟。
- 寫入：
write通常只把資料放進頁快取就回傳了，之後才由核心寫到磁碟。
所以 write 回傳不代表資料已經在磁碟上。這帶來一個問題：斷電怎麼辦？下一課就處理這件事。
確認一下
磁頭在磁區 50，等待中的請求是 40、90、45。用 SSTF 的總移動距離是多少？
一台忙碌的伺服器用硬碟，請求不斷進來，偶爾有請求等了非常久。把排程從 SSTF 換成 SCAN，最可能的效果是什麼？
一張高速網路卡每秒收到大量封包，每個封包都發一次中斷。CPU 使用率滿載，但實際處理的封包反而變少。比較好的做法是什麼？
DMA 傳輸進行中，CPU 可以做什麼？
為什麼對 SSD 下 TRIM 有幫助？
公司用 4 顆硬碟組 RAID 5 存重要資料，所以不再做備份。有人誤刪了一個資料夾，會怎麼樣？
重點整理
- 輪詢讓 CPU 空轉，中斷讓 CPU 去做別的事但每次付切換成本，DMA 連搬資料都交出去，但有設定成本。沒有誰永遠最好：慢裝置用中斷，極快的裝置輪詢可能比較好，少量資料 DMA 不一定划算。
- 硬碟的時間花在尋軌和旋轉等待，所以要重排請求。SSTF 總距離短但會餓死請求，SCAN 系列用方向規定換取公平，LOOK 省掉跑到盡頭的距離。
- SSD 沒有移動成本，重排的意義不大；它的成本在抹除與回收，所以有 FTL、寫入放大與 TRIM。
- RAID 防硬碟故障，不防誤刪。頁快取讓讀寫變快，也讓
write回傳時資料可能還不在磁碟上。
下一課：檔案系統怎麼組織這些區塊，以及寫到一半斷電時怎麼救回來。