操作系統(tǒng)實(shí)驗(yàn)十

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

2、.3 驗(yàn)證最短尋道時(shí)間優(yōu)先（SSTF）磁盤調(diào)度算法4.4 驗(yàn)證SSTF算法造成的線程“饑餓”現(xiàn)象 4.5 驗(yàn)證掃描（SCAN）磁盤調(diào)度算法4.6 改寫SCAN算法 4.7 編寫循環(huán)掃描（CSCAN）磁盤調(diào)度算法 4.8 驗(yàn)證SSTF、SCAN及CSCAN算法中的“磁臂粘著”現(xiàn)象4.9 編寫N-Step-SCAN磁盤調(diào)度算法二、實(shí)驗(yàn)環(huán)境操作系統(tǒng)：Windows XP編譯器：Tevalation OS Lab語言：C三、實(shí)驗(yàn)過程1. 設(shè)計(jì)思路和流程圖SCAN算法流程圖：SSTF算法流程圖：流程圖：算法調(diào)度：. 需要解決的問題及解答（）在執(zhí)行SCAN、N-Step-SCAN 磁盤調(diào)度算法時(shí)

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

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

5、DiskSchedule函數(shù)，也要修改為調(diào)用函數(shù)指針DiskScheduleFunc指向的磁盤調(diào)度算法函數(shù)。最后，添加一個(gè)控制臺(tái)命令“sstf”，該命令使函數(shù)指針DiskScheduleFunc指向?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”命令。說明這種在EOS運(yùn)行時(shí)動(dòng)態(tài)切換磁盤調(diào)度算法的好處。 答：首先在block.c 中定義一個(gè)全局的函數(shù)指針變量DiskScheduleFunc。修改IopProcessNextRequ

6、est 函數(shù)和ConsoleCmdDiskSchedule 函數(shù)，使其不再直接調(diào)用IopDiskSchedule 函數(shù)而是調(diào)用函數(shù)指針DiskScheduleFunc指向的磁盤調(diào)度算法函數(shù)。調(diào)用函數(shù)前先聲明。添加一個(gè)控制臺(tái)命令“sstf”，該命令使函數(shù)指針DiskScheduleFunc 指向?qū)崿F(xiàn)了 SSTF 算法的函數(shù)。（）分析已經(jīng)實(shí)現(xiàn)的各種磁盤調(diào)度算法的優(yōu)缺點(diǎn)，嘗試實(shí)現(xiàn)更多其它的磁盤調(diào)度算法。 答：先來先服務(wù)算法是一種比較簡(jiǎn)單的磁盤調(diào)度算法，它根據(jù)進(jìn)程請(qǐng)求訪問磁盤的先后次序進(jìn)行調(diào)度，此算法的優(yōu)點(diǎn)是公平、簡(jiǎn)單，且每個(gè)進(jìn)程的請(qǐng)求都能依

7、次得到處理，不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長(zhǎng)期得不到滿足的情況，在對(duì)磁盤的訪問請(qǐng)求比較多的情況下，致使平均尋道時(shí)間可能較長(zhǎng)；最短尋道時(shí)間優(yōu)先算法選擇這樣的進(jìn)程，其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時(shí)間最短，其缺點(diǎn)是在服務(wù)請(qǐng)求很多的情況下，對(duì)內(nèi)外邊緣磁道的請(qǐng)求將會(huì)無限期的被延遲；掃描算法不僅考慮到欲訪問的磁道與當(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)式

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

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

10、 PREQUEST pRequest; LONG Offset; ULONG InsideShortestDistance = 0xFFFFFFFF; ULONG OutsideShortestDistance = 0xFFFFFFFF; PREQUEST pNextRequest; PREQUEST pNextRequestInside = NULL; PREQUEST pNextRequestOutside = NULL; /*遍歷請(qǐng)求隊(duì)列，計(jì)算磁道的偏移，如果Offset=0，則不需要移動(dòng)；Offset > 0 && Offset < InsideShorte

11、stDistance則向內(nèi)測(cè)移動(dòng)并計(jì)下最短距離；Offset < 0 && -Offset < OutsideShortestDistance則向外側(cè)移動(dòng)并計(jì)下最短距離。*/ for (pListEntry = RequestListHead.Next; pListEntry != &RequestListHead;pListEntry = pListEntry->Next) pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry); Offset = pRequest->Cylin

12、der - CurrentCylinder; if (Offset=0) pNextRequest = pRequest; goto RETURN; else if (Offset > 0 && Offset < InsideShortestDistance) InsideShortestDistance = Offset; pNextRequestInside = pRequest; else if (Offset < 0 && -Offset < OutsideShortestDistance) OutsideShortestDist

13、ance = -Offset; pNextRequestOutside = pRequest; ; /* 判定移動(dòng)方向，判定ScanInside是否為0,在判定pNextRequestInside、pNextRequestOutside是否為0，確定移動(dòng)方向。 */ if (ScanInside) if(pNextRequestInside != NULL) pNextRequest = pNextRequestInside; ScanInside = ScanInside; else pNextRequest = pNextRequestOutside; ScanInside = !Scan

14、Inside; else if(pNextRequestOutside != NULL) pNextRequest = pNextRequestOutside; ScanInside = ScanInside; else pNextRequest =pNextRequestInside; ScanInside = !ScanInside; RETURN:return pNextRequest; 編寫循環(huán)掃描（CSCAN）磁盤調(diào)度算法 ：BOOL ScanInside = TRUE;PREQUEST IopDiskSchedule(VOID) PLIST_ENTRY pListEntry; PR

15、EQUEST pRequest; LONG Offset; ULONG InsideShortestDistance = 0xFFFFFFFF; ULONG OutsideShortestDistance = 0x0; PREQUEST pNextRequest; PREQUEST pNextRequestInside = NULL; PREQUEST pNextRequestOutside = NULL; /*遍歷請(qǐng)求隊(duì)列，計(jì)算磁道的偏移，如果Offset=0，則不需要移動(dòng)；Offset > 0 && Offset < InsideShortestDistance

16、則向內(nèi)測(cè)移動(dòng)并計(jì)下最短距離；Offset < 0 && -Offset < OutsideShortestDistance則向外側(cè)移動(dòng)并計(jì)下最短距離。*/ for (pListEntry = RequestListHead.Next; pListEntry != &RequestListHead;pListEntry = pListEntry->Next) pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry); Offset = pRequest->Cylinder - Curr

17、entCylinder; if (Offset=0) pNextRequest = pRequest; goto RETURN; else if (Offset > 0 && Offset < InsideShortestDistance) InsideShortestDistance = Offset; pNextRequestInside = pRequest; else if (Offset < 0 && -Offset > OutsideShortestDistance) OutsideShortestDistance = -Of

18、fset; pNextRequestOutside = pRequest; ; /* 判定移動(dòng)方向，判定ScanInside是否為0,在判定pNextRequestInside、pNextRequestOutside是否為0，確定移動(dòng)方向。 */ if(pNextRequestInside != NULL) pNextRequest = pNextRequestInside; ScanInside = ScanInside; else pNextRequest = pNextRequestOutside; ScanInside = !ScanInside; RETURN:return pNex

19、tRequest; . 程序運(yùn)行時(shí)的初值和運(yùn)行結(jié)果.1 準(zhǔn)備實(shí)驗(yàn) 按照下面的步驟準(zhǔn)備實(shí)驗(yàn)： 1. 啟動(dòng)OS Lab。 2. 新建一個(gè)EOS Kernel項(xiàng)目。 .2 驗(yàn)證先來先服務(wù)（FCFS）磁盤調(diào)度算法 按照下面的步驟進(jìn)行驗(yàn)證： 1. 在“項(xiàng)目管理器”窗口中雙擊ke文件夾中的sysproc.c文件，打開此文件。 2. 在sysproc.c文件的第580行找到控制臺(tái)命令“ds”對(duì)應(yīng)的函數(shù)ConsoleCmdDiskSchedule?！癲s”命令專門用來測(cè)試磁盤調(diào)度算法。閱讀該函數(shù)中的源代碼，目前該函數(shù)使磁頭初始停留在磁道10，其它被阻塞的線程依次訪問磁道8、21、9、78、0、41、10、67

20、、12、10。 3. 打開io/block.c文件，在第378行找到磁盤調(diào)度算法函數(shù)IopDiskSchedule。閱讀該函數(shù)中的源代碼，目前此函數(shù)實(shí)現(xiàn)了FCFS磁盤調(diào)度算法。4. 按F7生成項(xiàng)目，然后按F5啟動(dòng)調(diào)試。 5. 待EOS啟動(dòng)完畢，在EOS控制臺(tái)中輸入命令“ds”后按回車。 在EOS控制臺(tái)中會(huì)首先顯示磁頭的起始位置是10磁道，然后按照線程被阻塞的順序依次顯示線程的信息（包括線程ID和訪問的磁道號(hào)）。磁盤調(diào)度算法執(zhí)行的過程中，在OS Lab的“輸出”窗口中也會(huì)首先顯示磁頭的起始位置，然后按照線程被喚醒的順序依次顯示線程信息（包括線程ID、訪問的磁道號(hào)、磁頭移動(dòng)的距離和方向），并在磁盤

21、調(diào)度結(jié)束后顯示此次調(diào)度的統(tǒng)計(jì)信息（包括總尋道數(shù)、尋道次數(shù)和平均尋道數(shù)）。對(duì)比EOS控制臺(tái)和“輸出”窗口中的內(nèi)容，可以發(fā)現(xiàn)FCFS算法是根據(jù)線程訪問磁盤的先后順序進(jìn)行調(diào)度的。圖18-2顯示了本次調(diào)度執(zhí)行時(shí)磁頭移動(dòng)的軌跡。 可以在控制臺(tái)中多次輸入“ds”命令，查看磁盤調(diào)度算法執(zhí)行的情況。將“輸出”窗口中的內(nèi)容復(fù)制到一個(gè)文本文件中，然后結(jié)束此次調(diào)試。 .3 驗(yàn)證最短尋道時(shí)間優(yōu)先（SSTF）磁盤調(diào)度算法 使用OS Lab打開本實(shí)驗(yàn)文件夾中的sstf.c文件（將sstf.c文件拖動(dòng)到OS Lab窗口中釋放即可）。該文件提供的IopDiskSchedule函數(shù)實(shí)現(xiàn)了SSTF磁盤調(diào)度算法。在閱讀此函數(shù)的源代

22、碼的時(shí)，可以參考圖18-3所示的流程圖，并且應(yīng)該特別注意下面幾點(diǎn)： l 變量Offset是有符號(hào)的長(zhǎng)整型，用來表示磁頭的偏移（包括距離和方向）。Offset大于0時(shí)表示磁頭向內(nèi)移動(dòng)（磁道號(hào)增加）；小于0時(shí)表示磁頭向外移動(dòng)（磁道號(hào)減少）；等于0時(shí)表示磁頭沒有移動(dòng)。而名稱以“Distance”結(jié)尾的變量都是無符號(hào)長(zhǎng)整型，只表示磁頭移動(dòng)的距離（無方向）。所以在比較磁頭的偏移和距離時(shí)，或者在將偏移賦值給距離時(shí)，都要取偏移的絕對(duì)值（調(diào)用C庫函數(shù)abs）。本實(shí)驗(yàn)在實(shí)現(xiàn)其它磁盤調(diào)度算法時(shí)也同樣遵守此約定。 l 在開始遍歷之前，將最小距離（ShortestDistance）初始化為最大的無符號(hào)長(zhǎng)整型數(shù)，這樣，

23、第一次計(jì)算的距離一定會(huì)小于最小距離，從而可以使用第一次計(jì)算的距離來再次初始化最小距離。本實(shí)驗(yàn)在實(shí)現(xiàn)其它磁盤調(diào)度算法時(shí)也同樣使用了此技巧。 按照下面的步驟進(jìn)行驗(yàn)證： 1. 使用sstf.c文件中IopDiskSchedule函數(shù)的函數(shù)體，替換block.c文件中IopDiskSchedule函數(shù)的函數(shù)體。 2. 按F7生成項(xiàng)目，然后按F5啟動(dòng)調(diào)試。 3. 待EOS啟動(dòng)完畢，在EOS控制臺(tái)中輸入命令“ds”后按回車。 對(duì)比EOS控制臺(tái)和“輸出”窗口中的內(nèi)容（特別是線程ID的順序），可以發(fā)現(xiàn)，SSTF算法喚醒線程的順序與線程被阻塞的順序是不同的。圖18-4顯示了本次調(diào)度執(zhí)行時(shí)磁頭移動(dòng)的軌跡。對(duì)比SS

24、TF算法與FCFS算法在“輸出”窗口中的內(nèi)容，可以看出，SSTF算法的平均尋道數(shù)明顯低于FCFS算法。但是，SSTF算法能保證平均尋道數(shù)最少嗎？在后面的實(shí)驗(yàn)中會(huì)進(jìn)行驗(yàn)證。 可以在控制臺(tái)中多次輸入“ds”命令，查看磁盤調(diào)度算法執(zhí)行的情況。將“輸出”窗口中的內(nèi)容復(fù)制到一個(gè)文本文件中，然后結(jié)束此次調(diào)試。 .4 驗(yàn)證SSTF算法造成的線程“饑餓”現(xiàn)象 使用SSTF算法時(shí)，如果不斷有新線程要求訪問磁盤，而且其所要訪問的磁道與當(dāng)前磁頭所在磁道的距離較近，這些新線程的請(qǐng)求必然會(huì)被優(yōu)先滿足，而等待隊(duì)列中一些老線程的請(qǐng)求就會(huì)被嚴(yán)重推遲，從而使老線程出現(xiàn)“饑餓”現(xiàn)象。 按照下面的步驟進(jìn)行實(shí)驗(yàn)，觀察這個(gè)現(xiàn)象： 1.

25、 修改sysproc.c文件ConsoleCmdDiskSchedule函數(shù)中的源代碼，仍然使磁頭初始停留在磁道10，而讓其它線程依次訪問磁道78、21、9、8、11、41、10、67、12、10。 2. 按F7生成項(xiàng)目，然后按F5啟動(dòng)調(diào)試。 3. 待EOS啟動(dòng)完畢，在EOS控制臺(tái)中輸入命令“ds”后按回車。 查看“輸出”窗口中顯示的內(nèi)容，可以發(fā)現(xiàn)，雖然訪問78號(hào)磁道的線程的請(qǐng)求第一個(gè)被放入請(qǐng)求隊(duì)列，但卻被推遲到最后才被處理，出現(xiàn)了“饑餓”現(xiàn)象。如果不斷有新線程的請(qǐng)求到達(dá)并被優(yōu)先滿足，則訪問78號(hào)磁道的線程的“饑餓”情況就會(huì)更加嚴(yán)重。 將“輸出”窗口中的內(nèi)容復(fù)制到一個(gè)文本文件中，然后結(jié)束此次調(diào)

26、試。將ConsoleCmdDiskSchedule函數(shù)中線程訪問的磁道號(hào)恢復(fù)到本實(shí)驗(yàn)3.2中的樣子，在后面的實(shí)驗(yàn)中還要使用這些數(shù)據(jù)。 .5 驗(yàn)證掃描（SCAN）磁盤調(diào)度算法 對(duì)SSTF算法稍加改進(jìn)后可以形成SCAN算法，可防止老線程出現(xiàn)“饑餓”現(xiàn)象。使用OS Lab打開本實(shí)驗(yàn)文件夾中的scan.c文件，該文件提供的IopDiskSchedule函數(shù)實(shí)現(xiàn)了SCAN磁盤調(diào)度算法。在閱讀此函數(shù)的源代碼的時(shí)，應(yīng)該特別注意下面幾點(diǎn)： l 在block.c文件中的第374行定義了一個(gè)布爾類型的全局變量ScanInside，用于表示掃描算法中磁頭移動(dòng)的方向。該變量值為TRUE時(shí)表示磁頭向內(nèi)移動(dòng)（磁道號(hào)增加）

27、；值為FALSE時(shí)表示磁頭向外移動(dòng)（磁道號(hào)減少）。該變量初始化為TRUE，表示SCAN算法第一次執(zhí)行時(shí)，磁頭向內(nèi)移動(dòng)。 l 在scan.c文件的IopDiskSchedule函數(shù)中使用了雙重循環(huán)。第一次遍歷隊(duì)列時(shí)，查找指定方向上移動(dòng)距離最短的線程，如果在指定方向上已經(jīng)沒有線程，就變換方向，進(jìn)行第二次遍歷，同樣是查找移動(dòng)距離最短的線程。在這兩次遍歷中一定能找到合適的線程。 按照下面的步驟進(jìn)行驗(yàn)證： 1. 使用scan.c文件中IopDiskSchedule函數(shù)的函數(shù)體，替換block.c文件中IopDiskSchedule函數(shù)的函數(shù)體。 2. 按F7生成項(xiàng)目，然后按F5啟動(dòng)調(diào)試。 3. 待EOS

28、啟動(dòng)完畢，在EOS控制臺(tái)中輸入命令“ds”后按回車。 對(duì)比SCAN算法與SSTF算法在“輸出”窗口中的內(nèi)容，可以看出，SCAN算法的平均尋道數(shù)有可能小于SSTF算法，所以說SSTF算法不能保證平均尋道數(shù)最少。圖18-5顯示了本次調(diào)度執(zhí)行時(shí)磁頭移動(dòng)的軌跡。嘗試在控制臺(tái)中多次輸入“ds”命令，查看磁盤調(diào)度算法執(zhí)行的情況，說明為什么線程調(diào)度的順序會(huì)發(fā)生變化。將“輸出”窗口中的內(nèi)容復(fù)制到一個(gè)文本文件中，然后結(jié)束此次調(diào)試。 使用SCAN算法調(diào)度在本實(shí)驗(yàn)3.4中產(chǎn)生“饑餓”現(xiàn)象的數(shù)據(jù)，驗(yàn)證SCAN算法能夠解決“饑餓”現(xiàn)象，并將“輸出”窗口中的內(nèi)容保存到一個(gè)文本文件中。最后將ConsoleCmdDiskSc

29、hedule函數(shù)中線程訪問的磁道號(hào)恢復(fù)到本實(shí)驗(yàn)3.2中的樣子，在后面的實(shí)驗(yàn)中還要使用這些數(shù)據(jù)。 .6 改寫SCAN算法 .6.1 要求 在已有SCAN算法源代碼的基礎(chǔ)上進(jìn)行改寫，要求不再使用雙重循環(huán)，而是只遍歷一次請(qǐng)求隊(duì)列中的請(qǐng)求，就可以選中下一個(gè)要處理的請(qǐng)求。由于線程和請(qǐng)求總是一一對(duì)應(yīng)的，為了使后面的內(nèi)容更加簡(jiǎn)單易懂，有時(shí)就不再區(qū)分這兩個(gè)概念。 .6.2 提示 1. 在一次遍歷中，不再關(guān)心當(dāng)前磁頭移動(dòng)的方向，而是同時(shí)找到兩個(gè)方向上移動(dòng)距離最短的線程所對(duì)應(yīng)的請(qǐng)求，這樣就不再需要遍歷兩次。 2. 在計(jì)算出線程要訪問的磁道與當(dāng)前磁頭所在磁道的偏移后，可以將偏移分為三種類型：偏移為0，表示線程要訪問

30、的磁道與當(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)求。 3. 循環(huán)結(jié)束后，根據(jù)當(dāng)前磁頭移動(dòng)的方向選擇同方向移動(dòng)距離最短的線程，如果在同方向上沒有線程，就變換方向，選擇反方向移動(dòng)距離最短的線程。具體邏輯可以參見圖18-6所示的流程圖。 制作軟盤鏡像.正在啟動(dòng) Virtual PC.開始調(diào)試.* Disk schedule start working *Start Cylinder: 10TID: 37 Cylinder: 10 Offset: 0 =TID: 40

31、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: 33 Cylinder: 9 Offset: 69 -TID: 31 Cylinder: 8 Offset: 1 -TID: 35 Cylinder: 0 Offset: 8 -Total offset: 146 T

32、ransfer times: 10 Average offset: 14* Disk schedule stop working * Disk schedule start working *Start Cylinder: 10TID: 47 Cylinder: 10 Offset: 0 =TID: 50 Cylinder: 10 Offset: 0 =TID: 43 Cylinder: 9 Offset: 1 -TID: 41 Cylinder: 8 Offset: 1 -TID: 45 Cylinder: 0 Offset: 8 -TID: 49 Cylinder: 12 Offset:

33、12 +TID: 42 Cylinder: 21 Offset: 9 +TID: 46 Cylinder: 41 Offset: 20 +TID: 48 Cylinder: 67 Offset: 26 +TID: 44 Cylinder: 78 Offset: 11 +Total offset: 88 Transfer times: 10 Average offset: 8* Disk schedule stop working *.6.3 測(cè)試方法 使用本實(shí)驗(yàn)3.2中的數(shù)據(jù)進(jìn)行測(cè)試，確保調(diào)度的結(jié)果與圖18-5中顯示的一致，也可以多準(zhǔn)備幾組測(cè)試數(shù)據(jù)，保證改寫的SCAN算法是正確的。測(cè)試成功后，

34、將改寫的SCAN算法源代碼備份。 .7 編寫循環(huán)掃描（CSCAN）磁盤調(diào)度算法 .7.1 要求 在已經(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算法更加簡(jiǎn)單。 .7.2 提示 1. 由于規(guī)定了磁頭只能從外向內(nèi)移動(dòng)，所以在每次遍歷中，總是同時(shí)找到向內(nèi)移動(dòng)距離最短的線程和向外移動(dòng)距離最長(zhǎng)的線程。

35、注意，與SCAN算法查找向外移動(dòng)距離最短線程不同，這里查找向外移動(dòng)距離最長(zhǎng)的線程。在開始遍歷前，可以將用來記錄向外移動(dòng)最長(zhǎng)距離的變量賦值為0。 2. 在計(jì)算出線程要訪問的磁道與當(dāng)前磁頭所在磁道的偏移后，同樣可以將偏移分為三種類型：偏移為0，表示線程要訪問的磁道與當(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)求。 3. 循環(huán)結(jié)束后，選擇向內(nèi)移動(dòng)距離最短的線程，如果沒有向內(nèi)移動(dòng)的線程，就選擇向外移動(dòng)距離最長(zhǎng)的線程。 .7.3 測(cè)試方法 使用本實(shí)驗(yàn)3.2中的數(shù)據(jù)進(jìn)行測(cè)試，?？?/p>

36、以在控制臺(tái)中多次輸入“ds”命令，查看磁盤調(diào)度算法執(zhí)行的情況。測(cè)試成功后，將“輸出”窗口中的內(nèi)容復(fù)制到一個(gè)文本文件中，并將編寫的CSCAN算法源代碼備份。制作軟盤鏡像.正在啟動(dòng) Virtual PC.開始調(diào)試.* Disk schedule start working *Start Cylinder: 10TID: 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:

37、41 Offset: 20 +TID: 38 Cylinder: 67 Offset: 26 +TID: 34 Cylinder: 78 Offset: 11 +TID: 35 Cylinder: 0 Offset: 78 -TID: 31 Cylinder: 8 Offset: 8 +TID: 33 Cylinder: 9 Offset: 1 +Total offset: 155 Transfer times: 10 Average offset: 15* Disk schedule stop working * Disk schedule start working *Start Cyli

38、nder: 10TID: 47 Cylinder: 10 Offset: 0 =TID: 50 Cylinder: 10 Offset: 0 =TID: 49 Cylinder: 12 Offset: 2 +TID: 42 Cylinder: 21 Offset: 9 +TID: 46 Cylinder: 41 Offset: 20 +TID: 48 Cylinder: 67 Offset: 26 +TID: 44 Cylinder: 78 Offset: 11 +TID: 45 Cylinder: 0 Offset: 78 -TID: 41 Cylinder: 8 Offset: 8 +TI

39、D: 43 Cylinder: 9 Offset: 1 +Total offset: 155 Transfer times: 10 Average offset: 15* Disk schedule stop working *.8 驗(yàn)證SSTF、SCAN及CSCAN算法中的“磁臂粘著”現(xiàn)象 觀察執(zhí)行SSTF、SCAN及CSCAN算法時(shí)磁頭移動(dòng)的軌跡，可以看到，在開始時(shí)磁頭都停留在10磁道不動(dòng)，這就是“磁臂粘著”現(xiàn)象。為了更加明顯的觀察該現(xiàn)象，按照下面的步驟進(jìn)行實(shí)驗(yàn)： 1. 修改sysproc.c文件ConsoleCmdDiskSchedule函數(shù)中的源代碼，仍然使磁頭初始停留在磁道10，而讓其它線程依次訪問磁道78、10、10、10、10、10、10、10、10、10。 2. 分別使用SSTF、SCAN和CSCAN算法調(diào)度這組數(shù)據(jù)。 查看各種算法在“輸出”窗口中顯示的內(nèi)容，可以發(fā)現(xiàn)，雖然訪問78號(hào)磁道的線程的請(qǐng)求第一個(gè)被放入請(qǐng)求隊(duì)列，但卻被推遲到最后才被處理，出現(xiàn)了“磁臂粘著”現(xiàn)象。