磁碟調度在多道程式設計的計算機系統中，各個進程可能會不斷提出不同的對磁碟進行讀/寫操作的請求。由於有時候這些進程的傳送請求的速度比磁碟回響的還要快，因此我們有必要為每個磁碟設備建立一個等待佇列，常用的磁碟調度算法有以下四種：
先來先服務算法（FCFS），
最短尋道時間優先算法（SSTF），
掃描算法（SCAN），
循環掃描算法（CSCAN）
基本介紹
- 中文名：磁碟調度算法
- 類型：算法
- 分類：計算機作業系統
簡介,常用磁碟調度算法,先來先服務算法,最短尋找時間優先算法,掃描算法（又稱電梯算法）,循環掃描算法,比較,
簡介
一次磁碟讀寫操作的時間由尋找（尋道）時間、延遲時間和傳輸時間決定：
1) 尋找時間Ts：活動頭磁碟在讀寫信息前，將磁頭移動到指定磁軌所需要的時間。這個時間除跨越n條磁軌的時間外，還包括啟動磁臂的時間s，即：Ts = m * n + s。式中，m是與磁碟驅動器速度有關的常數，約為0.2ms，磁臂的啟動時間約為2ms。
2)延遲時間Tr：磁頭定位到某一磁軌的扇區（塊號）所需要的時間，設磁碟的旋轉速度為r，則：Tr = 1 / (2 * r)。對於硬碟，典型的旋轉速度為5400r/m，相當於一周11.1ms，則Tr為5.55ms;對於軟碟，其旋轉速度在300~600r/m之間，則Tr為50~100ms。
3) 傳輸時間Tt：從磁碟讀出或向磁碟寫入數據所經歷的時間，這個時間取決於每次所讀/寫的位元組數b和磁碟的旋轉速度：Tt = b / (r * N)。式中，r為磁碟每秒鐘的轉數；N為一個磁軌上的位元組數。
在磁碟存取時間的計算中，尋道時間與磁碟調度算法相關，下面將會介紹分析幾種算法，而延遲時間和傳輸時間都與磁碟旋轉速度相關，且為線性相關，所以在硬體上，轉速是磁碟性能的一個非常重要的參數。
總平均存取時間Ta可以表示為：Ta = Ts + Tr + Tt。
雖然這裡給出了總平均存取時間的公式，但是這個平均值是沒有太大實際意義的，因為在實際的磁碟I/O操作中，存取時間與磁碟調度算法密切相關。調度算法直接決定尋找時間，從而決定了總的存取時間。
常用磁碟調度算法
先來先服務算法
FCFS算法根據進程請求訪問磁碟的先後順序進行調度，這是一種最簡單的調度算法。該算法的優點是具有公平性。如果只有少量進程需要訪問，且大部分請求都是訪問簇聚的檔案扇區，則有望達到較好的性能；但如果有大量進程競爭使用磁碟，那么這種算法在性能上往往接近於隨機調度。所以，實際磁碟調度中考慮一些更為複雜的調度算法。
1、算法思想：按訪問請求到達的先後次序服務。
2、優點：簡單，公平。
3、缺點：效率不高，相鄰兩次請求可能會造成最內到最外的柱面尋道，使磁頭反覆移動，增加了服務時間，對機械也不利。
4、例子：
假設磁碟訪問序列：98，183，37，122，14，124，65，67。讀寫頭起始位置：53。求：磁頭服務序列和磁頭移動總距離（道數）。
由題意和先來先服務算法的思想，得到下圖所示的磁頭移動軌跡。由此：
磁頭服務序列為：98，183，37，122，14，124，65，67
磁頭移動總距離=（98-53）+（183-98）+|37-183|+（122-37）+|14-122|+（124-14）+|65-124|+（67-65）=640（磁軌）
FCFS最短尋找時間優先算法
SSTF算法選擇調度處理的磁軌是與當前磁頭所在磁軌距離最近的磁軌，以使每次的尋找時間最短。當然，總是選擇最小尋找時間並不能保證平均尋找時間最小，但是能提供比FCFS算法更好的性能。這種算法會產生“飢餓”現象。
1、算法思想：優先選擇距當前磁頭最近的訪問請求進行服務，主要考慮尋道優先。
2、優點：改善了磁碟平均服務時間。
3、缺點：造成某些訪問請求長期等待得不到服務。
4、例子：對上例的磁碟訪問序列，可得磁頭移動的軌跡如下圖。
掃描算法（又稱電梯算法）
SCAN算法在磁頭當前移動方向上選擇與當前磁頭所在磁軌距離最近的請求作為下一次服務的對象。由於磁頭移動規律與電梯運行相似，故又稱為電梯調度算法。SCAN算法對最近掃描過的區域不公平，因此，它在訪問局部性方面不如FCFS算法和SSTF算法好。
算法思想：當設備無訪問請求時，磁頭不動；當有訪問請求時，磁頭按一個方向移動，在移動過程中對遇到的訪問請求進行服務，然後判斷該方向上是否還有訪問請求，如果有則繼續掃描；否則改變移動方向，並為經過的訪問請求服務，如此反覆。如下圖所示：
掃描算法（電梯算法）的磁頭移動軌跡
2、優點：克服了最短尋道優先的缺點，既考慮了距離，同時又考慮了方向。
循環掃描算法
在掃描算法的基礎上規定磁頭單向移動來提供服務，回返時直接快速移動至起始端而不服務任何請求。由於SCAN算法偏向於處理那些接近最里或最外的磁軌的訪問請求，所以使用改進型的C-SCAN算法來避免這個問題。
釆用SCAN算法和C-SCAN算法時磁頭總是嚴格地遵循從盤面的一端到另一端，顯然，在實際使用時還可以改進，即磁頭移動只需要到達最遠端的一個請求即可返回，不需要到達磁碟端點。這種形式的SCAN算法和C-SCAN算法稱為LOOK和C-LOOK調度。這是因為它們在朝一個給定方向移動前會查看是否有請求。注意，若無特別說明，也可以默認SCAN算法和C-SCAN算法為LOOK和C-LOOK調度。
比較
| 優點 | 缺點 | |
|---|---|---|
FCFS算法 | 公平、簡單 | 平均尋道距離大，僅套用在磁碟I/O較少的場合 |
SSTF算法 | 性能比“先來先服務”好 | 不能保證平均尋道時間最短，可能出現“飢餓”現象 |
SCAN算法 | 尋道性能較好，可避免“飢餓”現象 | 不利於遠離磁頭一端的訪問請求 |
C-SCAN算法 | 消除了對兩端磁軌請求的不公平 | -- |
