移臂調度算法(共16頁)

1、精選優(yōu)質文檔-傾情為你奉上移臂調度算法一、實驗目的作為操作系統(tǒng)的輔助存儲器，用來存放文件的磁盤是一類高速大容量旋轉型存儲設備，在繁重的I/O設備負載下，同時會有若干傳輸請求來到并等待處理，系統(tǒng)必須采用一種調度策略，能夠按最佳次序執(zhí)行要求訪問的諸多請求，這叫做驅動調度，所使用的算法叫做驅動調度算法。驅動調度算法能減少為若干I/O請求服務所需消耗的總時間，從而提高系統(tǒng)效率。對于磁盤設備，在啟動之前按驅動調度策略對訪問的請求優(yōu)化其排序十分必要。除了使旋轉圈數(shù)達到最少的調度策略外，還應考慮使移動臂的移動時間最短的調度策略。二、實驗要求書寫實驗報告，應該包括以下幾項內(nèi)容:(1) 實驗題目；(2) 程序中

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

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

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

5、int DiscL); /隨機生成磁道數(shù)void Print(int Pri,int x); /打印輸出數(shù)組Pri void 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 Ha

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

7、nd; cout<< 輸入尋找的范圍:" int Limit; if(Limit>65536) cout<<"超出磁道范圍!" elsecout<<"1.先來先服務算法(FCFS )n" cout<<"2.最短尋道時間優(yōu)先算法(SSTF)n" cout<<"3.掃描算法(SCAN) n" int n;if(n=0) exit(0); cout<<"n" switch(n) case 1: SetDI(Disc

8、Line); /隨機生成磁道數(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; SetDI(DiscLine); /隨機生成磁道數(shù)FCFS(Hand,DiscLine); /先來先服務算法(FCFS) SSTF(Hand,DiscLine); /最短尋

9、道時間優(yōu)先算法(SSTF) SCAN(Hand,DiscLine,0,9); /掃描算法(SCAN) cout<< “是否繼續(xù)(按0結束,按1繼續(xù))?" scanf("%5d",&Con); /數(shù)組Sour復制到數(shù)組Dist，復制到x個數(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("%5

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

11、ri=Souri+1; x+; /先來先服務算法(FCFS) void FCFS(int Han,int DiscL) int RLine10; /將隨機生成的磁道數(shù)數(shù)組Discl復制給數(shù)組RLine int i,k,All,Temp; /Temp是計算移動的磁道距離的臨時變量All=0; /統(tǒng)計全部的磁道數(shù)變量k=9; /限定10個的磁道數(shù)CopyL(DiscL,RLine,9); /復制磁道號到臨時數(shù)組RLine cout<<"FCFS訪問順序為:" All=Han-RLine0; for(i=0;i<=9;i+) Temp=RLine0-RLine1

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

13、ot;<<All; cout<<" 平均尋道長度:*%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復制給數(shù)組RLine int Min; All=0; /統(tǒng)計全部的磁道數(shù)變量k=9; /限定10個的磁道數(shù)CopyL(DiscL,RLine,9); /復制磁道號到臨時數(shù)組RLine cout<<&q

14、uot; SSTF訪問順序為:" for(i=0;i<=9;i+) Min=64000; for(j=0;j<=k;j+) /內(nèi)循環(huán)尋找與當前磁道號最短尋道的時間的磁道號 if(RLinej>Han) /如果第一個隨機生成的磁道號大于當前的磁道號，執(zhí)行下一句Temp=RLinej-Han; /求出臨時的移動距離else Temp=Han-RLinej; /求出臨時的移動距離if(Temp<Min) /如果每求出一次的移動距離小于Min，執(zhí)行下一句 Min=Temp; /Temp臨時值賦予Min h=j; /把最近當前磁道號的數(shù)組下標賦予h All=All+Mi

15、n; /統(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ù)printf("n+ 移動磁道數(shù):<%5d> ",All); printf("n+ 平均尋道長度:*%0.2f* ",Aver); /掃描算法(SCAN) int SC

16、AN(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復制給數(shù)組RLine int Order; Order=1; k=y; m=2; /控制while語句的執(zhí)行，即是一定要使當前磁道向內(nèi)向外都要掃描到All=0; /統(tǒng)計全部的磁道數(shù)變量CopyL(DiscL,RLine,9);/復制磁道號到臨時數(shù)組RLine cout<<"SCAN訪問順序為:" Min=64000; for(j=x;j<

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

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