操作系統(tǒng)實(shí)驗(yàn)報(bào)告課程名稱操作系統(tǒng)實(shí)驗(yàn)課程編號(hào)實(shí)驗(yàn)項(xiàng)目名稱磁盤調(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é)院磁盤調(diào)度算法一.實(shí)驗(yàn)概述：.實(shí)驗(yàn)名稱：磁盤調(diào)度算法.實(shí)驗(yàn)?zāi)康模?）通過學(xué)習(xí)EOS實(shí)現(xiàn)磁盤調(diào)度算法的機(jī)制，掌握磁盤調(diào)度算法執(zhí)行的條件和時(shí)機(jī);2）觀察EOS實(shí)現(xiàn)的FCFS、SSTF和SCAN磁盤調(diào)度算法，了解常用的磁盤調(diào)度算法；3）編寫CSCAN和N-Step-SCAN磁盤調(diào)度算法，加深對各種掃描算法的理解。.實(shí)驗(yàn)類型：驗(yàn)證、設(shè)計(jì).實(shí)驗(yàn)內(nèi)容：1）準(zhǔn)備實(shí)驗(yàn)，創(chuàng)建一個(gè)EOSKernel項(xiàng)目；2）驗(yàn)證先來先服務(wù)（FCFS）磁盤調(diào)度算法；3）驗(yàn)證最短尋道時(shí)間優(yōu)先（SSTF）磁盤調(diào)度算法；4）驗(yàn)證SSTF算法造成的線程“饑餓現(xiàn)象”5）驗(yàn)證掃描（SCAN）磁盤調(diào)度算法；6）改寫SCAN算法；7）編寫循環(huán)掃描（CSCAN）磁盤調(diào)度算法；8）驗(yàn)證SSTF、SCAN及CSCAN算法中的“磁臂粘著”現(xiàn)象；9）編寫N-Step-SCAN磁盤調(diào)度算法。二.實(shí)驗(yàn)環(huán)境操作系統(tǒng)：windowsXP編譯器：TevalatonOSLab語言：C三.實(shí)驗(yàn)過程.設(shè)計(jì)思路和流程圖：SCAN算法流程圖：

磁頭向內(nèi)有向內(nèi)移動(dòng)一的線程？.存向外移;一的域程了循環(huán)結(jié)束后同時(shí)記錄了兩個(gè)方向上稱動(dòng)距離最矩的線程選擇向內(nèi)移動(dòng)距離量矩的觥程磁頭向內(nèi)有向內(nèi)移動(dòng)一的線程？.存向外移;一的域程了循環(huán)結(jié)束后同時(shí)記錄了兩個(gè)方向上稱動(dòng)距離最矩的線程選擇向內(nèi)移動(dòng)距離量矩的觥程將磁頭都動(dòng)方向變?yōu)橄騼?nèi)移動(dòng)選擇向外移助距離最策的線程選擇向內(nèi)移動(dòng)距離最短的線程選把向外移勁距離最短的線程他磁頭移動(dòng)方向變?yōu)橄蛲庖苿?dòng)SSTF算法的流程圖:隊(duì)列結(jié)束返回選中的涓求的窗距離小匚垂軻距商?計(jì)算諳求時(shí)府的繾程要訪網(wǎng)的施道當(dāng)前融頭麻花磁機(jī)的偏移SSTF算法的流程圖:隊(duì)列結(jié)束返回選中的涓求的窗距離小匚垂軻距商?計(jì)算諳求時(shí)府的繾程要訪網(wǎng)的施道當(dāng)前融頭麻花磁機(jī)的偏移將新距離記錄為晶小距離，井H錄卜清求的指針?注Q.隊(duì)乳是一個(gè)雙向選擇港求隊(duì)列中的第一個(gè)請求IcpDiskSc.hcdulc函數(shù)開始；那耳陣也明以』迎田丁問到,4列頭時(shí),我小隊(duì)I列結(jié)束“L-獲取亂列中的卜一個(gè)請求CSACN流程圖:循環(huán)結(jié)束后記錄了向內(nèi)移動(dòng)距離最短的線程和向外移動(dòng)距離最長的線程選擇向外移動(dòng)距離最長的線程選擇向內(nèi)移動(dòng)距離最短的線程N(yùn)-STEP-SCAN算法調(diào)度:.實(shí)驗(yàn)過程：1）新建一個(gè)EOSKernel項(xiàng)目；2）在sysproc.c文件中找到控制臺(tái)命令“ds”對應(yīng)的函數(shù)ConsoleCmdDiskSchedule?！癲s”命令專門用來測試磁盤調(diào)度算法。閱讀該函數(shù)中的源代碼，目前該函數(shù)使磁頭初始停留在磁道10，其它被阻塞的線程依次訪問磁道8、21、9、78、0、41、10、67、12、10；3）打開io/block.c文件，在第378行找到磁盤調(diào)度算法函數(shù)IopDiskSchedule。閱讀該函數(shù)中的源代碼，目前此函數(shù)實(shí)現(xiàn)了FCFS磁盤調(diào)度算法，流程圖如下：

4）生成項(xiàng)目，啟動(dòng)調(diào)試，待EOS啟動(dòng)完畢，在EOS4）生成項(xiàng)目，啟動(dòng)調(diào)試，待EOS啟動(dòng)完畢，在EOS控制臺(tái)中輸入命令“ds”后按回車；輸出章*****Diskschedulestartworking**#***StartCylinder：10TID;TID:TID:TID;TID:TID:TID:TID:TID:TID:TID:TID:TID:Cylinder：Cylinder:Cylinder:Cylinder:Cylinder:Cylinder:Cylinder:Cylinder:Cylinder:Cylinder:Offset:12-78Offset:69十0Offset:73-41Offset:41+Offset:31-67Offset:5T+12Offset:55-10Offset:2~Totaloffset：360Transfertiires：10Averageoffset：36**邛叱*:*Disksc：h已dul已stopworking**噂叱*邛在EOS控制臺(tái)中會(huì)首先顯示磁頭的起始位置是10磁道，然后按照線程被阻塞的順序依次顯示線程的信息（包括線程ID和訪問的磁道號(hào)）。磁盤調(diào)度算法執(zhí)行的過程中，在OSLab的“輸出”窗口中也會(huì)首先顯示磁頭的起始位置，然后按照線程被喚醒的順序依次顯示線程信息（包括線程ID、訪問的磁道號(hào)、磁頭移動(dòng)的距離和方向），并在磁盤調(diào)度結(jié)束后顯示此次調(diào)度的統(tǒng)計(jì)信息（包括總尋道數(shù)、尋道次數(shù)和平均尋道數(shù)）。對比EOS控制臺(tái)和“輸出”窗口中的內(nèi)容，可以發(fā)現(xiàn)FCFS算法是根據(jù)線程訪問磁盤的先后順序進(jìn)行調(diào)度的。下圖顯示了本次調(diào)度執(zhí)行時(shí)磁頭移動(dòng)的軌跡：5）打開sstf.c文件，該文件提供的lopDiskSchedule函數(shù)實(shí)現(xiàn)了SSTF磁盤調(diào)度算法，其中應(yīng)注意：①變量Offset是有符號(hào)的長整型，用來表示磁頭的偏移（包括距離和方向）。Offset大于0時(shí)表示磁頭向內(nèi)移動(dòng)（磁道號(hào)增加）;小于0時(shí)表示磁頭向外移動(dòng)（磁道號(hào)減少）；等于0時(shí)表示磁頭沒有移動(dòng)。而名稱以“Distance”結(jié)尾的變量都是無符號(hào)長整型，只表示磁頭移動(dòng)的距離（無方向）。所以在比較磁頭的偏移和距離時(shí)，或者在將偏移賦值給距離時(shí)，都要取偏移的絕對值（調(diào)用C庫函數(shù)abs）。本實(shí)驗(yàn)在實(shí)現(xiàn)其它磁盤調(diào)度算法時(shí)也同樣遵守此約定；②在開始遍歷之前，將最小距離（ShortestDistance）初始化為最大的無符號(hào)長整型數(shù)，這樣，第一次計(jì)算的距離一定會(huì)小于最小距離，從而可以使用第一次計(jì)算的距離來再次初始化最小距離。本實(shí)驗(yàn)在實(shí)現(xiàn)其它磁盤調(diào)度算法時(shí)也同樣使用了此技巧。6）生成項(xiàng)目，啟動(dòng)調(diào)試，待EOS啟動(dòng)完畢，在EOS控制臺(tái)中輸入命令“ds”后按回車；對比EOS控制臺(tái)和“輸出”窗口中的內(nèi)容（特別是線程ID的順序），可以發(fā)現(xiàn)，SSTF算法喚醒線程的順序與線程被阻塞的順序是不同的。圖18-4顯示了本次調(diào)度執(zhí)行時(shí)磁頭移動(dòng)的軌跡。對比SSTF算法與FCFS算法在“輸出”窗口中的內(nèi)容，可以看出，SSTF算法的平均尋道數(shù)明顯低于FCFS算法。■OSLabPC-KicrosoftVirtualPC2007ActioiiEditCDFlojip7HelpCONSOLE-1(PressCtrl+Fl"FBtoswitchccnsoleulndcu...)UeleonetoEOSshell>dsa21978g〃1067lz10StartCylinder；T(D：31QjlinderT(D：32CylinderTIB：33QjlinderT[?：34CylinderT(D：35Cl|1InderT(D：36CylinderHD：37CylinderTI?：38QjlinderT(D：39QjlinderT(D：前Qjlindera21978g〃1067lz10調(diào)試 ,洞力永W 東水木水*木Diskschedulestartworking木水木市東市IStartCylinder：10|TID：37Cylinder：10。玨sE：0=TID:40Cylinder：100玨比t;0=TID:33Cylinder:9Offset:1-TID:31Cylinder:8Offset:1-TID:39Cylinder:12Offset:4+TID：32Cylinder：21Offset：9+TID:36Cylinder：41Offset;20+TID:38Cylinder:67Offset:26+TID:34Cylinder:78Offset:11+TID:35Cylinder:0Offset:78-Totaloffset:150Transfertiroes:10Averageoffset:15******口］豈卜schedulestopworking******7）驗(yàn)證SSTF算法造成的線程“饑餓現(xiàn)象”，使用SSTF算法時(shí)，如果不斷有新線程要求訪問磁盤，而且其所要訪問的磁道與當(dāng)前磁頭所在磁道的距離較近，這些新線程的請求必然會(huì)被優(yōu)先滿足，而等待隊(duì)列中一些老線程的請求就會(huì)被嚴(yán)重推遲，從而使老線程出現(xiàn)“饑餓”現(xiàn)象。8）修改sysproc.c文件ConsoleCmdDiskSchedule函數(shù)中的源代碼，仍然使磁頭初始停留在磁道10，而讓其它線程依次訪問磁道78、21、9、8、11、41、10、67、12、10，生成項(xiàng)目，啟動(dòng)調(diào)試，待EOS啟動(dòng)完畢，在EOS控制臺(tái)中輸入命令“ds”后按回車;查看“輸出”窗口中顯示的內(nèi)容，可以發(fā)現(xiàn)，雖然訪問78號(hào)磁道的線程的請求第一個(gè)被放入請求隊(duì)列U，但卻被推遲到最后才被處理，出現(xiàn)了“饑餓”現(xiàn)象。如果不斷有新線程的請求到達(dá)并被優(yōu)先滿足，則訪問78號(hào)磁道的線程的“饑餓”情況就會(huì)更加

嚴(yán)重；修改訪問磁道順序:6161461561661161862062；62362626//修改后執(zhí)行“ds”命令的結(jié)果:輸出riiiiTitirf-i>,-i-Mr、idnTI AU『I-rmtITITT.I4「T-I1-iUinNewThreadAccessCylinder(StdHandl&NewThreadAccessCy1inder(StdHandle,NewThreadAccessCylinder(StdHandle,NewThreadAccessCy1inder(StdHandle,NewThreadAccessCy1inder(StdHandle,NewThreadAccessCy1inder(StdHandle,N已網(wǎng)Thr已a(bǔ)dAcc已ssCylind已r(StdHandl已,NewThreadAccessCy1inder(StdHandl易NewThreadAccessCy1inder(StdHandl//修改后執(zhí)行“ds”命令的結(jié)果:輸出riiiiTitirf-i>,-i-Mr、idnTI AU『I-rmtITITT.I4「T-I1-iUin二7二丁liiikr1二Of:5c;;D=1(1ZjCinder二Offje7:i)一1；jp-indpr：1-工Klinkr30二lb,;1-ZuZjCindcr110ff5C7：31r3Cinder二 14]r2ZvlinJer21uffse:：9十二G二丁1inJ匚r410匚文?二2：+3SZiCinder67Offse7:2:-寸3P-indFr“xuf-：[|-材科**DiskschedulestartwcirKinm止*x：匕**3二ar二Cvlincer：L(iT：3;T：3:riD：T：3;T：D:T：3:T：j：T：D:T：D:[ID：Tottioffset:72Transfer:inc二：10??Tcrazczffzet:7******|〕isi：p-hp-.n.=stnpgjirlrinj******多次輸入“4$”命令:

******Diskschedulem******Diskschedulem二artworking******StartCylinder：IC10Offset：0=10Offset：0=9Offset：1-8Offset：1-12Offset：4+21Offset：9'+41Offset：20+67Offset:26+78Offset:11+0Offset:78-TIDTIDTIDTIDTIDTIDTIDTIDTIDTIDTIDTIDTIDTIDTIDTIDTIDTIDTID50Cylinder43Cylinder41Cylinder49Cylinder42Cylinder46Cylinder48Cylinder44Cylinder45CylinderTotaloffset：150Transfertimes：10Averageoffset：IE9）對SSTF算法稍加改進(jìn)后可以形成SCAN算法，可防止老線程出現(xiàn)“饑餓”現(xiàn)象。打開scan.c文件，該文件提供的lopDiskSchedule函數(shù)實(shí)現(xiàn)了SCAN磁盤調(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)沒有線程，就變換方向，進(jìn)行第二次遍歷，同樣是查找移動(dòng)距離最短的線程。在這兩次遍歷中一定能找到合適的線程。10）使用scan.c文件中IopDiskSchedule函數(shù)的函數(shù)體，替換block.c文件中IopDiskSchedule函數(shù)的函數(shù)體，生成項(xiàng)目，啟動(dòng)調(diào)試，待EOS啟動(dòng)完畢，在EOS控制臺(tái)中輸入命令“ds”后按回車；輸出調(diào)試4##小和卜[is工sched<estartworking?卜■小StartCylinder:1〕TIETIETIETIETILTIEFTIETIETIEr40妁TIETIETIETIETILTIEFTIETIETIEr40妁32弘羽33工拈Cyliiidci-CylinderCylinderCylincerCylincerCylinderCyliy\c.fvCylincerCvlincerCylinder1(OfficL;1=ICOffset：〕=11Offset:2421Offset:3■+41Offset:20■+]67Offset:26+可口FFef十：1一十9Cffset:53-8Offset:1-0Offset:8-Tctaloffset:1437r￡n=fertimes:13Av已rmgeoffset:14輸出調(diào)試******DiskschedulestartworkingStartCylinder：10TID:47Cylinder：10Offset:0=TID:50Cylind已r：10Offset:0二TID:43Cylind已r：9Offs已t二1一TID:41Cylinder：5Offset:1-TID：45Cylinder：0Offs已t二8-TID:49Cylinder：12Offset:12+TID:42Cylinder：21Offset:9+TID:46Cylinder：41Offset:20+TID:4SCylinder：6TOffset:26+TID:44Cylind已r：78Offset:11+Totaloffset：88Transfertimes：10Averageoffset：8對比SCAN算法與SSTF算法在“輸出”窗口中的內(nèi)容，可以看出，SCAN算法的平均尋道數(shù)有可能小于SSTF算法，所以說SSTF算法不能保證平均尋道數(shù)最少。下圖顯示了本次調(diào)度執(zhí)行時(shí)磁頭移動(dòng)的軌跡：。 事？沖序。 事？沖序2) 41 AT 7*MWiH4I(Till-11）改寫SCAN算法，算法提示：①在一次遍歷中，不再關(guān)心當(dāng)前磁頭移動(dòng)的方向，而是同時(shí)找到兩個(gè)方向上移動(dòng)距離最短的線程所對應(yīng)的請求，這樣就不再需要遍歷兩次；②在計(jì)算出線程要訪問的磁道與當(dāng)前磁頭所在磁道的偏移后，可以將偏移分為三種類型：偏移為0，表示線程要訪問的磁道與當(dāng)前磁頭所在磁道相同，此情況應(yīng)該優(yōu)先被調(diào)度，可立即返回該線程對應(yīng)的請求的指針；偏移大于0，記錄向內(nèi)移動(dòng)距離最短的線程對應(yīng)的請求；偏移小于0，記錄向外移動(dòng)距離最短的線程對應(yīng)的請求；③循環(huán)結(jié)束后，根據(jù)當(dāng)前磁頭移動(dòng)的方向選擇同方向移動(dòng)距離最短的線程，如果在同方向上沒有線程，就變換方向，選擇反方向移動(dòng)距離最短的線程；流程如下所示：SCAN改寫代碼：PREQUESTIopDiskSchedule(VOID)(PLIST_ENTRYpListEntry;PREQUESTpRequest;PREQUESTINpNextRequest=NULL;PREQUESTOUTpNextRequest=NULL;LONGOffset;ULONGInsideShortestDistance=0xFFFFFFFF;ULONGOutsideShortestDistance=0xFFFFFFFF;PREQUESTpNextRequest=NULL;//需要遍歷請求隊(duì)列一次或兩次for(pListEntry=RequestListHead.Next;//請求隊(duì)列中的第一個(gè)請求是鏈表頭指向的下一個(gè)請求。pListEntry!=&RequestListHead;//遍歷到請求隊(duì)列頭時(shí)結(jié)束循環(huán)。pListEntry=pListEntry->Next){//根據(jù)鏈表項(xiàng)獲得請求的指針pRequest=CONTAINING_RECORD(pListEntry,REQUEST,ListEntry);//計(jì)算請求對應(yīng)的線程所訪問的磁道與當(dāng)前磁頭所在磁道的偏移(方向由正負(fù)表示)Offset=pRequest->Cylinder-CurrentCylinder;if(0==Offset){//如果線程要訪問的磁道與當(dāng)前磁頭所在磁道相同，可立即返回。pNextRequest=pRequest;gotoRETURN;}elseif(Offset<InsideShortestDistance&&Offset>0){//記錄向內(nèi)移動(dòng)距離最短的線程InsideShortestDistance=Offset;INpNextRequest=pRequest;}elseif(-Offset<OutsideShortestDistance&&Offset<0){//記錄向外移動(dòng)距離最短的線程OutsideShortestDistance=-Offset;OUTpNextRequest=pRequest;}}〃判斷磁頭移動(dòng)方向，若向內(nèi)移動(dòng)if(ScanInside){〃判斷是否有向內(nèi)移動(dòng)的線程if(INpNextRequest){〃有則原則該進(jìn)程returnINpNextRequest;}else{

〃沒有則修改磁頭方向，選擇向外移動(dòng)距離最短的線程ScanInside=!ScanInside;returnOUTpNextRequest;))〃如果向外移動(dòng)else{〃判斷是否有向外移動(dòng)的線程if(OUTpNextRequest){〃有則選擇該進(jìn)程returnOUTpNextRequest;)else{〃沒有則修改磁頭的方向，選擇向內(nèi)移動(dòng)距離最短的線程ScanInside=!ScanInside;returnINpNextRequest;))RETURN:returnpNextRequest;)修改完SCAN算法后輸入5$”命令:調(diào)試輸出調(diào)試才相由幸三StartCylinder:1DTIE:TIE：TIE:TIE:"ir：TIE:F:TIE:TIE:TIE:37Cylinder：40Cylinder：Cylinder：32Cylincer:彳向CylincFr:38Cylinder：34Cylinder:33Cylincer:上Cvlincer:35Cylinder：ICOffset:3-式Offset：〕=|」Offset:2421Offset:3441AFFsf十：2。467Offset:26+可口FF*十：1TIE:TIE：TIE:TIE:"ir：TIE:F:TIE:TIE:TIE:37Cylinder：40Cylinder：Cylinder：32Cylincer:彳向CylincFr:38Cylinder：34Cylinder:33Cylincer:上Cvlincer:35Cylinder：Tctaloffs=t：143"rai^fertimes：13Averageoffset：14<I，—/12)在已經(jīng)完成的SCAN算法源代碼的基礎(chǔ)上進(jìn)行改寫，不再使用全局變量ScanInside確定磁頭移動(dòng)的方向，而是規(guī)定磁頭只能從外向內(nèi)移動(dòng)。當(dāng)磁頭移動(dòng)到最內(nèi)的被訪問磁道時(shí)，磁頭立即移動(dòng)到最外的被訪問磁道，即將最大磁道號(hào)緊接著最小磁道號(hào)構(gòu)成循環(huán)，進(jìn)行掃描。由于磁頭移動(dòng)的方向被固定，也就不需要根據(jù)磁頭移動(dòng)的方向進(jìn)行分類處理，所以CSCAN算法的源代碼會(huì)較SCAN算法更加簡單。改寫提示：①由于規(guī)定了磁頭只能從外向內(nèi)移動(dòng)，所以在每次遍歷中，總是同時(shí)找到向內(nèi)移動(dòng)距離最短的線程和向外移動(dòng)距離最長的線程。注意，與SCAN算法查找向外移動(dòng)距離最短線程不同，這里查找向外移動(dòng)距離最長的線程。在開始遍歷前，可以將用來記錄向外移動(dòng)最長距離的變量賦值為0；②在計(jì)算出線程要訪問的磁道與當(dāng)前磁頭所在磁道的偏移后，同樣可以將偏移分為三種類型：偏移為0，表示線程要訪問的磁道與當(dāng)前磁頭所在磁道相同，此情況應(yīng)優(yōu)先被調(diào)度，可立即返回該線程對應(yīng)的請求的指針；偏移大于0，記錄向內(nèi)移動(dòng)距離最短的線程對應(yīng)的請求；偏移小于0，記錄向外移動(dòng)距離最長的線程對應(yīng)的請求；③循環(huán)結(jié)束后，選擇向內(nèi)移動(dòng)距離最短的線程，如果沒有向內(nèi)移動(dòng)的線程，就選擇向外移動(dòng)距離最長的線程。CSCAN修改代碼：PREQUESTIopDiskSchedule(VOID)(PLIST_ENTRYpListEntry;PREQUESTpRequest;PREQUESTINpNextRequest=NULL;PREQUESTOUTpNextRequest=NULL;LONGOffset;ULONGInsideShortestDistance=0xFFFFFFFF;ULONGOutsideShortestDistance=0x00000000;PREQUESTpNextRequest=NULL;//需要遍歷請求隊(duì)列一次或兩次for(pListEntry=RequestListHead.Next;//請求隊(duì)列中的第一個(gè)請求是鏈表頭指向的下一個(gè)請求。pListEntry!=&RequestListHead;//遍歷到請求隊(duì)列頭時(shí)結(jié)束循環(huán)。pListEntry=pListEntry->Next){//根據(jù)鏈表項(xiàng)獲得請求的指針pRequest=CONTAINING_RECORD(pListEntry,REQUEST,ListEntry);//計(jì)算請求對應(yīng)的線程所訪問的磁道與當(dāng)前磁頭所在磁道的偏移(方向由正負(fù)表示)Offset=pRequest->Cylinder-CurrentCylinder;if(0==Offset){//如果線程要訪問的磁道與當(dāng)前磁頭所在磁道相同，可立即返回。pNextRequest=pRequest;gotoRETURN;}elseif(Offset<InsideShortestDistance&&Offset>0){//記錄向內(nèi)移動(dòng)距離最短的線程InsideShortestDistance=Offset;INpNextRequest=pRequest;}elseif(-Offset>OutsideShortestDistance&&Offset<0){//記錄向外移動(dòng)距離最短的線程OutsideShortestDistance=-Offset;OUTpNextRequest=pRequest;}}〃需要向內(nèi)移動(dòng)的線程是否存在if(INpNextRequest){〃存在則返回向內(nèi)移動(dòng)的請求returnINpNextRequest;}else{〃沒有則返回向外移動(dòng)的請求returnOUTpNextRequest;}RETURN:returnpNextRequest;}13)啟動(dòng)修改后的程序，輸入“4$”命令，查看磁盤調(diào)度算法的執(zhí)行情況。*****Diskschedulestartworking******StartCylinder:10TOC\o"1-5"\h\z\o"CurrentDocument"TID: 37 Cylinder： 10 Offset: 0=TID: 40 Cylinder: 10 Offset: 0=TID: 39 Cylinder: 12 Offset: 2+TID: 32 Cylinder; 21 Offset: 9+TID: 36 Cylinder: 41 Offset: 20+TID: 38 Cylinder： 67 Offset: 26+TID: 34 Cylinder: 78 Offset: 11+TID：35Cylinder：0Offset：78-TID:31Cylinder;8Offset;S+TID:33Cylinder;9Offset:1+Totaloffset：155Transfertimes：10Averageoffset：15*****Diskschedulestopworking******mi11

14)觀察執(zhí)行SSTF、SCAN及CSCAN算法時(shí)磁頭移動(dòng)的軌跡可以看到，在開始時(shí)磁頭都停留在10磁道不動(dòng)，這就是“磁臂粘著”現(xiàn)象，通過修改代碼，進(jìn)一步觀察。修改sysproc.c文件ConsoleCmdDiskSchedule函數(shù)中的源代碼，仍然使磁頭初始停留在磁道10，而讓其它線程依次訪問磁道78、10、10、10、10、10、10、10、10、10，分別使用SSTF、SCAN和CSCAN算法調(diào)度這組數(shù)據(jù)。NewThreadAccessCy1inder(StdHandle,78);NewThreadAccessCy1inder(StdHandle?10);NewThreadAccessCy1inder(StdHandle,10)」NewThreadAccessCy1inder(StdHandle,10);NewThreadAccegsCy1inder(StdHandle,10);NewThreadAccessCy1inder(StdHandle,10);NewThreadAccessCy1inder(StdHandle,10);NewThreadAccessCy1inder(StdHandle,10);NewThreadAccessCy1inder(StdHandlej10);NewThreadAccessCy1inder(StdHandle,10);查看各種算法在“輸出”窗口中顯示的內(nèi)容，可以發(fā)現(xiàn)，雖然訪問78號(hào)磁道的線程的請求第一個(gè)被放入請求隊(duì)列，但卻被推遲到最后才被處理，出現(xiàn)了“磁臂粘著”現(xiàn)象。SCAN算法測試：坤十斗十斗十DIlsE坤十斗十斗十DIlsEmjL匚」ul匚占LcltLwurkiufi******Cylindi=T:1門J'lU： Cylindi=T:1門J'lU： 3E Cylin-der： 1U Uffcet ：t工d： 33 CviiiiJcj.-； io orricL ;TTD: ^4 Cyl: 1A ：J'lD： 35 Cylinder： 1U Uffcet ：t工d： 3G CviiiiJcj.-： io orricI :TTD:"TCyl:1A門TTek十二J'lD：3KCylinder：1UUffcet：tid；33CniiiiU匚：ioorricL;TTD:4ACylindPT:1AClff^PTz11D：31Cylinder：YXUffcet：+一一--一一一一--一一一一----Soooo--o--0o-o-O6Trif『i]riffp尸十：內(nèi)只Ttpttinn=p:1門兒行—十為巴戶口「下口|=十：AMcMcMcMcMcM；Dickccheduleutcrpworking*火火：+：止北CSCAN算法測試:++++++Diskschedule++++++Diskschedulestartworking*￥****StartCylind已r：10TOC\o"1-5"\h\zTID： 32 Cylind已r： 10 Offset： 0 =T1D： 33 Cylinder： 10 Uftset： 0 =TID: 34 Cylinder： 10 Offset: 0 =TID: 35 Cylind已r： 10 Offset: 0 二TID: 36 Cylind已r： 10 Offset: 0 =TID; 37 Cylinder: 10 Offset: 0 -|TID: 38 Cylinder： 10 Offset: 0 =TID: 39 Cylinder： 10 Offset: 0 =TID: 40 Cylind已r： 10 Offset: 0 二TID:31Cylindci-:7SOffset:GSITotaloffset：68TransferTotaloffset：68Transfer******Diskschedulestop1imes：10Averageciffs巳t：6r.'.jnrki ****二**SSTF算法測試:******DiskscheduleSSTF算法測試:******DiskschedulestartworkingStartCylinder!10TID:TID:TID：TID:TID:TID：TID：TID：TID：TID:TID:TID：TID：32Cylinder：10Offset：0=33Cylinder：10Offset：0=34Cylinder；10Offset：0=35Cylinder：10Offset：0=36Cylinder：10Offset：0=37Cylinder!10OFFs已t：0=3SCylinder:10OFFs已t:0=39Cylinder:10Offs已t:0=4QCylinder：10Offset：0=31Cylinder：78Offset：68+Totaloffset:68TzransF已rtim已s：10Averageoffset:6******Diskmeh已dul已stopDorkins案非案非案*< d15）在已經(jīng)完成的SCAN算法源代碼的基礎(chǔ)上進(jìn)行改寫，將請求隊(duì)列分成若干個(gè)長度為N的子隊(duì)列，調(diào)度程序按照FCFS原則依次處理這些子隊(duì)列，而每處理一個(gè)子隊(duì)列時(shí)，又是按照SCAN算法，修改提示：①在block.c文件中的第360行定義了一個(gè)宏SUB_QUEUE_LENGTH，表示子隊(duì)列的長度（即N值）。目前這個(gè)宏定義的值為6。在第367行定義了一個(gè)全局變量SubQueueRemainLength，表示第一個(gè)子隊(duì)列剩余的長度，并初始化其值為SUB_QUEUE_LENGTH；②在執(zhí)行N-Step-SCAN算法時(shí)，要以第一個(gè)子隊(duì)列剩余的長度做為計(jì)數(shù)器，確保只遍歷第一個(gè)子隊(duì)列剩余的項(xiàng)。所以，結(jié)束遍歷的條件就既包括第一個(gè)子隊(duì)列結(jié)束，又包括整個(gè)隊(duì)列結(jié)束（如果整個(gè)隊(duì)列的長度小于第一個(gè)子隊(duì)列剩余的長度）。注意，不要直接使用第一個(gè)子隊(duì)列剩余的長度做為計(jì)數(shù)器，可以定義一個(gè)新的局部變量來做為計(jì)數(shù)器；③按照SCAN算法從第一個(gè)子隊(duì)列剩余的項(xiàng)中選擇一個(gè)合適的請求。最后，需要將第一個(gè)子隊(duì)列剩余長度減少1（SubQueueRemainLength減少1），如果第一個(gè)子隊(duì)列剩余長度變?yōu)?，說明第一個(gè)子隊(duì)列處理完畢，需要將子隊(duì)列剩余的長度重新變?yōu)镹(SubQueueRemainLength重新賦值為SUB_QUEUE_LENGTH),從而開始處理下一個(gè)子隊(duì)列；修改代碼：//N-Step-SCAN磁盤調(diào)度算法使用的子隊(duì)列長度N#defineSUB_QUEUE_LENGTH//記錄N-Step-SCAN磁盤調(diào)度算法第一個(gè)子隊(duì)列剩余的長度。//子隊(duì)列初始長度為N，每執(zhí)行一次磁盤調(diào)度算法會(huì)從子隊(duì)列中移除一個(gè)請求，子隊(duì)列//長度就要減少1，待長度變?yōu)?時(shí)，再將長度重新變?yōu)镹，開始處理下一個(gè)子隊(duì)列。ULONGSubQueueRemainLength=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)減少。BOOLScanInside=TRUE;PREQUESTIopDiskSchedule(VOID)(PLIST_ENTRYpListEntry;PREQUESTpRequest;PREQUESTINpNextRequest=NULL;PREQUESTOUTpNextRequest=NULL;LONGOffset;ULONGInsideShortestDistance=0xFFFFFFFF;ULONGOutsideShortestDistance=0xFFFFFFFF;PREQUESTpNextRequest=NULL;ULONGcounter;//需要遍歷請求隊(duì)列一次或兩次〃計(jì)數(shù)器記錄一個(gè)子隊(duì)列剩余的長度counter=SubQueueRemainLength；〃每調(diào)度一次子隊(duì)列剩余的長度減一SubQueueRemainLength--；〃如果子隊(duì)列剩余長度為0，則重置為子隊(duì)列原長度if(SubQueueRemainLength==0)SubQueueRemainLength=SUB_QUEUE_LENGTH;for(pListEntry=RequestListHead.Next;//請求隊(duì)列中的第一個(gè)請求是鏈表頭指向的下一個(gè)請求。pListEntry!=&RequestListHead&&c