前言
磁盤是計算機中最重要的外部存儲設備之一。不同於內存，磁盤提供持久化存儲，但其訪問速度遠低於內存和CPU的處理速度。因此操作系統需要在磁盤訪問上做大量優化：既要保證正確性與公平性，又要儘量減少延遲、提高吞吐量。

文章目錄

• 計算機操作系統 - 設備管理

• 一、磁盤的物理結構與基本概念

• 為什麼要理解物理結構？

• 二、磁盤訪問時間的分解與數學模型

• 數值示例

• 三、磁盤調度問題的形式化描述
• 四、常見磁盤調度算法（詳解）

• 1. FCFS（ 先來先服務）
• 2. SSTF（最短尋道時間優先）
• 3. SCAN（電梯算法）與變體

• 五、實現細節與工程注意事項
• 六、性能度量與實驗方法
• 七、現代存儲（SSD）對磁盤調度的影響
• 總結

計算機操作系統 - 設備管理

一、磁盤的物理結構與基本概念

磁盤（以傳統機械硬盤 HDD 為例）可以抽象為若干同心圓與讀寫裝置的組合：

• 盤面（Platter）：磁性材料製成的圓盤，數據記錄在盤面上。
• 磁道（Track）：盤面上的同心圓—每個盤面有許多磁道。
• 扇區（Sector）：磁道被切分為多個扇區，是最小的物理記錄單元（常見：512B、4KB）。
• 柱面（Cylinder）：同一半徑上不同盤面上的磁道集合，讀寫時多個磁頭可同時對齊該柱面。
• 磁頭（Head）：用於讀寫的電磁裝置，懸浮在盤面上方。
• 制動手臂（Actuator Arm）：移動磁頭以對準不同磁道。
• 主軸（Spindle）：驅動盤面高速旋轉。

示意：多盤面同時旋轉時，磁頭在不同盤面上形成一組，可以同時訪問同一柱面上的不同扇區（但仍受尋道和旋轉延遲影響）。

為什麼要理解物理結構？

磁盤調度優化的目標與手段都直接來源於物理限制：磁頭移動（尋道）需要時間，盤片旋轉帶來延遲，數據傳輸速率有限——因此優先優化尋道通常最有效。

二、磁盤訪問時間的分解與數學模型

讀取一個扇區（或一個塊）通常包含三部分時間：

1. 尋道時間（Seek Time） ：磁頭從當前磁道移動到目標磁道所需時間。
2. 旋轉延遲（Rotational Latency） ：等待盤片旋轉使目標扇區到達磁頭下方。平均旋轉延遲通常為半圈時間 ，其中
3. 數據傳輸時間（Transfer Time） ：磁頭與磁盤之間實際讀寫數據所需時間，取決於接口帶寬與扇區大小。

總訪問時間可近似表示為：

[ T_{access} = T_{seek} + T_{rot} + T_{trans} ]

數值示例

• 若硬盤為 7200 RPM（每分鐘轉數），則一圈時間為 ，平均旋轉延遲約 （4.167 ms）。
• 尋道時間視具體機械構造而不同，一般在 1 ms 到 10 ms 之間。

從上述可見，尋道時間通常佔主導（尤其當磁頭跨越較大距離時），因此磁盤調度算法的優化目標通常是最小化平均尋道距離/時間。

三、磁盤調度問題的形式化描述

輸入：一組磁盤請求 ，每個請求包含目標磁道號與到達時間 。當前磁頭位於磁道 ，並具有移動方向（向內/向外）。

目標：按某種調度策略決定下一個要服務的請求，優化的度量通常包括：平均尋道時間、最大響應時間、吞吐量、公平性（避免飢餓）。

注意：若請求帶有優先級或實時約束，問題會變得更復雜，需引入優先級調度或實時調度理論。

四、常見磁盤調度算法（詳解）

下面逐一講解常見算法的原理、實現要點、複雜度、優缺點，並給出偽代碼與示例。

1. FCFS（ 先來先服務）

（FCFS, First Come First Served）
原理：按請求到達的時間順序處理。

偽代碼：

queue = 請求隊列(按到達時間)
while queue 非空:
    r = queue.pop_front()
    處理 r

時間複雜度：（逐個處理）。

優缺點：實現最簡單且公平，但不考慮尋道距離，可能產生大量不必要的磁頭移動，平均尋道時間可能較大。

適用場景：負載輕或請求時間序列本身已較局部化的場景。

2. SSTF（最短尋道時間優先）

（SSTF, Shortest Seek Time First）
原理：每次選擇距離當前磁頭位置

偽代碼（樸素實現）：

while requests 未完成:
choose r in requests that minimizes |r.track - h|
process r
h = r.track

時間複雜度：樸素實現 ，使用平衡樹或雙端隊列可優化到 。

優缺點：平均尋道時間通常較短，但可能造成遠端請求長期得不到服務（飢餓）。

邊界情況：若請求分佈高度不均，靠近中心的請求會頻繁被選擇，遠端請求遭遇延遲。

3. SCAN（電梯算法）與變體

原理（SCAN）：磁頭沿當前方向逐一掃描並處理遇到的請求，直到到達末端再反向掃描（類似電梯）。

偽代碼簡要：

方向 = outwards
while requests 未完成:
if 有 requests 在方向上:
按磁道順序處理這些 requests
else:
方向 = -方向

變體：

• LOOK：與SCAN類似，但磁頭只移動到當前方向上最後一個請求的磁道再反向（不移動到磁盤物理端點）。
• C-SCAN（Circular SCAN）：磁頭只在一個方向上服務請求，到達端點後立即返回起點（不服務返回途中請求），使響應分佈更均勻。
• C-LOOK：結合LOOK與C-SCAN思想，返回時跳回最小未處理請求處。

優缺點：

• 兼顧效率與公平性，能避免SSTF的嚴重飢餓問題。
• SCAN 在高負載下能提供較好的吞吐量；C-SCAN 在響應時間上更加均勻。

複雜度：排序請求（按磁道）成本 ，或在請求到達時維護有序結構以實現在線處理。

五、實現細節與工程注意事項

1. 在線 vs 離線：真實系統中請求是在線到達的，算法需能動態插入新請求並及時調整調度隊列。維護有序結構（如雙向鏈表、平衡樹、跳錶）有助於提高在線性能。
2. 請求合併（Request Merging）：相鄰或連續扇區的請求可以合併為一次I/O以降低開銷（尤其在文件系統層常見）。
3. 寫入策略：寫操作可延後（寫回）或立即寫入（直寫），寫緩衝與寫回策略會影響調度與數據一致性，需要與文件系統與緩存策略協同設計。
4. 實時/優先級請求：引入優先級後要權衡實時性與吞吐量，可能採取分級隊列或搶佔策略。
5. 接口與DMA：現代磁盤通過 DMA 或 NVMe 等接口實現高效傳輸，調度還要考慮傳輸通道的爭用。

六、性能度量與實驗方法

常用指標：

• 平均尋道時間、平均響應時間（包含等待與服務時間）、吞吐量（IOPS）、最大響應時間、公平性/飢餓發生率。

實驗建議：構造多種請求分佈（均勻、聚集、單向增長、隨機突發），以比較不同算法在不同場景下的表現。記錄並繪製平均響應時間和尋道距離隨時間變化的曲線，有助於直觀評估。

七、現代存儲（SSD）對磁盤調度的影響

固態硬盤（SSD）沒有機械尋道與旋轉延遲，讀寫延遲主要受 Flash 訪問、控制器調度與垃圾回收影響。因此經典 HDD 調度算法（以減少尋道為目標）對 SSD 的意義有限。相反，SSD 更關注：

• 寫放大（Write Amplification）與均衡寫入（Wear Leveling）
• 內部並行性（多個芯片/通道的調度）
• 控制器層的 GC（Garbage Collection）與映射表管理

在混合系統中（HDD + SSD 緩存），操作系統仍需基於設備特性選擇合適的調度策略。

總結

磁盤調度是操作系統設備管理中的基礎問題。理解磁盤的物理特性（尋道、旋轉、傳輸）是設計算法與優化策略的前提。FCFS、SSTF、SCAN 及其變體各有利弊：

• FCFS：簡單公平；
• SSTF：尋道短但易餓；
• SCAN/LOOK/C-SCAN/C-LOOK：在效率與公平間取得較好平衡。

在工程實踐中，需要結合硬件特性（HDD/SSD）、工作負載與文件系統策略來選擇或設計合適的調度方案。