移臂調(diào)度算法研究

張菊

(遼寧省交通高等?？茖W(xué)校，遼寧沈陽(yáng)110122)

磁盤(pán)是一種典型的共享存儲(chǔ)設(shè)備，允許多個(gè)作業(yè)進(jìn)程同時(shí)使用，而不是讓一個(gè)作業(yè)在整個(gè)執(zhí)行期間獨(dú)占.當(dāng)有很多進(jìn)程提出I/O請(qǐng)求時(shí)，對(duì)它們就有一個(gè)調(diào)度安排問(wèn)題:即讓誰(shuí)先用，讓誰(shuí)后用.當(dāng)一個(gè)進(jìn)程需要I/O時(shí)，它發(fā)出一個(gè)系統(tǒng)調(diào)用給操作系統(tǒng)，I/O請(qǐng)求要包含4方面必要的信息:輸入還是輸出、磁盤(pán)地址、內(nèi)存地址和傳送信息長(zhǎng)度.如果所要求的磁盤(pán)驅(qū)動(dòng)器和控制器是空閑的和可用的，則I/O請(qǐng)求被立即執(zhí)行;如果設(shè)備和控制器正在為其它進(jìn)程的I/O請(qǐng)求服務(wù)，則I/O請(qǐng)求必須排隊(duì)等待.訪問(wèn)磁盤(pán)信息時(shí)，要經(jīng)過(guò)移動(dòng)磁頭、扇區(qū)轉(zhuǎn)動(dòng)等待和讀寫(xiě)操作3個(gè)步驟，即先要把移動(dòng)臂移到相應(yīng)的柱面上，然后等待數(shù)據(jù)所在的扇區(qū)旋轉(zhuǎn)到磁頭位置下，最后讓指定的磁頭讀/寫(xiě)信息，完成數(shù)據(jù)的傳輸.因此，執(zhí)行一次磁盤(pán)的輸入輸出需要花費(fèi)的時(shí)間有:

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

(2)等待時(shí)間，將指定的扇區(qū)旋轉(zhuǎn)到磁頭下所需要的時(shí)間.

(3)傳輸時(shí)間，由磁頭進(jìn)行讀寫(xiě)操作，完成信息傳送所需要的時(shí)間.

其中，傳輸時(shí)間是設(shè)備固有的特性.要提高磁盤(pán)的使用效率，只能減少查找時(shí)間和等待時(shí)間，它們都與I/O在磁盤(pán)上的分布位置有關(guān).由于移動(dòng)臂的移動(dòng)是靠控制電路驅(qū)動(dòng)步進(jìn)電機(jī)來(lái)實(shí)現(xiàn)，它的運(yùn)動(dòng)速度相對(duì)于磁盤(pán)軸的旋轉(zhuǎn)要緩慢，因此，減少查找時(shí)間比減少等待時(shí)間更能提高磁盤(pán)的使用效率［1］.

根據(jù)用戶作業(yè)發(fā)出的磁盤(pán)I/O請(qǐng)求的柱面位置，來(lái)決定請(qǐng)求執(zhí)行順序的調(diào)度，被稱為“移臂調(diào)度”.移臂調(diào)度的目標(biāo)是使磁盤(pán)的平均尋道時(shí)間最少.移臂調(diào)度常采用的算法有:先來(lái)先服務(wù)、最短查找時(shí)間優(yōu)先調(diào)度算法、掃描算法和單項(xiàng)掃描調(diào)度算法［2－7］.

1 算法描述

(1)先來(lái)先服務(wù) FCFS(First Come First Served)

算法思想:它根據(jù)進(jìn)程請(qǐng)求訪問(wèn)磁盤(pán)的先后次序進(jìn)行調(diào)度.

這是一種最簡(jiǎn)單的磁盤(pán)調(diào)度算法.此算法的優(yōu)點(diǎn)是公平、簡(jiǎn)單，每個(gè)進(jìn)程的請(qǐng)求都能依次得到處理，不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長(zhǎng)時(shí)間得不到滿足的情況.但此算法由于未對(duì)尋道進(jìn)行優(yōu)化，如果I/O請(qǐng)求很多，移動(dòng)臂就有可能會(huì)里外地來(lái)回“振動(dòng)”，致使平均尋道時(shí)間可能較長(zhǎng)，極大地影響輸入/輸出的工作效率，因此這種算法并不理想.

(2)最短查找時(shí)間優(yōu)先SSTF(Shortest Seek Time First)

算法思想:把距離磁頭當(dāng)前位置最近的I/O請(qǐng)求作為下一次調(diào)度的對(duì)象，這就是最短查找時(shí)間優(yōu)先調(diào)度算法.

(3)掃描(SCAN)算法

算法思想:總是沿著磁盤(pán)移動(dòng)臂的移動(dòng)方向選擇距離磁頭當(dāng)前位置最近的I/O請(qǐng)求，作為下一次調(diào)度的對(duì)象.如果該方向上已無(wú)I/O請(qǐng)求，則改變方向，再做選擇.

該算法既考慮到要訪問(wèn)的磁道與當(dāng)前磁道的距離，又考慮到磁頭的當(dāng)前移動(dòng)方向，而且首先是方向一致，其次才是距離最短，從而避免了饑餓現(xiàn)象.因?yàn)樵撍惴ㄖ写蓬^的移動(dòng)規(guī)律與電梯類似，故稱為電梯算法(Elevator Controller).

LOOK算法［8－9］是SCAN算法的一種改進(jìn).磁頭只移動(dòng)到一個(gè)方向上最遠(yuǎn)的請(qǐng)求為止，接著馬上回頭，而不是繼續(xù)到磁盤(pán)的盡頭.這種形式SCAN算法稱為L(zhǎng)OOK算法.

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

算法思想:總是從0號(hào)柱面開(kāi)始由里向外移動(dòng)移動(dòng)臂，遇到有I/O請(qǐng)求就進(jìn)行處理，直到到達(dá)最后一個(gè)請(qǐng)求柱面;然后移動(dòng)臂立即帶動(dòng)磁頭不做任何服務(wù)地快速返回到0號(hào)柱面，開(kāi)始下一輪掃描.

該算法是SCAN算法的變種，提供了一個(gè)更為均勻的等待時(shí)間.

2 案例分析

假設(shè)有一個(gè)磁盤(pán)組共有200個(gè)柱面，每個(gè)柱面上有8個(gè)磁道，每個(gè)盤(pán)面被劃分成4個(gè)扇區(qū).編號(hào)從0開(kāi)始，假定讀寫(xiě)磁頭位于53號(hào)柱面，假設(shè)移動(dòng)臂移動(dòng)一個(gè)柱面需要3 ms，開(kāi)始調(diào)度時(shí)，有8個(gè)I/O請(qǐng)求等待訪問(wèn)磁盤(pán)，如表1所示.

表1 I/O請(qǐng)求序列Table 1 The request sequence in disk I/O

2.1 各種算法的移動(dòng)臂運(yùn)動(dòng)軌跡

(1)FCFS算法的移動(dòng)臂運(yùn)動(dòng)軌跡如圖1所示.

圖1 先來(lái)先服務(wù)(FCFS)調(diào)度算法移動(dòng)臂運(yùn)動(dòng)軌跡Fig.1 First come first served scheduling algorithm

(2)SSTF算法的移動(dòng)臂運(yùn)動(dòng)軌跡如圖2所示.

圖2 最短查找時(shí)間優(yōu)先(SSTF)調(diào)度算法移動(dòng)臂運(yùn)動(dòng)軌跡Fig.2 Shortest seek time First scheduling algorithm

(3)LOOK算法的移動(dòng)臂運(yùn)動(dòng)軌跡如圖3、圖4所示.

圖3 LOOK算法(1)移動(dòng)臂運(yùn)動(dòng)軌跡Fig.3 LOOK scheduling algorithm(1)

圖4 LOOK算法(2)移動(dòng)臂運(yùn)動(dòng)軌跡Fig.4 LOOK scheduling algorithm(2)

(4)CSCAN算法移動(dòng)臂運(yùn)動(dòng)軌跡如圖5所示.

圖5 單項(xiàng)掃描(CSCAN)調(diào)度算法移動(dòng)臂運(yùn)動(dòng)軌跡Fig.5 Circular SCAN scheduling algorithm

2.2 數(shù)據(jù)對(duì)比分析

將4種調(diào)度算法對(duì)同一I/O請(qǐng)求訪問(wèn)序列進(jìn)行調(diào)度，所得到的響應(yīng)次序如表2所示.

表2 各種調(diào)度算法的響應(yīng)次序(從53號(hào)柱面開(kāi)始)Table 2 Response sequence of various scheduling algorithms(From the 53 cylinder start)

所有請(qǐng)求訪問(wèn)柱面序列采用4種不同的調(diào)度算法的移動(dòng)距離、尋道時(shí)間等數(shù)據(jù)如表3所示.

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

可見(jiàn)，F(xiàn)CFS算法相對(duì)于各個(gè)請(qǐng)求進(jìn)程的到達(dá)順序來(lái)說(shuō)，對(duì)各個(gè)請(qǐng)求進(jìn)程是公平的，該算法也是非常簡(jiǎn)單、容易實(shí)現(xiàn)的，但是它的平均尋道時(shí)間最長(zhǎng)，效率最低，可以作為衡量其它算法標(biāo)準(zhǔn).

SSTF算法可以獲得較好的尋道性能，但它可能導(dǎo)致某些進(jìn)程發(fā)生饑餓現(xiàn)象(Starvation).因?yàn)橹灰粩嗟赜行逻M(jìn)程到達(dá)，而且其所要訪問(wèn)的磁道與磁頭當(dāng)前所在磁道的距離較近，這種新進(jìn)程的I/O請(qǐng)求必須被優(yōu)先滿足.如果磁盤(pán)負(fù)載很重，SSTF算法存在一個(gè)問(wèn)題:移動(dòng)臂大部分時(shí)間將停留在柱面中部區(qū)域，而兩端極端區(qū)域的請(qǐng)求將不得不等待，直到由于負(fù)載的統(tǒng)計(jì)波動(dòng)使得中部區(qū)域沒(méi)有請(qǐng)求位置.遠(yuǎn)離柱面中部區(qū)域的請(qǐng)求進(jìn)程得到的服務(wù)很差.例如位于183號(hào)柱面的請(qǐng)求進(jìn)程，雖然在請(qǐng)求序列中排在第2位，但是卻是最后一個(gè)被響應(yīng).顯然，SSTF和FCFS算法相比，將磁頭移動(dòng)減少了一半，SSTF算法雖然獲得了較短的尋道時(shí)間，但是獲得最短響應(yīng)時(shí)間的目標(biāo)和公平性之間存在著沖突，有失公平性.

LOOK算法是當(dāng)磁頭所移動(dòng)的方向上不再有請(qǐng)求時(shí)立即改變運(yùn)行方向，而CSCAN算法則需要移動(dòng)到最底層或者最頂層時(shí)才改變運(yùn)行方向.

LOOK(1)算法的平均響應(yīng)時(shí)間比SSTF算法略短，但是響應(yīng)時(shí)間方差比SSTF算法小很多，從統(tǒng)計(jì)學(xué)角度來(lái)講 LOOK(1)算法要比SSTF算法穩(wěn)定.

CSCAN算法是對(duì)SSTF算法的改進(jìn)，也是LOOK算法的變種，能防止老進(jìn)程出現(xiàn)饑餓現(xiàn)象，也能得到相對(duì)較好的尋道性能.但是，因?yàn)橐?guī)定了磁頭單向移動(dòng)，例如只能由外向里移動(dòng)，即當(dāng)磁頭移動(dòng)到最大磁道號(hào)后立刻返回到0號(hào)柱面，開(kāi)始下一次掃描，缺乏靈活性.

3 算法改進(jìn)

FCFS、SSTF、LOOK和CSCAN 4種移臂調(diào)度算法，都可能出現(xiàn)磁臂停留在某處不動(dòng)的情況，例如，有一個(gè)或幾個(gè)進(jìn)程對(duì)某一磁道有著較高的訪問(wèn)頻率，即它們反復(fù)請(qǐng)求對(duì)某一磁道進(jìn)行I/O，從而壟斷了整個(gè)磁盤(pán)設(shè)備.這一現(xiàn)象稱為磁臂粘著，在高密度磁盤(pán)上更容易出現(xiàn)此情況.下面改進(jìn)一下LOOK算法.

(1)N-Step-LOOK算法

算法思想:把磁盤(pán)I/O請(qǐng)求隊(duì)列分成若干個(gè)長(zhǎng)度為n的子隊(duì)列，磁盤(pán)調(diào)度將按FCFS算法依次處理這些子隊(duì)列.按LOOK算法處理每一個(gè)隊(duì)列，一個(gè)隊(duì)列處理完后再處理其它隊(duì)列.

N-Step-LOOK算法可以有效避免粘著現(xiàn)象.

說(shuō)明:當(dāng)n=1時(shí)，N-Step-LOOK算法退化為FCFS算法;當(dāng) n很大時(shí)，該算法接近于LOOK算法.

案例:假定當(dāng)前讀寫(xiě)磁頭位于53號(hào)柱面，則LOOK算法和N-Step-LOOK算法對(duì)同一個(gè)請(qǐng)求序列的響應(yīng)次序如表4所示.

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

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

(2)FLOOK算法

算法思想:把磁盤(pán)I/O請(qǐng)求隊(duì)列分成2個(gè)隊(duì)列.一個(gè)隊(duì)列:由當(dāng)前所有請(qǐng)求磁盤(pán)I/O的進(jìn)程組成，按LOOK算法處理;另一個(gè)隊(duì)列:由新出現(xiàn)的所有請(qǐng)求磁盤(pán)I/O的進(jìn)程組成.

FLOOK算法實(shí)質(zhì)是N-Step-LOOK算法的簡(jiǎn)化，即n=2.

4 結(jié)語(yǔ)

諸多移臂調(diào)度算法各有利弊，如何選擇一個(gè)最佳的算法很重要.FCFS算法簡(jiǎn)單，容易實(shí)現(xiàn)，但性能欠佳;SSTF算法較為普通而且很有吸引力，因?yàn)樗菷CFS算法的性能要好;LOOK和CSCAN算法對(duì)于磁盤(pán)負(fù)荷較大的系統(tǒng)會(huì)更好，因?yàn)樗鼈兡鼙苊狻梆囸I”現(xiàn)象的發(fā)生.對(duì)于一個(gè)特定的請(qǐng)求隊(duì)列，能定義一個(gè)最佳的執(zhí)行順序，但是查找最佳調(diào)度序列所需的時(shí)間有可能很長(zhǎng)，總的來(lái)說(shuō)可能并不比SSTF算法或FCFS算法節(jié)省時(shí)間.

總之，無(wú)論何種調(diào)度算法，其性能主要依賴于I/O請(qǐng)求的數(shù)量和類型，在設(shè)計(jì)操作系統(tǒng)的移臂調(diào)度算法時(shí)應(yīng)綜合考慮各種因素，特別是系統(tǒng)性能的要求，來(lái)進(jìn)行尋道算法的設(shè)計(jì)和選擇.

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

［2］ 湯子贏，哲鳳屏，湯小丹.計(jì)算機(jī)操作系統(tǒng)［M］.西安:西安電子科技大學(xué)出版社，1996:260－262.

［3］ 彭廣習(xí)，余勝生，周敬利.基于磁盤(pán)性能模型的優(yōu)化調(diào)度算法［J］.計(jì)算機(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］ 崔英志.面向多媒體應(yīng)用的磁盤(pán)調(diào)度算法研究［D］.重慶:重慶理工大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)系，2010:20－21.

［6］ Rahmani Hossein，F(xiàn)aghih 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］ 周湘貞，曾憲權(quán).操作系統(tǒng)原理與實(shí)踐教程［M］.北京:清華大學(xué)出版社，2006:305.

［9］ 張順香，朱廣麗.一種基于平均尋道時(shí)間的磁盤(pán)調(diào)度優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用，2009，29(4):1147－1150.