磁盤(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í)姓名專業(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)類型：驗(yàn)證、設(shè)計(jì)4.實(shí)驗(yàn)內(nèi)容： 1）準(zhǔn)備實(shí)驗(yàn)，創(chuàng)

2、建一個(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” 命令專門用來(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”后按回車；在 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”后按回車；對(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、11

8、、41、10、67、12、10，生成項(xiàng)目，啟動(dòng)調(diào)試，待 EOS 啟動(dòng)完畢，在 EOS 控制臺(tái)中輸入命令“ds”后按回車；查看“輸出”窗口中顯示的內(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è)布爾類型的全局變量 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”后按回車；對(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ì)應(yīng)

11、的請(qǐng)求，這樣就不再需要遍歷兩次；在計(jì)算出線程要訪問(wèn)的磁道與當(dāng)前磁頭所在磁道的偏移后，可以將偏移分為三種類型：偏移為 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;PREQ

12、UEST 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 = pRequ

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

15、equest;/判斷磁頭移動(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

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

17、向內(nèi)移動(dòng)，所以在每次遍歷中，總是同時(shí)找到向內(nèi)移動(dòng)距離最短的線程 和向外移動(dòng)距離最長(zhǎng)的線程。注意，與 SCAN 算法查找向外移動(dòng)距離最短線程不同，這里查找向 外移動(dòng)距離最長(zhǎng)的線程。在開(kāi)始遍歷前，可以將用來(lái)記錄向外移動(dòng)最長(zhǎng)距離的變量賦值為0；在計(jì)算出線程要訪問(wèn)的磁道與當(dāng)前磁頭所在磁道的偏移后，同樣可以將偏移分為三種類型：偏移為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)距離最長(zhǎng)的線程對(duì)應(yīng)的請(qǐng)求；循環(huán)結(jié)束后，選擇向內(nèi)移動(dòng)距離最短的線程，如果沒(méi)有向內(nèi)移動(dòng)的線程，就選擇

18、向外移動(dòng)距離最長(zhǎng)的線程。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;/ 需要遍歷請(qǐng)求隊(duì)列一次或兩次 fo

19、r (pListEntry = RequestListHead.Next;/ 請(qǐng)求隊(duì)列中的第一個(gè)請(qǐng)求是鏈表頭指向的下一個(gè)請(qǐng)求。 pListEntry != &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 - Curr

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

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

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

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

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

25、-Step-SCAN 磁盤(pán)調(diào)度算法使用的子隊(duì)列長(zhǎng)度 N#define SUB_QUEUE_LENGTH/ 記錄 N-Step-SCAN 磁盤(pán)調(diào)度算法第一個(gè)子隊(duì)列剩余的長(zhǎng)度。/ 子隊(duì)列初始長(zhǎng)度為 N，每執(zhí)行一次磁盤(pán)調(diào)度算法會(huì)從子隊(duì)列中移除一個(gè)請(qǐng)求，子隊(duì)列/ 長(zhǎng)度就要減少 1，待長(zhǎng)度變?yōu)?0 時(shí)，再將長(zhǎng)度重新變?yōu)?N，開(kāi)始處理下一個(gè)子隊(duì)列。ULONG SubQueueRemainLength = SUB_QUEUE_LENGTH;/ 掃描算法中磁頭移動(dòng)的方向。操作系統(tǒng)啟動(dòng)時(shí)初始化為磁頭向內(nèi)移動(dòng)。/ TRUE，磁頭向內(nèi)移動(dòng)，磁道號(hào)增加。/ FALSE，磁頭向外移動(dòng)，磁道號(hào)減少。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;/ 需要遍歷請(qǐng)求隊(duì)列一次或兩

27、次/計(jì)數(shù)器記錄一個(gè)子隊(duì)列剩余的長(zhǎng)度counter=SubQueueRemainLength；/每調(diào)度一次子隊(duì)列剩余的長(zhǎng)度減一SubQueueRemainLength-；/如果子隊(duì)列剩余長(zhǎng)度為0，則重置為子隊(duì)列原長(zhǎng)度if(SubQueueRemainLength=0) SubQueueRemainLength=SUB_QUEUE_LENGTH; for (pListEntry = RequestListHead.Next;/ 請(qǐng)求隊(duì)列中的第一個(gè)請(qǐng)求是鏈表頭指向的下一個(gè)請(qǐng)求。 pListEntry != &RequestListHead && counter>0;/ 遍歷到請(qǐng)求隊(duì)列頭時(shí)結(jié)束循環(huán)或子隊(duì)列結(jié)束。 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