第十講 磁盤調度算法

操作系統(tǒng)實驗報告課程名稱操作系統(tǒng)實驗實驗項目名稱磁盤調度算法學號班級姓名專業(yè)計算機科學與技術學生所在學院計算機學院指導教師實驗室名稱地點計算機基礎實驗第七實驗室哈爾濱工程大學計算機科學與技術學院一、實驗概述1.實驗名稱磁盤調度算法2.實驗目的=1\*ROMANI．通過學習EOS實現(xiàn)磁盤調度算法的機制，掌握磁盤調度算法執(zhí)行的條件和時機。=2\*ROMANII.觀察EOS實現(xiàn)的FCFS、SSTF和SCAN磁盤調度算法，了解常用的磁盤調度算法。=3\*ROMANIII.編寫CSCAN和N-Step-SCAN磁盤調度算法，加深對各種掃描算法的理解。3.實驗類型（驗證、設計）驗證＋設計4.實驗內容1.準備實驗2.驗證先來先服務（FCFS）磁盤調度算法2.1在“項目管理器”窗口中雙擊ke文件夾中的sysproc.c文件，打開此文件。2.2在sysproc.c文件的第580行找到控制臺命令“ds”對應的函數(shù)ConsoleCmdDiskSchedule。2.3打開io/block.c文件，在第378行找到磁盤調度算法函數(shù)IopDiskSchedule。2.4按F7生成項目，然后按F5啟動調試。3.驗證最短尋道時間優(yōu)先（SSTF）磁盤調度算法3.1使用sstf.c文件中IopDiskSchedule函數(shù)的函數(shù)體，替換block.c文件中IopDiskSchedule函數(shù)的函數(shù)體。3.2按F7生成項目，然后按F5啟動調試。3.3待EOS啟動完畢，在EOS控制臺中輸入命令“ds”后按回車。4.驗SSTF算法造成的線程“饑餓”現(xiàn)象4.1修改sysproc.c文件ConsoleCmdDiskSchedule函數(shù)中的源代碼，仍然使磁頭初始停留在磁道10，而讓其它線程依次訪問磁道78、21、9、8、11、41、10、67、12、10。4.2按F7生成項目，然后按F5啟動調試。4.3待EOS啟動完畢，在EOS控制臺中輸入命令“ds”后按回車。5.驗證掃描（SCAN）磁盤調度算法6.改寫SCAN算法二、實驗環(huán)境操作系統(tǒng)：EOS操作系統(tǒng)編譯器：IDE集成實驗環(huán)境語言：C語言三、實驗過程（1）驗證先來先服務（FCFS）磁盤調度算法1.在“項目管理器”窗口中雙擊ke文件夾中的sysproc.c文件，打開此文件。2.在sysproc.c文件的第580行找到控制臺命令“ds”對應的函數(shù)ConsoleCmdDiskSchedule。“ds”命令專門用來測試磁盤調度算法。閱讀該函數(shù)中的源代碼，目前該函數(shù)使磁頭初始停留在磁道10，其它被阻塞的線程依次訪問磁道8、21、9、78、0、41、10、67、12、10。3.打開io/block.c文件，在第378行找到磁盤調度算法函數(shù)IopDiskSchedule。閱讀該函數(shù)中的源代碼，目前此函數(shù)實現(xiàn)了FCFS磁盤調度算法，其流程圖可以參見圖18-1。4.按F7生成項目，然后按F5啟動調試。5.待EOS啟動完畢，在EOS控制臺中輸入命令“ds”后按回車。FCFS磁盤調度算法，“輸出”結果:******Diskschedulestartworking******StartCylinder:10TID:31Cylinder:8Offset:2-TID:32Cylinder:21Offset:13+TID:33Cylinder:9Offset:12-TID:34Cylinder:78Offset:69+TID:35Cylinder:0Offset:78-TID:36Cylinder:41Offset:41+TID:37Cylinder:10Offset:31-TID:38Cylinder:67Offset:57+TID:39Cylinder:12Offset:55-TID:40Cylinder:10Offset:2-Totaloffset:360Transfertimes:10Averageoffset:36（2）驗證最短尋道時間優(yōu)先（SSTF）磁盤調度算法1.使用sstf.c文件中IopDiskSchedule函數(shù)的函數(shù)體，替換block.c文件中IopDiskSchedule函數(shù)的函數(shù)體。2.按F7生成項目，然后按F5啟動調試。3.待EOS啟動完畢，在EOS控制臺中輸入命令“ds”后按回車。4.對比EOS控制臺和“輸出”窗口中的內容（特別是線程ID的順序），可以發(fā)現(xiàn)，SSTF算法喚醒線程的順序與線程被阻塞的順序是不同的。圖18-4顯示了本次調度執(zhí)行時磁頭移動的軌跡。對比SSTF算法與FCFS算法在“輸出”窗口中的內容，可以看出，SSTF算法的平均尋道數(shù)明顯低于FCFS算法。SSTF磁盤調度算法，“輸出”結果:******Diskschedulestartworking******StartCylinder:10TID:37Cylinder:10Offset:0=TID:40Cylinder:10Offset:0=TID:33Cylinder:9Offset:1-TID:31Cylinder:8Offset:1-TID:39Cylinder:12Offset:4+TID:32Cylinder:21Offset:9+TID:36Cylinder:41Offset:20+TID:38Cylinder:67Offset:26+TID:34Cylinder:78Offset:11+TID:35Cylinder:0Offset:78-Totaloffset:150Transfertimes:10Averageoffset:15******Diskschedulestopworking******（3）驗證SSTF算法造成的線程“饑餓”現(xiàn)象修改sysproc.c文件ConsoleCmdDiskSchedule函數(shù)中的源代碼，仍然使磁頭初始停留在磁道10，而讓其它線程依次訪問磁道78、21、9、8、11、41、10、67、12、10。按F7生成項目，然后按F5啟動調試。待EOS啟動完畢，在EOS控制臺中輸入命令“ds”后按回車。查看“輸出”窗口中顯示的內容，可以發(fā)現(xiàn)，雖然訪問78號磁道的線程的請求第一個被放入請求隊列，但卻被推遲到最后才被處理，出現(xiàn)了“饑餓”現(xiàn)象。如果不斷有新線程的請求到達并被優(yōu)先滿足，則訪問78號磁道的線程的“饑餓”情況就會更加嚴重。SSTF算法造成的線程“饑餓”現(xiàn)象，“輸出”結果:******Diskschedulestartworking******StartCylinder:10TID:37Cylinder:10Offset:0=TID:40Cylinder:10Offset:0=TID:33Cylinder:9Offset:1-TID:34Cylinder:8Offset:1-TID:35Cylinder:11Offset:3+TID:39Cylinder:12Offset:1+TID:32Cylinder:21Offset:9+TID:36Cylinder:41Offset:20+TID:38Cylinder:67Offset:26+TID:31Cylinder:78Offset:11+Totaloffset:72Transfertimes:10Averageoffset:7******Diskschedulestopworking******(4)驗證掃描（SCAN）磁盤調度算法1.使用scan.c文件中IopDiskSchedule函數(shù)的函數(shù)體，替換block.c文件中IopDiskSchedule函數(shù)的函數(shù)體。2.按F7生成項目，然后按F5啟動調試。3.待EOS啟動完畢，在EOS控制臺中輸入命令“ds”后按回車。4.對比SCAN算法與SSTF算法在“輸出”窗口中的內容，可以看出，SCAN算法的平均尋道數(shù)有可能小于SSTF算法，所以說SSTF算法不能保證平均尋道數(shù)最少。驗證電梯調度解決最鄰近優(yōu)先的饑餓，78在調度隊列首:******Diskschedulestartworking******StartCylinder:10TID:37Cylinder:10Offset:0=TID:40Cylinder:10Offset:0=TID:35Cylinder:11Offset:1+TID:39Cylinder:12Offset:1+TID:32Cylinder:21Offset:9+TID:36Cylinder:41Offset:20+TID:38Cylinder:67Offset:26+TID:31Cylinder:78Offset:11+TID:33Cylinder:9Offset:69-TID:34Cylinder:8Offset:1-Totaloffset:138Transfertimes:10Averageoffset:13******Diskschedulestopworking******（5）改寫SCAN算法在一次遍歷中，不再關心當前磁頭移動的方向，而是同時找到兩個方向上移動距離最短的線程所對應的請求，這樣就不再需要遍歷兩次。在計算出線程要訪問的磁道與當前磁頭所在磁道的偏移后，可以將偏移分為三種類型：偏移為0，表示線程要訪問的磁道與當前磁頭所在磁道相同，此情況應該優(yōu)先被調度，可立即返回該線程對應的請求的指針；偏移大于0，記錄向內移動距離最短的線程對應的請求；偏移小于0，記錄向外移動距離最短的線程對應的請求。循環(huán)結束后，根據(jù)當前磁頭移動的方向選擇同方向移動距離最短的線程，如果在同方向上沒有線程，就變換方向，選擇反方向移動距離最短的線程。具體邏輯可以參見圖18-6所示的流程圖。源代碼PLIST_ENTRYpListEntry; PREQUESTpRequest; LONGOffset; ULONGInsideShortestDistance=0xFFFFFFFF; ULONGOutsideShortestDistance=0xFFFFFFFF;//設置兩個指針變量 PREQUESTpNextRequest_1=NULL;PREQUESTpNextRequest_2=NULL; PREQUESTpNextRequest=NULL; // //需要遍歷請求隊列一次或兩次 // for(pListEntry=RequestListHead.Next; //請求隊列中的第一個請求是鏈表頭指向的下一個請求。 pListEntry!=&RequestListHead; //遍歷到請求隊列頭時結束循環(huán)。 pListEntry=pListEntry->Next) {//根據(jù)鏈表項獲得請求的指針pRequest=CONTAINING_RECORD(pListEntry,REQUEST,ListEntry); //計算請求對應的線程所訪問的磁道與當前磁頭所在磁道的偏移（方向由正負表示） Offset=pRequest->Cylinder-CurrentCylinder; if(0==Offset)//如果線程要訪問的磁道與當前磁頭所在磁道相同，可立即返回。 { pNextRequest=pRequest; returnpNextRequest; } if(Offset>0) { if(Offset<InsideShortestDistance) { InsideShortestDistance=Offset;//記錄向內移動距離最短的線程 pNextRequest_1=pRequest; } } if(Offset<0) { if(-Offset<OutsideShortestDistance) { OutsideShortestDistance=-Offset;//記錄向外移動距離最短的線程 pNextRequest_2=pRequest; } } } //循環(huán)結束后同時記錄了兩個方向上移動距離最短的線程if(ScanInside)//是否有向內的線程 {if(pNextRequest_1)returnpNextRequest_1;//返回向內移動距離最短的線程 else {ScanInside=!ScanInside;returnpNextRequest_2;//選擇向外移動距離最短的線程 } }else//有向外的線程 {if(pNextRequest_2) returnpNextRequest_2;//選擇向外移動距離最短的線程 else {ScanInside=!ScanInside;returnpNextRequest_1;//選擇向內移動距離最短的線程 } } 輸出結果：******Diskschedulestartworking******StartCylinder:10TID:37Cylinder:10Offset:0=TID:40Cylinder:10Offset:0=TID:39Cylinder:12Offset:2+TID:32Cylinder:21Offset:9+TID:36Cylinder:41Offset:20+TID:38Cylinder:67Offset:26+TID:34Cylinder:78Offset:11+TID:33Cylinder:9Offset:69-TID:31Cylinder:8Offset:1-TID:35Cylinder:0Offset:8-Totaloffset:14