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

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

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

3、。圖 3.1.1 SCAN 算法 IopDiskSchedule 函數(shù)流程圖（2）編寫循環(huán)掃描（ CSCAN）磁盤調度算法在已經(jīng)完成的SCAN算法源代碼的基礎上進行改寫，不再使用全局變量ScanInside確定磁頭移動的方向， 而是規(guī)定磁頭只能從外向內移動。當磁頭移動到最內的被訪問磁道時，磁頭立即移動到最外的被訪問磁道，即將最大磁道號緊接著最小磁道號構成循環(huán)，進行掃描。算法流程圖如下圖所示。圖 3.1.2 CSCAN 算法 IopDiskSchedule函數(shù)流程圖（3）編寫 N-Step-SCAN磁盤調度算法在已經(jīng)完成的SCAN 算法源代碼的基礎上進行改寫，將請求隊列分成若干個長度為N的子隊列

4、，調度程序按照FCFS 原則依次處理這些子隊列，而每處理一個子隊列時，又是按照 SCAN算法。算法流程圖如下圖所示。圖 3.1.3 N-Step-SCAN 算法 IopDiskSchedule 函數(shù)流程圖2. 算法實現(xiàn)（1）改寫 SCAN算法在一次遍歷中，不再關心當前磁頭移動的方向，而是同時找到兩個方向上移動距離最短的線程所對應的請求， 這樣就不再需要遍歷兩次。在計算出線程要訪問的磁道與當前磁頭所在磁道的偏移后，可以將偏移分為三種類型：偏移為0，表示線程要訪問的磁道與當前磁頭所在磁道相同，此情況應該優(yōu)先被調度，可立即返回該線程對應的請求的指針；偏移大于 0 ，記錄向內移動距離最短的線程對應的請

5、求；偏移小于 0 ，記錄向外移動距離最短的線程對應的請求。循環(huán)結束后，根據(jù)當前磁頭移動的方向選擇同方向移動距離最短的線程，如果在同方向上沒有線程，就變換方向，選擇反方向移動距離最短的線程。（2）編寫循環(huán)掃描（ CSCAN）磁盤調度算法由于規(guī)定了磁頭只能從外向內移動，所以在每次遍歷中，總是同時找到向內移動距離最短的線程和向外移動距離最長的線程。注意，與 SCAN 算法查找向外移動距離最短線程不同，這里查找向外移動距離最長的線程。在開始遍歷前，可以將用來記錄向外移動最長距離的變量賦值為 0。在計算出線程要訪問的磁道與當前磁頭所在磁道的偏移后，同樣可以將偏移分為三種類型：偏移為0 ，表示線程要訪問的

6、磁道與當前磁頭所在磁道相同，此情況應優(yōu)先被調度，可立即返回該線程對應的請求的指針；偏移大于0 ，記錄向內移動距離最短的線程對應的請求；偏移小于0 ，記錄向外移動距離最長的線程對應的請求。循環(huán)結束后，選擇向內移動距離最短的線程，如果沒有向內移動的線程，就選擇向外移動距離最長的線程。（3）編寫 N-Step-SCAN磁盤調度算法在 block.c 文件中的第 360 行定義了一個宏 SUB_QUEUE_LENGTH，表示子隊列的長度（ 即 N 值 ）。目前這個宏定義的值為 6。在第 367 行定義了一個全局變量SubQueueRemainLength， 表 示 第 一 個 子 隊 列 剩 余 的

7、長 度 ， 并 初 始 化 其 值 為SUB_QUEUE_LENGTH。在執(zhí)行 N-Step-SCAN 算法時，要以第一個子隊列剩余的長度做為計數(shù)器，確保只遍歷第一個子隊列剩余的項。所以，結束遍歷的條件就既包括第一個子隊列結束，又包括整個隊列結束（如果整個隊列的長度小于第一個子隊列剩余的長度）。注意，不要直接使用第一個子隊列剩余的長度做為計數(shù)器，可以定義一個新的局部變量來做為計數(shù)器。按照 SCAN 算法從第一個子隊列剩余的項中選擇一個合適的請求。最后，需要將第一個子隊列剩余長度減少1（SubQueueRemainLength減少 1），如果第一個子隊列剩余長度變?yōu)?，說明第一個子隊列處理完畢，

8、需要將子隊列剩余的長度重新變?yōu)镹（ SubQueueRemainLength重新賦值為 SUB_QUEUE_LENGTH），從而開始處理下一個子隊列。3. 需要解決的問題及解答（1）實驗指導P176-3.2驗證先來先服務（ FCFS）磁盤調度算法，要求請給出在“輸出”窗口中的結果。答：先來先服務（ FCFS）磁盤調度算法在“輸出”窗口中的結果如下圖所示。圖 3.3.1（2）實驗指導P177-3.3驗證驗證最短尋道時間優(yōu)先（SSTF）磁盤調度算法，要求請給出在“輸出”窗口中的結果。答：最短尋道時間優(yōu)先（SSTF）磁盤調度算法在“輸出”窗口中的結果如下圖所示。圖 3.3.2（3）實驗指導 P178

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

10、出”窗口中的結果如下圖所示。圖 3.3.5ScanInside 是一個全局變量，當?shù)谝淮螆?zhí)行“ ds”命令時，調用 IopDiskSchedule 函數(shù)， ScanInside 被修改了一次，再次執(zhí)行“ ds”命令時， ScanInside 不會被重置，因此輸出的結果會不一樣。（5）在執(zhí)行 SCAN、N-Step-SCAN 磁盤調度算法時， 如果在 EOS控制臺中多次輸入 “ ds”命令，調度的順序會發(fā)生變化，說明造成這種現(xiàn)象的原因（提示：注意這兩種算法使用的全局變量）。嘗試修改源代碼， 使這兩種算法在多次執(zhí)行時，都能確保調度的順序一致 （提示：可以參考 io/block.c文件中 IopRe

11、ceiveRequest函數(shù)和 IopProcessNextRequest函數(shù)判斷磁盤調度算法開始工作和結束工作的方法）。答：ScanInside 是一個全局變量，當?shù)谝淮螆?zhí)行“ds”命令時，調用 IopDiskSchedule函數(shù)， ScanInside 被修改了一次，再次執(zhí)行“ds”命令時， ScanInside 不會被重置，因此輸出的結果會不一樣。只需在for 循環(huán)結束后添加如下代碼，就能確保調度的順序一致。圖 3.3.6（6）嘗試在 io/block.c文件中定義一個全局的函數(shù)指針變量DiskScheduleFunc ，該函數(shù)指針初始指向實現(xiàn)了FCFS 算法的 IopDiskSched

12、ule函數(shù)。修改 io/block.c文件中的 IopProcessNextRequest函數(shù)，在該函數(shù)中不再直接調用IopDiskSchedule函數(shù)，而是調用函數(shù)指針DiskScheduleFunc指向的磁盤調度算法函數(shù)； ke/sysproc.c文件中的ConsoleCmdDiskSchedule 函數(shù)中也不再直接調用IopDiskSchedule函數(shù)，也要修改為調用函數(shù)指針 DiskScheduleFunc 指向的磁盤調度算法函數(shù)。 最后，添加一個控制臺命令 “ sstf ”，該命令使函數(shù)指針DiskScheduleFunc指向實現(xiàn)了 SSTF 算法的函數(shù)。這樣，在EOS啟動后默認會執(zhí)

13、行 FCFS 算法，執(zhí)行控制臺命令“ sstf ”后，會執(zhí)行 SSTF算法。按照這種方式依次實現(xiàn)“ fcfs ”、“ scan”、“ cscan”和“ nstepscan ”命令。說明這種在EOS運行時動態(tài)切換磁盤調度算法的好處。答：首先在 block.c中定義一個全局的函數(shù)指針變量DiskScheduleFunc 。圖 3.3.7修改 IopProcessNextRequest函數(shù)和ConsoleCmdDiskSchedule 函數(shù)，使其不再直接調用 IopDiskSchedule函數(shù)而是調用函數(shù)指針DiskScheduleFunc 指向的磁盤調度算法函數(shù)。圖 3.3.8調用函數(shù)前先聲明。圖

14、 3.3.9添加一個控制臺命令 “sstf ”，該命令使函數(shù)指針DiskScheduleFunc指向實現(xiàn)了 SSTF算法的函數(shù)。驗證結果如下圖所示。（7）分析已經(jīng)實現(xiàn)的各種磁盤調度算法的優(yōu)缺點，嘗試實現(xiàn)更多其它的磁盤調度算法。答：先來先服務算法 是一種比較簡單的磁盤調度算法，它根據(jù)進程請求訪問磁盤的先后次序進行調度，此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現(xiàn)某一進程的請求長期得不到滿足的情況，在對磁盤的訪問請求比較多的情況下，致使平均尋道時間可能較長；最短尋道時間優(yōu)先算法選擇這樣的進程，其要求訪問的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短，該算法可以得

15、到比較好的吞吐量，但卻不能保證平均尋道時間最短，其缺點是在服務請求很多的情況下，對內外邊緣磁道的請求將會無限期的被延遲； 掃描算法 不僅考慮到欲訪問的磁道與當前磁道的距離，更優(yōu)先考慮的是磁頭的當前移動方向，此算法基本上克服了最短尋道時間優(yōu)先算法的服務集中于中間磁道和響應時間變化比較大的缺點，而具有最短尋道時間優(yōu)先算法的優(yōu)點即吞吐量較大，平均響應時間較小，但由于是擺動式的掃描方法，兩側磁道被訪問的頻率仍低于中間磁道； 循環(huán)掃描算法 是對掃描算法的改進，如果對磁道的訪問請求是均勻分布的，當磁頭到達磁盤的一端，并反向運動時落在磁頭之后的訪問請求相對較少；N-Step-SCAN 算法是掃描算法和先來先

16、服務算法的一個綜合算法，將請求隊列分成若干個長度為N 的子隊列，調度程序按照 FCFS 原則依次處理這些子隊列， 而每處理一個子隊列時， 又是按照 SCAN算法，所以它是一種性能比較平均的算法。（6）EOS在塊設備層實現(xiàn)了磁盤調度算法后，由于請求隊列中的請求一定是被逐個處理的，所以并發(fā)的多個線程已經(jīng)可以互斥的訪問磁盤上的數(shù)據(jù)，那為什么在IopReadWriteSector函數(shù)中還要使用磁盤設備的互斥信號量進行互斥呢？（提示：如果一個線程只是要獲取磁盤設備的狀態(tài)而不是要訪問磁盤上的數(shù)據(jù)，是否需要對該線程進行磁盤調度？該線程是否要與其它并發(fā)訪問磁盤設備的線程進行互斥？）答：如果一個線程只是要獲取磁

17、盤設備的狀態(tài)而不是要訪問磁盤上的數(shù)據(jù)，那這個線程是不需要進行磁盤調度的，所以不會進入請求隊列，但該線程同樣需要與其它并發(fā)訪問磁盤設備的線程進行互斥，這時就需要使用磁盤設備的互斥信號量進行互斥。4. 源程序并附上注釋（1）改寫 SCAN算法BOOL ScanInside = TRUE;PREQUESTIopDiskSchedule(VOID)PLIST_ENTRY pListEntry;PREQUEST pRequest;PREQUEST INpNextRequest = NULL;PREQUEST OUTpNextRequest = NULL;LONG Offset;ULONG InsideS

18、hortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0xFFFFFFFF;PREQUEST pNextRequest = NULL;/ 需要遍歷請求隊列一次或兩次for (pListEntry = RequestListHead.Next;/請求隊列中的第一個請求是鏈表頭指 / 向的下一個請求。pListEntry != &RequestListHead;/遍歷到請求隊列頭時結束循環(huán)。pListEntry = pListEntry-Next) / 根據(jù)鏈表項獲得請求的指針pRequest = CONTAINING_RECOR

19、D(pListEntry, REQUEST, ListEntry);/ 計算請求對應的線程所訪問的磁道與當前磁頭所在磁道的偏移（方向由正負表示）Offset = pRequest-Cylinder - CurrentCylinder;if (0 = Offset) / 如果線程要訪問的磁道與當前磁頭所在磁道相同，可立即返回。pNextRequest = pRequest;goto RETURN; else if ( Offset 0 & Offset InsideShortestDistance ) / 記錄向內移動距離最短的線程InsideShortestDistance = Offset;

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

21、N; else if ( Offset 0 & Offset InsideShortestDistance ) / 記錄向內移動距離最短的線程InsideShortestDistance = Offset; INpNextRequest = pRequest; else if ( Offset OutsideShortestDistance ) / 記錄向外移動距離最長的線程OutsideShortestDistance = -Offset;OUTpNextRequest = pRequest;/ 需要向內移動的線程是否存在if( INpNextRequest )/ 存在則返回向內移動的請求r

22、eturn INpNextRequest;else/ 否則返回向外移動的請求return OUTpNextRequest;RETURN:return pNextRequest;（3）編寫 N-Step-SCAN磁盤調度算法/ N-Step-SCAN 磁盤調度算法使用的子隊列長度 N#define SUB_QUEUE_LENGTH 6/ 記錄 N-Step-SCAN 磁盤調度算法第一個子隊列剩余的長度。/ 子隊列初始長度為 N，每執(zhí)行一次磁盤調度算法會從子隊列中移除一個請求，子隊列/ 長度就要減少 1，待長度變?yōu)?0 時，再將長度重新變?yōu)?N，開始處理下一個子隊列。ULONG SubQueueR

23、emainLength = SUB_QUEUE_LENGTH;/ 掃描算法中磁頭移動的方向。操作系統(tǒng)啟動時初始化為磁頭向內移動。/ TRUE ，磁頭向內移動，磁道號增加。/ FALSE ，磁頭向外移動，磁道號減少。BOOL ScanInside = TRUE;PREQUESTIopDiskSchedule(VOID)PLIST_ENTRY pListEntry;PREQUEST pRequest;PREQUEST INpNextRequest = NULL;PREQUEST OUTpNextRequest = NULL;LONG Offset;ULONG InsideShortestDista

24、nce = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0xFFFFFFFF;PREQUEST pNextRequest = NULL;ULONG counter;/ 需要遍歷請求隊列一次或兩次/ 計數(shù)器記錄一個子隊列剩余的長度counter = SubQueueRemainLength;/ 沒調度一次子隊列剩余的長度減SubQueueRemainLength-;/ 如果子隊列剩余的長度為，則重置為子隊列原長度if(SubQueueRemainLength = 0)SubQueueRemainLength = SUB_QUEUE_LENGTH;for

25、(pListEntry = RequestListHead.Next;/請求隊列中的第一個請求是鏈表頭指 / 向的下一個請求。pListEntry != &RequestListHead & counter0;/遍歷到請求隊列頭時結 / 束循環(huán)或子隊列結束。pListEntry = pListEntry-Next) / 根據(jù)鏈表項獲得請求的指針pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);/ 計算請求對應的線程所訪問的磁道與當前磁頭所在磁道的偏移（方向由正負表示）Offset = pRequest-Cylinder -

26、 CurrentCylinder;if (0 = Offset) / 如果線程要訪問的磁道與當前磁頭所在磁道相同，可立即返回。pNextRequest = pRequest;return pNextRequest; else if ( Offset 0 & Offset InsideShortestDistance ) / 記錄向內移動距離最短的線程InsideShortestDistance = Offset;INpNextRequest = pRequest; else if ( Offset 0 & -Offset OutsideShortestDistance ) / 記錄向外移動距離

27、最短的線程OutsideShortestDistance = -Offset; OUTpNextRequest = pRequest;counter-;if( ScanInside )if(INpNextRequest)return INpNextRequest;elseScanInside = !ScanInside;return OUTpNextRequest;elseif(OUTpNextRequest)return OUTpNextRequest;elseScanInside = !ScanInside;return INpNextRequest;5. 程序運行時的初值和運行結果（1）

28、驗證先來先服務（ FCFS）磁盤調度算法新建一個EOS Kernel項目，雙擊ke 文件夾中的sysproc.c文件，閱讀函數(shù)ConsoleCmdDiskSchedule，目前該函數(shù)使磁頭初始停留在磁道10，其它被阻塞的線程依次訪問磁道 8、21、9、78、0、41、 10、67、12、10。按 F5 調試項目，待 EOS 啟動完畢，在EOS控制臺中輸入命令“ ds”后按回車。控制臺和輸出窗口顯示內容如下圖所示。圖 3.5.2圖 3.5.3對比 EOS控制臺和“輸出”窗口中的內容，可以發(fā)現(xiàn)FCFS算法是根據(jù)線程訪問磁盤的先后順序進行調度的。（2）驗證最短尋道時間優(yōu)先（SSTF）磁盤調度算法使用

29、sstf.c文件 中IopDiskSchedule函數(shù) 的函數(shù)體 ，替 換block.c文 件中IopDiskSchedule函數(shù)的函數(shù)體。按F7 生成項目，然后按F5 啟動調試。待 EOS 啟動完畢，在 EOS控制臺中輸入命令“ ds”后按回車。輸出窗口輸出結果如下圖所示。圖 3.5.4（3）驗證 SSTF算法造成的線程“饑餓”現(xiàn)象修改 sysproc.c文件 ConsoleCmdDiskSchedule 函數(shù)中的源代碼， 仍然使磁頭初始停留在磁道 10，而讓其它線程依次訪問磁道78、21、 9、 8、 11、41、10、 67、12、 10。按 F7生成項目，然后按F5 啟動調試。待 EOS啟動完畢，在 EOS控制臺中輸入命令“ ds”后按回車。輸出窗口輸出結果如下圖所示。圖 3.5.5（4）驗證掃描（ SCAN）磁盤調度算法使用scan.c文件 中IopDiskSchedule函數(shù) 的函數(shù)體 ，替 換block.c文 件中