10磁盤調(diào)度算法

1、操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目磁盤調(diào)度算法學(xué)生姓名lee學(xué) 號(hào)專業(yè)班級(jí)指導(dǎo)教師院系名稱計(jì)算機(jī)與信息學(xué)院2017年 10 月 30 日11 掃描 FAT12 文件系統(tǒng)管理的軟盤1. 實(shí)驗(yàn)?zāi)康呐c要求通過(guò)學(xué)習(xí)EOS；現(xiàn)磁盤調(diào)度算法的機(jī)制，掌握磁盤調(diào)度算法執(zhí)行的條件和時(shí)機(jī)。觀察EOS；現(xiàn)的FCFS SST舜口 SCA肱盤調(diào)度算法，了解常用的磁盤調(diào)度算法。編寫CSCANN-Step-SCANW盤調(diào)度算法，加深對(duì)各種掃描算法的理解。2. 實(shí)驗(yàn)原理閱讀本書第7章的第7.5 節(jié)， 并結(jié)合 io/block.c 文件中的 IopReceiveRequest 函數(shù) （第 67行） 、IopProcessNextRequ

2、est 函數(shù)（第 181 行）、 IopDiskSchedule 函數(shù)（第378行）和IopReadWriteSector函數(shù)（第263行）的源代碼，理解 EOS!如何實(shí)現(xiàn)磁盤調(diào)度算法的。閱讀 ke/sysproc.c 文件中第 580 行的 ConsoleCmdDiskSchedule 函數(shù)及其調(diào)用的其它函數(shù) （包括第 536 行的 NewThreadAccessCylinder 函數(shù)和第 499 行的 AccessCylinderThread 函數(shù)） ， 學(xué) 習(xí) EOS 是如何測(cè)試磁盤調(diào)度算法的，并體會(huì)這種測(cè)試方法的優(yōu)缺點(diǎn)。3. 實(shí)驗(yàn)內(nèi)容6553.1 準(zhǔn)備實(shí)驗(yàn)按照下面的步驟準(zhǔn)備實(shí)驗(yàn)：1.

3、啟動(dòng) OS Lab。2. 新建一個(gè) EOS Kernel 項(xiàng)目。3.2 驗(yàn)證先來(lái)先服務(wù)（FCF9磁盤調(diào)度算法 按照下面的步驟進(jìn)行驗(yàn)證：1 .在 項(xiàng)目管理器”窗口中雙擊ke文件夾中的sysproc.c文件，打開此文件。2 .在sysproc.c文件的第580行找到控制臺(tái)命令ds”對(duì)應(yīng)的函數(shù) ConsoleCmdDiskSchedule 。“ds” 命令專門用來(lái)測(cè)試磁盤調(diào)度算法。閱讀該函數(shù)中的源代碼， 目前該函數(shù)使磁頭初始停留在磁道 10，其它被阻塞的線程依次訪問(wèn)磁道8、 21、 9、 78、 0、 41、 10、 67、 12、 10。3 . 打開 io/block.c 文件，在第378行找到磁

4、盤調(diào)度算法函數(shù)IopDiskSchedule 。閱讀該函數(shù)中的源代碼，目前此函數(shù)實(shí)現(xiàn)了 FCFS1盤調(diào)度算法，其流程圖可以參見圖 18-1。4 .按F7生成項(xiàng)目，然后按F5啟動(dòng)調(diào)試。5 .待EOSB動(dòng)完畢，在EO醛制臺(tái)中輸入命令 ds”后按回車。在EO醛制臺(tái)中會(huì)首先顯示磁頭的起始位置是10磁道，然后按照線程被阻塞的順序依次顯示線程的信息（包括線程ID和訪問(wèn)的磁道號(hào)）。磁盤調(diào)度算法執(zhí)行的過(guò)程中，在OS Lab的 輸出 ” 窗口中也會(huì)首先顯示磁頭的起始位置， 然后按照線程被喚醒的順序依次顯示線程信息 （包 括線程 ID 、 訪問(wèn)的磁道號(hào)、磁頭移動(dòng)的距離和方向），并在磁盤調(diào)度結(jié)束后顯示此次調(diào)度的統(tǒng)計(jì)

5、信息（包括總尋道數(shù)、尋道次數(shù)和平均尋道數(shù)）。對(duì)比EOS!制臺(tái)和 輸出”窗口中的內(nèi)容，可以發(fā)現(xiàn)FCFS?法是根據(jù)線程訪問(wèn)磁盤的先后順序進(jìn)行調(diào)度的。圖18-2顯示了本次調(diào)度 執(zhí)行時(shí)磁頭移動(dòng)的軌跡?？梢栽诳刂婆_(tái)中多次輸入ds”命令，查看磁盤調(diào)度算法執(zhí)行的情況。將 輸出”窗口中的內(nèi)容復(fù)制到一個(gè)文本文件中，然后結(jié)束此次調(diào)試。EOS操作系統(tǒng)實(shí)驗(yàn)教程北京海西慧學(xué)科技有限公司 177 lopDiskSchedule函數(shù)開始選擇請(qǐng)求隊(duì)列中的第一個(gè)請(qǐng)求返回選中的請(qǐng)求的指針注意，鏈表 頭指向的下一個(gè)請(qǐng)求是請(qǐng)求隊(duì)列中的第一個(gè)請(qǐng)求。注意.能表頭指向的卜 二一個(gè)請(qǐng)求是清末隊(duì)列申 "I的海一個(gè)請(qǐng)求.聞18-實(shí)現(xiàn)了

6、 FCFS算法儆lopDiskSchfdul#函效流程圖18-2： FCFS算法誕頭移動(dòng)的軌遮f茗尋道數(shù)3珈尋道次數(shù)10平均尋追敝36）圖1:實(shí)現(xiàn)了 FCFSf法的IopDiskSchedule函數(shù)流程圖圖2: FCFST法磁頭移動(dòng)的軌跡（總尋道數(shù)360尋道次數(shù)10平均尋道數(shù)36）3.3驗(yàn)證最短尋道時(shí)間優(yōu)先（SSTF）磁盤調(diào)度算法使用OS Lab打開本實(shí)驗(yàn)文件夾中的 sstf.c文件（將sstf.c文件拖動(dòng)到OS Lab窗口中釋放即 可）。該文件提供的IopDiskSchedule函數(shù)實(shí)現(xiàn)了 SSTFB盤調(diào)度算法。在閱讀此函數(shù)的源代 碼的時(shí)，可以參考圖18-3所示的流程圖，并且應(yīng)該特別注意下面

7、幾點(diǎn)：變量Offset是有符號(hào)的長(zhǎng)整型，用來(lái)表示磁頭的偏移（包括距離和方向）。 Offset大于0時(shí)表示磁頭向內(nèi)移動(dòng)（磁道號(hào)增加）；小于0時(shí)表示磁頭向外移動(dòng)（磁道號(hào)減少）；等于 0時(shí)表示磁頭沒(méi)有移動(dòng)。而名稱以Distance 結(jié)尾的變量都是無(wú)符號(hào)長(zhǎng)整型，只表示磁頭移動(dòng)的距離（無(wú)方向）。所以在比較磁頭的偏移和距離時(shí)，或者在將偏移賦值給距離時(shí)，都要 取偏移的絕對(duì)值（調(diào)用C庫(kù)函數(shù)abs）。本實(shí)驗(yàn)在實(shí)現(xiàn)其它磁盤調(diào)度算法時(shí)也同樣遵守此約定。在開始遍歷之前，將最小距離（ ShortestDistance ）初始化為最大的無(wú)符號(hào)長(zhǎng)整型數(shù)， 這樣，第一次計(jì)算的距離一定會(huì)小于最小距離，從而可以使用第一次計(jì)算的距

8、離來(lái)再次初始化最小距離。本實(shí)驗(yàn)在實(shí)現(xiàn)其它磁盤調(diào)度算法時(shí)也同樣使用了此技巧。按照下面的步驟進(jìn)行驗(yàn)證：1 .使用sstf.c 文件中IopDiskSchedule 函數(shù)的函數(shù)體，替換block.c文件中IopDiskSchedule 函數(shù)的函數(shù)體。2 .按F7生成項(xiàng)目，然后按F5啟動(dòng)調(diào)試。3 .待EOSB動(dòng)完畢，在EO醛制臺(tái)中輸入命令ds后按回車。物出調(diào)國(guó)且3 入* Disk schedule start working * Start Cylinder: 10TID31 Cylinder8 Offset: 2 TID32 Cylinder21 Offset： 13 +TID33 Cylinder

9、9 Offset: 12 -TID34 Cylinder78 Offset: 6g +TID35 Cylinder0 Offset： 78 -T1D36 Cylinder41 Offset: 41 +TID37 Cylinder10 Offset: 31 -TID38 Cylinder67 Offset ： 57 +T1D39 Cylinder12 Offset: 55 -TID40 Cylinder10 Offset: 2 -Total offset: 360 Transfer tiroes: 10 Average offset: 36卜*:* Disk schedule stop work

10、ing *對(duì)比EOSS制臺(tái)和 輸出 窗口中的內(nèi)容（特別是線程 ID的順序），可以發(fā)現(xiàn)，SSTFT法喚醒線程的順序與線程被阻塞的順序是不同的。圖18-4顯示了本次調(diào)度執(zhí)行時(shí)磁頭移動(dòng)的軌跡。對(duì)比SSTFI法與FCFST法在 輸出 窗口中的內(nèi)容，可以看出，SSTFI法的平均尋道數(shù)明顯低于FCFS?法。但是，SSTFT法能保證平均尋道數(shù)最少嗎？在后面的實(shí)驗(yàn)中會(huì)進(jìn)行驗(yàn)證?？梢栽诳刂婆_(tái)中多次輸入ds命令，查看磁盤調(diào)度算法執(zhí)行的情況。將 輸出 窗口中的內(nèi)容復(fù)制到一個(gè)文本文件中，然后結(jié)束此次調(diào)試。 OS Lab PC - Iicrosoft Vxrtual PC 2007Action Edit CD Flop

11、py K«lpCONSOLE-1 (Press CtrHFl*F8 to switch console window.) Me leone to EOS shell >dsStart Cylinder： 10TID： 31 Cylinder： 8TID： 32 Cylinder： 21TID： 33 Cylinder： 3TID： 34 Cylinder： 78TID： 35 Cylinder： 0TID： 36 Cylinder： 41TID： 37 Cylinder： 16TID： 38 Cylinder： 67TID: 33 Cylinder： 12TID： 40 Cyl

12、inder： 16謂試, 1333當(dāng)Disk schedule Start Cylinder： 10| TID: 37 Cylinder: 10 TID: 40 Cylinder： 10start working *Offset: 0 =Offset: 0 =TID： 33 Cylinder：TID: 31 Cylinder：TID： 39 Cylinder：TID: 32 Cylinder：TID: 36 Cylinder:TID： 38 Cylinder：TID: 34 Cylinder：TID: 35 Cylinder：9 Offset： 1 -8 Offset： 1 -12 Offse

13、t： 4 +21 Offset： 9 +41 Offset: 20 +67 Offset: 26 +78 Offset: 11 + 0 Offset： 78 -Total offset： 150 Transfer times： 10 Average offset： 15* Disk schedule stop working *M >W何 百7B(ffl 15-31 實(shí)現(xiàn)了 5STF 算法的 mpDi.k5cli.dul函«（流程圖圖SSTF算法磁頭移動(dòng)的軌跡（總各道數(shù)150字道次數(shù)10平均尋道里15）圖18-3:實(shí)現(xiàn)了 SSTFT法的lopDiskSchedule函數(shù)流程圖圖

14、18-4： SSTFI法磁頭移動(dòng)的軌跡（總尋道數(shù)150尋道次數(shù)10平均尋道數(shù)15）3.4 驗(yàn)證SSTFT法造成的線程 饑餓”現(xiàn)象使用SSTFT法時(shí)，如果不斷有新線程要求訪問(wèn)磁盤， 而且其所要訪問(wèn)的磁道與當(dāng)前磁頭所在 磁道的距離較近，這些新線程的請(qǐng)求必然會(huì)被優(yōu)先滿足，而等待隊(duì)列中一些老線程的請(qǐng)求就會(huì)被嚴(yán)重推遲，從而使老線程出現(xiàn) 饑餓”現(xiàn)象。按照下面的步驟進(jìn)行實(shí)驗(yàn)，觀察這個(gè)現(xiàn)象：1 .修改sysproc.c文件ConsoleCmdDiskSchedule函數(shù)中的源代碼，仍然使磁頭初始停留在 磁道10,而讓其它線程依次訪問(wèn)磁道78、21、9、8、11、41、10、67、12、10。修改代碼：2.61

15、4i615'6166176186196201621|622623|62 4l625|626i按F7生成項(xiàng)目,N ewT hr eadAcc e s 式y(tǒng) 1 i nder (StdH andl 島 NeThreadAccessyl inder (Si dHandl e* N ewThreadAcc e ssCyl inder (St dHandl e, N ewThreadAcc e s ?yli nder (St dHandl e, N ewThreadAcee ssCyl inder (S t dHandl ef NewThreadAcc e ssCyl inder (S t dH

16、andl e, NewThrea'dAccessCylinder (StdHandle, MewThreadAccrsylinder(StdHandle? NewThrfadAccessCylinder(StdHandle, II ewThr ea dAcc e s sCy 1 inder (St dHandl j78). 21);9)； S)；ID； 41); 10); 67); 12); 1削/w *4 *CE rt-nf > I工ell11sju_ > |i 干e 使士_I f_I ll然后按F5啟動(dòng)調(diào)試。3.待EOSB動(dòng)完畢，在EO的制臺(tái)中輸入命令 ds”后按回車。

17、將“輸出”窗口中的內(nèi)容復(fù)制到一個(gè)文本文件中，然后結(jié)束此次調(diào)試。將ConsoleCmdDiskSchedule函數(shù)中線程訪問(wèn)的磁道號(hào)恢復(fù)到本實(shí)驗(yàn)3.2中的樣子，在后面的實(shí) 驗(yàn)中還要使用這些數(shù)據(jù)。-r-rrf-fti-*+* Disk schedule start werkinsTID: 37 blinderTID： 40 CylinderT1D: 33 Cylindtr 71D: 34 Cylinder ?D: 15 ylin Irr TID: 39 Cylinhr TIDi 32 Cylinder TID： 36 CylinderTID: 38 CylTID： 31 Cylinder10 Of

18、fset： 0 -10 Offsets 0 =9 Offset: I -E Offset ： 1 -11 Of furl: 3 +12 Offset: 1 421 Offset: 9 +Offset： 20 +6T Offset： E6 + ?B Offset: 11 +Stjrt ?yllnJrr： 1UTotal offset： 72 Transfer tines： 10 Average jffaet： 7D"k schedule stop norkin£ <»*查看 輸出”窗口中顯示的內(nèi)容， 可以發(fā)現(xiàn)，雖然訪問(wèn)78號(hào)磁道的線程的請(qǐng)求第一個(gè)被放入請(qǐng) 求隊(duì)

19、列，但卻被推遲到最后才被處理，出現(xiàn)了 饑餓”現(xiàn)象。如果不斷有新線程的請(qǐng)求到達(dá)并被優(yōu)先滿足，則訪問(wèn)78號(hào)磁道的線程的 饑餓”情況就會(huì)更加嚴(yán)重。* Disk schedule start working *Stiti Cylinder: 10TID: 47 Cylinder:TID: 50 Cylinder:TID: 43 Cylinder:TID: 41 Cylinder：TID： 49 Cylinder：TID: 42 Cylinder：TID： 46 Cylinder：TID: 48 Cylinder:TID： 44 Cylinder:TID: 45 Cylinder:ITotal offs

20、et： 15010 Offset: 0 二 10 Off sei: 0 二9 Offset: 1 - S Offset: 1 - 12 Offset: 4 + 21 Offset: 9 + 41 Offset： 20 + 67 Offset: 26 + 78 Offset: 11 + 0 Offset: 78 -Trinsfer 1ines：10 Average offset:153.5 驗(yàn)證掃描（SCAN磁盤調(diào)度算法又SSTFf法稍加改進(jìn)后可以形成 SCANT法，可防止老線程出現(xiàn) 饑餓”現(xiàn)象。使用OSLab打開 本實(shí)驗(yàn)文件夾中的scan.c文件，該文件提供的lopDiskSchedule函數(shù)

21、實(shí)現(xiàn)了 SCA瞰盤調(diào)度算 法。在閱讀此函數(shù)的源代碼的時(shí)，應(yīng)該特別注意下面幾點(diǎn)：在block.c文件中的第374行定義了一個(gè)布爾類型的全局變量ScanInside ,用于表示掃描算法中磁頭移動(dòng)的方向。該變量值為TRUE寸表示磁頭向內(nèi)移動(dòng)（磁道號(hào)增加）；值為 FALSE時(shí)表示磁頭向外移動(dòng)（磁道號(hào)減少）。該變量初始化為TRUE表示SCANT法第一次執(zhí)行時(shí)，磁頭向內(nèi)移動(dòng)。在scan.c文件的IopDiskSchedule函數(shù)中使用了雙重循環(huán)。第一次遍歷隊(duì)列時(shí)，查找指定方向上移動(dòng)距離最短的線程，如果在指定方向上已經(jīng)沒(méi)有線程，就變換方向，進(jìn)行第二次遍歷，同樣是查找移動(dòng)距離最短的線程。在這兩次遍歷中一定能找

22、到合適的線程。按照下面的步驟進(jìn)行驗(yàn)證：1 .使用scan.c文件中IopDiskSchedule 函數(shù)的函數(shù)體，替換block.c文件中IopDiskSchedule 函數(shù)的函數(shù)體。2 .按F7生成項(xiàng)目，然后按F5啟動(dòng)調(diào)試。3 .待EOSB動(dòng)完畢，在EO醛制臺(tái)中輸入命令ds后按回車。幃出* Disk schedule start marking *7*Slart Cylinder: 10TID: 37 Cylinder: 10 Offset: 0 =TID： 40 Cylinder： 10 Offset： 0 -TID: 39 Cylinder: 12 Offset; 2 +TID: 32 C

23、ylinder: 21 Offset： 9 +TID: 36 Cylinder: 41 Offset ： 20 可TID: 38 Cylinder: 6T Offset! 26 +TID： 34 Cylinder: 73 Offset: 11 +TID: 33 Cylinder: 9 Offset: 69 -TID: 31 Cylinder： 8 Offset: 1 -TID: 35 Cylinder： 0 Offset: 8 -,Total offset ： 1r非 Transfer times： 10 Average offset： 14TID:47 Cylinder10 Offset:

24、0 =TID50 Cylinder10 Offset: 0 二TID:43 Cylinder9 Offset: 1 -TID41 Cylinder8 Offset: 1 -TID45 Cylinder0 Offset: 8 -TID49 Cylinder12 Offset: 12 +TID.42 Cylinder21 Offset ： 9 +TID46 Cylinder41 Offset： 20 +TID48 Cylinder67 Offset： 26 +TID44 Cylinder78 Offset: 11 +* Disk schedule start working *Start Cyli

25、nder： 10Total offset： 83Transfer times： 10 Average offset： 8對(duì)比SCA醇法與SSTFT法在 輸出 窗口中的內(nèi)容，可以看出，SCANT法的平均尋道數(shù)有可 能小于SSTFT法，所以說(shuō)SSTFI法不能保證平均尋道數(shù)最少。圖18-5顯示了本次調(diào)度執(zhí)行時(shí)磁頭移動(dòng)的軌跡。嘗試在控制臺(tái)中多次輸入ds命令，查看磁盤調(diào)度算法執(zhí)行的情況，說(shuō)明為什么線程調(diào)度的順序會(huì)發(fā)生變化。將 輸出 窗口中的內(nèi)容復(fù)制到一個(gè)文本文件中，然后結(jié)束此次調(diào)試。圖18-5: SCA醇法磁頭移動(dòng)的軌跡（總尋道數(shù) 146尋道次數(shù)10平均尋道數(shù)14）使用SCA醇法調(diào)度在本實(shí)驗(yàn)3.4中產(chǎn)生

26、 饑餓 現(xiàn)象的數(shù)據(jù)，驗(yàn)證SCA醇法能夠解決 饑餓 現(xiàn)象，并將 輸出 窗口中的內(nèi)容保存到一個(gè)文本文件中。最后將ConsoleCmdDiskSchedule 函數(shù)中線程訪問(wèn)的磁道號(hào)恢復(fù)到本實(shí)驗(yàn)3.2 中的樣子，在后面的實(shí)驗(yàn)中還要使用這些數(shù)據(jù)。3.6改寫SCANT法3.6.1 要求在已有SCANT法源代碼的基礎(chǔ)上進(jìn)行改寫，要求不再使用雙重循環(huán)，而是只遍歷一次請(qǐng)求隊(duì)列中的請(qǐng)求， 就可以選中下一個(gè)要處理的請(qǐng)求。 由于線程和請(qǐng)求總是一一對(duì)應(yīng)的， 為了使后面的內(nèi)容更加簡(jiǎn)單易懂，有時(shí)就不再區(qū)分這兩個(gè)概念。3.6.2 提示1. 在一次遍歷中，不再關(guān)心當(dāng)前磁頭移動(dòng)的方向，而是同時(shí)找到兩個(gè)方向上移動(dòng)距離最短的線程所

27、對(duì)應(yīng)的請(qǐng)求，這樣就不再需要遍歷兩次。2. 在計(jì)算出線程要訪問(wèn)的磁道與當(dāng)前磁頭所在磁道的偏移后，可以將偏移分為三種類型：偏移為0，表示線程要訪問(wèn)的磁道與當(dāng)前磁頭所在磁道相同，此情況應(yīng)該優(yōu)先被調(diào)度，可立即返回該線程對(duì)應(yīng)的請(qǐng)求的指針；偏移大于0 ，記錄向內(nèi)移動(dòng)距離最短的線程對(duì)應(yīng)的請(qǐng)求；偏移小于0，記錄向外移動(dòng)距離最短的線程對(duì)應(yīng)的請(qǐng)求。3. 循環(huán)結(jié)束后，根據(jù)當(dāng)前磁頭移動(dòng)的方向選擇同方向移動(dòng)距離最短的線程，如果在同方向上沒(méi)有線程， 就變換方向， 選擇反方向移動(dòng)距離最短的線程。 具體邏輯可以參見圖 18-6 所示 的流程圖。SCA題寫代碼：PREQUEST IopDiskSchedule( VOID )P

28、LIST_ENTRY pListEntry;PREQUEST pRequest;PREQUEST INpNextRequest = NULL;PREQUEST OUTpNextRequest = NULL;LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0xFFFFFFFF;PREQUEST pNextRequest = NULL;/ 需要遍歷請(qǐng)求隊(duì)列一次或兩次for (pListEntry = RequestListHead.Next; /請(qǐng)求隊(duì)列中的第一個(gè)請(qǐng)求是鏈表頭

29、指向的下一個(gè)請(qǐng)求。pListEntry != &RequestListHead; /遍歷到請(qǐng)求隊(duì)列頭時(shí)結(jié)束循環(huán)。pListEntry = pListEntry->Next) /根據(jù)鏈表項(xiàng)獲得請(qǐng)求的指針pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);/ 計(jì)算請(qǐng)求對(duì)應(yīng)的線程所訪問(wèn)的磁道與當(dāng)前磁頭所在磁道的偏移(方向由正負(fù)表示)Offset = pRequest->Cylinder - CurrentCylinder; if (0 = Offset) / 如果線程要訪問(wèn)的磁道與當(dāng)前磁頭所在磁道相同，可立即返

30、回。pNextRequest = pRequest; goto RETURN; else if (Offset<InsideShortestDistance && Offset > 0) / 記錄向內(nèi)移動(dòng)距離最短的線程InsideShortestDistance = Offset;INpNextRequest = pRequest; else if (-Offset < OutsideShortestDistance && Offset < 0) / 記錄向外移動(dòng)距離最短的線程OutsideShortestDistance = -Offs

31、et;OUTpNextRequest = pRequest; /判斷磁頭移動(dòng)方向，若向內(nèi)移動(dòng)if(ScanInside) /判斷是否有向內(nèi)移動(dòng)的線程if(INpNextRequest) /有則原則該進(jìn)程return INpNextRequest; else/沒(méi)有則修改磁頭方向，選擇向外移動(dòng)距離最短的線程 ScanInside=!ScanInside;return OUTpNextRequest; /如果向外移動(dòng)else /判斷是否有向外移動(dòng)的線程if(OUTpNextRequest) /有則選擇該進(jìn)程return OUTpNextRequest; else/沒(méi)有則修改磁頭的方向，選擇向內(nèi)移動(dòng)距

32、離最短的線程 ScanInside =!ScanInside;return INpNextRequest; RETURN:return pNextRequest; 修改完SCANT法后車入“ ds”命令：DDDD-DDDDDD I I I- I 1 1 I I I ITTTTTTTTTT* Disk schedule start workingSi art Cylinder： 1037 Cylinder： 10 Offset： 0 =40 Cylinder： 10 Offset： 0 39 Cylinder: 12 Offset; 2 +32 Cylinder: 21 Offset: 9 +3

33、6 Cylinder: 41 Offset: 20 +38 Cylinder： 67 Offset： 26 +34 Cylinder； 78 Offset; 11 +33 Cylinder: 9 Offset: 69 -31 Cylinder： E Offset： 1 -35 Cylinder： 0 Offset： 8 -Total offset： 146 Transfer times： 10 Average offset： 143.6.3測(cè)試方法使用本實(shí)驗(yàn)3.2中的數(shù)據(jù)進(jìn)行測(cè)試，確保調(diào)度的結(jié)果與圖18-5中顯示的一致，也可以多準(zhǔn)備幾組測(cè)試數(shù)據(jù)，保證改寫的SCANT法是正確的。測(cè)試成功后，將改

34、寫的SCANT法源代碼備份。循環(huán)結(jié)束:同酎記 錄了兩個(gè)方向上杼 動(dòng)距離短的戰(zhàn)程圖18-6:循環(huán)結(jié)束后，根據(jù)磁頭移動(dòng)方向選擇合適線程的流程圖3.7編寫循環(huán)掃描(CSCAN磁盤調(diào)度算法3.7.1 要求在已經(jīng)完成的SCAN?法源代碼的基礎(chǔ)上進(jìn)行改寫，不再使用全局變量ScanInside確定磁頭移 動(dòng)的方向，而是規(guī)定磁頭只能從外向內(nèi)移動(dòng)。 當(dāng)磁頭移動(dòng)到最內(nèi)的被訪問(wèn)磁道時(shí)， 磁頭立即 移動(dòng)到最外的被訪問(wèn)磁道，即將最大磁道號(hào)緊接著最小磁道號(hào)構(gòu)成循環(huán)，進(jìn)行掃描。由于磁頭移動(dòng)的方向被固定，也就不需要根據(jù)磁頭移動(dòng)的方向進(jìn)行分類處理，所以CSCAN法的源代碼會(huì)較SCANT法更加簡(jiǎn)單。3.7.2 提示1 .由于規(guī)定

35、了磁頭只能從外向內(nèi)移動(dòng)，所以在每次遍歷中，總是同時(shí)找到向內(nèi)移動(dòng)距離最 短的線程和向外移動(dòng)距離最長(zhǎng)的線程。注意，與SCA醇法查找向外移動(dòng)距離最短線程不同，這里查找向外移動(dòng)距離最長(zhǎng)的線程。在開始遍歷前，可以將用來(lái)記錄向外移動(dòng)最長(zhǎng)距離的變量賦值為0。2 .在計(jì)算出線程要訪問(wèn)的磁道與當(dāng)前磁頭所在磁道的偏移后，同樣可以將偏移分為三種類 型：偏移為0,表示線程要訪問(wèn)的磁道與當(dāng)前磁頭所在磁道相同，此情況應(yīng)優(yōu)先被調(diào)度，可 立即返回該線程對(duì)應(yīng)的請(qǐng)求的指針；偏移大于0,記錄向內(nèi)移動(dòng)距離最短的線程對(duì)應(yīng)的請(qǐng)求；偏移小于0,記錄向外移動(dòng)距離最長(zhǎng)的線程對(duì)應(yīng)的請(qǐng)求。3 .循環(huán)結(jié)束后，選擇向內(nèi)移動(dòng)距離最短的線程，如果沒(méi)有向內(nèi)

36、移動(dòng)的線程，就選擇向外移 動(dòng)距離最長(zhǎng)的線程。CSCA修改代碼：PREQUEST IopDiskSchedule( VOID ) PLIST_ENTRY pListEntry;PREQUEST pRequest;PREQUEST INpNextRequest = NULL;PREQUEST OUTpNextRequest = NULL;LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0x00000000;PREQUEST pNextRequest = NULL;/ 需要遍歷

37、請(qǐng)求隊(duì)列一次或兩次for (pListEntry = RequestListHead.Next;/ 請(qǐng)求隊(duì)列中的第一個(gè)請(qǐng)求是鏈表頭指向的下一個(gè)請(qǐng)求。pListEntry != &RequestListHead; /遍歷到請(qǐng)求隊(duì)列頭時(shí)結(jié)束循環(huán)。pListEntry = pListEntry->Next) /根據(jù)鏈表項(xiàng)獲得請(qǐng)求的指針pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);/ 計(jì)算請(qǐng)求對(duì)應(yīng)的線程所訪問(wèn)的磁道與當(dāng)前磁頭所在磁道的偏移(方向由正負(fù)表示)Offset = pRequest->Cylinde

38、r - CurrentCylinder;if (0 = Offset) / 如果線程要訪問(wèn)的磁道與當(dāng)前磁頭所在磁道相同，可立即返回。pNextRequest = pRequest;goto RETURN; else if (Offset<InsideShortestDistance && Offset > 0) / 記錄向內(nèi)移動(dòng)距離最短的線程InsideShortestDistance = Offset;INpNextRequest = pRequest; else if (-Offset > OutsideShortestDistance &&

39、; Offset < 0) / 記錄向外移動(dòng)距離最短的線程OutsideShortestDistance = -Offset;OUTpNextRequest = pRequest;/ 需要向內(nèi)移動(dòng)的線程是否存在if(INpNextRequest)/ 存在則返回向內(nèi)移動(dòng)的請(qǐng)求return INpNextRequest; else / 沒(méi)有則返回向外移動(dòng)的請(qǐng)求return OUTpNextRequest;RETURN: return pNextRequest;啟動(dòng)修改后的程序，輸入“ ds ”命令：* Disk scheduleStart Cylinder: 10start working

40、*TID TID TID TID TID TID TID TID TID TID37403932363834353133Cylinder Cylinder Cylinder Cyl i nder Cylinder Cylinder Cyl inder Cylinder Cylinder CylinderTotal offset: 155101012214167780 8 9 Offset: Offset ： ：Offset 1Offset:Offset 1 Offset: i Offset ： Offset：Offset: Offset:0 二0 =2 +9 +20 +26 +11 +78 -

41、8 +1 +Transfer times: 10 Average offset: 15+* Disk schedule stop working *3.7.3測(cè)試方法使用本實(shí)驗(yàn)3.2中的數(shù)據(jù)進(jìn)行測(cè)試，確保調(diào)度的結(jié)果與圖18-7中顯示的一致?？梢栽诳刂婆_(tái)中多次輸入ds”命令，查看磁盤調(diào)度算法執(zhí)行的情況。測(cè)試成功后，將輸出”窗口中的內(nèi)容觀察執(zhí)行SSTF SCA阪CSCANT法時(shí)磁頭移動(dòng)的軌跡（圖 18-4、圖18-5和圖18-7 ）,可以看到，在開始時(shí)磁頭都停留在 10磁道不動(dòng)，這就是 磁臂粘著”現(xiàn)象。為了更加明顯的觀察該現(xiàn) 象，按照下面的步驟進(jìn)行實(shí)驗(yàn)：1.修改sysproc.c文件Console

42、CmdDiskSchedule函數(shù)中的源代碼，仍然使磁頭初始停留在磁道10,而讓其它線程依次訪問(wèn)磁道78、10、10、10、10、10、10、10、10、10。NewThreadAccessCylinder (StdHandl e, 78);MewThreadAccessCyl inder (StdHandle, 10);NewThreadAccessCyl inder (StdHandle, 10);WewThreadAccessCylinder (StdHandl e3 10);NeffThrcadAccessCyl inder (StdHandle, 10);NewThreadAcces

43、sCylinder CStdHandle? 10);MewThreadAccessCylinder (StdRandle1 10);NewThreadAccessCyl inder (St dHandle, 10);MewThreadAccessCylinder tStdHandle, 10):NewThreadAccessCyl inder (St dHandle, 10);JF J2.分別使用SSTR SCAND CSCAN法調(diào)度這組數(shù)據(jù)。查看各種算法在 輸出”窗口中顯示的內(nèi)容， 可以發(fā)現(xiàn)，雖然訪問(wèn)78號(hào)磁道的線程的請(qǐng)求第一個(gè)被放入請(qǐng)求隊(duì)列，但卻被推遲到最后才被處理，出現(xiàn)了磁臂粘著”現(xiàn)象。

44、將 輸出“窗口中的內(nèi)容復(fù)制到一個(gè)文本文件中后，將ConsoleCmdDiskSchedule函數(shù)中線程訪問(wèn)的磁道號(hào)恢復(fù)到本實(shí)驗(yàn) 3.2中的樣子，在后面的實(shí)驗(yàn)中還要使用這些數(shù)據(jù)。SCANT法測(cè)試：* an-DDDDDnDDD* tlllll-IIIII* s T T T T T T _T T T T* *L10 Offset:78 Offset:I 二二二二二二二一二8 0000000006Total oftscT: 68* Disk schedule stooTiines ： 10 Average offset ： 6*4orkinst * * * *CSCAN算法測(cè)試:* Disk sche

45、duleStart Cylinder： 10:32 Cylinder: 1033 Cylinder: 1034 Cylinder: 1035 Cylinder： 1036 Cylinder: 1037 Cylinder： 1038 Cylinder: 1039 Cylinder: 1040 Cylinder： 1031 Cylinder： 78DDDDDDDDDDstart working *Offset Offset Offset Offset Offset Offset Offset Offset Offset Offset一二二二二-1T -= 0 0000000068Total off

46、set： 68 Transfer times： 10 Average offset： 6* Disk schedule stop working *SST嗡法測(cè)試:* Disk scheduleStart Cylinder: 10start working *DDDDDDDDDD32 Cylinder: 10 Offset0 =33 Cylinder: 10 Offset0 =34 Cylinder: 10 Offset0 =35 Cylinder: 10 Offset0 =36 Cylinder: 10 Offset0 =37 Cylinder: 10 Offset0 =38 Cylinde

47、r: 10 Offset0 =39 Cylin<ier: 10 Offset0 =40 Cylinder: 10 Offset0 =31 Cylinder 1 78 Offset68 +Total offset: 68Tresnsfer times 1 10 Average offset: 6* Disk schedule stop working *3.9編寫N-Step-SCANB盤調(diào)度算法3.9.1 要求在已經(jīng)完成的SCAN?法源代碼的基礎(chǔ)上進(jìn)行改寫，將請(qǐng)求隊(duì)列分成若干個(gè)長(zhǎng)度為 N的子隊(duì)列， 調(diào)度程序按照FCFSM則依次處理這些子隊(duì)列，而每處理一個(gè)子隊(duì)列時(shí)，又是按照SCANT法。3

48、.9.2 提示1 .在block.c文件中的第360行定義了一個(gè)宏SUB_QUEUE_LENGTH示子隊(duì)列的長(zhǎng)度(即 N 值)。目前這個(gè)宏定義的值為 6。在第367行定義了一個(gè)全局變量 SubQueueRemainLength,表 示第一個(gè)子隊(duì)列剩余的長(zhǎng)度，并初始化其值為SUB_QUEUE_LENGTH2 .在執(zhí)行N-Step-SCAN算法時(shí)，要以第一個(gè)子隊(duì)列剩余的長(zhǎng)度做為計(jì)數(shù)器，確保只遍歷第一個(gè)子隊(duì)列剩余的項(xiàng)。所以，結(jié)束遍歷的條件就既包括第一個(gè)子隊(duì)列結(jié)束，又包括整個(gè)隊(duì)列結(jié)束(如果整個(gè)隊(duì)列的長(zhǎng)度小于第一個(gè)子隊(duì)列剩余的長(zhǎng)度)。注意，不要直接使用第一個(gè)子隊(duì)列剩余的長(zhǎng)度做為計(jì)數(shù)器，可以定義一個(gè)新的局

49、部變量來(lái)做為計(jì)數(shù)器。3 .按照SCANT法從第一個(gè)子隊(duì)列剩余的項(xiàng)中選擇一個(gè)合適的請(qǐng)求。最后，需要將第一個(gè)子 隊(duì)列剩余長(zhǎng)度減少1 (SubQueueRemainLength減少1),如果第一個(gè)子隊(duì)列剩余長(zhǎng)度變?yōu)?,說(shuō)明第一個(gè)子隊(duì)列處理完畢，需要將子隊(duì)列剩余的長(zhǎng)度重新變?yōu)镹 (SubQueueRemainLength重新賦值為SUB_QUEUE_LENGTH從而開始處理下一個(gè)子隊(duì)列。ULONG SubQueueRemainLength = SUB_QUEUE_LENGTH;/掃描算法中磁頭移動(dòng)的方向。操作系統(tǒng)啟動(dòng)時(shí)初始化為磁頭向內(nèi)移動(dòng)。/ TRUE ,磁頭向內(nèi)移動(dòng)，磁道號(hào)增加。 FALSE ,磁頭

50、向外移動(dòng)，磁道號(hào)減少。BOOL ScanInside = TRUE; PREQUEST IopDiskSchedule( VOID ) PLIST_ENTRY pListEntry; PREQUEST pRequest;PREQUEST INpNextRequest = NULL;PREQUEST OUTpNextRequest = NULL; LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0xFFFFFFFF;PREQUEST pNextRequest = NULL;

51、ULONG counter;/需要遍歷請(qǐng)求隊(duì)列一次或兩次/計(jì)數(shù)器記錄一個(gè)子隊(duì)列剩余的長(zhǎng)度 counter=SubQueueRemainLength ;/每調(diào)度一次子隊(duì)列剩余的長(zhǎng)度減一SubQueueRemainLength- ；/ 如果子隊(duì)列剩余長(zhǎng)度為0 ，則重置為子隊(duì)列原長(zhǎng)度if(SubQueueRemainLength=0)SubQueueRemainLength=SUB_QUEUE_LENGTH;for (pListEntry = RequestListHead.Next;/ 請(qǐng)求隊(duì)列中的第一個(gè)請(qǐng)求是鏈表頭指向的下一個(gè)請(qǐng)求。pListEntry != &RequestListHe

52、ad && counter>0; /遍歷到請(qǐng)求隊(duì)列頭時(shí)結(jié)束循環(huán)或子隊(duì)列結(jié)束。pListEntry = pListEntry->Next) /根據(jù)鏈表項(xiàng)獲得請(qǐng)求的指針pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);/ 計(jì)算請(qǐng)求對(duì)應(yīng)的線程所訪問(wèn)的磁道與當(dāng)前磁頭所在磁道的偏移(方向由正負(fù)表示)Offset = pRequest->Cylinder - CurrentCylinder;if (0 = Offset) / 如果線程要訪問(wèn)的磁道與當(dāng)前磁頭所在磁道相同，可立即返回。pNextReque

53、st = pRequest; goto RETURN; else if (Offset<InsideShortestDistance && Offset > 0) / 記錄向內(nèi)移動(dòng)距離最短的線程InsideShortestDistance = Offset;INpNextRequest = pRequest;else if (-Offset < OutsideShortestDistance && Offset < 0) / 記錄向外移動(dòng)距離最短的線程OutsideShortestDistance = -Offset;OUTpNextRe

54、quest = pRequest; counter-; /判斷磁頭移動(dòng)方向，若向內(nèi)移動(dòng)if(ScanInside) / 判斷是否有向內(nèi)移動(dòng)的線程if(INpNextRequest)/有則原則該進(jìn)程return INpNextRequest; else / 沒(méi)有則修改磁頭方向，選擇向外移動(dòng)距離最短的線程ScanInside=!ScanInside;return OUTpNextRequest; /如果向外移動(dòng)else / 判斷是否有向外移動(dòng)的線程if(OUTpNextRequest) / 有則選擇該進(jìn)程return OUTpNextRequest; else / 沒(méi)有則修改磁頭的方向，選擇向內(nèi)移動(dòng)距離最短的線程ScanInside =!ScanInside;return INpNextRequest; 3.9.3 測(cè)試方法使用本實(shí)驗(yàn)3.2 中的數(shù)據(jù)進(jìn)行測(cè)試，確保調(diào)度的結(jié)果與圖 18-8 中顯示的一致。嘗試在控制臺(tái)中多次輸入ds”命令，查看磁盤調(diào)度算法執(zhí)行的情況，說(shuō)明為什么調(diào)度的順序會(huì)發(fā)生變化。將 “輸出 ”窗口中的內(nèi)容復(fù)制到