移臂調度算法研究

張菊

(遼寧省交通高等專科學校，遼寧沈陽110122)

磁盤是一種典型的共享存儲設備，允許多個作業進程同時使用，而不是讓一個作業在整個執行期間獨占.當有很多進程提出I/O請求時，對它們就有一個調度安排問題:即讓誰先用，讓誰后用.當一個進程需要I/O時，它發出一個系統調用給操作系統，I/O請求要包含4方面必要的信息:輸入還是輸出、磁盤地址、內存地址和傳送信息長度.如果所要求的磁盤驅動器和控制器是空閑的和可用的，則I/O請求被立即執行;如果設備和控制器正在為其它進程的I/O請求服務，則I/O請求必須排隊等待.訪問磁盤信息時，要經過移動磁頭、扇區轉動等待和讀寫操作3個步驟，即先要把移動臂移到相應的柱面上，然后等待數據所在的扇區旋轉到磁頭位置下，最后讓指定的磁頭讀/寫信息，完成數據的傳輸.因此，執行一次磁盤的輸入輸出需要花費的時間有:

(1)尋道時間，在移動臂的帶動下，把磁頭移動到指定柱面所需要的時間.

(2)等待時間，將指定的扇區旋轉到磁頭下所需要的時間.

(3)傳輸時間，由磁頭進行讀寫操作，完成信息傳送所需要的時間.

其中，傳輸時間是設備固有的特性.要提高磁盤的使用效率，只能減少查找時間和等待時間，它們都與I/O在磁盤上的分布位置有關.由于移動臂的移動是靠控制電路驅動步進電機來實現，它的運動速度相對于磁盤軸的旋轉要緩慢，因此，減少查找時間比減少等待時間更能提高磁盤的使用效率［1］.

根據用戶作業發出的磁盤I/O請求的柱面位置，來決定請求執行順序的調度，被稱為“移臂調度”.移臂調度的目標是使磁盤的平均尋道時間最少.移臂調度常采用的算法有:先來先服務、最短查找時間優先調度算法、掃描算法和單項掃描調度算法［2－7］.

1 算法描述

(1)先來先服務 FCFS(First Come First Served)

算法思想:它根據進程請求訪問磁盤的先后次序進行調度.

這是一種最簡單的磁盤調度算法.此算法的優點是公平、簡單，每個進程的請求都能依次得到處理，不會出現某一進程的請求長時間得不到滿足的情況.但此算法由于未對尋道進行優化，如果I/O請求很多，移動臂就有可能會里外地來回“振動”，致使平均尋道時間可能較長，極大地影響輸入/輸出的工作效率，因此這種算法并不理想.

(2)最短查找時間優先SSTF(Shortest Seek Time First)

算法思想:把距離磁頭當前位置最近的I/O請求作為下一次調度的對象，這就是最短查找時間優先調度算法.

(3)掃描(SCAN)算法

算法思想:總是沿著磁盤移動臂的移動方向選擇距離磁頭當前位置最近的I/O請求，作為下一次調度的對象.如果該方向上已無I/O請求，則改變方向，再做選擇.

該算法既考慮到要訪問的磁道與當前磁道的距離，又考慮到磁頭的當前移動方向，而且首先是方向一致，其次才是距離最短，從而避免了饑餓現象.因為該算法中磁頭的移動規律與電梯類似，故稱為電梯算法(Elevator Controller).

LOOK算法［8－9］是SCAN算法的一種改進.磁頭只移動到一個方向上最遠的請求為止，接著馬上回頭，而不是繼續到磁盤的盡頭.這種形式SCAN算法稱為LOOK算法.

(4)單項掃描算法CSCAN(Circular SCAN)

算法思想:總是從0號柱面開始由里向外移動移動臂，遇到有I/O請求就進行處理，直到到達最后一個請求柱面;然后移動臂立即帶動磁頭不做任何服務地快速返回到0號柱面，開始下一輪掃描.

該算法是SCAN算法的變種，提供了一個更為均勻的等待時間.

2 案例分析

假設有一個磁盤組共有200個柱面，每個柱面上有8個磁道，每個盤面被劃分成4個扇區.編號從0開始，假定讀寫磁頭位于53號柱面，假設移動臂移動一個柱面需要3 ms，開始調度時，有8個I/O請求等待訪問磁盤，如表1所示.

表1 I/O請求序列Table 1 The request sequence in disk I/O

2.1 各種算法的移動臂運動軌跡

(1)FCFS算法的移動臂運動軌跡如圖1所示.

圖1 先來先服務(FCFS)調度算法移動臂運動軌跡Fig.1 First come first served scheduling algorithm

(2)SSTF算法的移動臂運動軌跡如圖2所示.

圖2 最短查找時間優先(SSTF)調度算法移動臂運動軌跡Fig.2 Shortest seek time First scheduling algorithm

(3)LOOK算法的移動臂運動軌跡如圖3、圖4所示.

圖3 LOOK算法(1)移動臂運動軌跡Fig.3 LOOK scheduling algorithm(1)

圖4 LOOK算法(2)移動臂運動軌跡Fig.4 LOOK scheduling algorithm(2)

(4)CSCAN算法移動臂運動軌跡如圖5所示.

圖5 單項掃描(CSCAN)調度算法移動臂運動軌跡Fig.5 Circular SCAN scheduling algorithm

2.2 數據對比分析

將4種調度算法對同一I/O請求訪問序列進行調度，所得到的響應次序如表2所示.

表2 各種調度算法的響應次序(從53號柱面開始)Table 2 Response sequence of various scheduling algorithms(From the 53 cylinder start)

所有請求訪問柱面序列采用4種不同的調度算法的移動距離、尋道時間等數據如表3所示.

表3 各種調度算法的平均尋道時間Table 3 Average seek time of various scheduling algorithms(Millisecond)

可見，FCFS算法相對于各個請求進程的到達順序來說，對各個請求進程是公平的，該算法也是非常簡單、容易實現的，但是它的平均尋道時間最長，效率最低，可以作為衡量其它算法標準.

SSTF算法可以獲得較好的尋道性能，但它可能導致某些進程發生饑餓現象(Starvation).因為只要不斷地有新進程到達，而且其所要訪問的磁道與磁頭當前所在磁道的距離較近，這種新進程的I/O請求必須被優先滿足.如果磁盤負載很重，SSTF算法存在一個問題:移動臂大部分時間將停留在柱面中部區域，而兩端極端區域的請求將不得不等待，直到由于負載的統計波動使得中部區域沒有請求位置.遠離柱面中部區域的請求進程得到的服務很差.例如位于183號柱面的請求進程，雖然在請求序列中排在第2位，但是卻是最后一個被響應.顯然，SSTF和FCFS算法相比，將磁頭移動減少了一半，SSTF算法雖然獲得了較短的尋道時間，但是獲得最短響應時間的目標和公平性之間存在著沖突，有失公平性.

LOOK算法是當磁頭所移動的方向上不再有請求時立即改變運行方向，而CSCAN算法則需要移動到最底層或者最頂層時才改變運行方向.

LOOK(1)算法的平均響應時間比SSTF算法略短，但是響應時間方差比SSTF算法小很多，從統計學角度來講 LOOK(1)算法要比SSTF算法穩定.

CSCAN算法是對SSTF算法的改進，也是LOOK算法的變種，能防止老進程出現饑餓現象，也能得到相對較好的尋道性能.但是，因為規定了磁頭單向移動，例如只能由外向里移動，即當磁頭移動到最大磁道號后立刻返回到0號柱面，開始下一次掃描，缺乏靈活性.

3 算法改進

FCFS、SSTF、LOOK和CSCAN 4種移臂調度算法，都可能出現磁臂停留在某處不動的情況，例如，有一個或幾個進程對某一磁道有著較高的訪問頻率，即它們反復請求對某一磁道進行I/O，從而壟斷了整個磁盤設備.這一現象稱為磁臂粘著，在高密度磁盤上更容易出現此情況.下面改進一下LOOK算法.

(1)N-Step-LOOK算法

算法思想:把磁盤I/O請求隊列分成若干個長度為n的子隊列，磁盤調度將按FCFS算法依次處理這些子隊列.按LOOK算法處理每一個隊列，一個隊列處理完后再處理其它隊列.

N-Step-LOOK算法可以有效避免粘著現象.

說明:當n=1時，N-Step-LOOK算法退化為FCFS算法;當 n很大時，該算法接近于LOOK算法.

案例:假定當前讀寫磁頭位于53號柱面，則LOOK算法和N-Step-LOOK算法對同一個請求序列的響應次序如表4所示.

表4 LOOK算法和N-Step-LOOK算法的響應次序Table 4 Response sequence of LOOK algorithm and N-Step-LOOK algorithm

顯然，有4個進程反復請求對53號磁道進行磁盤I/O操作，如果采用LOOK算法，磁臂就會粘著在53號磁道上，從而壟斷了整個磁盤設備，不能及時響應其它進程的磁盤I/O請求，這樣對其它進程不公平.若采用N-Step-LOOK算法，假設令n=4，把磁盤I/O請求序列按長度為4劃分成2個子隊列，磁盤調度將按FCFS算法先處理隊列1，再處理隊列2，而隊列1和隊列2內部又是按LOOK算法處理.當正在處理隊列1或隊列2時，如果又出現新的磁盤I/O請求，便將新請求進程放入隊列3，依此類推.這樣就可避免出現粘著現象.當n值取得很大時，會使N-Step-LOOK算法的性能接近于LOOK算法的性能;當N=1時，N步 LOOK算法便蛻化為FCFS算法.

(2)FLOOK算法

算法思想:把磁盤I/O請求隊列分成2個隊列.一個隊列:由當前所有請求磁盤I/O的進程組成，按LOOK算法處理;另一個隊列:由新出現的所有請求磁盤I/O的進程組成.

FLOOK算法實質是N-Step-LOOK算法的簡化，即n=2.

4 結語

諸多移臂調度算法各有利弊，如何選擇一個最佳的算法很重要.FCFS算法簡單，容易實現，但性能欠佳;SSTF算法較為普通而且很有吸引力，因為它比FCFS算法的性能要好;LOOK和CSCAN算法對于磁盤負荷較大的系統會更好，因為它們能避免“饑餓”現象的發生.對于一個特定的請求隊列，能定義一個最佳的執行順序，但是查找最佳調度序列所需的時間有可能很長，總的來說可能并不比SSTF算法或FCFS算法節省時間.

總之，無論何種調度算法，其性能主要依賴于I/O請求的數量和類型，在設計操作系統的移臂調度算法時應綜合考慮各種因素，特別是系統性能的要求，來進行尋道算法的設計和選擇.

［1］ 宗大華，宗濤，陳吉人.操作系統［M］.3版.北京:人民郵電出版社，2011:119.

［2］ 湯子贏，哲鳳屏，湯小丹.計算機操作系統［M］.西安:西安電子科技大學出版社，1996:260－262.

［3］ 彭廣習，余勝生，周敬利.基于磁盤性能模型的優化調度算法［J］.計算機工程，2002，28(5):20－22.

［4］ Hu ming.A Disk Scheduling Algorithm:SPFF［J］.Wuhan University Journal ofNatural Sciences，2005，10(6):983－987.

［5］ 崔英志.面向多媒體應用的磁盤調度算法研究［D］.重慶:重慶理工大學計算機應用技術系，2010:20－21.

［6］ Rahmani Hossein，Faghih Mohammad Mehdi，Moghaddam Mohsen Ebrahimi.A New Real Time Diskscheduling Method Based on GSR Algorithm［J］.Journal of Systems and Software，2010，83(11): 2147－2164.

［7］ CHANG H P，CHANG R I，SHIH W K，et al.GSR: A Global Seek-optimizing Real-time Disk-scheduling Algorithm［J］.Journal of Systems and Software，2007，80(2):198－215.

［8］ 周湘貞，曾憲權.操作系統原理與實踐教程［M］.北京:清華大學出版社，2006:305.

［9］ 張順香，朱廣麗.一種基于平均尋道時間的磁盤調度優化算法［J］.計算機應用，2009，29(4):1147－1150.