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

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

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

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

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

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

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

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

8、離來再次初始化最小距離。本實驗在實現(xiàn)其它磁盤調(diào)度算法時也同樣使用了此技巧。按照下面的步驟進行驗證：1 .使用sstf.c 文件中IopDiskSchedule 函數(shù)的函數(shù)體，替換block.c文件中IopDiskSchedule 函數(shù)的函數(shù)體。2 .按F7生成項目，然后按F5啟動調(diào)試。3 .待EOSB動完畢，在EO醛制臺中輸入命令ds后按回車。物出調(diào)國且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 *對比EOSS制臺和 輸出 窗口中的內(nèi)容（特別是線程 ID的順序），可以發(fā)現(xiàn)，SSTFT法喚醒線程的順序與線程被阻塞的順序是不同的。圖18-4顯示了本次調(diào)度執(zhí)行時磁頭移動的軌跡。對比SSTFI法與FCFST法在 輸出 窗口中的內(nèi)容，可以看出，SSTFI法的平均尋道數(shù)明顯低于FCFS?法。但是，SSTFT法能保證平均尋道數(shù)最少嗎？在后面的實驗中會進行驗證?？梢栽诳刂婆_中多次輸入ds命令，查看磁盤調(diào)度算法執(zhí)行的情況。將 輸出 窗口中的內(nèi)容復制到一個文本文件中，然后結束此次調(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當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 實現(xiàn)了 5STF 算法的 mpDi.k5cli.dul函«（流程圖圖SSTF算法磁頭移動的軌跡（總各道數(shù)150字道次數(shù)10平均尋道里15）圖18-3:實現(xiàn)了 SSTFT法的lopDiskSchedule函數(shù)流程圖圖

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

15、4i615'6166176186196201621|622623|62 4l625|626i按F7生成項目,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啟動調(diào)試。3.待EOSB動完畢，在EO的制臺中輸入命令 ds”后按回車。

17、將“輸出”窗口中的內(nèi)容復制到一個文本文件中，然后結束此次調(diào)試。將ConsoleCmdDiskSchedule函數(shù)中線程訪問的磁道號恢復到本實驗3.2中的樣子，在后面的實 驗中還要使用這些數(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)，雖然訪問78號磁道的線程的請求第一個被放入請 求隊

19、列，但卻被推遲到最后才被處理，出現(xiàn)了 饑餓”現(xiàn)象。如果不斷有新線程的請求到達并被優(yōu)先滿足，則訪問78號磁道的線程的 饑餓”情況就會更加嚴重。* 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 驗證掃描（SCAN磁盤調(diào)度算法又SSTFf法稍加改進后可以形成 SCANT法，可防止老線程出現(xiàn) 饑餓”現(xiàn)象。使用OSLab打開 本實驗文件夾中的scan.c文件，該文件提供的lopDiskSchedule函數(shù)

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

22、到合適的線程。按照下面的步驟進行驗證：1 .使用scan.c文件中IopDiskSchedule 函數(shù)的函數(shù)體，替換block.c文件中IopDiskSchedule 函數(shù)的函數(shù)體。2 .按F7生成項目，然后按F5啟動調(diào)試。3 .待EOSB動完畢，在EO醛制臺中輸入命令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對比SCA醇法與SSTFT法在 輸出 窗口中的內(nèi)容，可以看出，SCANT法的平均尋道數(shù)有可 能小于SSTFT法，所以說SSTFI法不能保證平均尋道數(shù)最少。圖18-5顯示了本次調(diào)度執(zhí)行時磁頭移動的軌跡。嘗試在控制臺中多次輸入ds命令，查看磁盤調(diào)度算法執(zhí)行的情況，說明為什么線程調(diào)度的順序會發(fā)生變化。將 輸出 窗口中的內(nèi)容復制到一個文本文件中，然后結束此次調(diào)試。圖18-5: SCA醇法磁頭移動的軌跡（總尋道數(shù) 146尋道次數(shù)10平均尋道數(shù)14）使用SCA醇法調(diào)度在本實驗3.4中產(chǎn)生

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

27、對應的請求，這樣就不再需要遍歷兩次。2. 在計算出線程要訪問的磁道與當前磁頭所在磁道的偏移后，可以將偏移分為三種類型：偏移為0，表示線程要訪問的磁道與當前磁頭所在磁道相同，此情況應該優(yōu)先被調(diào)度，可立即返回該線程對應的請求的指針；偏移大于0 ，記錄向內(nèi)移動距離最短的線程對應的請求；偏移小于0，記錄向外移動距離最短的線程對應的請求。3. 循環(huán)結束后，根據(jù)當前磁頭移動的方向選擇同方向移動距離最短的線程，如果在同方向上沒有線程， 就變換方向， 選擇反方向移動距離最短的線程。 具體邏輯可以參見圖 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;/ 需要遍歷請求隊列一次或兩次for (pListEntry = RequestListHead.Next; /請求隊列中的第一個請求是鏈表頭

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

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

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

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測試方法使用本實驗3.2中的數(shù)據(jù)進行測試，確保調(diào)度的結果與圖18-5中顯示的一致，也可以多準備幾組測試數(shù)據(jù)，保證改寫的SCANT法是正確的。測試成功后，將改

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

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

36、移動的線程，就選擇向外移 動距離最長的線程。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、請求隊列一次或兩次for (pListEntry = RequestListHead.Next;/ 請求隊列中的第一個請求是鏈表頭指向的下一個請求。pListEntry != &RequestListHead; /遍歷到請求隊列頭時結束循環(huán)。pListEntry = pListEntry->Next) /根據(jù)鏈表項獲得請求的指針pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);/ 計算請求對應的線程所訪問的磁道與當前磁頭所在磁道的偏移(方向由正負表示)Offset = pRequest->Cylinde

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

39、; Offset < 0) / 記錄向外移動距離最短的線程OutsideShortestDistance = -Offset;OUTpNextRequest = pRequest;/ 需要向內(nèi)移動的線程是否存在if(INpNextRequest)/ 存在則返回向內(nèi)移動的請求return INpNextRequest; else / 沒有則返回向外移動的請求return OUTpNextRequest;RETURN: return pNextRequest;啟動修改后的程序，輸入“ 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測試方法使用本實驗3.2中的數(shù)據(jù)進行測試，確保調(diào)度的結果與圖18-7中顯示的一致。可以在控制臺中多次輸入ds”命令，查看磁盤調(diào)度算法執(zhí)行的情況。測試成功后，將輸出”窗口中的內(nèi)容觀察執(zhí)行SSTF SCA阪CSCANT法時磁頭移動的軌跡（圖 18-4、圖18-5和圖18-7 ）,可以看到，在開始時磁頭都停留在 10磁道不動，這就是 磁臂粘著”現(xiàn)象。為了更加明顯的觀察該現(xiàn) 象，按照下面的步驟進行實驗：1.修改sysproc.c文件Console

42、CmdDiskSchedule函數(shù)中的源代碼，仍然使磁頭初始停留在磁道10,而讓其它線程依次訪問磁道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)，雖然訪問78號磁道的線程的請求第一個被放入請求隊列，但卻被推遲到最后才被處理，出現(xiàn)了磁臂粘著”現(xiàn)象。

44、將 輸出“窗口中的內(nèi)容復制到一個文本文件中后，將ConsoleCmdDiskSchedule函數(shù)中線程訪問的磁道號恢復到本實驗 3.2中的樣子，在后面的實驗中還要使用這些數(shù)據(jù)。SCANT法測試：* 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算法測試:* 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嗡法測試:* 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?法源代碼的基礎上進行改寫，將請求隊列分成若干個長度為 N的子隊列， 調(diào)度程序按照FCFSM則依次處理這些子隊列，而每處理一個子隊列時，又是按照SCANT法。3

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

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

50、向外移動，磁道號減少。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;/需要遍歷請求隊列一次或兩次/計數(shù)器記錄一個子隊列剩余的長度 counter=SubQueueRemainLength ;/每調(diào)度一次子隊列剩余的長度減一SubQueueRemainLength- ；/ 如果子隊列剩余長度為0 ，則重置為子隊列原長度if(SubQueueRemainLength=0)SubQueueRemainLength=SUB_QUEUE_LENGTH;for (pListEntry = RequestListHead.Next;/ 請求隊列中的第一個請求是鏈表頭指向的下一個請求。pListEntry != &RequestListHe

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

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

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