JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

磁碟排程：電梯演算法

當許多請求都在等同一支緩慢的磁碟臂時，你服務它們的順序會改變一切。這篇導覽會從最天真的順序一路建立到真正的磁碟用了數十年的電梯演算法——並誠實面對為什麼這整門技藝在固態硬碟上幾乎無關緊要。

為什麼為請求排序值得這番功夫

第 2 篇導覽留給你一個頑固的事實：在一顆硬碟上，一次存取最慢的部分是把磁臂移到正確的磁軌，也就是尋道時間。尋道是機械性的——一支實體的磁臂在碟片上來回擺動——它讓旋轉延遲與真正的傳輸都相形見絀。現在加上真實世界的轉折：一台繁忙的機器不會一次只要一個區塊。許多行程都有未完成的讀寫，所以在任一瞬間，磁碟手上都有一整列等待中的請求，每一個都指名碟片上某處的一個區塊。

槓桿就在這裡。磁臂一次只能在一個地方，而磁碟花掉的總時間，主要由磁臂走過的總距離決定。這些請求終究都得被服務，但「順序」由你決定。選得糟，磁臂就在碟片上來回乒乓、累積一堆尋道；選得好，它就平順地掃過去，用極小的移動服務許多請求。這個順序的選擇，正是所謂的磁碟排程。關鍵在於，排程在最要緊的意義上是「免費」的：它並沒有少讀任何區塊，它只是把同樣的工作重新排序，好削減彼此之間的移動。

天真的順序：公平但慢、貪心但不公

從顯而易見的策略開始：先到先服務（FCFS）。完全照請求抵達的順序服務，像銀行櫃檯前的單一隊伍。它非常公平——沒有任何請求會被插隊——而且實作起來輕而易舉。但公平忽略了地理。如果隊伍要的是區塊 98、183、37、122、14、124、65、67，而磁臂從 53 出發，FCFS 會讓磁臂跳到 98、退到 183、一路下到 37、上到 122、下到 14，如此往復。磁臂把整片碟片來回穿越好幾次，因為抵達順序裡相鄰的請求，在空間上毫不相干。

相反的直覺是貪心：永遠服務目前離磁臂最近的那個等待請求。那就是最短尋道時間優先（SSTF）。從 53 出發，它會抓 65、再抓 67、再 37、再 14，然後往上跳到 98、122、124、183——總移動量遠少於 FCFS，因為每一步都是當下最便宜的。如果 SSTF 讓你想起前面某一階 CPU 排程裡的最短工作優先，那並非巧合：它是同一個貪心的點子，也繼承了同樣的缺陷。一股穩定湧入、靠近磁臂當前位置的請求，可能一直餓死一個卡在遙遠邊緣的請求——這正是磁碟版的飢餓。那個遠處的區塊一等再等，而較近的區塊不斷插隊。

SCAN：把磁碟臂當成一部電梯

這就是為這篇導覽命名的點子。想想大樓的電梯怎麼運作。它不會貪心地衝去找最近按鈕的那個人。它選一個方向——譬如往上——然後一路往上，在每一個有等待呼叫的樓層停下，直到它上方再也沒有呼叫。接著它反向，往下掃，服務所有反方向的人。沒有人會被餓死，因為電梯保證會在它規律的來回中重新經過你的樓層。這正是磁碟的SCAN 演算法，也正是它舉世皆稱電梯演算法的原因。

機械上，SCAN 是這樣做的：磁臂朝碟片的一個方向移動，服務它經過的每一個請求，直到抵達盡頭（最後一個區塊）；然後它反向，在回程上服務沿途的一切。請求不再依抵達順序、也不再依純粹的遠近來服務，而是依它們落在這趟掃描上的位置。一個遠在邊緣的請求永遠不會餓死，因為每一趟完整的掃描都保證會抵達邊緣並服務它。你用 SSTF 那稍微短一點的總移動，換來了一個硬性的公平保證——而實務上，這趟平順的單向掃描反正也快，因為磁臂在一個來回中從不中途折返。

Queue (block numbers): 98 183 37 122 14 124 65 67   arm starts at 53, heading UP

  0        14   37   53   65 67     98       122 124        183        199
  |--------+----+----o----+--+------+--------+---+----------+----------|
  start at 53, sweep UP, serving in passing:
     53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183  (reach top end)
  then reverse and sweep DOWN:
                                        ... -> 37 -> 14

  SCAN order: 65, 67, 98, 122, 124, 183, (end), 37, 14
  Nobody at the far low end (14) starves: the down-sweep is guaranteed to reach it.
SCAN 從區塊 53 往上服務這個範例隊伍：一趟平順地掃到頂端，再一趟掃回底部——途中沒有折返，而遠處的區塊會在回程被抵達。

兩個微調：為了公平的 C-SCAN，與為了偷懶的 LOOK

單純的 SCAN 有一個微妙的不公平。當磁臂在某一端反向時，它剛剛經過的那些區塊很快又會在回程被再次服務，而最遠端的區塊卻等得最久。所以中段的請求被服務的頻率，大約是兩端的兩倍。C-SCAN（環狀 SCAN）的修法是把碟片當成一個圓：它只朝一個方向掃描、服務請求；當它撞到盡頭時，不反向，而是直接飛奔回最起點、回程途中什麼都不服務，然後展開另一趟單向掃描。如今每一個區塊等待的時間大致相同，因為每一個都在一趟一模一樣、均勻的掃描裡被造訪一次——更公平的等待時間，代價是每個週期要付一次長長的、不產生服務的回頭尋道。

第二個微調純粹是務實。單純的 SCAN 與 C-SCAN 就算外頭根本沒有請求，也會一路行軍到磁碟的實體盡頭——白白移動到一個空蕩的邊緣。LOOK（以及它的環狀表親 C-LOOK）只是說：在這個方向上只走到最後一個請求那裡，然後就反向（或繞回）。磁臂往前「看一眼」，發現再也沒有待辦的，便提早掉頭，而不是去撞牆。LOOK 幾乎總是真實實作真正採用的——它保住了電梯的公平，同時略過那段毫無意義、跑到邊框的移動。

  1. FCFS——照抵達順序服務。公平、極簡，但磁臂來回乒乓，總尋道極大。
  2. SSTF——永遠服務最近的等待請求。移動少很多，但局部貪心，可能餓死遠處的區塊。
  3. SCAN（電梯）——朝一個方向掃到盡頭，再反向。沒有飢餓，平順的單向移動。
  4. C-SCAN——只朝一個方向掃、跳回起點、重複。等待時間比 SCAN 更均勻，代價是那次跳回的尋道。
  5. LOOK／C-LOOK——像 SCAN／C-SCAN，但在最後一個請求處反向，而不是在實體邊緣。真實磁碟通常跑的版本。

誠實的但書：為什麼這在固態硬碟上幾乎無關緊要

以上的一切都靠一個假設：實體距離要花時間，因為有一支磁臂得移動。把那個假設抽走，整座建築就洩了氣。在一顆固態硬碟上，沒有磁臂、沒有碟片、沒有尋道——資料住在以電子方式存取的快閃晶片裡，區塊 14 並不比區塊 183 更遠。尋道時間既然消失了，電梯就沒什麼好最佳化的。重新排序請求來把磁臂移動最小化，幾乎替你省不了任何東西，因為本來就沒有任何磁臂移動可省。這是儲存裡最重要的誠實但書之一：那門精雕細琢了數十年的磁碟排程技藝，對固態硬碟幾乎沒幫助。

不過要小心別矯枉過正。「幾乎沒幫助」不等於「毫無作用」。固態硬碟仍受惠於另一種排序——例如把許多相鄰的小寫入合併成較少的大寫入，並善用裝置內部跨晶片的平行性。所以現代作業系統並不會在固態硬碟上單純跑那套經典電梯；舉例來說，Linux 提供了為快速裝置調校的排程器（甚至有一個「none」選項，把排序直接交給磁碟機自己的控制器）。但主旨依然成立：尋道最小化的排程，是一個關於旋轉鐵鏽的故事，而下一篇導覽會接著談「真正主宰固態硬碟行為」的東西。