磁盤調(diào)度算法的實現(xiàn)

姓名學號專業(yè)班級實驗項目實驗三：磁盤調(diào)度算法的實現(xiàn)課程名稱操作系統(tǒng)課程代碼實驗時間2011年11月06日2011年11月09日2011年12月13日2011年12月16日實驗地點軟件實驗室7-215批改意見成績教師簽字：【實驗環(huán)境】Windows操作系統(tǒng)環(huán)境下的個人微機【實驗目的】了解操作系統(tǒng)磁盤調(diào)度的基本概念，磁盤調(diào)度程序的功能，常用的磁盤調(diào)度算法?！緦嶒炓蟆繉W生應正確地設計有關的數(shù)據(jù)結(jié)構(gòu)與各個功能模塊，畫出程序的流程圖，編寫程序，程序執(zhí)行結(jié)果應正確。【實驗內(nèi)容】本實驗是模擬操作系統(tǒng)的磁盤尋道方式，運用磁盤訪問順序的不同來設計磁盤的調(diào)度算法。實現(xiàn)的磁盤調(diào)度算法有FCFS，SSTF，SCAN，CSCAN和NStepSCAN算法。設定開始磁道號尋道范圍，依據(jù)起始掃描磁道號和最大磁道號數(shù)，隨機產(chǎn)生要進行尋道的磁道號序列。選擇磁盤調(diào)度算法，顯示該算法的磁道訪問順序，計算出移動的磁道總數(shù)和平均尋道總數(shù)。按算法的尋道效率進行排序，并對各算法的性能進行分析比較?！緦嶒炘怼縁CFS這是一種最簡單的磁盤調(diào)度算法。它根據(jù)進程請求訪問磁盤的先后次序進行調(diào)度。SSTF該算法選擇這樣的進程：其要求訪問的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短。SCAN該算法不僅考慮到欲訪問的磁道與當前磁道間的距離，更優(yōu)先考慮的是磁頭當前的移動方向。例如，當磁頭正在自里向外移動時，SCAN算法所考慮的下一個訪問對象，應是其欲訪問的磁道既在當前磁道之外，又是距離最近的。這樣自里向外地訪問，直至再無更外的磁道需要訪問時，才將磁臂換向為自外向里移動。CSCANCSCAN算法規(guī)定磁頭單向移動，例如，只是自里向外移動，當磁頭移到最外的磁道并訪問后，磁頭立即返回到最里的欲訪問的磁道，亦即將最小磁道號緊接著最大磁道號構(gòu)成循環(huán)，進行循環(huán)掃描。NStepSCANN步SCAN算法是將磁盤請求隊列分成若干個長度為N的子隊列，磁盤調(diào)度將按FCFS算法依次處理這些子隊列。而每處理一個隊列時又是按SCAN算法，對一個隊列處理完后，再處理其他隊列?！緦嶒灢襟E、過程】1、程序主要流程(1)手動輸入當前的磁道號,該磁道號在0<n<65536以內(nèi)(65536是2的16次方),超出范圍則需重新輸入。(2)手動輸入要尋找磁道的范圍。(3)主菜單,選擇要進行磁道調(diào)度算法,此時會隨機生成一個在第二步生成磁道范圍以內(nèi)的10個磁道數(shù),由SetDI方法生成,再將生成的隨機磁道號以數(shù)組形式作為參數(shù)被某個算法調(diào)用。2、程序部分代碼函數(shù)聲明及數(shù)據(jù)定義#include"stdio.h"#include"stdlib.h"#include"iostream.h"voidCopyL(intSour[],intDist[],intx);//數(shù)組Sour復制到數(shù)組Dist，復制到x個數(shù)voidSetDI(intDiscL[]);//隨機生成磁道數(shù)voidPrint(intPri[],intx);//打印輸出數(shù)組PrivoidDelInq(intSour[],intx,inty);//數(shù)組Sour把x位置的數(shù)刪除，并把y前面的數(shù)向前移動，y后的數(shù)保持不變(即會出現(xiàn)2個y)voidFCFS(intHan,intDiscL[]);//先來先服務算法(FCFS)voidSSTF(intHan,intDiscL[]);//最短尋道時間優(yōu)先算法(SSTF)intSCAN(intHan,intDiscL[],intx,inty);//掃描算法(SCAN)voidFCFS(intHan,intDiscL[]);//先來先服務算法(FCFS)voidSSTF(intHan,intDiscL[]);//最短尋道時間優(yōu)先算法(SSTF)intSCAN(intHan,intDiscL[],intx,inty);//掃描算法(SCAN)voidCSCAN(intHan,intDiscL[]);//循環(huán)掃描算法(CSCAN)voidN_Step_SCAN(intHan1,intDiscL[]);//N步掃描算法(NStepScan)voidPaiXu();//尋道長度由低到高排序voidPri();intNAll=0;intBest[5][2];//用作尋道長度由低到高排序時存放的數(shù)組intLimit=0;//輸入尋找的范圍磁道數(shù)iintJage;floatAver=0;隨機生成磁道數(shù)//隨機生成磁道數(shù)voidSetDI(intDiscL[]){ inti; for(i=0;i<=9;i++) { DiscL[i]=rand()%Limit;//隨機生成10個磁道號 } printf("\n需要尋找的磁道號:"); Print(DiscL,9); //輸出隨機生成的磁道號 printf("");}FCFS//先來先服務算法(FCFS)voidFCFS(intHan,intDiscL[]){ intRLine[10];//將隨機生成的磁道數(shù)數(shù)組Discl[]復制給數(shù)組RLine[] inti,k,All,Temp;//Temp是計算移動的磁道距離的臨時變量 All=0;//統(tǒng)計全部的磁道數(shù)變量 k=9;//限定10個的磁道數(shù) CopyL(DiscL,RLine,9);//復制磁道號到臨時數(shù)組RLine printf("\n按照FCFS算法磁道的訪問順序為:"); All=Han-RLine[0]; for(i=0;i<=9;i++) { Temp=RLine[0]-RLine[1];//求出移動磁道數(shù),前一個磁道數(shù)減去后一個磁道數(shù)得出臨時的移動距離 if(Temp<0)Temp=(-Temp);//移動磁道數(shù)為負數(shù)時,算出相反數(shù)作為移動磁道數(shù) printf("%5d",RLine[0]);All=Temp+All;//求全部磁道數(shù)的總和 DelInq(RLine,0,k);//每個磁道數(shù)向前移動一位 k--; } Best[Jage][1]=All;//Best[][1]存放移動磁道數(shù) Best[Jage][0]=1;//Best[][0]存放算法的序號為:1 Jage++;//排序的序號加1 Aver=((float)All)/10;//求平均尋道次數(shù) printf("\n移動磁道數(shù):<%5d>",All); printf("\n平均尋道長度:*%0.2f*",Aver);}SSTF//最短尋道時間優(yōu)先算法(SSTF)voidSSTF(intHan,intDiscL[]){ inti,j,k,h,All; intTemp;//Temp是計算移動的磁道距離的臨時變量 intRLine[10];//將隨機生成的磁道數(shù)數(shù)組Discl[]復制給數(shù)組RLine[] intMin; All=0;//統(tǒng)計全部的磁道數(shù)變量 k=9;//限定10個的磁道數(shù) CopyL(DiscL,RLine,9);//復制磁道號到臨時數(shù)組RLine printf("\n按照SSTF算法磁道的訪問順序為:"); for(i=0;i<=9;i++) { Min=64000; for(j=0;j<=k;j++)//內(nèi)循環(huán)尋找與當前磁道號最短尋道的時間的磁道號 { if(RLine[j]>Han)//如果第一個隨機生成的磁道號大于當前的磁道號，執(zhí)行下一句 Temp=RLine[j]-Han;//求出臨時的移動距離 else Temp=Han-RLine[j];//求出臨時的移動距離 if(Temp<Min)//如果每求出一次的移動距離小于Min，執(zhí)行下一句 { Min=Temp;//Temp臨時值賦予Min h=j;//把最近當前磁道號的數(shù)組下標賦予h } } All=All+Min;//統(tǒng)計一共移動的距離 printf("%5d",RLine[h]); Han=RLine[h]; DelInq(RLine,h,k);//每個磁道數(shù)向前移動一位 k--; } Best[Jage][1]=All;//Best[][1]存放移動磁道數(shù) Best[Jage][0]=2;//Best[][0]存放算法的序號為:2 Jage++;//排序序號加1 Aver=((float)All)/10;//求平均尋道次數(shù) printf("\n移動磁道數(shù):<%5d>",All); printf("\n平均尋道長度:*%0.2f*",Aver);}SCAN//掃描算法(SCAN)intSCAN(intHan,intDiscL[],intx,inty){ intj,n,k,h,m,All; intt=0; intTemp; intMin; intRLine[10];//將隨機生成的磁道數(shù)數(shù)組Discl[]復制給數(shù)組RLine[] intOrder; Order=1; k=y; m=2;//控制while語句的執(zhí)行，即是一定要使當前磁道向內(nèi)向外都要掃描到 All=0;//統(tǒng)計全部的磁道數(shù)變量 CopyL(DiscL,RLine,9);//復制磁道號到臨時數(shù)組RLine printf("\n按照SCAN算法磁道的訪問順序為:"); Min=64000; for(j=x;j<=y;j++)//尋找與當前磁道號最短尋道的時間的磁道號 { if(RLine[j]>Han)//如果第一個隨機生成的磁道號大于當前的磁道號，執(zhí)行下一句 Temp=RLine[j]-Han;//求出臨時的移動距離 else Temp=Han-RLine[j];//求出臨時的移動距離 if(Temp<Min) { Min=Temp;//Temp臨時值賦予Min h=j;//把最近當前磁道號的數(shù)組下標賦予h } } All=All+Min; printf("%5d",RLine[h]); if(RLine[h]>=Han) {//判斷磁道的移動方向，即是由里向外還是由外向里 Order=0; t=1; } Han=RLine[h]; 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(RLine[n]<=Han) { Temp=Han-RLine[n]; if(Temp<Min) { Min=Temp;//Temp臨時值賦予Min h=n;//把最近當前磁道號的數(shù)組下標賦予h } } } if(h!=-1) { All=All+Min;//疊加移動距離 printf("%5d",RLine[h]); Han=RLine[h];//最近的磁道號作為當前磁道 DelInq(RLine,h,k); k--; } } Order=0;//當完成向內(nèi)的移動，order賦予0，執(zhí)行else語句，使磁道向外移動 m--;//向內(nèi)完成一次，m減一次，保證while循環(huán)執(zhí)行兩次 } else//order是0的話，磁道向外移動 { for(j=x;j<=y;j++) { h=-1; Min=64000; for(n=x;n<=k;n++)//判斷離當前磁道最近的磁道號 { if(RLine[n]>=Han) { Temp=RLine[n]-Han; if(Temp<Min) { Min=Temp;//Temp臨時值賦予Min h=n;//把最近當前磁道號的數(shù)組下標賦予h } } } if(h!=-1) { All=All+Min;//疊加移動距離 printf("%5d",RLine[h]); Han=RLine[h];//最近的磁道號作為當前磁道 DelInq(RLine,h,k); k--; } } Order=1;//當完成向外的移動，order賦予1，執(zhí)行else語句，使磁道向內(nèi)移動 m--;//向內(nèi)完成一次，m減一次，保證while循環(huán)執(zhí)行兩次 } } NAll=NAll+All; if((y-x)>5) { Best[Jage][1]=All;//Best[][1]存放移動磁道數(shù) Best[Jage][0]=3;//Best[][0]存放算法的序號為:3 Jage++;//排序序號加1 Aver=((float)All)/10;//求平均尋道次數(shù) printf("\n移動磁道數(shù):<%5d>",All); printf("\n平均尋道長度:*%0.2f*",Aver); } if(t==1) printf("\n磁道由內(nèi)向外移動"); else printf("\n磁道由外向內(nèi)移動"); return(Han);}CSCAN//循環(huán)掃描算法(CSCAN)voidCSCAN(intHan,intDiscL[]){ intj,h,n,Temp,m,k,All,Last,i; intRLine[10];//將隨機生成的磁道數(shù)數(shù)組Discl[]復制給數(shù)組RLine[] intMin; inttmp=0;m=2;k=9;All=0;//統(tǒng)計全部的磁道數(shù)變量 Last=Han; CopyL(DiscL,RLine,9);//復制磁道號到臨時數(shù)組RLine printf("\n按照CSCAN算法磁道的訪問順序為:"); while(k>=0) { for(j=0;j<=9;j++)//從當前磁道號開始，由內(nèi)向外搜索離當前磁道最近的磁道號 { h=-1; Min=64000; for(n=0;n<=k;n++) { if(RLine[n]>=Han) { Temp=RLine[n]-Han; if(Temp<Min) { Min=Temp; h=n; } } } if(h!=-1) { All=All+Min;//統(tǒng)計一共移動的距離 printf("%5d",RLine[h]); Han=RLine[h]; Last=RLine[h]; DelInq(RLine,h,k); k--; } } if(k>=0) { tmp=RLine[0]; for(i=0;i<k;i++)//算出剩下磁道號的最小值 { if(tmp>RLine[i]) tmp=RLine[i]; } Han=tmp;//把最小的磁道號賦給Han Temp=Last-tmp;//求出最大磁道號和最小磁道號的距離差 All=All+Temp; } } Best[Jage][1]=All;//Best[][1]存放移動磁道數(shù) Best[Jage][0]=4;//Best[][0]存放算法的序號為:4 Jage++;//排序序號加1 Aver=((float)All)/10;//求平均尋道次數(shù) printf("\n移動磁道數(shù):<%5d>",All); printf("\n平均尋道長度:*%0.2f*",Aver);}NStepSCAN//N步掃描算法(NStepScan)voidN_Step_SCAN(intHan1,intDiscL[]){ inti,m,k; intRLine1[10]; NAll=0;m=2;k=9;//限定10個磁道數(shù) i=-1; CopyL(DiscL,RLine1,9);//復制磁道號到臨時數(shù)組RLine printf("\n按照N_Step_SCAN算法磁道的訪問順序為:"); for(m=0;m<2;m++)//由于限定10磁道數(shù)，將10個磁道數(shù)分為兩組，每組5個磁道數(shù)，每個組按照SCAN算法執(zhí)行，該循環(huán)循環(huán)2次 { Han1=SCAN(Han1,RLine1,i+1,i+5); i=i+5; } Best[Jage][1]=NAll;//Best[][1]存放移動磁道數(shù) Best[Jage][0]=5;//Best[][0]存放算法的序號為:5 Aver=((float)NAll)/10;//求平均尋道次數(shù) printf("\n移動磁道數(shù):<%5d>",NAll); printf("\n平均尋道長度:*%0.2f*",Aver);}按算法的尋道效率進行排序//尋道長度由低到高排序voidPaiXu(){ inti,j,Temp; for(i=0;i<5;i++) { for(j=0;j<4;j++) { if(Best[j][1]>Best[j+1][1])//如果前一個算法的移動磁道距離大于后一個移動磁道數(shù)，執(zhí)行下面語句 { Temp=Best[j+1][1];//從這起下三行執(zhí)行冒泡法將移動距離大小排序，排完后則執(zhí)行每個算法的排序 Best[j+1][1]=Best[j][1]; Best[j][1]=Temp; Temp=Best[j+1][0];//將每個算法的序號用冒泡法排序 Best[j+1][0]=Best[j][0]; Best[j][0]=Temp; } } }}主函數(shù)intmain(){ inti; intDiscLine[10];//聲明準備要生成的隨機磁道號的數(shù)組 intHand;//磁道數(shù) intCon=1; intn; while(Con==1) { Jage=0; printf("\n請輸入初始的磁道數(shù)(0<n<65536):"); scanf("%d",&Hand); printf("\n輸入尋找的范圍:"); scanf("%d",&Limit); if(Limit>65536) { printf("超出范圍!"); } else{ printf("╭═══════════════╮\n"); printf("║操作系統(tǒng)課程設計║\n"); printf("╭═════┤磁盤調(diào)度算法├═════╮\n"); printf("║║║║\n"); printf("║╰═══════════════╯║\n"); printf("║1.先來先服務算法(FCFS)║\n"); printf("║║\n"); printf("║2.最短尋道時間優(yōu)先算法(SSTF)║\n"); printf("║║\n"); printf("║3.掃描算法(SCAN)║\n"); printf("║║\n"); printf("║4.循環(huán)掃描算法(CSCAN)║\n"); printf("║║\n"); printf("║5.N步掃描算法(NStepScan)║\n"); printf("║║\n"); printf("║6.各類算法的比較║\n"); printf("║║\n"); printf("║║\n"); printf("║╭───────────────────────╮║\n"); printf("╰═┤請輸入你的選擇的算法(輸入0離開)├═╯\n"); printf("╰───────────────────────╯\n"); scanf("%d",&n); if(n==0) exit(0); printf(""); switch(n) { case1: SetDI(DiscLine);//隨機生成磁道數(shù)