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

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

2、d，F(xiàn)CFS):這是一種簡單的磁盤調(diào)度算法。它根據(jù)進程請求訪問磁盤的先后次序進展調(diào)度。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現(xiàn)某一進程的請求長期得不到滿足的情況。但此算法由于未對尋道進展優(yōu)化，致使平均尋道時間可能較長。(2) 最短尋道時間優(yōu)先(ShortestSeekTimeFirst，SSTF): 該算法選擇這樣的進程，其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時間最短，但這種調(diào)度算法卻不能保證平均尋道時間最短。(3) 掃描(SCAN)算法: SCAN算法不僅考慮到欲訪問的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動方向。例如，當(dāng)磁頭正在自

3、里向外移動時，SCAN算法所選擇的下一個訪問對象應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調(diào)度，即其要訪問的磁道，在當(dāng)前磁道之內(nèi)，從而防止了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動的規(guī)律頗似電梯的運行，故又稱為電梯調(diào)度算法。(4) 循環(huán)掃描(CSCAN)算法: 處理該進程的請求，致使該進程的請求被嚴(yán)重地推遲。為了減少這種延遲，CSCAN算法規(guī)定磁頭單向移動。例如，只自里向外移動，當(dāng)磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道，即將最小磁道號緊接著最大磁道號構(gòu)成循環(huán)，進

4、展掃描。(5) N_Step_SCAN算法: N步SCAN算法是將磁盤請求隊列分成假設(shè)干個長度為N的子隊列,磁盤調(diào)度將按FCFS算法依次處理這些子隊列.而每處理一個隊列時又是按SCAN算法,對一個隊列處理完后,再處理其他隊列.當(dāng)正在處理某子隊列時,如果又出現(xiàn)新的磁盤I/O請求,便將新請求進程放進其他隊列.二程序構(gòu)造第一局部:程序的主要流程(1) 手動輸入當(dāng)前的磁道號,該磁道號在0<n<65536以內(nèi)(65536是2的16次方),超出X圍那么需重新輸入.(2) 手動輸入要尋找磁道的X圍.(3) 主菜單,選擇要進展磁道調(diào)度算法,此時會隨機生成一個在第二步生成磁道X圍以內(nèi)的10個磁道數(shù),

5、由SetDI方法生成,再將生成的隨機磁道號以數(shù)組形式作為參數(shù)被某個算法調(diào)用.例如,選擇了case 1,那么先調(diào)用SetDI方法,再執(zhí)行FCFS算法.如下: case 1: SetDI(DiscLine); /隨機生成磁道數(shù) FCFS(Hand,DiscLine); /先來先效勞算法(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)

6、在這5個算法中都有一個字函數(shù)DelInq，該函數(shù)的作用是使每個磁道數(shù)向前移動一位，簡單地以FCFS算法為例，這里只FCFS其中的核心代碼：All=Han-RLine0; for(i=0;i<=9;i+) Temp=RLine0-RLine1;/求出移動磁道數(shù),前一個磁道數(shù)減去后一個磁道數(shù)得出臨時的移動距離 if(Temp<0) Temp=(-Temp);/移動磁道數(shù)為負(fù)數(shù)時,算出相反數(shù)作為移動磁道數(shù) printf("%5d",RLine0); All=Temp+All;/求全部磁道數(shù)的總和 DelInq(RLine,0,k);/每個磁道數(shù)向前移動一位 k-; H

7、an是當(dāng)前磁道數(shù)，RLine0是第一個隨機磁道數(shù)，Han-RLine0得到的是一次磁頭移動的距離，再賦予All，即All是存放磁頭移動的距離總和，for循環(huán)是執(zhí)行10次，Temp變量是求出移動磁道數(shù),前一個磁道數(shù)減去后一個磁道數(shù)得出臨時的移動距離，All=Temp+All是求全部磁道數(shù)的總和之后是DelInq函數(shù)，使每個磁道數(shù)向前移動一位。例如隨機生成的磁道數(shù)數(shù)組RLine是：583 286 177 115 593 535 586 492 249 421 因為當(dāng)前的磁道數(shù)是500，通過All=Han-RLine0語句得到All等于83，接下來是Temp=RLine0-RLine1，是583-2

8、86=297，此時All等于83+297=380，再通過DelInq整個RLine數(shù)組的每個元素向前移一位，如下列圖所示：(3) 如果選擇case 6: 各類算法的比擬,該比擬是比擬這5種算法的尋道長度的總和,由小到大的排序.算法由PaiXu()函數(shù)實現(xiàn).具體是每種算法的最后都設(shè)置Best的二維數(shù)組, BestJage1=All,All是磁道數(shù)總和,Jage視每種算法而定,例如FCFS為1,那么Jage為1, SSTF為2,那么Jage為2,BestJage0=1(用來唯一標(biāo)識某個算法) .最后以PaiXu()算法,用冒泡法排序把5個算法的磁道數(shù)綜合由小到大排序.三數(shù)據(jù)構(gòu)造： Hand:當(dāng)前磁

9、道號;DiscLine10:隨機生成的磁道號; void SetDI(int DiscL)生成隨機磁道號算法; void CopyL(int Sour,int Dist ,int x) 數(shù)組Sour復(fù)制到數(shù)組Dist，復(fù)制到x個數(shù)四詳細(xì)設(shè)計; void DelInq(int Sour,int x,int y) 數(shù)組Sour把x位置的數(shù)刪除,x后的數(shù)組元素向前挪一位.void PaiXu()尋道長度由低到高排序void FCFS(int Han,int DiscL)先來先效勞算法(FCFS) void SSTF(int Han,int DiscL)最短尋道時間優(yōu)先算法(SSTF) int SCA

10、N(int Han,int DiscL,int x,int y) 掃描算法(SCAN) void CSCAN(int Han,int DiscL)循環(huán)掃描算法(CSCAN) void N_Step_SCAN(int Han1,int DiscL)N步掃描算法(NStepScan)* 課題：磁盤調(diào)度算法 *include "stdio.h"*include "stdlib.h"void CopyL(int Sour,int Dist ,int x); /數(shù)組Sour復(fù)制到數(shù)組Dist，復(fù)制到x個數(shù)void SetDI(int DiscL); /隨機生成磁道

11、數(shù) void Print(int Pri,int x); /打印輸出數(shù)組Privoid DelInq(int Sour,int x,int y); /數(shù)組Sour把x位置的數(shù)刪除，并把y前面的數(shù)向前移動，y后的數(shù)保持不變(即會出現(xiàn)2個y) void FCFS(int Han,int DiscL); /先來先效勞算法(FCFS)void SSTF(int Han,int DiscL); /最短尋道時間優(yōu)先算法(SSTF)int SCAN(int Han,int DiscL,int x,int y); /掃描算法(SCAN)void CSCAN(int Han,int DiscL); /循環(huán)掃描算

12、法(CSCAN)void N_Step_SCAN(int Han1,int DiscL); /N步掃描算法(NStepScan)void PaiXu(); /尋道長度由低到高排序void Pri();int NAll=0;int Best52; /用作尋道長度由低到高排序時存放的數(shù)組 int Limit=0; /輸入尋找的X圍磁道數(shù)iint Jage;float Aver=0;int main() int i; int DiscLine10; /聲明準(zhǔn)備要生成的隨機磁道號的數(shù)組 int Hand; /磁道數(shù) int Con=1; int n; while(Con=1) Jage=0; prin

13、tf(" 請輸入初始的磁道數(shù)(0<n<65536):"); scanf("%d",&Hand); printf(" + 輸入尋找的X圍:"); scanf("%d",&Limit); if(Limit>65536) printf("超出X圍!"); else printf(" "); printf(" 操作系統(tǒng)課程設(shè)計 "); printf(" 磁盤調(diào)度算法 "); printf(" &quo

14、t;); printf(" "); printf(" 1.先來先效勞算法(FCFS) "); printf(" "); printf(" 2.最短尋道時間優(yōu)先算法(SSTF) "); printf(" "); printf(" 3.掃描算法(SCAN) "); printf(" "); printf(" 4.循環(huán)掃描算法(CSCAN) "); printf(" "); printf(" 5.N步掃描算法(N

15、StepScan) "); printf(" "); printf(" 6.各類算法的比擬 "); printf(" "); printf(" "); printf(" "); printf(" 請輸入你的選擇的算法(輸入0離開) "); printf(" "); scanf("%d",&n); if(n=0) exit(0); printf(" "); switch(n) case 1: SetD

16、I(DiscLine); /隨機生成磁道數(shù) FCFS(Hand,DiscLine); /先來先效勞算法(FCFS) break; case 2: SetDI(DiscLine); /隨機生成磁道數(shù) SSTF(Hand,DiscLine); /最短尋道時間優(yōu)先算法(SSTF) break; case 3: SetDI(DiscLine); /隨機生成磁道數(shù) SCAN(Hand,DiscLine,0,9); /掃描算法(SCAN) break; case 4: SetDI(DiscLine); /隨機生成磁道數(shù) CSCAN(Hand,DiscLine); /循環(huán)掃描算法(CSCAN) break;

17、 case 5: SetDI(DiscLine); /隨機生成磁道數(shù) N_Step_SCAN(Hand,DiscLine); /N步掃描算法(NStepScan) break; case 6: SetDI(DiscLine); /隨機生成磁道數(shù) FCFS(Hand,DiscLine); /先來先效勞算法(FCFS) SSTF(Hand,DiscLine); /最短尋道時間優(yōu)先算法(SSTF) SCAN(Hand,DiscLine,0,9); /掃描算法(SCAN) CSCAN(Hand,DiscLine); /循環(huán)掃描算法(CSCAN) N_Step_SCAN(Hand,DiscLine);

18、/N步掃描算法(NStepScan) PaiXu(); /尋道長度由低到高排序 printf(" + 尋道長度由低到高排序:"); for(i=0;i<5;i+) printf("%4d ",Besti0); break; printf(" + 是否繼續(xù)(按0完畢,按1繼續(xù))"); scanf("%5d",&Con); /數(shù)組Sour復(fù)制到數(shù)組Dist，復(fù)制到x個數(shù)void CopyL(int Sour,int Dist ,int x) int i; for(i=0;i<=x;i+) Disti

19、=Souri; /打印輸出數(shù)組Privoid Print(int Pri,int x) int i; for(i=0;i<=x;i+) printf("%5d",Prii); /隨機生成磁道數(shù)void SetDI(int DiscL) int i; for(i=0;i<=9;i+) DiscLi=rand()%Limit;/隨機生成10個磁道號 printf("+ 需要尋找的磁道號:"); Print(DiscL,9); /輸出隨機生成的磁道號 printf(" ");/數(shù)組Sour把x位置的數(shù)刪除，并把y前面的數(shù)向前移動

20、，y后的數(shù)保持不變(即會出現(xiàn)2個y) void DelInq(int Sour,int x,int y) int i; for(i=x;i<y;i+) Souri=Souri+1; x+; /先來先效勞算法(FCFS)void FCFS(int Han,int DiscL) int RLine10; /將隨機生成的磁道數(shù)數(shù)組Discl復(fù)制給數(shù)組RLine int i,k,All,Temp; /Temp是計算移動的磁道距離的臨時變量 All=0; /統(tǒng)計全部的磁道數(shù)變量 k=9; /限定10個的磁道數(shù) CopyL(DiscL,RLine,9); /復(fù)制磁道號到臨時數(shù)組RLine print

21、f(" + 按照FCFS算法磁道的訪問順序為:"); All=Han-RLine0; for(i=0;i<=9;i+) Temp=RLine0-RLine1;/求出移動磁道數(shù),前一個磁道數(shù)減去后一個磁道數(shù)得出臨時的移動距離 if(Temp<0) Temp=(-Temp);/移動磁道數(shù)為負(fù)數(shù)時,算出相反數(shù)作為移動磁道數(shù) printf("%5d",RLine0); All=Temp+All;/求全部磁道數(shù)的總和 DelInq(RLine,0,k);/每個磁道數(shù)向前移動一位 k-; BestJage1=All;/Best1存放移動磁道數(shù) BestJ

22、age0=1; /Best0存放算法的序號為:1 Jage+;/排序的序號加1 Aver=(float) All)/10;/求平均尋道次數(shù) printf(" + 移動磁道數(shù):<%5d> ",All); printf(" + 平均尋道長度:*%0.2f* ",Aver);/最短尋道時間優(yōu)先算法(SSTF)void SSTF(int Han,int DiscL) int i,j,k,h,All; int Temp; /Temp是計算移動的磁道距離的臨時變量 int RLine10; /將隨機生成的磁道數(shù)數(shù)組Discl復(fù)制給數(shù)組RLine int

23、Min; All=0; /統(tǒng)計全部的磁道數(shù)變量 k=9; /限定10個的磁道數(shù) CopyL(DiscL,RLine,9); /復(fù)制磁道號到臨時數(shù)組RLine printf(" + 按照SSTF算法磁道的訪問順序為:"); for(i=0;i<=9;i+) Min=64000; for(j=0;j<=k;j+) /內(nèi)循環(huán)尋找與當(dāng)前磁道號最短尋道的時間的磁道號 if(RLinej>Han) /如果第一個隨機生成的磁道號大于當(dāng)前的磁道號，執(zhí)行下一句 Temp=RLinej-Han; /求出臨時的移動距離 else Temp=Han-RLinej; /求出臨時的移

24、動距離 if(Temp<Min) /如果每求出一次的移動距離小于Min，執(zhí)行下一句 Min=Temp; /Temp臨時值賦予Min h=j; /把最近當(dāng)前磁道號的數(shù)組下標(biāo)賦予h All=All+Min; /統(tǒng)計一共移動的距離 printf("%5d",RLineh); Han=RLineh; DelInq(RLine,h,k); /每個磁道數(shù)向前移動一位 k-; BestJage1=All;/Best1存放移動磁道數(shù) BestJage0=2;/Best0存放算法的序號為:2 Jage+;/排序序號加1 Aver=(float)All)/10;/求平均尋道次數(shù) prin

25、tf(" + 移動磁道數(shù):<%5d> ",All); printf(" + 平均尋道長度:*%0.2f* ",Aver);/掃描算法(SCAN)int SCAN(int Han,int DiscL,int x,int y) int j,n,k,h,m,All; int t=0; int Temp; int Min; int RLine10; /將隨機生成的磁道數(shù)數(shù)組Discl復(fù)制給數(shù)組RLine int Order; Order=1; k=y; m=2; /控制while語句的執(zhí)行，即是一定要使當(dāng)前磁道向內(nèi)向外都要掃描到 All=0; /統(tǒng)計

26、全部的磁道數(shù)變量 CopyL(DiscL,RLine,9); /復(fù)制磁道號到臨時數(shù)組RLine printf(" + 按照SCAN算法磁道的訪問順序為:"); Min=64000; for(j=x;j<=y;j+) /尋找與當(dāng)前磁道號最短尋道的時間的磁道號 if(RLinej>Han) /如果第一個隨機生成的磁道號大于當(dāng)前的磁道號，執(zhí)行下一句 Temp=RLinej-Han; /求出臨時的移動距離 else Temp=Han-RLinej; /求出臨時的移動距離 if(Temp<Min) Min=Temp; /Temp臨時值賦予Min h=j; /把最近當(dāng)

27、前磁道號的數(shù)組下標(biāo)賦予h All=All+Min; printf("%5d",RLineh); if(RLineh>=Han) /判斷磁道的移動方向，即是由里向外還是由外向里 Order=0; t=1; Han=RLineh; DelInq(RLine,h,k); /每個磁道數(shù)向前移動一位 k-; while(m>0) if(Order=1) /order是判斷磁盤掃描的方向標(biāo)簽，order是1的話，磁道向內(nèi)移動 for(j=x;j<=y;j+) h=-1; Min=64000; for(n=x;n<=k;n+) /判斷離當(dāng)前磁道最近的磁道號 if(

28、RLinen<=Han) Temp=Han-RLinen; if(Temp<Min) Min=Temp; /Temp臨時值賦予Min h=n; /把最近當(dāng)前磁道號的數(shù)組下標(biāo)賦予h if(h!=-1) All=All+Min; /疊加移動距離 printf("%5d",RLineh); Han=RLineh; /最近的磁道號作為當(dāng)前磁道 DelInq(RLine,h,k); k-; Order=0; /當(dāng)完成向內(nèi)的移動，order賦予0，執(zhí)行else語句，使磁道向外移動 m-; /向內(nèi)完成一次，m減一次，保證while循環(huán)執(zhí)行兩次 else /order是0的話，

29、磁道向外移動 for(j=x;j<=y;j+) h=-1; Min=64000; for(n=x;n<=k;n+) /判斷離當(dāng)前磁道最近的磁道號 if(RLinen>=Han) Temp=RLinen-Han; if(Temp<Min) Min=Temp; /Temp臨時值賦予Min h=n; /把最近當(dāng)前磁道號的數(shù)組下標(biāo)賦予h if(h!=-1) All=All+Min; /疊加移動距離 printf("%5d",RLineh); Han=RLineh; /最近的磁道號作為當(dāng)前磁道 DelInq(RLine,h,k); k-; Order=1; /

30、當(dāng)完成向內(nèi)的移動，order賦予0，執(zhí)行else語句，使磁道向外移動 m-; /向內(nèi)完成一次，m減一次，保證while循環(huán)執(zhí)行兩次 NAll=NAll+All; if(y-x)>5) BestJage1=All;/Best1存放移動磁道數(shù) BestJage0=3;/Best0存放算法的序號為:3 Jage+;/排序序號加1 Aver=(float)All)/10;/求平均尋道次數(shù) printf(" + 移動磁道數(shù):<%5d> ",All); printf(" + 平均尋道長度:*%0.2f* ",Aver); if(t=1) print

31、f(" + 磁道由內(nèi)向外移動"); else printf(" + 磁道由外向內(nèi)移動"); return(Han);/循環(huán)掃描算法(CSCAN)void CSCAN(int Han,int DiscL) int j,h,n,Temp,m,k,All,Last,i; int RLine10; /將隨機生成的磁道數(shù)數(shù)組Discl復(fù)制給數(shù)組RLine int Min; int tmp=0; m=2; k=9; All=0; /統(tǒng)計全部的磁道數(shù)變量 Last=Han; CopyL(DiscL,RLine,9); /復(fù)制磁道號到臨時數(shù)組RLine printf(&

32、quot; + 按照CSCAN算法磁道的訪問順序為:"); while(k>=0) for(j=0;j<=9;j+) /從當(dāng)前磁道號開場，由內(nèi)向外搜索離當(dāng)前磁道最近的磁道號 h=-1; Min=64000; for(n=0;n<=k;n+) if(RLinen>=Han) Temp=RLinen-Han; if(Temp<Min) Min=Temp; h=n; if(h!=-1) All=All+Min; /統(tǒng)計一共移動的距離 printf("%5d",RLineh); Han=RLineh; Last=RLineh; DelInq(RLine,h,k); k-; if(k>=0) tmp=RLine0; for(i=0;i<k;i+)/算出剩下磁道號的最小值 if(tmp>RLinei) tmp=RLinei; Han=tmp;/把最小的磁道號賦給Han Temp=Last-tmp;/求出最大磁道號和最小磁道號的距離差 All=All+Temp; Best