磁盤調度算法

一次磁盤讀寫操作的時間由尋找（尋道）時間、延遲時間和傳輸時間決定： ^[1] 

1) 尋找時間T_s：活動頭磁盤在讀寫信息前，將磁頭移動到指定磁道所需要的時間。這個時間除跨越n條磁道的時間外，還包括啓動磁臂的時間s，即：Ts = m * n + s。式中，m是與磁盤驅動器速度有關的常數，約為0.2ms，磁臂的啓動時間約為2ms。

2)延遲時間T_r：磁頭定位到某一磁道的扇區（塊號）所需要的時間，設磁盤的旋轉速度為r，則：Tr = 1 / (2 * r)。對於硬盤，典型的旋轉速度為5400r/m，相當於一週11.1ms，則T_r為5.55ms;對於軟盤，其旋轉速度在300~600r/m之間，則T_r為50~100ms。

3) 傳輸時間T_t：從磁盤讀出或向磁盤寫入數據所經歷的時間，這個時間取決於每次所讀/寫的字節數b和磁盤的旋轉速度：Tt = b / (r * N)。式中，r為磁盤每秒鐘的轉數；N為一個磁道上的字節數。

在磁盤存取時間的計算中，尋道時間與磁盤調度算法相關，下面將會介紹分析幾種算法，而延遲時間和傳輸時間都與磁盤旋轉速度相關，且為線性相關，所以在硬件上，轉速是磁盤性能的一個非常重要的參數。

總平均存取時間T_a可以表示為：Ta = Ts + Tr + Tt。

雖然這裏給出了總平均存取時間的公式，但是這個平均值是沒有太大實際意義的，因為在實際的磁盤I/O操作中，存取時間與磁盤調度算法密切相關。調度算法直接決定尋找時間，從而決定了總的存取時間。

FCFS算法根據進程請求訪問磁盤的先後順序進行調度，這是一種最簡單的調度算法。該算法的優點是具有公平性。如果只有少量進程需要訪問，且大部分請求都是訪問簇聚的文件扇區，則有望達到較好的性能；但如果有大量進程競爭使用磁盤，那麼這種算法在性能上往往接近於隨機調度。所以，實際磁盤調度中考慮一些更為複雜的調度算法。 ^[1] 

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（磁道）

^[1]  SSTF算法選擇調度處理的磁道是與當前磁頭所在磁道距離最近的磁道，以使每次的尋找時間最短。當然，總是選擇最小尋找時間並不能保證平均尋找時間最小，但是能提供比FCFS算法更好的性能。這種算法會產生“飢餓”現象。

1、算法思想：優先選擇距當前磁頭最近的訪問請求進行服務，主要考慮尋道優先。

2、優點：改善了磁盤平均服務時間。

3、缺點：造成某些訪問請求長期等待得不到服務。

4、例子：對上例的磁盤訪問序列，可得磁頭移動的軌跡如下圖。

SCAN算法在磁頭當前移動方向上選擇與當前磁頭所在磁道距離最近的請求作為下一次服務的對象。由於磁頭移動規律與電梯運行相似，故又稱為電梯調度算法。SCAN算法對最近掃描過的區域不公平，因此，它在訪問局部性方面不如FCFS算法和SSTF算法好。 ^[1] 

算法思想：當設備無訪問請求時，磁頭不動；當有訪問請求時，磁頭按一個方向移動，在移 ^[2]  動過程中對遇到的訪問請求進行服務，然後判斷該方向上是否還有訪問請求，如果有則繼續掃描；否則改變移動方向，併為經過的訪問請求服務，如此反覆。如下圖所示：

掃描算法（電梯算法）的磁頭移動軌跡

2、優點：克服了最短尋道優先的缺點，既考慮了距離，同時又考慮了方向。

^[1]  在掃描算法的基礎上規定磁頭單向移動來提供服務，回返時直接快速移動至起始端而不服務任何請求。由於SCAN算法偏向於處理那些接近最裏或最外的磁道的訪問請求，所以使用改進型的C-SCAN算法來避免這個問題。

釆用SCAN算法和C-SCAN算法時磁頭總是嚴格地遵循從盤面的一端到另一端，顯然，在實際使用時還可以改進，即磁頭移動只需要到達最遠端的一個請求即可返回，不需要到達磁盤端點。這種形式的SCAN算法和C-SCAN算法稱為LOOK和C-LOOK調度。這是因為它們在朝一個給定方向移動前會查看是否有請求。注意，若無特別説明，也可以默認SCAN算法和C-SCAN算法為LOOK和C-LOOK調度。

^[1] 

^[1]