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

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算法的总体思想 queuen 为请求调度序列，diskrode为磁盘磁道数，headstarts为正在调度的磁道先来先服务算法 （fcfs）按queuen数组的顺序进行磁盘调度，将前一个调度磁道与下一个调度磁道的差值累加起来，得到总的寻道长度，再除以n得到平均寻道长度。最短寻道时间优先算法（sstf）将queuen进行由小到大的排序，首先定位当前调度磁headstarts在queuen的位置，通过循环语句找出离起始磁头最短的位置。扫描算法（scan）将queuen进行由小到大的排序，首先定位当前调度磁headstarts在queuen的位置，然后在此位置按给定的方向遍历queuen，当道端点（queue0或queuen-1）时，再在定位处反向遍历到另一端。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁道差值的累加，当到达端点且queuen未全调度时，总寻道长度加上端点值再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。循环扫描算法（cscan）将queuen进行由小到大的排序，首先定位当前调度磁headstarts在queuen的位置，然后在此位置按给定的方向遍历queuen，当道端点（queue0或queuen-1）时，反向到另一端点再以此方向进行遍历，直到queuen中所有都调度完。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁道差值的累加，当到达端点且queuen未全调度时，总寻道长度加上端点值再加上磁盘磁道总长度，再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。5、源代码：#include#include#includevoid menu() cout*菜单*endl; cout*1、先来先服务算法（fcfs) *endl; cout*2、最短寻道时间优先算法(sstf) *endl; cout*3、扫描算法 (scan) *endl; cout*4、循环扫描算法 (cscan) *endl; cout*5、退出 *endl; cout*endl;/*=初始化序列=*/void init(int queue,int queue_copy,int n) int i; for(i=0;in;+i) queuei=queue_copyi;/对当前正在执行的磁道号进行定位，返回磁道号小于当前磁道中最大的一个int fix ( int queue, int n, int headstarts)int i =0;while ( iqueuei )i+;if ( in-1 )return n-1; /当前磁道号大于磁盘请求序列中的所有磁道if ( i=0 )return -1; /当前磁道号小于磁盘请求序列中的所有磁道else return i-1; /返回小于当前磁道号中最大的一个/*=使用冒泡算法从小到大排序=*/int *bubble(int queue,int m)int i,j;int temp;for( i=0; im;i+) for(j=i+1;j queuej)temp=queuei;queuei=queuej;queuej=temp;cout排序后的磁盘序列为：;for( i=0;im;i+) /输出排序结果coutqueuei ;coutendl;return queue;/* =以下是fcfs算法=*/void fcfs(int queue,int n,int diskrode,int headstarts) /queue是请求调度序列，n为其个数，diskroad为磁盘磁道数，headstarts为正在调度的磁道 cout*以下为fcfs调度算法*queue0) count +=headstarts-queue0; else count+=queue0-headstarts; cout调度序列为: ; coutheadstarts ; for(i=0;in-1;+i) coutqueueiqueuei+1) count +=queuei-queuei+1; else count +=queuei+1-queuei; coutqueuei; coutendl; cout总的寻道长度为: countendl; cout平均寻道长度为: float(count)/float(n)endl;/*=sstf算法=*/void sstf( int queue, int n, int diskrode, int headstarts) int k=1;int l,r;int i,j,count=0;queue =bubble(queue,n); cout*以下为sstf调度算法*endl;if ( queuen-1 =headstarts) /若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务cout磁盘扫描序列为： ;coutheadstarts=0;i-) coutqueuei=headstarts) /若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务cout磁盘扫描序列为： ;coutheadstarts ;for(i=0;in;i+)coutqueuei queue0 & headstarts queuen-1) /若当前磁道号大于请求序列中最小者且小于最大者 cout磁盘扫描序列为：; coutheadstarts; while ( queuek =0) & ( rn) /当前磁道在请求序列范围内 if ( (headstarts-queuel) (queue -headstarts) coutqueuel ; count +=headstarts-queuel; headstarts =queuel; l=l-1; else if ( (headstarts-queuel) =(queue-headstarts) coutqueuel ; count +=headstarts-queuel; headstarts =queuel; l =l-1; else coutqueue ; count+=queue-headstarts;headstarts =queue;r =r+1; if ( l=-1) /磁头移动到序列的最小号，返回外侧扫描仍未扫描的磁道 for ( j=r;jn;j+) coutqueuej=0;j-) coutqueuej ; count +=queuen-1-queue0; coutendl; cout总的寻道长度为: countendl; cout平均寻道长度为： (float)(count)/(float)(n)endl;/*=以下是scan算法=*/void scan( int queue, int n, int diskrode, int headstarts )int direction, i, fixi;cout*以下是scan调度算法*endl;cout请输入磁头的走向：1.由内向外 2.由外向内endl;coutdirection;double count=0;*bubble(queue,n);fixi = fix(queue,n,headstarts);coutfixiendl;cout调度序列为: headstarts ;if ( fixi =-1) / headstarts比请求调度序列都小if ( direction =1) /从大到小for ( i=0;in;i+)coutqueuei ;count +=queuei-headstarts;headstarts =queuei;if ( direction =2) /从小到大for (i=0; in; i+)coutqueuei=0;i-)coutqueuei=0;i-) /从大到小coutqueuei-1;i-)coutqueuei ;count +=headstarts-queuei; headstarts =queuei;count +=queuefixi+1-queue0; /磁头走到0再反向走headstarts =queuefixi+1;coutheadstarts ;for ( i =fixi+2;in;i+)coutqueuei ;count +=queuei-headstarts;headstarts =queuei;if (direction =2) /从小到大for ( i=fixi+1;in;i+)coutqueuei ;count +=queuei-headstarts;headstarts =queuei;headstarts =queuefixi;count +=queuen-1-queuefixi; /磁头走到n-1再反向走coutheadstarts-1;i-) /从大到小coutqueuei ;count +=headstarts-queuei;headstarts =queuei;coutendl;cout总的寻道长度为： countendl;cout平均寻道长度为: float(count)/nendl; /*=以下是cscan算法=*/void cscan(int queue,int n,int diskrode,int headstarts)int direction,i,fixi;cout*以下是cscan调度算法*endl;cout请输入磁头的走向：1.由内向外 2.由外向内endl;coutdirection;int count=0; /count表示磁道移动的长度*bubble(queue,n);fixi=fix(queue,n,headstarts);cout调度序列为: headstarts ;if(fixi=-1) /headstarts比请求调度序列都小if(direction=1) /从大到小 count +=queuefixi+1-queue0; /反向再反向headstarts =queuen-1; coutheadstarts-1;-i)coutqueuei ;count +=headstarts-queuei;headstarts=queuei;if(direction=2) /从小到大for(i=0;in;+i)coutqueuei-1;-i)coutqueuei ;count +=headstarts-queuei;headstarts=queuei;if( direction=2) /从小到大coutqueue0 ;for(i=1;in;+i)coutqueuei-1;i-)coutqueuei ;count +=headstarts-queuei;headstarts=queuei;count +=queuen-1-queue0; /磁头走到0时再反向.headstarts=queuen-1;coutheadstartsfixi;i-)coutqueuei ;count +=headstarts-queuei;headstarts =queuei;if(direction=2) /从小到大for( i=fixi+1;in;i+) if (direction=2) /从小到大 coutqueuei ; count +=queuei-headstarts; headstarts =queuei; count +=queuen-1-queue0; /磁头走到n-1再反向走.headstarts =queue0;coutheadstarts ;for(i=1;ifixi+1;i+)coutqueuei ;count +=queuei-headstarts;headstarts=queuei;coutendl;cout总的寻道长度为: countendl;cout平均寻道长度为: float(count)/nendl;void main()int n, i, diskrode, headstarts; /n表示调度磁盘请求序列queue的长度，diskrode表示磁盘磁道的个数，headstarts表示目前正在调度的磁道；cout请输入磁盘的总磁道数: diskrode;cout请输入磁盘调度请求序列个数:n;int *queue