第五章 磁盤(pán)移臂調(diào)度算法

1、5.4.1 磁盤(pán)移臂調(diào)度磁盤(pán)移臂調(diào)度 磁盤(pán)是對(duì)被多個(gè)進(jìn)程共享的設(shè)備。當(dāng)有多個(gè)進(jìn)磁盤(pán)是對(duì)被多個(gè)進(jìn)程共享的設(shè)備。當(dāng)有多個(gè)進(jìn)程都請(qǐng)求訪問(wèn)磁盤(pán)時(shí)，應(yīng)采用一種適當(dāng)?shù)恼{(diào)度算法，程都請(qǐng)求訪問(wèn)磁盤(pán)時(shí)，應(yīng)采用一種適當(dāng)?shù)恼{(diào)度算法，以使各進(jìn)程對(duì)磁盤(pán)的平均訪問(wèn)（主要是尋道）時(shí)間以使各進(jìn)程對(duì)磁盤(pán)的平均訪問(wèn)（主要是尋道）時(shí)間最小。由于在訪問(wèn)磁盤(pán)的時(shí)間中、主要是尋道時(shí)間，最小。由于在訪問(wèn)磁盤(pán)的時(shí)間中、主要是尋道時(shí)間，因此，磁盤(pán)調(diào)度的目標(biāo)應(yīng)是使磁盤(pán)的平均尋道時(shí)間因此，磁盤(pán)調(diào)度的目標(biāo)應(yīng)是使磁盤(pán)的平均尋道時(shí)間最少。最少。 常用的磁盤(pán)調(diào)度算法有：常用的磁盤(pán)調(diào)度算法有： 先來(lái)先服務(wù)；先來(lái)先服務(wù)； 最短尋道時(shí)間優(yōu)先；最短尋道時(shí)間優(yōu)先；

2、 掃描算法；掃描算法； 循環(huán)掃描算法循環(huán)掃描算法等等一、先來(lái)先服務(wù)一、先來(lái)先服務(wù)FCFS (First-Come, First-Served) 這是一種最簡(jiǎn)單的磁盤(pán)調(diào)度算法。它根這是一種最簡(jiǎn)單的磁盤(pán)調(diào)度算法。它根據(jù)進(jìn)程請(qǐng)求訪問(wèn)磁盤(pán)的先后次序進(jìn)行調(diào)度。據(jù)進(jìn)程請(qǐng)求訪問(wèn)磁盤(pán)的先后次序進(jìn)行調(diào)度。 在任何時(shí)候，都有許多在任何時(shí)候，都有許多I/O請(qǐng)求在排隊(duì)等請(qǐng)求在排隊(duì)等待。每次當(dāng)調(diào)用進(jìn)程從磁盤(pán)讀出時(shí)，首先要待。每次當(dāng)調(diào)用進(jìn)程從磁盤(pán)讀出時(shí)，首先要把磁頭定位到它所要求的正確磁道上。移動(dòng)把磁頭定位到它所要求的正確磁道上。移動(dòng)磁頭所需時(shí)間取決于磁頭必須移動(dòng)多遠(yuǎn)的距磁頭所需時(shí)間取決于磁頭必須移動(dòng)多遠(yuǎn)的距離。下頁(yè)表是

3、一作用于等待的離。下頁(yè)表是一作用于等待的I/O進(jìn)程請(qǐng)求其進(jìn)程請(qǐng)求其要求讀出的磁道的分布情況。要求讀出的磁道的分布情況。 當(dāng)前磁道=100進(jìn)程號(hào) 磁道號(hào) 移動(dòng)距離(磁道數(shù)) 4 19 81 9 376 357 23 205 171 7 134 71 34 18 116 22 56 38 14 192 136 3 396 204 32 29 367 17 3 26 12 19 16 29 40 21磁頭移動(dòng)的總距離=1604 (磁道) 其中進(jìn)程是按其發(fā)出其中進(jìn)程是按其發(fā)出請(qǐng)求的先后順序排列的。請(qǐng)求的先后順序排列的。采用的是采用的是FCFS調(diào)度策略。調(diào)度策略。完成這組完成這組I/O操作需移動(dòng)操作需移

4、動(dòng)磁頭的總距離為磁頭的總距離為1604磁道。磁道。 優(yōu)點(diǎn)：優(yōu)點(diǎn)：公平、簡(jiǎn)單，且公平、簡(jiǎn)單，且每個(gè)進(jìn)程的請(qǐng)求都能依次每個(gè)進(jìn)程的請(qǐng)求都能依次得到處理，不會(huì)出現(xiàn)某進(jìn)得到處理，不會(huì)出現(xiàn)某進(jìn)程的請(qǐng)求長(zhǎng)期得不到滿足程的請(qǐng)求長(zhǎng)期得不到滿足的情況。的情況。 缺點(diǎn)：缺點(diǎn)：與后面講的幾種與后面講的幾種調(diào)度算法相比，其平均尋道距離較大。故此算法僅調(diào)度算法相比，其平均尋道距離較大。故此算法僅適用于請(qǐng)求磁盤(pán)上的進(jìn)程數(shù)較少的場(chǎng)合。適用于請(qǐng)求磁盤(pán)上的進(jìn)程數(shù)較少的場(chǎng)合。例：例：假定磁盤(pán)共有40個(gè)柱面，當(dāng)前磁頭正在第11道服務(wù)，等待服務(wù)的進(jìn)程有6個(gè)，它們請(qǐng)求的柱面分別是：1, 36, 16, 34, 9 和 12 (以請(qǐng)求時(shí)間

5、先后為序)。按按FCFS算法：算法：移動(dòng)為：11 1 36 16 34 9 12總移動(dòng)柱面數(shù)：10+35+20+18+25+3 = 111思考：思考：假設(shè)磁盤(pán)訪問(wèn)序列：假設(shè)磁盤(pán)訪問(wèn)序列： 98, 183, 37, 122, 14, 124, 65, 67讀寫(xiě)頭起始位置：讀寫(xiě)頭起始位置：53試安排磁頭服務(wù)序列，并計(jì)算磁頭移動(dòng)總距離試安排磁頭服務(wù)序列，并計(jì)算磁頭移動(dòng)總距離(道數(shù)道數(shù))二、最短尋道時(shí)間優(yōu)先二、最短尋道時(shí)間優(yōu)先SSTF(Shortset Seek Time First) 第一種改進(jìn)方法是：第一種改進(jìn)方法是：最短尋找時(shí)間優(yōu)先最短尋找時(shí)間優(yōu)先(SSTF)的調(diào)度方法的調(diào)度方法。采用這種調(diào)。采

6、用這種調(diào)度策略，每當(dāng)啟動(dòng)一個(gè)新度策略，每當(dāng)啟動(dòng)一個(gè)新的磁盤(pán)的磁盤(pán) I/O操作時(shí)，首先操作時(shí)，首先查看這個(gè)等待請(qǐng)求的掛起查看這個(gè)等待請(qǐng)求的掛起隊(duì)列，找出其中尋找時(shí)間隊(duì)列，找出其中尋找時(shí)間最短的進(jìn)程。最短的進(jìn)程。 按此策略完成這組按此策略完成這組I/O操作需移動(dòng)磁頭的總距離操作需移動(dòng)磁頭的總距離為為700磁道。磁道。(如右圖所示如右圖所示) 當(dāng)前磁道=100進(jìn)程號(hào) 磁道號(hào) 移動(dòng)距離(磁道數(shù)) 7 134 34 14 192 58 23 205 13 22 56 149 29 40 16 32 29 11 4 19 10 12 19 0 34 18 1 17 3 15 9 376 373 3 396

7、 20磁頭移動(dòng)的總距離=700 (磁道) 該策略隱含有一個(gè)難以捉摸的問(wèn)題：這該策略隱含有一個(gè)難以捉摸的問(wèn)題：這就是有些進(jìn)程將會(huì)就是有些進(jìn)程將會(huì)“餓死餓死”。如假定在進(jìn)程。如假定在進(jìn)程9(要求讀出磁道要求讀出磁道376上的信息上的信息)的請(qǐng)求得到服的請(qǐng)求得到服務(wù)之前的某段時(shí)間，系統(tǒng)又收到一個(gè)請(qǐng)求流，務(wù)之前的某段時(shí)間，系統(tǒng)又收到一個(gè)請(qǐng)求流，而且這而且這些請(qǐng)求些請(qǐng)求所要求移動(dòng)的磁道數(shù)均小于所要求移動(dòng)的磁道數(shù)均小于376所移動(dòng)的距離，因而進(jìn)程所移動(dòng)的距離，因而進(jìn)程9和進(jìn)程和進(jìn)程3永遠(yuǎn)永遠(yuǎn)得不到服務(wù)。得不到服務(wù)。 優(yōu)點(diǎn)：優(yōu)點(diǎn)：改善了磁盤(pán)平均服務(wù)時(shí)間；改善了磁盤(pán)平均服務(wù)時(shí)間； 缺點(diǎn)：缺點(diǎn)：造成某些訪問(wèn)請(qǐng)求

8、長(zhǎng)期等待得不造成某些訪問(wèn)請(qǐng)求長(zhǎng)期等待得不到服務(wù)到服務(wù)例：例：假定磁盤(pán)共有40個(gè)柱面，當(dāng)前磁頭正在第11道服務(wù)，等待服務(wù)的進(jìn)程有6個(gè)，它們請(qǐng)求的柱面分別是：1, 36, 16, 34, 9 和 12 。按按SSTF算法：算法：移動(dòng)為：11 12 9 16 1 34 36總移動(dòng)柱面數(shù)：1+3+7+15+33+2 = 61由此可知總的柱面移動(dòng)數(shù)為61， 明顯地優(yōu)于FCFS。思考：思考：假設(shè)磁盤(pán)訪問(wèn)序列：假設(shè)磁盤(pán)訪問(wèn)序列： 98, 183, 37, 122, 14, 124, 65, 67讀寫(xiě)頭起始位置：讀寫(xiě)頭起始位置：53試安排磁頭服務(wù)序列，并計(jì)算磁頭移動(dòng)總距離試安排磁頭服務(wù)序列，并計(jì)算磁頭移動(dòng)總距

9、離(道數(shù)道數(shù))三、掃描三、掃描(SCAN)算法算法（電梯調(diào)度算法）（電梯調(diào)度算法） 具體做法：具體做法：當(dāng)設(shè)備無(wú)訪問(wèn)請(qǐng)求時(shí)，磁頭不動(dòng)；當(dāng)設(shè)備無(wú)訪問(wèn)請(qǐng)求時(shí)，磁頭不動(dòng)；當(dāng)有訪問(wèn)請(qǐng)求時(shí)，磁頭按一個(gè)方向移動(dòng)，在移動(dòng)過(guò)當(dāng)有訪問(wèn)請(qǐng)求時(shí)，磁頭按一個(gè)方向移動(dòng)，在移動(dòng)過(guò)程中對(duì)遇到的訪問(wèn)請(qǐng)求進(jìn)行服務(wù)，然后判斷該方向程中對(duì)遇到的訪問(wèn)請(qǐng)求進(jìn)行服務(wù)，然后判斷該方向上是否還有訪問(wèn)請(qǐng)求，如果有則繼續(xù)掃描；否則改上是否還有訪問(wèn)請(qǐng)求，如果有則繼續(xù)掃描；否則改變移動(dòng)方向，并為經(jīng)過(guò)的訪問(wèn)請(qǐng)求服務(wù)，如此反復(fù)變移動(dòng)方向，并為經(jīng)過(guò)的訪問(wèn)請(qǐng)求服務(wù)，如此反復(fù). . 按按此策略完成這組按按此策略完成這組I/O操作需移動(dòng)磁頭的總距操作需移動(dòng)磁頭

10、的總距離為離為490磁道磁道。( (如右下圖所示如右下圖所示) ) 當(dāng)前磁道=100 移動(dòng)方向=OUT(向0道)進(jìn)程號(hào) 磁道號(hào) 移動(dòng)距離(磁道數(shù)) 22 56 44 29 40 16 32 29 11 4 19 10 12 19 0 34 18 1 17 3 15 7 134 131(移動(dòng)方向=IN) 14 192 58 23 205 13 9 376 171 3 396 20磁頭移動(dòng)的總距離=490 (磁道) 該方法克服了最短該方法克服了最短尋道優(yōu)先的缺點(diǎn)，既考尋道優(yōu)先的缺點(diǎn)，既考慮了距離，同時(shí)又考慮慮了距離，同時(shí)又考慮了方向。了方向。 但是，必須說(shuō)明，但是，必須說(shuō)明，這種修改的這種修改的S

11、CAN調(diào)度調(diào)度策略并不總是優(yōu)于純策略并不總是優(yōu)于純SSTF調(diào)度算法。調(diào)度算法。 由于這種算法中磁由于這種算法中磁頭移動(dòng)的規(guī)律頗似電梯頭移動(dòng)的規(guī)律頗似電梯的運(yùn)行，故又常稱為的運(yùn)行，故又常稱為電電梯調(diào)度算法梯調(diào)度算法例：例：假定磁盤(pán)共有40個(gè)柱面，當(dāng)前磁頭正在第11道服務(wù)，等待服務(wù)的進(jìn)程有6個(gè)，它們請(qǐng)求的柱面分別是：1, 36, 16, 34, 9 和 12 。按按SCAN算法：算法：移動(dòng)為：11 12 16 34 36 9 1總移動(dòng)柱面數(shù)：1+4+18+2+27+8 = 60 盡管此例的平均尋道時(shí)間電梯算法優(yōu)于SSF算法，但一般而言SSTF算法下平均尋道時(shí)間要優(yōu)于電梯算法。從效率和公平性考慮，目

12、前較多采用電梯調(diào)度算法。思考：思考：假設(shè)磁盤(pán)訪問(wèn)序列：假設(shè)磁盤(pán)訪問(wèn)序列： 98, 183, 37, 122, 14, 124, 65, 67讀寫(xiě)頭起始位置：讀寫(xiě)頭起始位置：53試安排磁頭服務(wù)序列，并計(jì)算磁頭移動(dòng)總距離試安排磁頭服務(wù)序列，并計(jì)算磁頭移動(dòng)總距離(道數(shù)道數(shù))四、循環(huán)掃描算法四、循環(huán)掃描算法CSAN(Circular SCAN)（不考）（不考） SCAN算法存在這樣的問(wèn)題：當(dāng)磁頭剛從里向外算法存在這樣的問(wèn)題：當(dāng)磁頭剛從里向外移動(dòng)過(guò)某一磁道時(shí)、恰有進(jìn)程請(qǐng)求訪問(wèn)此磁道，這移動(dòng)過(guò)某一磁道時(shí)、恰有進(jìn)程請(qǐng)求訪問(wèn)此磁道，這時(shí)該進(jìn)程必須等待，待磁頭從里向外然后再?gòu)耐鈺r(shí)該進(jìn)程必須等待，待磁頭從里向外然

13、后再?gòu)耐庀蚶飹呙柰晁幸L問(wèn)的磁道后、才處理該進(jìn)程的向里掃描完所有要訪問(wèn)的磁道后、才處理該進(jìn)程的請(qǐng)求，致使該進(jìn)程的請(qǐng)求被嚴(yán)重地推遲。為了減少請(qǐng)求，致使該進(jìn)程的請(qǐng)求被嚴(yán)重地推遲。為了減少這種延遲，這種延遲， SSTF的另一個(gè)修改版本是循環(huán)掃描法的另一個(gè)修改版本是循環(huán)掃描法(CSAN)。 該算法規(guī)定磁頭單向移動(dòng)。例如，只自里該算法規(guī)定磁頭單向移動(dòng)。例如，只自里向外移動(dòng)，當(dāng)磁頭移到最外的被訪問(wèn)磁道時(shí)，磁頭向外移動(dòng)，當(dāng)磁頭移到最外的被訪問(wèn)磁道時(shí)，磁頭立即返回到最里的欲訪磁道，即將最小磁道號(hào)緊接立即返回到最里的欲訪磁道，即將最小磁道號(hào)緊接著最大磁道號(hào)構(gòu)成循環(huán)，進(jìn)行掃描。即一個(gè)在磁道著最大磁道號(hào)構(gòu)成循環(huán)，

14、進(jìn)行掃描。即一個(gè)在磁道0上的上的I/O請(qǐng)求，將在磁道請(qǐng)求，將在磁道400上請(qǐng)求之后馬上可以得上請(qǐng)求之后馬上可以得到滿足。到滿足。當(dāng)前磁道=100 移動(dòng)方向=IN(向里)進(jìn)程號(hào) 磁道號(hào) 移動(dòng)距離(磁道數(shù)) 7 134 34 14 192 58 23 205 13 9 376 171 3 396 20 17 3 393 34 18 15 12 19 1 4 19 0 32 29 10 29 40 11 22 56 16磁頭移動(dòng)的總距離=642 (磁道) 按按此策略完成按按此策略完成這組這組I/O操作需移動(dòng)操作需移動(dòng)磁頭的總距離為磁頭的總距離為642磁道。磁道。 CSCAN的優(yōu)缺點(diǎn)的優(yōu)缺點(diǎn)的討論作為

15、一個(gè)習(xí)題留的討論作為一個(gè)習(xí)題留給讀者給讀者五、五、N-Step-SCAN和和FSCAN調(diào)度算法（不考）調(diào)度算法（不考） 1 N-Step-SCAN算法算法 在在 SSTF、SCAN及及CSCAN幾種調(diào)度算法中，幾種調(diào)度算法中，都可能出現(xiàn)磁臂停留在某處不動(dòng)的情況。都可能出現(xiàn)磁臂停留在某處不動(dòng)的情況。 例如，有一個(gè)或幾個(gè)進(jìn)程對(duì)某一磁道有著較高例如，有一個(gè)或幾個(gè)進(jìn)程對(duì)某一磁道有著較高的訪問(wèn)頻率，即他們反復(fù)請(qǐng)求對(duì)某一磁道進(jìn)行的訪問(wèn)頻率，即他們反復(fù)請(qǐng)求對(duì)某一磁道進(jìn)行 I/O，從而壟斷了整個(gè)磁盤(pán)設(shè)備。我們把這一現(xiàn)象稱為從而壟斷了整個(gè)磁盤(pán)設(shè)備。我們把這一現(xiàn)象稱為磁磁臂粘著臂粘著(Armstickiness)

16、。在高密度盤(pán)上更容易出現(xiàn)此。在高密度盤(pán)上更容易出現(xiàn)此情況。情況。 N-Step-SCAN是將磁盤(pán)請(qǐng)求隊(duì)列分成若干個(gè)是將磁盤(pán)請(qǐng)求隊(duì)列分成若干個(gè)長(zhǎng)度為長(zhǎng)度為N的子隊(duì)列，對(duì)一個(gè)隊(duì)列處理完后又處理另一的子隊(duì)列，對(duì)一個(gè)隊(duì)列處理完后又處理另一個(gè)隊(duì)列，這樣可避免出現(xiàn)粘著現(xiàn)象。個(gè)隊(duì)列，這樣可避免出現(xiàn)粘著現(xiàn)象。 當(dāng)當(dāng)N很大時(shí)，會(huì)使很大時(shí)，會(huì)使N-Step-SCAN的性能，接近于的性能，接近于 SCAN算法的性能；當(dāng)算法的性能；當(dāng) N=1時(shí)，時(shí)， N-Step-SCAN算法算法退化為退化為FCFS算法。算法。 2 FSCAN算法算法 FSCAN算法算法實(shí)質(zhì)上是實(shí)質(zhì)上是N-Step-SCAN算法算法的簡(jiǎn)化。它只將磁

17、盤(pán)請(qǐng)求訪問(wèn)隊(duì)列分成兩個(gè)的簡(jiǎn)化。它只將磁盤(pán)請(qǐng)求訪問(wèn)隊(duì)列分成兩個(gè)子隊(duì)列。子隊(duì)列。 一是當(dāng)前所有請(qǐng)求磁盤(pán)一是當(dāng)前所有請(qǐng)求磁盤(pán)I/O的進(jìn)程形成的的進(jìn)程形成的隊(duì)列，由磁盤(pán)調(diào)度按隊(duì)列，由磁盤(pán)調(diào)度按SCAN算法進(jìn)行處理。算法進(jìn)行處理。 另一個(gè)隊(duì)列則是在掃描期間，新出現(xiàn)的另一個(gè)隊(duì)列則是在掃描期間，新出現(xiàn)的所有請(qǐng)求磁盤(pán)所有請(qǐng)求磁盤(pán)I/O進(jìn)程的隊(duì)列，把它們排入另進(jìn)程的隊(duì)列，把它們排入另一個(gè)等待處理的請(qǐng)求隊(duì)列。一個(gè)等待處理的請(qǐng)求隊(duì)列。 這樣，所有的新請(qǐng)求都將被推遲到下一這樣，所有的新請(qǐng)求都將被推遲到下一次掃描時(shí)處理。次掃描時(shí)處理。例例1：假定某移動(dòng)磁盤(pán)上，處理了訪問(wèn)假定某移動(dòng)磁盤(pán)上，處理了訪問(wèn)56號(hào)柱面的請(qǐng)?zhí)栔娴?/p>

18、請(qǐng)求后，現(xiàn)在正在求后，現(xiàn)在正在70號(hào)柱面上讀信息，目前有下面的請(qǐng)?zhí)栔嫔献x信息，目前有下面的請(qǐng)求訪問(wèn)磁盤(pán)柱面的序列：求訪問(wèn)磁盤(pán)柱面的序列： 73, 68, 100, 120, 60, 108, 8, 50請(qǐng)寫(xiě)出下請(qǐng)寫(xiě)出下列各小題的響應(yīng)的次序及移動(dòng)的柱面數(shù)。列各小題的響應(yīng)的次序及移動(dòng)的柱面數(shù)。用最短查找時(shí)間優(yōu)先算法用最短查找時(shí)間優(yōu)先算法電梯調(diào)度算法電梯調(diào)度算法解：解： 用用SSTF，響應(yīng)的次序?yàn)?，響?yīng)的次序?yàn)?70、68、73、60、50、8、100、108、120 移動(dòng)的柱面數(shù)：移動(dòng)的柱面數(shù)：2+5+13+10+42+92+8+12=184 用電梯調(diào)度算法，響應(yīng)的次序?yàn)橛秒娞菡{(diào)度算法，響應(yīng)的次序?yàn)?70、73、100、108、120、68、60、50、8 移動(dòng)的柱面數(shù)：移動(dòng)的柱面數(shù)：3+27+8+12+52+8+10+42=162例例2： 若干個(gè)等待訪問(wèn)磁盤(pán)者依次要訪問(wèn)的柱面為若干個(gè)等待訪問(wèn)磁盤(pán)者依次要訪問(wèn)的柱面為 20, 44, 40, 4, 80, 12, 76。 假設(shè)每移動(dòng)一個(gè)柱面需要假設(shè)每移動(dòng)一個(gè)柱面需要3毫秒毫秒時(shí)間，時(shí)間，移動(dòng)臂當(dāng)前位于移動(dòng)臂當(dāng)前位于40號(hào)柱面，請(qǐng)按下列算法分別計(jì)算為完成號(hào)柱面，請(qǐng)按下列算法分別計(jì)算為完