操作系統(tǒng)實驗第五講磁盤調(diào)度算法

1、操作系統(tǒng)實驗報告課程名稱操作系統(tǒng)實驗實驗項目名稱磁盤調(diào)度算法學(xué)號班級姓名專業(yè)計算機(jī)科學(xué)與技術(shù)學(xué)生所在學(xué)院計算機(jī)科學(xué)與技術(shù)學(xué)院指導(dǎo)教師初妍實驗室名稱地點21#428哈爾濱工程大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院第六講磁盤調(diào)度算法一、實驗概述1. 實驗名稱磁盤調(diào)度算法2. 實驗?zāi)康模?1）通過學(xué)習(xí)EOS實現(xiàn)磁盤調(diào)度算法的機(jī)制，掌握磁盤調(diào)度算法執(zhí)行的條件和時機(jī)；（ 2）觀察EOS實現(xiàn)的FCFS、SSTF和SCAN磁盤調(diào)度算法，了解常用的磁盤調(diào)度算法；（ 3）編寫CSCAN和N-Step-SCAN磁盤調(diào)度算法，加深對各種掃描算法的理解。3. 實驗類型驗證性+設(shè)計性實驗4. 實驗內(nèi)容（1）驗證先來先服務(wù)（FCFS）

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

3、iskSchedule函數(shù)流程圖（2）編寫循環(huán)掃描（CSCAN）磁盤調(diào)度算法在已經(jīng)完成的SCAN算法源代碼的基礎(chǔ)上進(jìn)行改寫，不再使用全局變量ScanInside確定磁頭移動的方向，而是規(guī)定磁頭只能從外向內(nèi)移動。當(dāng)磁頭移動到最內(nèi)的被訪問磁道時，磁頭立即移動到最外的被訪問磁道，即將最大磁道號緊接著最小磁道號構(gòu)成循環(huán)，進(jìn)行掃描。算法流程圖如下圖所示。圖3.1.2CSCAN算法IopDiskSchedule函數(shù)流程圖在已經(jīng)完成的SCAN算法源代碼的基礎(chǔ)上進(jìn)行改寫，將請求隊列分成若干個長度為N的子隊列，調(diào)度程序按照FCFS原則依次處理這些子隊列，而每處理一個子隊列時，又是按照SCAN算法。算法流程圖如下

4、圖所示。圖3.1.3N-Step-SCAN算法IopDiskSchedule函數(shù)流程圖2. 算法實現(xiàn)（1）改寫SCAN算法在一次遍歷中，不再關(guān)心當(dāng)前磁頭移動的方向，而是同時找到兩個方向上移動距離最短的線程所對應(yīng)的請求，這樣就不再需要遍歷兩次。在計算出線程要訪問的磁道與當(dāng)前磁頭所在磁道的偏移后，可以將偏移分為三種類型：偏移為0，表示線程要訪問的磁道與當(dāng)前磁頭所在磁道相同，此情況應(yīng)該優(yōu)先被調(diào)度，可立即返回該線程對應(yīng)的請求的指針；偏移大于0，記錄向內(nèi)移動距離最短的線程對應(yīng)的請求；偏移小于0，記錄向外移動距離最短的線程對應(yīng)的請求。循環(huán)結(jié)束后，根據(jù)當(dāng)前磁頭移動的方向選擇同方向移動距離最短的線程，如果在同

5、方向上沒有線程，就變換方向，選擇反方向移動距離最短的線程。（2）編寫循環(huán)掃描（CSCAN）磁盤調(diào)度算法由于規(guī)定了磁頭只能從外向內(nèi)移動，所以在每次遍歷中，總是同時找到向內(nèi)移動距離最短的線程和向外移動距離最長的線程。注意，與SCAN算法查找向外移動距離最短線程不同，這里查找向外移動距離最長的線程。在開始遍歷前，可以將用來記錄向外移動最長距離的變量賦值為0。在計算出線程要訪問的磁道與當(dāng)前磁頭所在磁道的偏移后，同樣可以將偏移分為三種類型：偏移為0，表示線程要訪問的磁道與當(dāng)前磁頭所在磁道相同，此情況應(yīng)優(yōu)先被調(diào)度，可立即返回該線程對應(yīng)的請求的指針；偏移大于0，記錄向內(nèi)移動距離最短的線程對應(yīng)的請求；偏移小于

6、0，記錄向外移動距離最長的線程對應(yīng)的請求。循環(huán)結(jié)束后，選擇向內(nèi)移動距離最短的線程，如果沒有向內(nèi)移動的線程，就選擇向外移動距離最長的線程。（3）編寫N-Step-SCAN磁盤調(diào)度算法在block.c文件中的第360行定義了一個宏SUB_QUEUE_LENGTH，表示子隊列的長度（即N值）。目前這個宏定義的值為6。在第367行定義了一個全局變量SubQueueRemainLength表示第一個子隊列剩余的長度，并初始化其值為SUB_QUEUE_LENGTH。在執(zhí)行N-Step-SCAN算法時，要以第一個子隊列剩余的長度做為計數(shù)器，確保只遍歷第一個子隊列剩余的項。所以，結(jié)束遍歷的條件就既包括第一個子

7、隊列結(jié)束，又包括整個隊列結(jié)束（如果整個隊列的長度小于第一個子隊列剩余的長度）。注意，不要直接使用第一個子隊列剩余的長度做為計數(shù)器，可以定義一個新的局部變量來做為計數(shù)器。按照SCAN算法從第一個子隊列剩余的項中選擇一個合適的請求。最后，需要將第一個子隊列剩余長度減少1（SubQueueRemainLengthM少1）,如果第一個子隊列剩余長度變?yōu)?，說明第一個子隊列處理完畢，需要將子隊列剩余的長度重新變?yōu)镹（SubQueueRemainLength重新賦值為SUB_QUEUE_LENGTH）,從而開始處理下一個子隊列。3. 需要解決的問題及解答（1）實驗指導(dǎo)P176-3.2驗證先來先服務(wù)（FCF

8、S）磁盤調(diào)度算法，要求請給出在“輸出”窗口中的結(jié)果。答：先來先服務(wù)（FCFS）磁盤調(diào)度算法在“輸出”窗口中的結(jié)果如下圖所示。圖3.3.1（2）實驗指導(dǎo)P177-3.3驗證驗證最短尋道時間優(yōu)先（SSTF）磁盤調(diào)度算法，要求請給出在“輸出”窗口中的結(jié)果。答：最短尋道時間優(yōu)先（SSTF）磁盤調(diào)度算法在“輸出”窗口中的結(jié)果如下圖所示。圖3.3.2（3）實驗指導(dǎo)P178-3.4驗證SSTF算法造成的線程“饑餓”現(xiàn)象，要求請給出在“輸出”窗口中的結(jié)果。答：SSTF算法造成的線程“饑餓”現(xiàn)象在“輸出”窗口中的結(jié)果如下圖所示。圖3.3.3（4）實驗指導(dǎo)P179-3.5驗證掃描（SCAN）磁盤調(diào)度算法，要求在非

9、饑餓（即實驗指導(dǎo)P176-3.2節(jié)中的數(shù)據(jù)）和饑餓（即實驗指導(dǎo)P178-3.4節(jié)中的數(shù)據(jù)）請給出在“輸出”窗口中的結(jié)果，并且要求在每次輸入兩次“ds”命令（注意不要連續(xù)輸入，要等第一次“ds”命令執(zhí)行完，再輸入第二次“ds”命令），分析結(jié)果為什么不同。答：在非饑餓情況下，“輸出”窗口中的結(jié)果如下圖所示。圖3.3.4在饑餓情況下，“輸出”窗口中的結(jié)果如下圖所示。圖3.3.5ScanInside是一個全局變量，當(dāng)?shù)谝淮螆?zhí)行“ds”命令時，調(diào)用IopDiskSchedule函數(shù)，ScanInside被修改了一次，再次執(zhí)行“ds”命令時，ScanInside不會被重置，因此輸出的結(jié)果會不一樣。（5）在

10、執(zhí)行SCAN、N-Step-SCAN磁盤調(diào)度算法時，如果在EOS控制臺中多次輸入“ds”命令，調(diào)度的順序會發(fā)生變化，說明造成這種現(xiàn)象的原因（提示：注意這兩種算法使用的全局變量）。嘗試修改源代碼，使這兩種算法在多次執(zhí)行時，都能確保調(diào)度的順序一致（提示：可以參考io/block.c文件中IopReceiveRequest函數(shù)和IopProcessNextRequest函數(shù)判斷磁盤調(diào)度算法開始工作和結(jié)束工作的方法）。答：ScanInside是一個全局變量，當(dāng)?shù)谝淮螆?zhí)行“ds”命令時，調(diào)用IopDiskSchedule函數(shù)，ScanInside被修改了一次，再次執(zhí)行“ds”命令時，ScanInside

11、不會被重置，因此輸出的結(jié)果會不一樣。只需在for循環(huán)結(jié)束后添加如下代碼，就能確保調(diào)度的順序一致。(6)嘗試在io/block.c文件中定義一個全局的函數(shù)指針變量DiskScheduleFunc,該函數(shù)指針初始指向?qū)崿F(xiàn)了FCFS算法的IopDiskSchedule函數(shù)。修改io/block.c文件中的IopProcessNextRequest函數(shù)，在該函數(shù)中不再直接調(diào)用lopDiskSchedule函數(shù)，而是調(diào)用函數(shù)指針DiskScheduleFunc指向的磁盤調(diào)度算法函數(shù)；ke/sysproc.c文件中的ConsoleCmdDiskSchedule函數(shù)中也不再直接調(diào)用IopDiskSchedu

12、le函數(shù)，也要修改為調(diào)用函數(shù)指針DiskScheduleFunc指向的磁盤調(diào)度算法函數(shù)。最后，添加一個控制臺命令“sstf"，該命令使函數(shù)指針DiskScheduleFunc指向?qū)崿F(xiàn)了SSTF算法的函數(shù)。這樣，在EOS啟動后默認(rèn)會執(zhí)行FCFS算法，執(zhí)行控制臺命令“sstf”后，會執(zhí)行SSTF算法。按照這種方式依次實現(xiàn)“fcfs”、“scan”、“cscan”和“nstepscan?命令。說明這種在EOS運(yùn)行時動態(tài)切換磁盤調(diào)度算法的好處。答：首先在block.c中定義一個全局的函數(shù)指針變量DiskScheduleFunc。圖3.3.7修改IopProcessNextRequest函數(shù)和

13、ConsoleCmdDiskSchedule函數(shù)，使其不再直接調(diào)用IopDiskSchedule函數(shù)而是調(diào)用函數(shù)指針DiskScheduleFunc指向的磁盤調(diào)度算法函數(shù)。圖3.3.8調(diào)用函數(shù)前先聲明。圖3.3.9添加一個控制臺命令“sstf”，該命令使函數(shù)指針DiskScheduleFunc指向?qū)崿F(xiàn)了SSTF算法的函數(shù)。驗證結(jié)果如下圖所示。(7)分析已經(jīng)實現(xiàn)的各種磁盤調(diào)度算法的優(yōu)缺點，嘗試實現(xiàn)更多其它的磁盤調(diào)度算法。答：先來先服務(wù)算法是一種比較簡單的磁盤調(diào)度算法，它根據(jù)進(jìn)程請求訪問磁盤的先后次序進(jìn)行調(diào)度，此算法的優(yōu)點是公平、簡單，且每個進(jìn)程的請求都能依次得到處理，不會出現(xiàn)某一進(jìn)程的請求長期得

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

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

16、示：如果一個線程只是要獲取磁盤設(shè)備的狀態(tài)而不是要訪問磁盤上的數(shù)據(jù)，是否需要對該線程進(jìn)行磁盤調(diào)度？該線程是否要與其它并發(fā)訪問磁盤設(shè)備的線程進(jìn)行互斥？）答：如果一個線程只是要獲取磁盤設(shè)備的狀態(tài)而不是要訪問磁盤上的數(shù)據(jù)，那這個線程是不需要進(jìn)行磁盤調(diào)度的，所以不會進(jìn)入請求隊列，但該線程同樣需要與其它并發(fā)訪問磁盤設(shè)備的線程進(jìn)行互斥，這時就需要使用磁盤設(shè)備的互斥信號量進(jìn)行互斥。4. 源程序并附上注釋（1）改寫SCAN算法BOOLScanInside=TRUE;PREQUESTIopDiskSchedule（VOID）PLIST_ENTRYpListEntry;PREQUESTpRequest;PREQUE

17、STINpNextRequest=NULL;PREQUESTOUTpNextRequest=NULL;LONGOffset;ULONGInsideShortestDistance=0xFFFFFFFF;ULONGOutsideShortestDistance=0xFFFFFFFF;PREQUESTpNextRequest=NULL;/需要遍歷請求隊列一次或兩次for（pListEntry=RequestListHead.Next;/請求隊列中的第一個請求是鏈表頭指/向的下一個請求。pListEntry!=&RequestListHead;/遍歷到請求隊列頭時結(jié)束循環(huán)。pListEntr

18、y=pListEntry->Next）/根據(jù)鏈表項獲得請求的指針pRequest=CONTAINING_RECORD（pListEntry,REQUEST,ListEntry）;/計算請求對應(yīng)的線程所訪問的磁道與當(dāng)前磁頭所在磁道的偏移（方向由正負(fù)表示）Offset=pRequest->Cylinder-CurrentCylinder;if（0=Offset）/如果線程要訪問的磁道與當(dāng)前磁頭所在磁道相同，可立即返回。pNextRequest=pRequest;gotoRETURN;elseif（Offset>0&&Offset<InsideShortest

19、Distance）/記錄向內(nèi)移動距離最短的線程InsideShortestDistance=Offset;INpNextRequest=pRequest;elseif(Offset<0&&-Offset<OutsideShortestDistance)/記錄向外移動距離最短的線程OutsideShortestDistance=-Offset;OUTpNextRequest=pRequest;/判斷磁頭移動方向，若向內(nèi)移動if(ScanInside)/判斷是否有向內(nèi)移動的線程if(INpNextRequest)/有則選擇該線程returnINpNextRequest;

20、else/沒有則修改磁頭方向，選擇向外移動距離最短的線程ScanInside=!ScanInside;returnOUTpNextRequest;/如果向外移動else/判斷是否有向外移動的線程if(OUTpNextRequest)/有則選擇該線程returnOUTpNextRequest;else/沒有則修改詞頭方向，選擇向內(nèi)移動距離最短的線程ScanInside=!ScanInside;returnINpNextRequest;RETURN:returnpNextRequest;PREQUEST( 2)編寫循環(huán)掃描(CSCAN )磁盤調(diào)度算法IopDiskSchedule(VOID)PLI

21、ST_ENTRYpListEntry;PREQUESTpRequest;PREQUESTINpNextRequest=NULL;PREQUESTOUTpNextRequest=NULL;LONGOffset;ULONGInsideShortestDistance=0xFFFFFFFF;ULONGOutsideShortestDistance=0x00000000;PREQUESTpNextRequest=NULL;/需要遍歷請求隊列一次或兩次for(pListEntry=RequestListHead.Next;/請求隊列中的第一個請求是鏈表頭指/向的下一個請求。pListEntry!=&am

22、p;RequestListHead;/遍歷到請求隊列頭時結(jié)束循環(huán)。pListEntry=pListEntry->Next)/根據(jù)鏈表項獲得請求的指針pRequest=CONTAINING_RECORD(pListEntry,REQUEST,ListEntry);/計算請求對應(yīng)的線程所訪問的磁道與當(dāng)前磁頭所在磁道的偏移(方向由正負(fù)表示)Offset=pRequest->Cylinder-CurrentCylinder;if(0=Offset)/如果線程要訪問的磁道與當(dāng)前磁頭所在磁道相同，可立即返回。pNextRequest=pRequest;gotoRETURN;elseif(Off

23、set>0&&Offset<InsideShortestDistance)/記錄向內(nèi)移動距離最短的線程InsideShortestDistance=Offset;INpNextRequest=pRequest;elseif(Offset<0&&-Offset>OutsideShortestDistance)/記錄向外移動距離最長的線程OutsideShortestDistance=-Offset;OUTpNextRequest=pRequest;/需要向內(nèi)移動的線程是否存在if(INpNextRequest)/存在則返回向內(nèi)移動的請求re

24、turnINpNextRequest;else/否則返回向外移動的請求returnOUTpNextRequest;RETURN:returnpNextRequest;(3)編寫N-Step-SCAN磁盤調(diào)度算法/N-Step-SCAN磁盤調(diào)度算法使用的子隊列長度N#defineSUB_QUEUE_LENGTH6/記錄N-Step-SCAN磁盤調(diào)度算法第一個子隊列剩余的長度。/子隊列初始長度為N，每執(zhí)行一次磁盤調(diào)度算法會從子隊列中移除一個請求，子隊列/長度就要減少1，待長度變?yōu)?時，再將長度重新變?yōu)镹，開始處理下一個子隊列。ULONGSubQueueRemainLength=SUB_QUEUE_

25、LENGTH;/掃描算法中磁頭移動的方向。操作系統(tǒng)啟動時初始化為磁頭向內(nèi)移動。/TRUE，磁頭向內(nèi)移動，磁道號增加。/FALSE，磁頭向外移動，磁道號減少。BOOLScanInside=TRUE;PREQUESTIopDiskSchedule(VOID)PLIST_ENTRYpListEntry;PREQUESTpRequest;PREQUESTINpNextRequest=NULL;PREQUESTOUTpNextRequest=NULL;LONGOffset;ULONGInsideShortestDistance=0xFFFFFFFF;ULONGOutsideShortestDistanc

26、e=0xFFFFFFFF;PREQUESTpNextRequest=NULL;ULONGcounter;/需要遍歷請求隊列一次或兩次/計數(shù)器記錄一個子隊列剩余的長度counter=SubQueueRemainLength;/沒調(diào)度一次子隊列剩余的長度減SubQueueRemainLength-;/如果子隊列剩余的長度為，則重置為子隊列原長度if(SubQueueRemainLength=0)SubQueueRemainLength=SUB_QUEUE_LENGTH;for(pListEntry=RequestListHead.Next;/請求隊列中的第一個請求是鏈表頭指/向的下一個請求。pLi

27、stEntry!=&RequestListHead&&counter>0;/遍歷到請求隊列頭時結(jié)/束循環(huán)或子隊列結(jié)束。pListEntry=pListEntry->Next)/根據(jù)鏈表項獲得請求的指針pRequest=CONTAINING_RECORD(pListEntry,REQUEST,ListEntry);/計算請求對應(yīng)的線程所訪問的磁道與當(dāng)前磁頭所在磁道的偏移(方向由正負(fù)表示)Offset=pRequest->Cylinder-CurrentCylinder;if(0=Offset)/如果線程要訪問的磁道與當(dāng)前磁頭所在磁道相同，可立即返回。pN

28、extRequest=pRequest;returnpNextRequest;elseif(Offset>0&&Offset<InsideShortestDistance)/記錄向內(nèi)移動距離最短的線程InsideShortestDistance=Offset;INpNextRequest=pRequest;elseif(Offset<0&&-Offset<OutsideShortestDistance)/記錄向外移動距離最短的線程OutsideShortestDistance=-Offset;OUTpNextRequest=pReques

29、t;counter-;if(ScanInside)if(INpNextRequest)returnINpNextRequest;elseScanInside=!ScanInside;returnOUTpNextRequest;elseif(OUTpNextRequest)returnOUTpNextRequest;elseScanInside=!ScanInside;returnINpNextRequest;5. 程序運(yùn)行時的初值和運(yùn)行結(jié)果新建一個EOSKernel項目，雙擊ke文件夾中的sysproc.c文件，閱讀函數(shù)ConsoleCmdDiskSchedule目前該函數(shù)使磁頭初始停留在磁道

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