磁盘调度算法的实现

姓名学号专业班级实验项目实验三：磁盘调度算法的实现课程名称操作系统课程代码实验时间2011年11月06日2011年11月09日2011年12月13日2011年12月16日实验地点软件实验室7-215批改意见成绩教师签字：【实验环境】Windows操作系统环境下的个人微机【实验目的】了解操作系统磁盘调度的基本概念，磁盘调度程序的功能，常用的磁盘调度算法。【实验要求】学生应正确地设计有关的数据结构与各个功能模块，画出程序的流程图，编写程序，程序执行结果应正确。【实验内容】本实验是模拟操作系统的磁盘寻道方式，运用磁盘访问顺序的不同来设计磁盘的调度算法。实现的磁盘调度算法有FCFS，SSTF，SCAN，CSCAN和NStepSCAN算法。设定开始磁道号寻道范围，依据起始扫描磁道号和最大磁道号数，随机产生要进行寻道的磁道号序列。选择磁盘调度算法，显示该算法的磁道访问顺序，计算出移动的磁道总数和平均寻道总数。按算法的寻道效率进行排序，并对各算法的性能进行分析比较。【实验原理】FCFS这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。SSTF该算法选择这样的进程：其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。SCAN该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动。CSCANCSCAN算法规定磁头单向移动，例如，只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问的磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。NStepSCANN步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列。【实验步骤、过程】1、程序主要流程(1)手动输入当前的磁道号,该磁道号在0<n<65536以内(65536是2的16次方),超出范围则需重新输入。(2)手动输入要寻找磁道的范围。(3)主菜单,选择要进行磁道调度算法,此时会随机生成一个在第二步生成磁道范围以内的10个磁道数,由SetDI方法生成,再将生成的随机磁道号以数组形式作为参数被某个算法调用。2、程序部分代码函数声明及数据定义#include"stdio.h"#include"stdlib.h"#include"iostream.h"voidCopyL(intSour[],intDist[],intx);//数组Sour复制到数组Dist，复制到x个数voidSetDI(intDiscL[]);//随机生成磁道数voidPrint(intPri[],intx);//打印输出数组PrivoidDelInq(intSour[],intx,inty);//数组Sour把x位置的数删除，并把y前面的数向前移动，y后的数保持不变(即会出现2个y)voidFCFS(intHan,intDiscL[]);//先来先服务算法(FCFS)voidSSTF(intHan,intDiscL[]);//最短寻道时间优先算法(SSTF)intSCAN(intHan,intDiscL[],intx,inty);//扫描算法(SCAN)voidFCFS(intHan,intDiscL[]);//先来先服务算法(FCFS)voidSSTF(intHan,intDiscL[]);//最短寻道时间优先算法(SSTF)intSCAN(intHan,intDiscL[],intx,inty);//扫描算法(SCAN)voidCSCAN(intHan,intDiscL[]);//循环扫描算法(CSCAN)voidN_Step_SCAN(intHan1,intDiscL[]);//N步扫描算法(NStepScan)voidPaiXu();//寻道长度由低到高排序voidPri();intNAll=0;intBest[5][2];//用作寻道长度由低到高排序时存放的数组intLimit=0;//输入寻找的范围磁道数iintJage;floatAver=0;随机生成磁道数//随机生成磁道数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];//将随机生成的磁道数数组Discl[]复制给数组RLine[] inti,k,All,Temp;//Temp是计算移动的磁道距离的临时变量 All=0;//统计全部的磁道数变量 k=9;//限定10个的磁道数 CopyL(DiscL,RLine,9);//复制磁道号到临时数组RLine printf("\n按照FCFS算法磁道的访问顺序为:"); All=Han-RLine[0]; for(i=0;i<=9;i++) { Temp=RLine[0]-RLine[1];//求出移动磁道数,前一个磁道数减去后一个磁道数得出临时的移动距离 if(Temp<0)Temp=(-Temp);//移动磁道数为负数时,算出相反数作为移动磁道数 printf("%5d",RLine[0]);All=Temp+All;//求全部磁道数的总和 DelInq(RLine,0,k);//每个磁道数向前移动一位 k--; } Best[Jage][1]=All;//Best[][1]存放移动磁道数 Best[Jage][0]=1;//Best[][0]存放算法的序号为:1 Jage++;//排序的序号加1 Aver=((float)All)/10;//求平均寻道次数 printf("\n移动磁道数:<%5d>",All); printf("\n平均寻道长度:*%0.2f*",Aver);}SSTF//最短寻道时间优先算法(SSTF)voidSSTF(intHan,intDiscL[]){ inti,j,k,h,All; intTemp;//Temp是计算移动的磁道距离的临时变量 intRLine[10];//将随机生成的磁道数数组Discl[]复制给数组RLine[] intMin; All=0;//统计全部的磁道数变量 k=9;//限定10个的磁道数 CopyL(DiscL,RLine,9);//复制磁道号到临时数组RLine printf("\n按照SSTF算法磁道的访问顺序为:"); for(i=0;i<=9;i++) { Min=64000; for(j=0;j<=k;j++)//内循环寻找与当前磁道号最短寻道的时间的磁道号 { if(RLine[j]>Han)//如果第一个随机生成的磁道号大于当前的磁道号，执行下一句 Temp=RLine[j]-Han;//求出临时的移动距离 else Temp=Han-RLine[j];//求出临时的移动距离 if(Temp<Min)//如果每求出一次的移动距离小于Min，执行下一句 { Min=Temp;//Temp临时值赋予Min h=j;//把最近当前磁道号的数组下标赋予h } } All=All+Min;//统计一共移动的距离 printf("%5d",RLine[h]); Han=RLine[h]; DelInq(RLine,h,k);//每个磁道数向前移动一位 k--; } Best[Jage][1]=All;//Best[][1]存放移动磁道数 Best[Jage][0]=2;//Best[][0]存放算法的序号为:2 Jage++;//排序序号加1 Aver=((float)All)/10;//求平均寻道次数 printf("\n移动磁道数:<%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];//将随机生成的磁道数数组Discl[]复制给数组RLine[] intOrder; Order=1; k=y; m=2;//控制while语句的执行，即是一定要使当前磁道向内向外都要扫描到 All=0;//统计全部的磁道数变量 CopyL(DiscL,RLine,9);//复制磁道号到临时数组RLine printf("\n按照SCAN算法磁道的访问顺序为:"); Min=64000; for(j=x;j<=y;j++)//寻找与当前磁道号最短寻道的时间的磁道号 { if(RLine[j]>Han)//如果第一个随机生成的磁道号大于当前的磁道号，执行下一句 Temp=RLine[j]-Han;//求出临时的移动距离 else Temp=Han-RLine[j];//求出临时的移动距离 if(Temp<Min) { Min=Temp;//Temp临时值赋予Min h=j;//把最近当前磁道号的数组下标赋予h } } All=All+Min; printf("%5d",RLine[h]); if(RLine[h]>=Han) {//判断磁道的移动方向，即是由里向外还是由外向里 Order=0; t=1; } Han=RLine[h]; DelInq(RLine,h,k);//每个磁道数向前移动一位 k--; while(m>0) { if(Order==1)//order是判断磁盘扫描的方向标签，order是1的话，磁道向内移动 { 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;//把最近当前磁道号的数组下标赋予h } } } if(h!=-1) { All=All+Min;//叠加移动距离 printf("%5d",RLine[h]); Han=RLine[h];//最近的磁道号作为当前磁道 DelInq(RLine,h,k); k--; } } Order=0;//当完成向内的移动，order赋予0，执行else语句，使磁道向外移动 m--;//向内完成一次，m减一次，保证while循环执行两次 } 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;//把最近当前磁道号的数组下标赋予h } } } if(h!=-1) { All=All+Min;//叠加移动距离 printf("%5d",RLine[h]); Han=RLine[h];//最近的磁道号作为当前磁道 DelInq(RLine,h,k); k--; } } Order=1;//当完成向外的移动，order赋予1，执行else语句，使磁道向内移动 m--;//向内完成一次，m减一次，保证while循环执行两次 } } NAll=NAll+All; if((y-x)>5) { Best[Jage][1]=All;//Best[][1]存放移动磁道数 Best[Jage][0]=3;//Best[][0]存放算法的序号为:3 Jage++;//排序序号加1 Aver=((float)All)/10;//求平均寻道次数 printf("\n移动磁道数:<%5d>",All); printf("\n平均寻道长度:*%0.2f*",Aver); } if(t==1) printf("\n磁道由内向外移动"); else printf("\n磁道由外向内移动"); return(Han);}CSCAN//循环扫描算法(CSCAN)voidCSCAN(intHan,intDiscL[]){ intj,h,n,Temp,m,k,All,Last,i; intRLine[10];//将随机生成的磁道数数组Discl[]复制给数组RLine[] intMin; inttmp=0;m=2;k=9;All=0;//统计全部的磁道数变量 Last=Han; CopyL(DiscL,RLine,9);//复制磁道号到临时数组RLine printf("\n按照CSCAN算法磁道的访问顺序为:"); while(k>=0) { for(j=0;j<=9;j++)//从当前磁道号开始，由内向外搜索离当前磁道最近的磁道号 { 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;//统计一共移动的距离 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]存放移动磁道数 Best[Jage][0]=4;//Best[][0]存放算法的序号为:4 Jage++;//排序序号加1 Aver=((float)All)/10;//求平均寻道次数 printf("\n移动磁道数:<%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个磁道数 i=-1; CopyL(DiscL,RLine1,9);//复制磁道号到临时数组RLine printf("\n按照N_Step_SCAN算法磁道的访问顺序为:"); for(m=0;m<2;m++)//由于限定10磁道数，将10个磁道数分为两组，每组5个磁道数，每个组按照SCAN算法执行，该循环循环2次 { Han1=SCAN(Han1,RLine1,i+1,i+5); i=i+5; } Best[Jage][1]=NAll;//Best[][1]存放移动磁道数 Best[Jage][0]=5;//Best[][0]存放算法的序号为:5 Aver=((float)NAll)/10;//求平均寻道次数 printf("\n移动磁道数:<%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])//如果前一个算法的移动磁道距离大于后一个移动磁道数，执行下面语句 { Temp=Best[j+1][1];//从这起下三行执行冒泡法将移动距离大小排序，排完后则执行每个算法的排序 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; } } }}主函数intmain(){ inti; intDiscLine[10];//声明准备要生成的随机磁道号的数组 intHand;//磁道数 intCon=1; intn; while(Con==1) { Jage=0; printf("\n请输入初始的磁道数(0<n<65536):"); scanf("%d",&Hand); printf("\n输入寻找的范围:"); scanf("%d",&Limit); if(Limit>65536) { printf("超出范围!"); } else{ printf("╭═══════════════╮\n"); printf("║操作系统课程设计║\n"); printf("╭═════┤磁盘调度算法├═════╮\n"); printf("║║║║\n"); printf("║╰═══════════════╯║\n"); printf("║1.先来先服务算法(FCFS)║\n"); printf("║║\n"); printf("║2.最短寻道时间优先算法(SSTF)║\n"); printf("║║\n"); printf("║3.扫描算法(SCAN)║\n"); printf("║║\n"); printf("║4.循环扫描算法(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);//随机生成磁道数