操作系统实验磁盘调度扫描算法循环扫描算法

学号P1514032专业计算机科学与技术姓名实验日期2017.12.7教师签字成绩实验报告【实验名称】磁盘调度（二）【实验目的】磁盘调度中寻道时间直接影响到数据访问的快慢，处理好磁盘寻道时间是关键。分别采用扫描策略、循环扫描策略处理。【实验原理】1.扫描算法（SCAN算法）SCAN算法，也就是很形象的电梯调度算法。先按照一个方向(比如从外向内扫描)，扫描的过程中依次调度经过的磁道。当扫描到最里层的一个磁道时反向扫描直至所有磁道都被调度。2.循环扫描算法（CSCAN算法）CSCAN算法，循环扫描算法，它的思想是，访问完最里面一个要求服务的序列之后，从最外层的序号开始往里走。也就是始终保持一个方向，故称为循环扫描算法。【数据结构和符号说明】（1）数据结构和符号说明编译语言：C++数据结构：结构体数组符号定义：typedefstructTrack//磁道结构体{intid;//磁道序列intstate=0;//是否访问过，未被访问置状态为0}Track;Tracktrack[N];//最大磁道数为100Tracktrack1[N];//复制的磁道数组用于输出intstep[N];//移动距离intnum,i,current_track,num1;//当前磁道即部分中间变量函数说明：voidinit()//初始化程序voidinput()//输入函数voidsort1()//从小到大排序intabs(inta,intb)//相减的绝对值intfind_first_bignum()//寻找第一个最大值intfind_first_smallnum()//寻找第一个最小值voidSCAN(intup_or_down)//扫描算法voidCSCAN(intup_or_down)//循环扫描算法voidoutput(Tracka[])//输出函数voidoutput_average_track()//输出平均寻道时间intshow()//显示用户界面//返回值为输入的选择项流程图：SCAN算法：CSCAN算法（与SCAN算法基本类似）：代码：#includestdio.h#defineN100typedefstructTrack{intid;//磁道序列intstate=0;//是否访问过，未被访问置状态为0}Track;Tracktrack[N];//最大磁道数为100Tracktrack1[N];intstep[N];//移动距离intnum,i,current_track,num1;voidinit()//初始化程序{num=0;for(i=0;inum;i++){track[i].state=-1;//id置为1track1[i].state=-1;step[i]=-1;//移动距离为-1}}voidinput()//输入函数{printf(输入当前磁道\n);scanf(%d,¤t_track);num1=current_track;printf(输入要访问的磁道数目\n);scanf(%d,&num);printf(输入要访问磁道序列\n);for(i=0;inum;i++)scanf(%d,&track[i].id);}voidFCFS()//先来先服务{for(i=0;inum;i++){if((current_track-track[i].id)0)//求移动距离step[i]=track[i].id-current_track;elsestep[i]=current_track-track[i].id;//取绝对值track[i].state=1;//状态置为1current_track=track[i].id;//更新当前磁道}}intabs(inta,intb)//相减的绝对值{returna-b0?a-b:b-a;}intSerch_min_pos()//寻找到当前磁道最短的需求磁道{intmin=45536;//最小距离标志intpos;for(inti=0;inum;i++)if(track[i].state==1)continue;elseif(minabs(track[i].id,current_track))//寻找最小距离{min=abs(track[i].id,current_track);pos=i;}track[pos].state=1;returnpos;//返回在数组中的位置}voidSSTF()//最短寻道优先{for(i=0;inum;i++)//计数器{track1[i]=track[Serch_min_pos()];//更新到要输出的数组中step[i]=abs(track1[i].id,current_track);//移动距离current_track=track1[i].id;//标志}}voidoutput(Tracka[])//输出函数{printf(\n\n从%d号磁道开始\n,num1);printf(==================================================\n);//排班printf(被访问的下一个磁道\t\t移动距离（磁道数）\n);for(i=0;inum;i++)printf(\t%4d\t\t||\t%4d\n,a[i].id,step[i]);printf(==================================================\n);}voidoutput_average_track()//输出平均寻道时间{doublesum=0;//和for(i=0;inum;i++)sum+=step[i];printf(平均寻道长度%3.2f\n\n\n,sum/num);//输出}intshow()//显示用户界面{intchoose;//选择printf(\n******************早期的磁盘调度算法******************\n);printf(\t\t1、先来先服务(FCFS)\n);printf(\t\t2、最短寻道时间优先（SSTF)\n);printf(\t\t3、退出（EXIT）\n);scanf(%d,&choose);returnchoose;}intmain(){do{init();switch(show())//返回值是选择{case1://FCFSinput();FCFS();output(track);output_average_track();break;case2://最短寻道input();SSTF();output(track1);output_average_track();break;case3://退出return0;default:break;}}while(1);return0;}截图：主界面开始，输入选择先来先服务还是最短寻道优先，输入当前磁道，输入要访问的磁道，输入要访问的磁道序列。SCAN算法输入当前磁道100,9个磁道，分别为555839189016015038184，此时选择方向向上结果正确。输入当前磁道100,9个磁道，分别为555839189016015038184，此时选择方向向下结果正确。CSCAN算法输入当前磁道100,9个磁道，分别为555839189016015038184，此时选择方向向上结果正确。输入当前磁道100,9个磁道，分别为555839189016015038184，此时选择方向向上结果正确。【小结与讨论】1、扫描算法又称为电梯算法，其原理与电梯运行情况相似，即运行方向上的请求优先，若是访问方向向上，则先依次访问较大的磁道号至顶，再向下访问娇小的磁道号；若是访问方向向下，则先依次访问较小的磁道号至底，再向上访问娇大的磁道号。2、循环扫描算法又称为单向电梯算法，若是访问方向向上，则向上依次访问完较大的磁道号后，返回最低端，依次向上访问较小的磁道号；若是访问方向向下，则向下依次访问完较小的磁道号后，返回最顶端，依次向下访问较大的磁道号。3、此次实验我用两个数组分别存放了一个磁道表和复制的磁道表，根据两个算法的原理，只要将其进行排序，然后分别对两个数组进行正向和逆向的访问即可。4、具体实现时，我将两种算法的两种初始扫描方向写在了一个函数之中，调用时通过参数scan和参数up_or_down设置。并设置了寻找大于当前数组的最近最小值和最近的大值进行选择结果，这是因为初始磁道号将磁道数组分成上下（高低地址）两块，这两块根据不同的扫描方向重新选择高低地址，又结合不同的算法决定正序排列还是反序排列。实现起来还是比较简单的。5、由于CSCAN算法的思想是，访问完最里面一个要求服务的序列之后，从最外层的序号开始往里走。也就是始终保持一个方向。所以如果用循环队列实现，时间复杂度会更低，效率更高。6、此次实验虽然较为简单，但还是发现了自己知识点有些方面的不足，让我更好的了解了磁盘调度的原理，使我收获颇多。