操作系统课程设计-磁盘调度算法

1.实验题目:磁盘调度算法。建立相应的数据结构；在屏幕上显示磁盘请求的服务状况；将一批磁盘请求的情况存磁盘文件，以后可以读出并重放；计算磁头移动的总距离及平均移动距离；支持算法：FIFO、SSTF、SCAN、CSCAN;2.设计目的:调度磁盘I/O请求服务，采用好的方式能提高访问时间和带宽。本实验通过编程对磁盘调度算法的实现，加深对算法的理解，同时通过用C++语言编写程序实现这些算法，并在windos平台上实现，更好的掌握操作系统的原理以及实现方法，提高综合运用专业课知识的能力。3.任务及要求3.1设计任务编程实现下述磁盘调度算法，并求出每种算法的平均寻道长度：1、先来先服务算法（FCFS）2、最短寻道时间算法（SSTF）3、扫描算法（SCAN）4、循环扫描算法（CSCAN）3.2设计要求对用户指定的磁盘调度请求序列，基于以上四种算法，实现各自的调度顺序并输出，同时计算出各种算法下的平均寻道长度。4.算法及数据结构4.1算法的总体思想queue[n]为请求调度序列，diskrode为磁盘磁道数，headstarts为正在调度的磁道①先来先服务算法（FCFS）按queue[n]数组的顺序进行磁盘调度，将前一个调度磁道与下一个调度磁道的差值累加起来，得到总的寻道长度，再除以n得到平均寻道长度。②最短寻道时间优先算法（SSTF）将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，通过循环语句找出离起始磁头最短的位置。③扫描算法（SCAN）将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，再在定位处反向遍历到另一端。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。④循环扫描算法（CSCAN）将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，反向到另一端点再以此方向进行遍历，直到queue[n]中所有都调度完。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上磁盘磁道总长度，再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。5、源代码：#includeiostream.h#includestdio.h#includestdlib.hvoidmenu(){cout*********************菜单*********************endl;cout******1、先来先服务算法（FCFS)**********endl;cout******2、最短寻道时间优先算法(SSTF)**********endl;cout******3、扫描算法(SCAN)**********endl;cout******4、循环扫描算法(CSCAN)**********endl;cout******5、退出**********endl;cout**********************************************endl;}/*======================初始化序列=======================*/voidinit(intqueue[],intqueue_copy[],intn){inti;for(i=0;in;++i)queue[i]=queue_copy[i];}//对当前正在执行的磁道号进行定位，返回磁道号小于当前磁道中最大的一个intfix(intqueue[],intn,intheadstarts){inti=0;while(in&&headstartsqueue[i]){i++;}if(in-1)returnn-1;//当前磁道号大于磁盘请求序列中的所有磁道if(i==0)return-1;//当前磁道号小于磁盘请求序列中的所有磁道elsereturni-1;//返回小于当前磁道号中最大的一个}/*=================使用冒泡算法从小到大排序==============*/int*bubble(intqueue[],intm){inti,j;inttemp;for(i=0;im;i++)for(j=i+1;jm;j++){if(queue[i]queue[j]){temp=queue[i];queue[i]=queue[j];queue[j]=temp;}}cout排序后的磁盘序列为：;for(i=0;im;i++)//输出排序结果{coutqueue[i];}coutendl;returnqueue;}/*====================以下是FCFS算法==================*/voidFCFS(intqueue[],intn,intdiskrode,intheadstarts)//queue是请求调度序列，n为其个数，diskroad为磁盘磁道数，headstarts为正在调度的磁道{cout************以下为FCFS调度算法***********endl;inti;intcount=0;if(headstartsqueue[0])count+=headstarts-queue[0];elsecount+=queue[0]-headstarts;cout调度序列为:;coutheadstarts;for(i=0;in-1;++i){coutqueue[i];if(queue[i]queue[i+1])count+=queue[i]-queue[i+1];elsecount+=queue[i+1]-queue[i];}coutqueue[i];coutendl;cout总的寻道长度为:countendl;cout平均寻道长度为:float(count)/float(n)endl;}/*=====================SSTF算法====================*/voidSSTF(intqueue[],intn,intdiskrode,intheadstarts){intk=1;intl,r;inti,j,count=0;queue=bubble(queue,n);cout************以下为SSTF调度算法***********endl;if(queue[n-1]=headstarts)//若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务{cout磁盘扫描序列为：;coutheadstarts;for(i=n-1;i=0;i--)coutqueue[i];count=headstarts-queue[0];}if(queue[0]=headstarts)//若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务{cout磁盘扫描序列为：;coutheadstarts;for(i=0;in;i++)coutqueue[i]endl;count=queue[n-1]-headstarts;}if(headstartsqueue[0]&&headstartsqueue[n-1])//若当前磁道号大于请求序列中最小者且小于最大者{cout磁盘扫描序列为：;coutheadstarts;while(queue[k]headstarts)//确定当前磁道在已排的序列中的位置{k++;}l=k-1;r=k;while((l=0)&&(rn))//当前磁道在请求序列范围内{if((headstarts-queue[l])(queue-headstarts)){coutqueue[l];count+=headstarts-queue[l];headstarts=queue[l];l=l-1;}elseif((headstarts-queue[l])==(queue-headstarts)){coutqueue[l];count+=headstarts-queue[l];headstarts=queue[l];l=l-1;}else{coutqueue;count+=queue-headstarts;headstarts=queue;r=r+1;}}if(l==-1)//磁头移动到序列的最小号，返回外侧扫描仍未扫描的磁道{for(j=r;jn;j++){coutqueue[j];}count+=queue[n-1]-queue[0];}else//磁头移动到序列的最大号，返回内侧扫描仍未扫描的磁道{for(j=l;j=0;j--){coutqueue[j];}count+=queue[n-1]-queue[0];}}coutendl;cout总的寻道长度为:countendl;cout平均寻道长度为：(float)(count)/(float)(n)endl;}/*======================以下是SCAN算法====================*/voidSCAN(intqueue[],intn,intdiskrode,intheadstarts){intdirection,i,fixi;cout***********以下是SCAN调度算法*************endl;cout请输入磁头的走向：1.由内向外2.由外向内endl;cout请输入磁头的走向:;cindirection;doublecount=0;*bubble(queue,n);fixi=fix(queue,n,headstarts);coutfixiendl;cout调度序列为:headstarts;if(fixi==-1)//headstarts比请求调度序列都小{if(direction==1)//从大到小{for(i=0;in;i++){coutqueue[i];count+=queue[i]-headstarts;headstarts=queue[i];}}if(direction==2)//从小到大{for(i=0;in;i++){coutqueue[i];count+=queue[i]-headstarts;headstarts=queue[i];}}}elseif(fixi==n-1)//headstarts比请求调度序列的都大{if(direction==1){for(i=n-1;i=0;i--){coutqueue[i];count+=headstarts-queue[i];headstarts=queue[i];}}if(direction==2)//从小到大{for(i=n-1;i=0;i--)//从大到小{coutqueue[i];count+=headstarts-queue[i];headstarts=queue[i];}}}else{if(direction==1)//从大到小{for(i=fixi;i-1;i--){coutqueue[i