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

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