磁盤調度算法實驗報告

1、操作系統(tǒng)實 驗 報 告課程名稱操作系統(tǒng)實驗課程編號0906553實驗項目名稱磁盤調度算法學號年級姓名專業(yè)計算機科學與技術學生所在學院計算機科學與技術學院指導教師實驗室名稱地點 哈爾濱工程大學計算機科學與技術學院磁盤調度算法一 實驗概述：1.實驗名稱：磁盤調度算法2.實驗目的：1）通過學習 EOS 實現(xiàn)磁盤調度算法的機制，掌握磁盤調度算法執(zhí)行的條件和時機；2）觀察 EOS 實現(xiàn)的 FCFS、SSTF 和 SCAN 磁盤調度算法，了解常用的磁盤調度算法；3）編寫 CSCAN 和 N-Step-SCAN 磁盤調度算法，加深對各種掃描算法的理解。3.實驗類型：驗證、設計4.實驗內(nèi)容： 1）準備實驗，創(chuàng)

2、建一個EOS Kernel項目； 2）驗證先來先服務（FCFS）磁盤調度算法； 3）驗證最短尋道時間優(yōu)先（SSTF）磁盤調度算法； 4）驗證SSTF算法造成的線程“饑餓現(xiàn)象”； 5）驗證掃描（SCAN）磁盤調度算法； 6）改寫SCAN算法； 7）編寫循環(huán)掃描（CSCAN）磁盤調度算法； 8）驗證SSTF、SCAN及CSCAN算法中的“磁臂粘著”現(xiàn)象； 9）編寫N-Step-SCAN磁盤調度算法。二實驗環(huán)境操作系統(tǒng)：windows XP編譯器：Tevalaton OS Lab語言：C三實驗過程1.設計思路和流程圖： SCAN算法流程圖： SSTF算法的流程圖： CSACN流程圖：循環(huán)結束后記錄了

3、向內(nèi)移動距離最短的線程和向外移動距離最長的線程 有向內(nèi)移動的線程？ YES NO選擇向內(nèi)移動距離最短的線程選擇向外移動距離最長的線程N-STEP-SCAN算法調度：2.實驗過程：1）新建一個 EOS Kernel 項目；2）在 sysproc.c 文件中找到控制臺命令“ds”對應的函數(shù) ConsoleCmdDiskSchedule?！?ds” 命令專門用來測試磁盤調度算法。閱讀該函數(shù)中的源代碼，目前該函數(shù)使磁頭初始停留在磁道 10， 其它被阻塞的線程依次訪問磁道 8、21、9、78、0、41、10、67、12、10；3）打開 io/block.c 文件，在 第 378 行找到磁盤調度算法函數(shù)

4、IopDiskSchedule。閱讀該函數(shù)中的源代碼，目前此函數(shù)實現(xiàn)了 FCFS 磁盤調度算法，流程圖如下：4）生成項目，啟動調試，待 EOS 啟動完畢，在 EOS 控制臺中輸入命令“ds”后按回車；在 EOS 控制臺中會首先顯示磁頭的起始位置是 10 磁道，然后按照線程被阻塞的順序依次顯示線程的 信息（包括線程 ID 和訪問的磁道號）。磁盤調度算法執(zhí)行的過程中，在 OS Lab 的“輸出”窗口中也會首 先顯示磁頭的起始位置，然后按照線程被喚醒的順序依次顯示線程信息（包括線程 ID、訪問的磁道號、磁 頭移動的距離和方向），并在磁盤調度結束后顯示此次調度的統(tǒng)計信息（包括總尋道數(shù)、尋道次數(shù)和平均

5、尋道數(shù)）。對比 EOS 控制臺和“輸出”窗口中的內(nèi)容，可以發(fā)現(xiàn) FCFS 算法是根據(jù)線程訪問磁盤的先后順序 進行調度的。下圖顯示了本次調度執(zhí)行時磁頭移動的軌跡：5）打開sstf.c 文件，該文件提供的 IopDiskSchedule 函數(shù)實現(xiàn)了 SSTF 磁盤調度算法，其中應注意：變量 Offset 是有符號的長整型，用來表示磁頭的偏移（包括距離和方向）。Offset 大于 0 時表示 磁頭向內(nèi)移動（磁道號增加）；小于 0 時表示磁頭向外移動（磁道號減少）；等于 0 時表示磁頭沒 有移動。而名稱以“Distance”結尾的變量都是無符號長整型，只表示磁頭移動的距離（無方向）。 所以在比較磁頭的

6、偏移和距離時，或者在將偏移賦值給距離時，都要取偏移的絕對值（調用 C 庫 函數(shù) abs）。本實驗在實現(xiàn)其它磁盤調度算法時也同樣遵守此約定；在開始遍歷之前，將最小距離（ShortestDistance）初始化為最大的無符號長整型數(shù)，這樣，第 一次計算的距離一定會小于最小距離，從而可以使用第一次計算的距離來再次初始化最小距離。 本實驗在實現(xiàn)其它磁盤調度算法時也同樣使用了此技巧。6）生成項目，啟動調試，待EOS 啟動完畢，在 EOS 控制臺中輸入命令“ds”后按回車；對比 EOS 控制臺和“輸出”窗口中的內(nèi)容（特別是線程 ID 的順序），可以發(fā)現(xiàn)，SSTF 算法喚醒線程的 順序與線程被阻塞的順序是不

7、同的。圖18-4顯示了本次調度執(zhí)行時磁頭移動的軌跡。對比SSTF算法與FCFS 算法在“輸出”窗口中的內(nèi)容，可以看出，SSTF 算法的平均尋道數(shù)明顯低于 FCFS 算法。7）驗證SSTF算法造成的線程“饑餓現(xiàn)象”，使用 SSTF 算法時，如果不斷有新線程要求訪問磁盤，而且其所要訪問的磁道與當前磁頭所在磁道的 距離較近，這些新線程的請求必然會被優(yōu)先滿足，而等待隊列中一些老線程的請求就會被嚴重推遲，從而 使老線程出現(xiàn)“饑餓”現(xiàn)象。8）修改sysproc.c文件ConsoleCmdDiskSchedule函數(shù)中的源代碼，仍然使磁頭初始停留在磁道10，而讓其它線程依次訪問磁道 78、21、9、8、11

8、、41、10、67、12、10，生成項目，啟動調試，待 EOS 啟動完畢，在 EOS 控制臺中輸入命令“ds”后按回車；查看“輸出”窗口中顯示的內(nèi)容，可以發(fā)現(xiàn)，雖然訪問 78 號磁道的線程的請求第一個被放入請求隊 列，但卻被推遲到最后才被處理，出現(xiàn)了“饑餓”現(xiàn)象。如果不斷有新線程的請求到達并被優(yōu)先滿足，則 訪問 78 號磁道的線程的“饑餓”情況就會更加嚴重；修改訪問磁道順序：修改后執(zhí)行“ds”命令的結果：多次輸入“ds”命令：9）對 SSTF 算法稍加改進后可以形成 SCAN 算法，可防止老線程出現(xiàn)“饑餓”現(xiàn)象。打開scan.c 文件，該文件提供的 IopDiskSchedule 函數(shù)實現(xiàn)了

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

10、能找到合適的線程。10）使用 scan.c 文件中 IopDiskSchedule 函數(shù)的函數(shù)體，替換 block.c 文件中 IopDiskSchedule 函 數(shù)的函數(shù)體，生成項目，啟動調試，待 EOS 啟動完畢，在 EOS 控制臺中輸入命令“ds”后按回車；對比 SCAN 算法與 SSTF 算法在“輸出”窗口中的內(nèi)容，可以看出，SCAN 算法的平均尋道數(shù)有可能小于 SSTF 算法，所以說 SSTF 算法不能保證平均尋道數(shù)最少。下圖顯示了本次調度執(zhí)行時磁頭移動的軌跡：11）改寫SCAN算法，算法提示：在一次遍歷中，不再關心當前磁頭移動的方向，而是同時找到兩個方向上移動距離最短的線程所 對應

11、的請求，這樣就不再需要遍歷兩次；在計算出線程要訪問的磁道與當前磁頭所在磁道的偏移后，可以將偏移分為三種類型：偏移為 0，表示線程要訪問的磁道與當前磁頭所在磁道相同，此情況應該優(yōu)先被調度，可立即返回該線程對應的請求的指針；偏移大于 0，記錄向內(nèi)移動距離最短的線程對應的請求；偏移小于0，記錄向 外移動距離最短的線程對應的請求；循環(huán)結束后，根據(jù)當前磁頭移動的方向選擇同方向移動距離最短的線程，如果在同方向上沒有線 程，就變換方向，選擇反方向移動距離最短的線程；流程如下所示：SCAN改寫代碼：PREQUESTIopDiskSchedule(VOID)PLIST_ENTRY pListEntry;PREQ

12、UEST pRequest;PREQUEST INpNextRequest = NULL; PREQUEST OUTpNextRequest = NULL;LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0xFFFFFFFF;PREQUEST pNextRequest = NULL;/ 需要遍歷請求隊列一次或兩次 for (pListEntry = RequestListHead.Next;/ 請求隊列中的第一個請求是鏈表頭指向的下一個請求。 pListEntry !=

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

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

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

16、 =!ScanInside; return INpNextRequest; RETURN:return pNextRequest;修改完SCAN算法后輸入“ds”命令：12) 在已經(jīng)完成的 SCAN 算法源代碼的基礎上進行改寫，不再使用全局變量 ScanInside 確定磁頭移動的方 向，而是規(guī)定磁頭只能從外向內(nèi)移動。當磁頭移動到最內(nèi)的被訪問磁道時，磁頭立即移動到最外的被訪問 磁道，即將最大磁道號緊接著最小磁道號構成循環(huán)，進行掃描。 由于磁頭移動的方向被固定，也就不需要根據(jù)磁頭移動的方向進行分類處理，所以 CSCAN 算法的源代 碼會較 SCAN 算法更加簡單。改寫提示：由于規(guī)定了磁頭只能從外

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

18、向外移動距離最長的線程。CSCAN修改代碼：PREQUESTIopDiskSchedule(VOID)PLIST_ENTRY pListEntry;PREQUEST pRequest;PREQUEST INpNextRequest = NULL; PREQUEST OUTpNextRequest = NULL;LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0x00000000;PREQUEST pNextRequest = NULL;/ 需要遍歷請求隊列一次或兩次 fo

19、r (pListEntry = RequestListHead.Next;/ 請求隊列中的第一個請求是鏈表頭指向的下一個請求。 pListEntry != &RequestListHead;/ 遍歷到請求隊列頭時結束循環(huán)。 pListEntry = pListEntry->Next) / 根據(jù)鏈表項獲得請求的指針pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);/ 計算請求對應的線程所訪問的磁道與當前磁頭所在磁道的偏移（方向由正負表示）Offset = pRequest->Cylinder - Curr

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

21、 < 0) / 記錄向外移動距離最短的線程OutsideShortestDistance = -Offset;OUTpNextRequest = pRequest;/需要向內(nèi)移動的線程是否存在if(INpNextRequest) /存在則返回向內(nèi)移動的請求 return INpNextRequest; else /沒有則返回向外移動的請求 return OUTpNextRequest; RETURN:return pNextRequest;13） 啟動修改后的程序，輸入“ds”命令，查看磁盤調度算法的執(zhí)行情況。 14）觀察執(zhí)行 SSTF、SCAN 及 CSCAN 算法時磁頭移動的軌跡可以

22、看到，在 開始時磁頭都停留在10磁道不動，這就是“磁臂粘著”現(xiàn)象，通過修改代碼，進一步觀察。修改sysproc.c文件ConsoleCmdDiskSchedule函數(shù)中的源代碼，仍然使磁頭初始停留在磁道10， 而讓其它線程依次訪問磁道 78、10、10、10、10、10、10、10、10、10，分別使用 SSTF、SCAN 和 CSCAN 算法調度這組數(shù)據(jù)。查看各種算法在“輸出”窗口中顯示的內(nèi)容，可以發(fā)現(xiàn)，雖然訪問 78 號磁道的線程的請求第一個被 放入請求隊列，但卻被推遲到最后才被處理，出現(xiàn)了“磁臂粘著”現(xiàn)象。SCAN算法測試：CSCAN算法測試：SSTF算法測試：15）在已經(jīng)完成的 SCA

23、N 算法源代碼的基礎上進行改寫，將請求隊列分成若干個長度為 N 的子隊列，調度 程序按照 FCFS 原則依次處理這些子隊列，而每處理一個子隊列時，又是按照 SCAN 算法，修改提示：在 block.c 文件中的第 360 行定義了一個宏 SUB_QUEUE_LENGTH，表示子隊列的長度（即 N 值）。 目前這個宏定義的值為 6。在第 367 行定義了一個全局變量 SubQueueRemainLength，表示第一個 子隊列剩余的長度，并初始化其值為 SUB_QUEUE_LENGTH；在執(zhí)行 N-Step-SCAN 算法時，要以第一個子隊列剩余的長度做為計數(shù)器，確保只遍歷第一個子隊 列剩余的項

24、。所以，結束遍歷的條件就既包括第一個子隊列結束，又包括整個隊列結束（如果整個隊列的長度小于第一個子隊列剩余的長度）。注意，不要直接使用第一個子隊列剩余的長度做 為計數(shù)器，可以定義一個新的局部變量來做為計數(shù)器；按照 SCAN 算法從第一個子隊列剩余的項中選擇一個合適的請求。最后，需要將第一個子隊列剩 余長度減少 1（SubQueueRemainLength 減少 1），如果第一個子隊列剩余長度變?yōu)?0，說明第一個 子隊列處理完畢，需要將子隊列剩余的長度重新變?yōu)?N（SubQueueRemainLength 重新賦值為 SUB_QUEUE_LENGTH），從而開始處理下一個子隊列；修改代碼：/ N

25、-Step-SCAN 磁盤調度算法使用的子隊列長度 N#define SUB_QUEUE_LENGTH/ 記錄 N-Step-SCAN 磁盤調度算法第一個子隊列剩余的長度。/ 子隊列初始長度為 N，每執(zhí)行一次磁盤調度算法會從子隊列中移除一個請求，子隊列/ 長度就要減少 1，待長度變?yōu)?0 時，再將長度重新變?yōu)?N，開始處理下一個子隊列。ULONG SubQueueRemainLength = SUB_QUEUE_LENGTH;/ 掃描算法中磁頭移動的方向。操作系統(tǒng)啟動時初始化為磁頭向內(nèi)移動。/ TRUE，磁頭向內(nèi)移動，磁道號增加。/ FALSE，磁頭向外移動，磁道號減少。BOOL ScanIn

26、side = TRUE;PREQUESTIopDiskSchedule(VOID)PLIST_ENTRY pListEntry;PREQUEST pRequest;PREQUEST INpNextRequest = NULL; PREQUEST OUTpNextRequest = NULL;LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0xFFFFFFFF;PREQUEST pNextRequest = NULL;ULONG counter;/ 需要遍歷請求隊列一次或兩

27、次/計數(shù)器記錄一個子隊列剩余的長度counter=SubQueueRemainLength；/每調度一次子隊列剩余的長度減一SubQueueRemainLength-；/如果子隊列剩余長度為0，則重置為子隊列原長度if(SubQueueRemainLength=0) SubQueueRemainLength=SUB_QUEUE_LENGTH; for (pListEntry = RequestListHead.Next;/ 請求隊列中的第一個請求是鏈表頭指向的下一個請求。 pListEntry != &RequestListHead && counter>0;/ 遍歷到請求隊列頭時結束循環(huán)或子隊列結束。 pListEntry = pListEntry->Next) / 根據(jù)鏈表項獲得請求的指針pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);/ 計算請求對應的線程所訪問的磁道與當前磁頭所在磁道的偏移（方向由正負表示）Offset = pRequest->Cylinder - CurrentCylinder;if (0 = Offset) / 如果線程要訪問的磁道與當前磁頭所在磁道相同，可立即返回。pNextRequest