磁盤(pán)調(diào)度算法實(shí)驗(yàn)報(bào)告

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

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

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

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

5、 尋道數(shù)）。對(duì)比 EOS 控制臺(tái)和“輸出”窗口中的內(nèi)容，可以發(fā)現(xiàn) FCFS 算法是根據(jù)線程訪問(wèn)磁盤(pán)的先后順序 進(jìn)行調(diào)度的。下圖顯示了本次調(diào)度執(zhí)行時(shí)磁頭移動(dòng)的軌跡：5）打開(kāi)sstf.c 文件，該文件提供的 IopDiskSchedule 函數(shù)實(shí)現(xiàn)了 SSTF 磁盤(pán)調(diào)度算法，其中應(yīng)注意：變量 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ú)方向）。 所以在比較磁頭

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

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

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

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

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

11、應(yīng)的請(qǐng)求，這樣就不再需要遍歷兩次；在計(jì)算出線程要訪問(wèn)的磁道與當(dāng)前磁頭所在磁道的偏移后，可以將偏移分為三種類(lèi)型：偏移為 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)求；循環(huán)結(jié)束后，根據(jù)當(dāng)前磁頭移動(dòng)的方向選擇同方向移動(dòng)距離最短的線程，如果在同方向上沒(méi)有線 程，就變換方向，選擇反方向移動(dòng)距離最短的線程；流程如下所示：SCAN改寫(xiě)代碼：PREQUESTIopDiskSchedule(VOID)PLIST_ENTRY pListEntry;PRE

12、QUEST 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)求是鏈表頭指向的下一個(gè)請(qǐng)求。 pListEntry !=

13、 &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)前磁頭所在磁道相同，可立即返回。pNextRequest = pRequest;goto RE

14、TURN; else if (Offset 0) / 記錄向內(nèi)移動(dòng)距離最短的線程InsideShortestDistance = Offset;INpNextRequest = pRequest; else if (-Offset OutsideShortestDistance & Offset 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 - Cur

15、rentCylinder;if (0 = Offset) / 如果線程要訪問(wèn)的磁道與當(dāng)前磁頭所在磁道相同，可立即返回。pNextRequest = pRequest;goto RETURN; else if (Offset 0) / 記錄向內(nèi)移動(dòng)距離最短的線程InsideShortestDistance = Offset;INpNextRequest = pRequest; else if (-Offset OutsideShortestDistance & Offset 0;/ 遍歷到請(qǐng)求隊(duì)列頭時(shí)結(jié)束循環(huán)或子隊(duì)列結(jié)束。 pListEntry = pListEntry-Next) / 根據(jù)鏈表

16、項(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)前磁頭所在磁道相同，可立即返回。pNextRequest = pRequest;goto RETURN; else if (Offset 0) / 記錄向內(nèi)移動(dòng)距離最短的線程InsideShortestDistance = Offset

17、;INpNextRequest = pRequest; else if (-Offset OutsideShortestDistance & Offset 0) / 記錄向外移動(dòng)距離最短的線程O(píng)utsideShortestDistance = -Offset;OUTpNextRequest = 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 INpNextReques