1、PAGE PAGE 29操作系統(co zu x tn)實 驗 報 告課程名稱操作系統實驗課程編號0906553實驗項目名稱磁盤調度算法學號年級姓名專業計算機科學與技術學生所在學院計算機科學與技術學院指導教師實驗室名稱地點 哈爾濱工程大學計算機科學與技術(jsh)學院磁盤調度(diod)算法實驗概述：1.實驗名稱：磁盤調度算法2.實驗(shyn)目的：1）通過(tnggu)學習 EOS 實現磁盤調度(diod)算法的機制，掌握磁盤調度算法執行的條件和時機；2）觀察 EOS 實現的 FCFS、SSTF 和 SCAN 磁盤調度算法，了解常用的磁盤調度算法；3）編寫 CSCAN 和 N-Step-S

2、CAN 磁盤調度算法，加深對各種掃描算法的理解。3.實驗類型：驗證、設計4.實驗內容： 1）準備實驗，創建一個EOS Kernel項目； 2）驗證先來先服務（FCFS）磁盤調度算法； 3）驗證最短尋道時間優先（SSTF）磁盤調度算法； 4）驗證SSTF算法造成的線程“饑餓現象”； 5）驗證掃描（SCAN）磁盤調度算法； 6）改寫SCAN算法； 7）編寫循環掃描（CSCAN）磁盤調度算法； 8）驗證SSTF、SCAN及CSCAN算法中的“磁臂粘著”現象； 9）編寫N-Step-SCAN磁盤調度算法。二實驗環境操作系統：windows XP編譯器：Tevalaton OS Lab語言：C三實驗過程

3、1.設計思路和流程圖： SCAN算法流程圖： SSTF算法(sun f)的流程圖： CSACN流程圖：循環結束后記錄了向內移動距離最短的線程和向外移動距離最長的線程 有向內移動(ydng)的線程？ YES NO選擇向內移動距離最短的線程選擇向外移動距離最長的線程N-STEP-SCAN算法(sun f)調度：2.實驗(shyn)過程：1）新建一個 EOS Kernel 項目；2）在 sysproc.c 文件中找到控制臺命令“ds”對應的函數 ConsoleCmdDiskSchedule。“ ds” 命令專門用來測試磁盤調度算法。閱讀該函數中的源代碼，目前該函數使磁頭初始停留在磁道 10， 其它被

4、阻塞的線程依次訪問磁道 8、21、9、78、0、41、10、67、12、10；3）打開(d ki) io/block.c 文件(wnjin)，在 第 378 行找到磁盤(c pn)調度算法函數 IopDiskSchedule。閱讀該函數中的源代碼，目前此函數實現了 FCFS 磁盤調度算法，流程圖如下：4）生成項目，啟動調試，待 EOS 啟動完畢，在 EOS 控制臺中輸入命令“ds”后按回車；在 EOS 控制臺中會首先顯示磁頭的起始(q sh)位置是 10 磁道，然后按照(nzho)線程被阻塞的順序依次(yc)顯示線程的 信息（包括線程 ID 和訪問的磁道號）。磁盤調度算法執行的過程中，在 OS

5、 Lab 的“輸出”窗口中也會首 先顯示磁頭的起始位置，然后按照線程被喚醒的順序依次顯示線程信息（包括線程 ID、訪問的磁道號、磁 頭移動的距離和方向），并在磁盤調度結束后顯示此次調度的統計信息（包括總尋道數、尋道次數和平均 尋道數）。對比 EOS 控制臺和“輸出”窗口中的內容，可以發現 FCFS 算法是根據線程訪問磁盤的先后順序 進行調度的。下圖顯示了本次調度執行時磁頭移動的軌跡：5）打開sstf.c 文件，該文件提供的 IopDiskSchedule 函數實現了 SSTF 磁盤調度算法，其中應注意：變量 Offset 是有符號的長整型，用來表示磁頭的偏移（包括距離和方向）。Offset 大

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

7、其它磁盤調度算法時也同樣使用了此技巧。6）生成項目，啟動調試，待EOS 啟動完畢，在 EOS 控制臺中輸入命令“ds”后按回車；對比 EOS 控制臺和“輸出”窗口中的內容（特別是線程 ID 的順序），可以發現，SSTF 算法喚醒線程的 順序與線程被阻塞的順序是不同的。圖18-4顯示了本次調度執行時磁頭移動的軌跡。對比SSTF算法與FCFS 算法在“輸出”窗口中的內容，可以看出，SSTF 算法的平均尋道數明顯低于 FCFS 算法。7）驗證(ynzhng)SSTF算法造成(zo chn)的線程“饑餓現象”，使用 SSTF 算法時，如果不斷有新線程要求訪問磁盤，而且(r qi)其所要訪問的磁道與當前

8、磁頭所在磁道的 距離較近，這些新線程的請求必然會被優先滿足，而等待隊列中一些老線程的請求就會被嚴重推遲，從而 使老線程出現“饑餓”現象。8）修改sysproc.c文件ConsoleCmdDiskSchedule函數中的源代碼，仍然使磁頭初始停留在磁道10，而讓其它線程依次訪問磁道 78、21、9、8、11、41、10、67、12、10，生成項目，啟動調試，待 EOS 啟動完畢，在 EOS 控制臺中輸入命令“ds”后按回車；查看“輸出”窗口中顯示的內容，可以發現，雖然訪問 78 號磁道的線程的請求第一個被放入請求隊 列，但卻被推遲到最后才被處理，出現了“饑餓”現象。如果不斷有新線程的請求到達并被

9、優先滿足，則 訪問 78 號磁道的線程的“饑餓”情況就會更加嚴重；修改訪問磁道順序：修改(xigi)后執行“ds”命令(mng lng)的結果：多次輸入(shr)“ds”命令：9）對 SSTF 算法稍加改進(gijn)后可以形成 SCAN 算法，可防止(fngzh)老線程出現“饑餓”現象。打開scan.c 文件(wnjin)，該文件提供的 IopDiskSchedule 函數實現了 SCAN 磁盤調度算法。其中應注意下面幾點：在 block.c 文件中的第 374 行定義了一個布爾類型的全局變量 ScanInside，用于表示掃描算法中 磁頭移動的方向。該變量值為 TRUE 時表示磁頭向內移動

10、（磁道號增加）；值為 FALSE 時表示磁頭 向外移動（磁道號減少）。該變量初始化為 TRUE，表示 SCAN 算法第一次執行時，磁頭向內移動；在 scan.c 文件的 IopDiskSchedule 函數中使用了雙重循環。第一次遍歷隊列時，查找指定方向 上移動距離最短的線程，如果在指定方向上已經沒有線程，就變換方向，進行第二次遍歷，同樣 是查找移動距離最短的線程。在這兩次遍歷中一定能找到合適的線程。10）使用 scan.c 文件中 IopDiskSchedule 函數的函數體，替換 block.c 文件中 IopDiskSchedule 函 數的函數體，生成項目，啟動調試，待 EOS 啟動完

11、畢，在 EOS 控制臺中輸入命令“ds”后按回車；對比(dub) SCAN 算法(sun f)與 SSTF 算法在“輸出”窗口中的內容，可以(ky)看出，SCAN 算法的平均尋道數有可能小于 SSTF 算法，所以說 SSTF 算法不能保證平均尋道數最少。下圖顯示了本次調度執行時磁頭移動的軌跡：11）改寫(gixi)SCAN算法(sun f)，算法提示：在一次遍歷中，不再關心當前磁頭移動(ydng)的方向，而是同時找到兩個方向上移動距離最短的線程所 對應的請求，這樣就不再需要遍歷兩次；在計算出線程要訪問的磁道與當前磁頭所在磁道的偏移后，可以將偏移分為三種類型：偏移為 0，表示線程要訪問的磁道與當

12、前磁頭所在磁道相同，此情況應該優先被調度，可立即返回該線程對應的請求的指針；偏移大于 0，記錄向內移動距離最短的線程對應的請求；偏移小于0，記錄向 外移動距離最短的線程對應的請求；循環結束后，根據當前磁頭移動的方向選擇同方向移動距離最短的線程，如果在同方向上沒有線 程，就變換方向，選擇反方向移動距離最短的線程；流程如下所示：SCAN改寫代碼：PREQUESTIopDiskSchedule(VOID)PLIST_ENTRY pListEntry;PREQUEST pRequest;PREQUEST INpNextRequest = NULL; PREQUEST OUTpNextRequest =

13、 NULL;LONG Offset;ULONG InsideShortestDistance = 0 xFFFFFFFF;ULONG OutsideShortestDistance = 0 xFFFFFFFF;PREQUEST pNextRequest = NULL;/ 需要遍歷請求隊列一次或兩次 for (pListEntry = RequestListHead.Next;/ 請求隊列中的第一個請求是鏈表頭指向的下一個請求。 pListEntry != &RequestListHead;/ 遍歷(bin l)到請求隊列頭時結束循環。 pListEntry = pListEntry-Next)

14、 / 根據鏈表項獲得(hud)請求的指針pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);/ 計算請求對應的線程所訪問的磁道與當前磁頭所在磁道的偏移（方向(fngxing)由正負表示）Offset = pRequest-Cylinder - CurrentCylinder;if (0 = Offset) / 如果線程要訪問的磁道與當前磁頭所在磁道相同，可立即返回。pNextRequest = pRequest;goto RETURN; else if (Offset 0) / 記錄向內移動距離最短的線程InsideShor

15、testDistance = Offset;INpNextRequest = pRequest; else if (-Offset OutsideShortestDistance & Offset Next) / 根據鏈表項獲得請求的指針pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);/ 計算請求對應的線程所訪問的磁道與當前磁頭所在磁道的偏移（方向由正負表示）Offset = pRequest-Cylinder - CurrentCylinder;if (0 = Offset) / 如果線程要訪問的磁道與當前磁頭所在(s

16、uzi)磁道相同，可立即返回。pNextRequest = pRequest;goto RETURN; else if (Offset 0) / 記錄(jl)向內移動距離最短的線程InsideShortestDistance = Offset;INpNextRequest = pRequest; else if (-Offset OutsideShortestDistance & Offset 0;/ 遍歷到請求隊列頭時結束循環或子隊列結束。 pListEntry = pListEntry-Next) / 根據(gnj)鏈表項獲得請求的指針pRequest = CONTAINING_RECOR

17、D(pListEntry, REQUEST, ListEntry);/ 計算(j sun)請求對應的線程所訪問的磁道與當前磁頭所在磁道的偏移（方向由正負表示）Offset = pRequest-Cylinder - CurrentCylinder;if (0 = Offset) / 如果(rgu)線程要訪問的磁道與當前磁頭所在磁道相同，可立即返回。pNextRequest = pRequest;goto RETURN; else if (Offset 0) / 記錄向內移動距離最短的線程InsideShortestDistance = Offset;INpNextRequest = pRequ

18、est; else if (-Offset OutsideShortestDistance & Offset 0) / 記錄向外移動距離最短的線程OutsideShortestDistance = -Offset;OUTpNextRequest = pRequest;counter-;/判斷磁頭移動方向，若向內移動if(ScanInside) /判斷是否有向內移動的線程 if(INpNextRequest) /有則原則該進程 return INpNextRequest; else /沒有則修改磁頭方向，選擇向外移動距離最短的線程 ScanInside=!ScanInside; return OUTpNextRequest; /如果向外移動else /判斷(pndun)是否有向外移動的線程 if(OUTpNextRequest) /有則選擇(xunz)該進程 return OUTpNextRequest; else /沒有則修改磁頭的方向，選擇(xunz)向內移動距離最短的線程 ScanInside =!ScanInside; return INpNextRequest; 16）生成項目，啟動程序，在控制臺中多次輸入“ds”命令，查看磁盤調度算法的執行情況。輸入“ds”命令進行測試：將宏定義(dngy) SUB_QUEUE_LENGTH 的值修改(xigi)為 100