大容量儲存與磁碟排程

最短搜尋時間優先排程(SSTF scheduling)

/ ess-ess-tee-eff /

想像你站在自助餐前,菜餚沿著一條長檯一字排開,而你手裡有一張還想吃的菜單。貪婪的策略很簡單:總是走向此刻離你最近的那道想要的菜,吃掉它,然後再走向剩下中最近的一道。你踏出許多小步,而非擬定一個大計畫。SSTF 排程替磁碟臂做的就是這件事:從它目前的磁軌,總是服務磁軌最接近的那個待處理請求,把下一次搜尋降到最低。

具體來說,SSTF 代表最短搜尋時間優先。在佇列裡等待的所有 I/O 請求中,排程器挑出目標磁軌離讀寫頭目前位置最近的那一個,服務它,再從新位置重複。它是 CPU 排程中最短工作優先在磁碟排程裡的表親:一個在區域上把當下成本最小化的貪婪選擇。相較於單純的 FCFS,SSTF 通常能大幅削減臂的總移動量,因為臂傾向把附近成群的請求一起處理,而不是橫越磁片亂跳。

為什麼重要,以及它誠實的缺陷:SSTF 在平均搜尋時間上明顯優於 FCFS,但它可能造成飢餓。如果請求不斷地在讀寫頭目前位置附近湧入,一個指向遙遠磁軌的請求可能無限期等待下去——臂永遠沒有理由跑出去到它那裡。這正是貪婪的最近優先策略在各處都會有的同一個飢餓問題。它也不是最佳的:總是取最近的,可能讓臂被困在某處,逼得之後得跑一趟遠路。這些弱點正是電梯式的 SCAN 與 LOOK 演算法被發明出來的原因——它們穩定地掃過去,使任何請求都不會被永遠遺落。

讀寫頭在第 53 軌,佇列為 {98, 183, 37, 122, 14, 124, 65, 67}。SSTF 每次都走向最近的:65、67、37、14、98、122、124、183。總移動量遠少於 FCFS——但若靠近第 60 軌的新請求不斷湧入,第 183 軌那個孤零零的請求可能被一再延後。

貪婪且平均而言快速,但它可能餓死遠處的請求。

SSTF 把下一次搜尋而非所有請求的總搜尋降到最低,所以它不是最佳的——而它的貪婪則有飢餓風險。電梯演算法(SCAN、LOOK)以一點平均效能換取「每個請求終究會被服務」的保證。

又稱
SSTFshortest-seek-time-first最短尋道時間優先