操作系統(tǒng)實(shí)驗(yàn)磁盤(pán)調(diào)度算法

1、操作系統(tǒng)實(shí)驗(yàn)報(bào)告課程名稱操作系統(tǒng)實(shí)驗(yàn)實(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)21#428哈爾濱工程大學(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)康?1) 通過(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ì)性實(shí)驗(yàn)4. 實(shí)驗(yàn)

2、內(nèi)容(1) 驗(yàn)證先來(lái)先服務(wù)(FCFS)磁盤(pán)調(diào)度算法；(2) 驗(yàn)證最短尋道時(shí)間優(yōu)先(SSTF)磁盤(pán)調(diào)度算法；( 3)驗(yàn)證 SSTF 算法造成的線程“饑餓”現(xiàn)象；( 4)驗(yàn)證掃描( SCAN )磁盤(pán)調(diào)度算法；( 5)改寫(xiě) SCAN 算法。二、實(shí)驗(yàn)環(huán)境在 OS Lab 實(shí)驗(yàn)環(huán)境的基礎(chǔ)上， 利用 EOS 操作系統(tǒng)， 由匯編語(yǔ)言及 C 語(yǔ)言編寫(xiě)代碼， 對(duì)需要的項(xiàng)目進(jìn)行生成、調(diào)試、查看和修改，并通過(guò)EOS應(yīng)用程序使內(nèi)核從源代碼變?yōu)榭梢栽谔摂M機(jī)上使用。三、實(shí)驗(yàn)過(guò)程1. 設(shè)計(jì)思路和流程圖( 1 )改寫(xiě) SCAN 算法在已有 SCAN 算法源代碼的基礎(chǔ)上進(jìn)行改寫(xiě)，要求不再使用雙重循環(huán)，而是只遍歷 一次請(qǐng)求隊(duì)列中

3、的請(qǐng)求，就可以選中下一個(gè)要處理的請(qǐng)求。算法流程圖如下圖所示。圖 3.1.1 SCAN 算法 IopDiskSchedule 函數(shù)流程圖(2)編寫(xiě)循環(huán)掃描(CSCAN)磁盤(pán)調(diào)度算法在已經(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)行掃描。算法流程圖如下圖所示。圖 3.1.2 CSCAN 算法 IopDiskSchedule 函數(shù)流程圖（3）編寫(xiě) N-Step-SCAN 磁盤(pán)調(diào)度算法在已經(jīng)完成的 S

4、CAN 算法源代碼的基礎(chǔ)上進(jìn)行改寫(xiě)， 將請(qǐng)求隊(duì)列分成若干個(gè)長(zhǎng)度為 N 的子隊(duì)列，調(diào)度程序按照 FCFS 原則依次處理這些子隊(duì)列，而每處理一個(gè)子隊(duì)列時(shí)， 又是按照 SCAN 算法。算法流程圖如下圖所示。圖 3.1.3 N-Step-SCAN 算法 IopDiskSchedule 函數(shù)流程圖2. 算法實(shí)現(xiàn)（1）改寫(xiě) SCAN 算法 在一次遍歷中，不再關(guān)心當(dāng)前磁頭移動(dòng)的方向，而是同時(shí)找到兩個(gè)方向上移動(dòng)距離 最短的線程所對(duì)應(yīng)的請(qǐng)求，這樣就不再需要遍歷兩次。 在計(jì)算出線程要訪問(wèn)的磁道與當(dāng) 前磁頭所在磁道的偏移后，可以將偏移分為三種類型：偏移為0，表示線程要訪問(wèn)的磁道與當(dāng)前磁頭所在磁道相同，此情況應(yīng)該優(yōu)先

5、被調(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)距離最短的線程。（2）編寫(xiě)循環(huán)掃描（CSCAN）磁盤(pán)調(diào)度算法由于規(guī)定了磁頭只能從外向內(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。在

6、計(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)的線程，就選擇 向外移動(dòng)距離最長(zhǎng)的線程。（ 3）編寫(xiě) N-Step-SCAN 磁盤(pán)調(diào)度算法在 block.c 文件中的第 360 行定義了一個(gè)宏 SUB_QUEUE_LENGTH ，表示子隊(duì)列 的長(zhǎng)度（即 N 值 ）。目前這個(gè)宏定義的值為 6。在

7、第 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)。所以，結(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 （SubQueueR

8、emainLength減少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ì)列。3. 需要解決的問(wèn)題及解答（1）實(shí)驗(yàn)指導(dǎo)P176-3.2驗(yàn)證先來(lái)先服務(wù)（FCFS）磁盤(pán)調(diào)度算法，要求請(qǐng)給出在“輸 出”窗口中的結(jié)果。答：先來(lái)先服務(wù)（FCFS）磁盤(pán)調(diào)度算法在“輸出”窗口中的結(jié)果如下圖所示。圖 3.3.1（2） 實(shí)驗(yàn)指導(dǎo)P177-3.3驗(yàn)證驗(yàn)證最短尋道時(shí)間優(yōu)先（SSTF）磁盤(pán)調(diào)度算法，要求請(qǐng) 給出在“輸出”窗口中的結(jié)果。答：最短尋道

9、時(shí)間優(yōu)先（SSTF）磁盤(pán)調(diào)度算法在“輸出”窗口中的結(jié)果如下圖所示。圖 3.3.2（3）實(shí)驗(yàn)指導(dǎo)P178-3.4驗(yàn)證SSTF算法造成的線程“饑餓”現(xiàn)象，要求請(qǐng)給出在“輸 出”窗口中的結(jié)果。答：SSTF算法造成的線程“饑餓”現(xiàn)象在“輸出”窗口中的結(jié)果如下圖所示。圖 3.3.3（4）實(shí)驗(yàn)指導(dǎo)P179-3.5驗(yàn)證掃描（SCAN）磁盤(pán)調(diào)度算法，要求在非饑餓（即實(shí)驗(yàn)指導(dǎo)P176-3.2節(jié)中的數(shù)據(jù)）和饑餓（即實(shí)驗(yàn)指導(dǎo)P178-3.4節(jié)中的數(shù)據(jù)）請(qǐng)給出在“輸出”窗口中的結(jié)果，并且要求在每次輸入兩次“ds”命令（注意不要連續(xù)輸入，要等第一次“ ds”命令執(zhí)行完，再輸入第二次“ ds”命令），分析結(jié)果為什么不同。

10、答：在非饑餓情況下，“輸出”窗口中的結(jié)果如下圖所示。圖 3.3.4在饑餓情況下，“輸出”窗口中的結(jié)果如下圖所示。圖 3.3.5SCanlnSide是一個(gè)全局變量，當(dāng)?shù)谝淮螆?zhí)行“ ds”命令時(shí)，調(diào)用IOPDiSkSChedUIe函 數(shù)，SCanlnSide被修改了一次，再次執(zhí)行“ ds”命令時(shí)，SCanlnSide不會(huì)被重置，因此輸 出的結(jié)果會(huì)不一樣。（5）在執(zhí)行SCAN、N-SteP-SCAN磁盤(pán)調(diào)度算法時(shí)，如果在 EOS控制臺(tái)中多次輸 入“ds”命令，調(diào)度的順序會(huì)發(fā)生變化，說(shuō)明造成這種現(xiàn)象的原因（提示：注意這兩種 算法使用的全局變量）。嘗試修改源代碼，使這兩種算法在多次執(zhí)行時(shí)，都能確保調(diào)度

11、的順序一致（提示：可以參考 iO/bIOCk.C 文件中 lOPReCeiveRequest 函數(shù)和 IopProcessNextRequest函數(shù)判斷磁盤(pán)調(diào)度算法開(kāi)始工作和結(jié)束工作的方法）。答：SCanlnSide是一個(gè)全局變量，當(dāng)?shù)谝淮螆?zhí)行“ ds”命令時(shí)，調(diào)用IOPDiSkSCheduIe 函數(shù)，SCanlnSide被修改了一次，再次執(zhí)行“ ds”命令時(shí)，SCanlnSide不會(huì)被重置，因此 輸出的結(jié)果會(huì)不一樣。只需在 fOr 循環(huán)結(jié)束后添加如下代碼，就能確保調(diào)度的順序一致。圖 3.3.6（6）嘗試在io/block.c文件中定義一個(gè)全局的函數(shù)指針變量DiSkSChedUIeFUnc該函

12、數(shù)指針初始指向?qū)崿F(xiàn)了 FCFS 算法的 lOPDiSkSCheduIe 函數(shù)。修改 iO/bIOCk.C 文件中 的IopprocessNextRequest函數(shù)，在該函數(shù)中不再直接調(diào)用IoPDiSkSChedUIe函數(shù)，而是調(diào)用函數(shù)指針 DiSkSChedUleFUnC 指向的磁盤(pán)調(diào)度算法函數(shù)； ke/SySProC.C 文件中的 Con SoleCmdDiskSchedule函數(shù)中也不再直接調(diào)用IoPDiSkSChedUle函數(shù)，也要修改為調(diào) 用函數(shù)指針DiSkSChedUIeFUnc指向的磁盤(pán)調(diào)度算法函數(shù)。最后，添加一個(gè)控制臺(tái)命令“sstf',該命令使函數(shù)指針 DiSkSChed

13、UIeFUnc指向?qū)崿F(xiàn)了 SSTF算法的函數(shù)。這樣， 在EOS啟動(dòng)后默認(rèn)會(huì)執(zhí)行FCFS算法，執(zhí)行控制臺(tái)命令“ sstf”后，會(huì)執(zhí)行SSTF算 法。按照這種方式依次實(shí)現(xiàn)“ fcfs ”、“ scan”、“ cscan”和“ nstepscan命令。說(shuō)明這 種在EOS運(yùn)行時(shí)動(dòng)態(tài)切換磁盤(pán)調(diào)度算法的好處。答：首先在 bIock.c 中定義一個(gè)全局的函數(shù)指針變量DiskSchedUIeFUnc。圖 3.3.7修改 IopProcessNextRequest函數(shù)和 ConsoleCmdDiskSchedule 函數(shù)，使其不再直接 調(diào)用IoPDiSkSChedUIe函數(shù)而是調(diào)用函數(shù)指針 DiSkSChedU

14、IeFUnc指向的磁盤(pán)調(diào)度算法函 數(shù)。圖 3.3.8調(diào)用函數(shù)前先聲明。圖 3.3.9添加一個(gè)控制臺(tái)命令“sstf”，該命令使函數(shù)指針DiSkSChedUIeFUnc指向?qū)崿F(xiàn)了 SSTF 算法的函數(shù)。驗(yàn)證結(jié)果如下圖所示。（7）分析已經(jīng)實(shí)現(xiàn)的各種磁盤(pán)調(diào)度算法的優(yōu)缺點(diǎn)，嘗試實(shí)現(xiàn)更多其它的磁盤(pán)調(diào)度算 法。答： 先來(lái)先服務(wù)算法 是一種比較簡(jiǎn)單的磁盤(pán)調(diào)度算法，它根據(jù)進(jìn)程請(qǐng)求訪問(wèn)磁盤(pán)的 先后次序進(jìn)行調(diào)度，此算法的優(yōu)點(diǎn)是公平、簡(jiǎn)單，且每個(gè)進(jìn)程的請(qǐng)求都能依次得到處理， 不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長(zhǎng)期得不到滿足的情況， 在對(duì)磁盤(pán)的訪問(wèn)請(qǐng)求比較多的情況下， 致使平均尋道時(shí)間可能較長(zhǎng)； 最短尋道時(shí)間優(yōu)先算法 選擇這樣的進(jìn)

15、程，其要求訪問(wèn)的磁 道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短，該算法可以得到比較好 的吞吐量，但卻不能保證平均尋道時(shí)間最短，其缺點(diǎn)是在服務(wù)請(qǐng)求很多的情況下，對(duì)內(nèi) 外邊緣磁道的請(qǐng)求將會(huì)無(wú)限期的被延遲； 掃描算法 不僅考慮到欲訪問(wèn)的磁道與當(dāng)前磁道 的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動(dòng)方向，此算法基本上克服了最短尋道時(shí)間優(yōu)先 算法的服務(wù)集中于中間磁道和響應(yīng)時(shí)間變化比較大的缺點(diǎn)，而具有最短尋道時(shí)間優(yōu)先算 法的優(yōu)點(diǎn)即吞吐量較大，平均響應(yīng)時(shí)間較小，但由于是擺動(dòng)式的掃描方法，兩側(cè)磁道被 訪問(wèn)的頻率仍低于中間磁道； 循環(huán)掃描算法 是對(duì)掃描算法的改進(jìn)，如果對(duì)磁道的訪問(wèn)請(qǐng) 求是均勻分布的，當(dāng)磁頭到達(dá)

16、磁盤(pán)的一端，并反向運(yùn)動(dòng)時(shí)落在磁頭之后的訪問(wèn)請(qǐng)求相對(duì) 較少； N-Step-SCAN 算法是掃描算法和先來(lái)先服務(wù)算法的一個(gè)綜合算法，將請(qǐng)求隊(duì)列分 成若干個(gè)長(zhǎng)度為 N 的子隊(duì)列，調(diào)度程序按照 FCFS 原則依次處理這些子隊(duì)列，而每處 理一個(gè)子隊(duì)列時(shí)，又是按照 SCAN 算法，所以它是一種性能比較平均的算法。（6）EOS 在塊設(shè)備層實(shí)現(xiàn)了磁盤(pán)調(diào)度算法后， 由于請(qǐng)求隊(duì)列中的請(qǐng)求一定是被逐個(gè) 處理的，所以并發(fā)的多個(gè)線程已經(jīng)可以互斥的訪問(wèn)磁盤(pán)上的數(shù)據(jù)，那為什么在 IopReadWriteSector 函數(shù)中還要使用磁盤(pán)設(shè)備的互斥信號(hào)量進(jìn)行互斥呢？ （提示：如果一 個(gè)線程只是要獲取磁盤(pán)設(shè)備的狀態(tài)而不是要訪問(wèn)

17、磁盤(pán)上的數(shù)據(jù)，是否需要對(duì)該線程進(jìn)行 磁盤(pán)調(diào)度？該線程是否要與其它并發(fā)訪問(wèn)磁盤(pán)設(shè)備的線程進(jìn)行互斥？）答：如果一個(gè)線程只是要獲取磁盤(pán)設(shè)備的狀態(tài)而不是要訪問(wèn)磁盤(pán)上的數(shù)據(jù)， 那這個(gè)線 程是不需要進(jìn)行磁盤(pán)調(diào)度的，所以不會(huì)進(jìn)入請(qǐng)求隊(duì)列，但該線程同樣需要與其它并發(fā)訪 問(wèn)磁盤(pán)設(shè)備的線程進(jìn)行互斥，這時(shí)就需要使用磁盤(pán)設(shè)備的互斥信號(hào)量進(jìn)行互斥。4. 源程序并附上注釋（1）改寫(xiě) SCAN 算法BOOL ScanInside = TRUE;PREQUESTIopDiskSchedule（VOID）PLIST_ENTRY pListEntry;PREQUEST pRequest;PREQUEST INpNextReque

18、st = 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 != &RequestListHead; / 遍歷到請(qǐng)求隊(duì)列頭時(shí)結(jié)

19、束循環(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 RETURN; else if ( Offset

20、 > 0 && Offset < InsideShortestDistance ) / 記錄向內(nèi)移動(dòng)距離最短的線程InsideShortestDistance = Offset; INpNextRequest = pRequest; else if ( Offset < 0 && -Offset < OutsideShortestDistance ) / 記錄向外移動(dòng)距離最短的線程O(píng)utsideShortestDistance = -Offset; OUTpNextRequest = pRequest;/判斷磁頭移動(dòng)方向，若向內(nèi)移動(dòng)if(

21、 ScanInside)/判斷是否有向內(nèi)移動(dòng)的線程if(INpNextRequest)/有則選擇該線程return INpNextRequest;else/沒(méi)有則修改磁頭方向，選擇向外移動(dòng)距離最短的線程ScanInside = !ScanInside;return OUTpNextRequest;/如果向外移動(dòng)else/判斷是否有向外移動(dòng)的線程if(OUTpNextRequest)/有則選擇該線程return OUTpNextRequest;else/沒(méi)有則修改詞頭方向，選擇向內(nèi)移動(dòng)距離最短的線程ScanInside = !ScanInside;return INpNextRequest;RE

22、TURN: return pNextRequest;(2) 編寫(xiě)循環(huán)掃描(CSCAN)磁盤(pán)調(diào)度算法PREQUESTIopDiskSchedule(VOID)PLIST_ENTRY pListEntry;PREQUEST pRequest;PREQUEST INpNextRequest = NULL;PREQUEST OUTpNextRequest = NULL;LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0x00000000;PREQUEST pNextRequest

23、 = NULL;/ 需要遍歷請(qǐng)求隊(duì)列一次或兩次for (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 = pRe

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

25、mp; -Offset > OutsideShortestDistance ) / 記錄向外移動(dòng)距離最長(zhǎng)的線程O(píng)utsideShortestDistance = -Offset;OUTpNextRequest = pRequest; /需要向內(nèi)移動(dòng)的線程是否存在 if( INpNextRequest )/存在則返回向內(nèi)移動(dòng)的請(qǐng)求 return INpNextRequest;else/否則返回向外移動(dòng)的請(qǐng)求return OUTpNextRequest;RETURN:return pNextRequest;(3) 編寫(xiě) N-Step-SCAN 磁盤(pán)調(diào)度算法/ N-Step-SCAN 磁盤(pán)調(diào)度

26、算法使用的子隊(duì)列長(zhǎng)度 N#define SUB_QUEUE_LENGTH 6/ 記錄 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 ScanInside = TR

27、UE;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ì)列一次或兩次/計(jì)數(shù)器記錄一個(gè)子

28、隊(duì)列剩余的長(zhǎng)度counter = SubQueueRemainLength;/沒(méi)調(diào)度一次子隊(duì)列剩余的長(zhǎng)度減SubQueueRemainLength-;/如果子隊(duì)列剩余的長(zhǎng)度為，則重置為子隊(duì)列原長(zhǎng)度 if(SubQueueRemainLength = 0)SubQueueRemainLength = SUB_QUEUE_LENGTH;/向的下一個(gè)/束循環(huán)或for (pListEntry = RequestListHead.Next; / 請(qǐng)求隊(duì)列中的第一個(gè)請(qǐng)求是鏈表頭指 請(qǐng)求。pListEntry != &RequestListHead && counter>0;

29、/ 遍歷到請(qǐng)求隊(duì)列頭時(shí)結(jié) 子隊(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 = pRequest;return pNextRe

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

31、quest;counter-;if( ScanInside )if(INpNextRequest)return INpNextRequest;elseScanInside = !ScanInside;return OUTpNextRequest;elseif(OUTpNextRequest)return OUTpNextRequest;elseScanInside = !ScanInside;return INpNextRequest;5. 程序運(yùn)行時(shí)的初值和運(yùn)行結(jié)果（1）驗(yàn)證先來(lái)先服務(wù)（FCFS）磁盤(pán)調(diào)度算法新建一個(gè)EoS Kemel項(xiàng)目，雙擊ke文件夾中的SySPrOc.c文件，閱讀函數(shù)C

32、onsoleCmdDiskSchedue目前該函數(shù)使磁頭初始停留在磁道 10，其它被阻塞的線程依 次訪問(wèn)磁道 8、21、9、78、0、41、10、67、12、10。按F5調(diào)試項(xiàng)目，待EOS啟動(dòng)完畢，在EOS控制臺(tái)中輸入命令“ ds”后按回車?？?制臺(tái)和輸出窗口顯示內(nèi)容如下圖所示。圖 3.5.2圖 3.5.3對(duì)比EOS控制臺(tái)和“輸出”窗口中的內(nèi)容，可以發(fā)現(xiàn)FCFS算法是根據(jù)線程訪問(wèn)磁盤(pán)的先后順序進(jìn)行調(diào)度的。（2）驗(yàn)證最短尋道時(shí)間優(yōu)先（SSTF）磁盤(pán)調(diào)度算法使用 sstf.c 文件中 IoPDiskSchedule 函數(shù)的函數(shù)體，替換 block.c 文件中IoPDiSkSChedUIe函數(shù)的函數(shù)體。按 F7生成項(xiàng)目，然后按F5啟動(dòng)調(diào)試。待EOS啟動(dòng)完 畢，在EOS控制臺(tái)中輸入命令“ ds”后按回車。輸出窗口輸出結(jié)果如下圖所示。圖 3.5.4（3）驗(yàn)證SSTF算法造成的線程“饑餓”現(xiàn)象修改SySProc.c文件ConSOIeCmdDiSkSChedUle函數(shù)中的源代碼，仍然使磁頭初始停留 在磁道 10，而讓其它線程依次訪問(wèn)磁道 78、21、9、8、11、41、10、67、12、10。按 F7生成項(xiàng)目，然后按F5啟動(dòng)調(diào)試。 待EOS啟動(dòng)完畢，在EOS控制臺(tái)中輸