移臂調(diào)度算法

1、移臂調(diào)度算法一、實(shí)驗(yàn)?zāi)康淖鳛椴僮飨到y(tǒng)的輔助存儲(chǔ)器，用來存放文件的磁盤是一類高速大容量旋轉(zhuǎn)型存儲(chǔ)設(shè)備，在繁重的I/O設(shè)備負(fù)載下，同時(shí)會(huì)有若干傳輸請(qǐng)求來到并等待處理，系統(tǒng)必須采用一種調(diào)度策略，能夠按最佳次序執(zhí)行要求訪問的諸多請(qǐng)求，這叫做驅(qū)動(dòng)調(diào)度，所使用的算法叫做驅(qū)動(dòng)調(diào)度算法。驅(qū)動(dòng)調(diào)度算法能減少為若干I/O請(qǐng)求服務(wù)所需消耗的總時(shí)間，從而提高系統(tǒng)效率。對(duì)于磁盤設(shè)備，在啟動(dòng)之前按驅(qū)動(dòng)調(diào)度策略對(duì)訪問的請(qǐng)求優(yōu)化其排序十分必要。除了使旋轉(zhuǎn)圈數(shù)達(dá)到最少的調(diào)度策略外，還應(yīng)考慮使移動(dòng)臂的移動(dòng)時(shí)間最短的調(diào)度策略。二、實(shí)驗(yàn)要求書寫實(shí)驗(yàn)報(bào)告，應(yīng)該包括以下幾項(xiàng)內(nèi)容:(1) 實(shí)驗(yàn)題目；(2) 程序中使用的數(shù)據(jù)結(jié)構(gòu)及主要符號(hào)說

2、明；(3) 程序流程圖和帶有注釋的源程序；(4) 執(zhí)行程序名，并打印程序運(yùn)行時(shí)的初值和運(yùn)行結(jié)果；(5) 通過實(shí)驗(yàn)后的收獲與體會(huì)及對(duì)實(shí)驗(yàn)的改進(jìn)意見和見解。三、程序及主要符號(hào)說明(1)先來先服務(wù)(FCFS) 這是一種簡(jiǎn)單的磁盤調(diào)度算法。它根據(jù)進(jìn)程請(qǐng)求訪問磁盤的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點(diǎn)是公平、簡(jiǎn)單，且每個(gè)進(jìn)程的請(qǐng)求都能依次得到處理，不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長(zhǎng)期得不到滿足的情況。但此算法由于未對(duì)尋道進(jìn)行優(yōu)化，致使平均尋道時(shí)間可能較長(zhǎng)。(2)最短尋道時(shí)間優(yōu)先(SSTF) 該算法選擇這樣的進(jìn)程，其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短，但這種調(diào)度算法卻不能保證平均尋道時(shí)間最

3、短。(3)掃描算法(SCAN) SCAN算法不僅考慮到欲訪問的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動(dòng)方向。例如，當(dāng)磁頭正在自里向外移動(dòng)時(shí),SCAN算法所選擇的下一個(gè)訪問對(duì)象應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動(dòng)。這時(shí)，同樣也是每次選擇這樣的進(jìn)程來調(diào)度，即其要訪問的磁道，在當(dāng)前磁道之內(nèi)，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動(dòng)的規(guī)律頗似電梯的運(yùn)行，故又稱為電梯調(diào)度算法。四、實(shí)驗(yàn)結(jié)果1、先來先服務(wù)調(diào)度(FCFS)2、最短尋道時(shí)間優(yōu)先調(diào)度(SSTF)3、掃描調(diào)度算法(SCAN)五、實(shí)驗(yàn)體會(huì)通過這

4、次的實(shí)驗(yàn)，更加深入的了解了移臂調(diào)度算法的具體過程，運(yùn)用起來也更加熟練，將課堂上的理論知識(shí)得到更好的體現(xiàn)。平時(shí)課堂上有些概念理解不清楚，導(dǎo)致在做實(shí)驗(yàn)時(shí)有點(diǎn)茫然，不知從何下手。 因?yàn)橹R(shí)掌握的不夠好，在本次實(shí)驗(yàn)中出現(xiàn)了很多問題，不過通過看書和同學(xué)的幫助也得以解決。在本次實(shí)驗(yàn)中，我收獲了很多，做出實(shí)驗(yàn)時(shí)有種前所未有的成就感。附錄:實(shí)驗(yàn)源程序#include <iostream> using namespace std; void CopyL(int Sour,int Dist ,int x); /數(shù)組Sour復(fù)制到數(shù)組Dist，復(fù)制到x個(gè)數(shù)void SetDI(int DiscL); /

5、隨機(jī)生成磁道數(shù)void Print(int Pri,int x); /打印輸出數(shù)組Pri void DelInq(int Sour,int x,int y); /數(shù)組Sour把x位置的數(shù)刪除，并把y前面的數(shù)向前移動(dòng)，y后的數(shù)保持不變(即會(huì)出現(xiàn)2個(gè)y) void FCFS(int Han,int DiscL); /先來先服務(wù)算法(FCFS) void SSTF(int Han,int DiscL); /最短尋道時(shí)間優(yōu)先算法(SSTF)int SCAN(int Han,int DiscL,int x,int y); /掃描算法(SCAN)void CSCAN(int Han,int DiscL);

6、 /循環(huán)掃描算法(CSCAN) void PaiXu(); /尋道長(zhǎng)度由低到高排序void Pri(); int NAll=0; int Best52; /用作尋道長(zhǎng)度由低到高排序時(shí)存放的數(shù)組int Limit=0; /輸入尋找的范圍磁道數(shù)i int Jage; float Aver=0; int main() int i; int DiscLine10; /聲明準(zhǔn)備要生成的隨機(jī)磁道號(hào)的數(shù)組int Hand; /磁道數(shù)int Con=1; int n; while(Con=1) Jage=0; cout<< “請(qǐng)輸入初始的磁道數(shù):" int Hand; cout<&

7、lt; 輸入尋找的范圍:" int Limit; if(Limit>65536) cout<<"超出磁道范圍!" elsecout<<"1.先來先服務(wù)算法(FCFS )n" cout<<"2.最短尋道時(shí)間優(yōu)先算法(SSTF)n" cout<<"3.掃描算法(SCAN) n" int n;if(n=0) exit(0); cout<<"n" switch(n) case 1: SetDI(DiscLine); /隨機(jī)生成磁

8、道數(shù)FCFS(Hand,DiscLine); /先來先服務(wù)算法(FCFS) break; case 2: SetDI(DiscLine); /隨機(jī)生成磁道數(shù)SSTF(Hand,DiscLine); /最短尋道時(shí)間優(yōu)先算法(SSTF) break; case 3: SetDI(DiscLine); /隨機(jī)生成磁道數(shù)SCAN(Hand,DiscLine,0,9); /掃描算法(SCAN) break; SetDI(DiscLine); /隨機(jī)生成磁道數(shù)FCFS(Hand,DiscLine); /先來先服務(wù)算法(FCFS) SSTF(Hand,DiscLine); /最短尋道時(shí)間優(yōu)先算法(SSTF)

9、 SCAN(Hand,DiscLine,0,9); /掃描算法(SCAN) cout<< “是否繼續(xù)(按0結(jié)束,按1繼續(xù))?" scanf("%5d",&Con); /數(shù)組Sour復(fù)制到數(shù)組Dist，復(fù)制到x個(gè)數(shù)void CopyL(int Sour,int Dist ,int x) int i; for(i=0;i<=x;i+) Disti=Souri; /打印輸出數(shù)組Pri void Print(int Pri,int x) int i; for(i=0;i<=x;i+) printf("%5d",Prii)

10、; /隨機(jī)生成磁道數(shù)void SetDI(int DiscL) int i;for(i=0;i<=9;i+) DiscLi=rand()%Limit;/隨機(jī)生成10個(gè)磁道號(hào) cout<<" 需要尋找的磁道號(hào):" Print(DiscL,9); /輸出隨機(jī)生成的磁道號(hào)cout<<"n" /數(shù)組Sour把x位置的數(shù)刪除，并把y前面的數(shù)向前移動(dòng)，y后的數(shù)保持不變(即會(huì)出現(xiàn)2個(gè)y) void DelInq(int Sour,int x,int y) int i; for(i=x;i<y;i+) Souri=Souri+1; x

11、+; /先來先服務(wù)算法(FCFS) void FCFS(int Han,int DiscL) int RLine10; /將隨機(jī)生成的磁道數(shù)數(shù)組Discl復(fù)制給數(shù)組RLine int i,k,All,Temp; /Temp是計(jì)算移動(dòng)的磁道距離的臨時(shí)變量All=0; /統(tǒng)計(jì)全部的磁道數(shù)變量k=9; /限定10個(gè)的磁道數(shù)CopyL(DiscL,RLine,9); /復(fù)制磁道號(hào)到臨時(shí)數(shù)組RLine cout<<"FCFS訪問順序?yàn)?" All=Han-RLine0; for(i=0;i<=9;i+) Temp=RLine0-RLine1;/求出移動(dòng)磁道數(shù)前一個(gè)磁

12、道數(shù)減去后一個(gè)磁道數(shù)得出臨時(shí)的移動(dòng)距離if(Temp<0) Temp=(-Temp);/移動(dòng)磁道數(shù)為負(fù)數(shù)時(shí)算出相反數(shù)作為移動(dòng)磁道數(shù)printf("%5d",RLine0); All=Temp+All;/求全部磁道數(shù)的總和DelInq(RLine,0,k);/每個(gè)磁道數(shù)向前移動(dòng)一位k-; BestJage1=All;/Best1存放移動(dòng)磁道數(shù)BestJage0=1; /Best0存放算法的序號(hào)為:1 Jage+;/排序的序號(hào)加1 Aver=(float) All)/10;/求平均尋道次數(shù)cout<<" 移動(dòng)磁道數(shù): "<<Al

13、l; cout<<" 平均尋道長(zhǎng)度:*%0.2f* "<<Aver; /最短尋道時(shí)間優(yōu)先算法(SSTF) void SSTF(int Han,int DiscL) int i,j,k,h,All; int Temp; /Temp是計(jì)算移動(dòng)的磁道距離的臨時(shí)變量int RLine10; /將隨機(jī)生成的磁道數(shù)數(shù)組Discl復(fù)制給數(shù)組RLine int Min; All=0; /統(tǒng)計(jì)全部的磁道數(shù)變量k=9; /限定10個(gè)的磁道數(shù)CopyL(DiscL,RLine,9); /復(fù)制磁道號(hào)到臨時(shí)數(shù)組RLine cout<<" SSTF訪問順序

14、為:" for(i=0;i<=9;i+) Min=64000; for(j=0;j<=k;j+) /內(nèi)循環(huán)尋找與當(dāng)前磁道號(hào)最短尋道的時(shí)間的磁道號(hào) if(RLinej>Han) /如果第一個(gè)隨機(jī)生成的磁道號(hào)大于當(dāng)前的磁道號(hào)，執(zhí)行下一句Temp=RLinej-Han; /求出臨時(shí)的移動(dòng)距離else Temp=Han-RLinej; /求出臨時(shí)的移動(dòng)距離if(Temp<Min) /如果每求出一次的移動(dòng)距離小于Min，執(zhí)行下一句 Min=Temp; /Temp臨時(shí)值賦予Min h=j; /把最近當(dāng)前磁道號(hào)的數(shù)組下標(biāo)賦予h All=All+Min; /統(tǒng)計(jì)一共移動(dòng)的距離

15、printf("%5d",RLineh); Han=RLineh; DelInq(RLine,h,k); /每個(gè)磁道數(shù)向前移動(dòng)一位k-; BestJage1=All;/Best1存放移動(dòng)磁道數(shù)BestJage0=2;/Best0存放算法的序號(hào)為:2 Jage+;/排序序號(hào)加1 Aver=(float)All)/10;/求平均尋道次數(shù)printf("n+ 移動(dòng)磁道數(shù):<%5d> ",All); printf("n+ 平均尋道長(zhǎng)度:*%0.2f* ",Aver); /掃描算法(SCAN) int SCAN(int Han,in

16、t DiscL,int x,int y) int j,n,k,h,m,All; int t=0; int Temp; int Min; int RLine10; /將隨機(jī)生成的磁道數(shù)數(shù)組Discl復(fù)制給數(shù)組RLine int Order; Order=1; k=y; m=2; /控制while語句的執(zhí)行，即是一定要使當(dāng)前磁道向內(nèi)向外都要掃描到All=0; /統(tǒng)計(jì)全部的磁道數(shù)變量CopyL(DiscL,RLine,9);/復(fù)制磁道號(hào)到臨時(shí)數(shù)組RLine cout<<"SCAN訪問順序?yàn)?" Min=64000; for(j=x;j<=y;j+) /尋找與當(dāng)前

17、磁道號(hào)最短尋道的時(shí)間的磁道號(hào) if(RLinej>Han)/如果第一個(gè)隨機(jī)生成的磁道號(hào)大于當(dāng)前的磁道號(hào),執(zhí)行下一句Temp=RLinej-Han; /求出臨時(shí)的移動(dòng)距離else Temp=Han-RLinej; /求出臨時(shí)的移動(dòng)距離if(Temp<Min) Min=Temp; /Temp臨時(shí)值賦予Min h=j; /把最近當(dāng)前磁道號(hào)的數(shù)組下標(biāo)賦予h All=All+Min; printf("%5d",RLineh); if(RLineh>=Han) /判動(dòng)方向，即是由里向外還是由外向里斷磁道的移Order=0; t=1; Han=RLineh; DelIn

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