磁盤的調(diào)度算法.doc

《磁盤的調(diào)度算法.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、實驗七磁盤的調(diào)度算法一.實驗要求設(shè)計五個算法,分別是先來先服務(wù)算法,最短尋道時間優(yōu)先算法,掃描(SCAN)算法,循環(huán)掃描(CSCAN)算法,NStepSCAN算法.由人工輸入當(dāng)前的磁道數(shù),由系統(tǒng)隨即生成要訪問的磁道.二、開發(fā)環(huán)境操作系統(tǒng):RadHatLinux,開發(fā)環(huán)境:C語言.三、分析設(shè)計（一）實驗原理.磁盤是可被多個進(jìn)程共享的設(shè)備。當(dāng)有多個進(jìn)程都請求訪問磁盤時，應(yīng)采用一種適當(dāng)?shù)恼{(diào)度算法，以使各進(jìn)程對磁盤的平均訪問(主要是尋道)時間最小。由于在訪問磁盤的時間中，主要是尋道時間，因此，磁盤調(diào)度的目標(biāo)應(yīng)是使磁盤的

2、平均尋道時間最少。(1)先來先服務(wù)．(First-Come，F(xiàn)irst-Served，F(xiàn)CFS):這是一種簡單的磁盤調(diào)度算法。它根據(jù)進(jìn)程請求訪問磁盤的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點是公平、簡單，且每個進(jìn)程的請求都能依次得到處理，不會出現(xiàn)某一進(jìn)程的請求長期得不到滿足的情況。但此算法由于未對尋道進(jìn)行優(yōu)化，致使平均尋道時間可能較長。(2)最短尋道時間優(yōu)先(ShortestSeekTimeFirst，SSTF):該算法選擇這樣的進(jìn)程，其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時間最短，但這種調(diào)度算法卻

3、不能保證平均尋道時間最短。(3)掃描(SCAN)算法:SCAN算法不僅考慮到欲訪問的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動方向。例如，當(dāng)磁頭正在自里向外移動時，SCAN算法所選擇的下一個訪問對象應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進(jìn)程來調(diào)度，即其要訪問的磁道，在當(dāng)前磁道之內(nèi)，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動的規(guī)律頗似電梯的運行，故又稱為電梯調(diào)度算法。(4)循環(huán)掃描(C

4、SCAN)算法:處理該進(jìn)程的請求，致使該進(jìn)程的請求被嚴(yán)重地推遲。為了減少這種延遲，CSCAN算法規(guī)定磁頭單向移動。例如，只自里向外移動，當(dāng)磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道，即將最小磁道號緊接著最大磁道號構(gòu)成循環(huán)，進(jìn)行掃描。(5)N_Step_SCAN算法:N步SCAN算法是將磁盤請求隊列分成若干個長度為N的子隊列,磁盤調(diào)度將按FCFS算法依次處理這些子隊列.而每處理一個隊列時又是按SCAN算法,對一個隊列處理完后,再處理其他隊列.當(dāng)正在處理某子隊列時,如果又出現(xiàn)新的磁盤I/O請求,便將新

5、請求進(jìn)程放進(jìn)其他隊列.（二）程序結(jié)構(gòu)第一部分:程序的主要流程(1)手動輸入當(dāng)前的磁道號,該磁道號在0

6、FS(Hand,DiscLine);//先來先服務(wù)算法(FCFS)break;第二部分:部分的代碼實現(xiàn)(1)就每個算法而言,都有調(diào)用一個子算法CopyL把函數(shù)SetDI隨機生成的磁道數(shù)數(shù)組復(fù)制給RLine[],為什么要復(fù)制,原因是在整個程序中的最后一項功能是實現(xiàn)5種算法對一次隨即生成的磁道數(shù)的比較,所以在每次調(diào)用一種算法時需要設(shè)置一個臨時的數(shù)組Rline[]來存放.(2)在這5個算法中都有一個字函數(shù)DelInq，該函數(shù)的作用是使每個磁道數(shù)向前移動一位，簡單地以FCFS算法為例，這里只FCFS其中的核心代碼：Al

7、l=Han-RLine[0];for(i=0;i<=9;i++){Temp=RLine[0]-RLine[1];//求出移動磁道數(shù),前一個磁道數(shù)減去后一個磁道數(shù)得出臨時的移動距離if(Temp<0)Temp=(-Temp);//移動磁道數(shù)為負(fù)數(shù)時,算出相反數(shù)作為移動磁道數(shù)printf("%5d",RLine[0]);All=Temp+All;//求全部磁道數(shù)的總和DelInq(RLine,0,k);//每個磁道數(shù)向前移動一位k--;}Han是當(dāng)前磁道數(shù)，RLine[0]是第一個隨機磁道數(shù)，Han-RLine[0

8、]得到的是一次磁頭移動的距離，再賦予All，即All是存放磁頭移動的距離總和，for循環(huán)是執(zhí)行10次，Temp變量是求出移動磁道數(shù),前一個磁道數(shù)減去后一個磁道數(shù)得出臨時的移動距離，All=Temp+All是求全部磁道數(shù)的總和之后是DelInq函數(shù)，使每個磁道數(shù)向前移動一位。例如隨機生成的磁道數(shù)數(shù)組RLine是：583286177115593535586492249421因為當(dāng)前的磁道數(shù)