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

课程设计课程名称操作系统题目名称磁盘调度算法学生学院计算机学院专业班级2010级计算机科学与技术四班学号3110006015学生姓名张法光指导教师______何翠红_________2013年1月13日操作系统课程设计任务书学生姓名张法光专业班级10计科4班学号3110006015题目磁盘调度算法1指导教师何翠红题目编号2012秋-16主要内容理解磁盘调度算法，并进一步加深对调度算法及其实现过程的理解。任务要求设计主界面以灵活选择某算法，且以下算法都要实现1、先来先服务算法（FCFS）2、最短寻道时间优先算法（SSTF）3、扫描算法（SCAN）4、循环扫描算法（CSCAN）并求出每种算法的平均寻道长度。参考文献[1]计算机操作系统，汤小丹等，西安电子科技大学出版社[2]操作系统实验指导书，傅秀芬，广东工业大学（自编）[3]计算机操作系统教程(第二版)，张尧学、史美林，清华大学出版社[4]现代操作系统，A.S.Tanenbaum著，陈向群等译机械工业出版社审查意见指导教师签字：系主任签字：年月日说明：本表由指导教师填写，由系主任审核后下达给选题学生，装订在设计（论文）首页目录一、设计思想说明..................................................71.1设计环境...................................................71.2设计思想...................................................7二、系统结构......................................................7三、数据结构的说明................................................7四、算法流程图....................................................81.先来先服务算法（FCFS）......................................92.最短寻道时间优先调度算法（SSTF）............................103.扫描算法（SCAN）............................................114.循环扫描算法（CSCAN）.......................................12五、主要函数列表..................................................12六、测试与分析....................................................13七、用户使用说明..................................................20八、心得体会......................................................20九、附录..........................................................20正文1设计思想说明1.1设计环境硬件环境：CPU(英特尔)Intel(R)Core(TM)i3-2310MCPU@2.10GHz(2100Mhz)内存4.00GB(1334MHz)硬盘5400转500G软件环境：Windows7SP1,VisualC++6.01.2设计思想1.先到先服务算法（FCFS）这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。2.最短寻道时间优先调度算法（SSTF）该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。3.扫描算法（SCAN）扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。4.循环扫描（CSACN）循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。2系统结构本系统划分为五个模块：1.冒泡排序算法模块：voidsort(intarray[],intm)2.先来先服务算法模块：voidFCFS(intarray[],intm)3.最短寻道时间优先算法模块：voidSSTF(intarray[],intm)4.扫描算法模块：voidSCAN(intarray[],intm)5.循环扫描算法模块：voidCSCAN(intarray[],intm)系统结构图：3数据结构的说明k:递增变量,为l,r赋值。now：用于记录当前磁道号l：用于记录k的左邻位置r:用于k的位置array[]:放置磁道号的数组;4算法流程图1.先来先服务算法（FCFS）流程图:2.最短寻道时间优先算法（SSTF）流程图:3.扫描算法（SCAN）流程图：求平均寻道长度选择与当前磁道距离最近的磁道进行扫描移动到最小（大）号，改向外（内）移动扫描未扫描的磁道输出移动的平均磁道数输出排好序的磁道序列判断当前磁头在序列中的位置结束开始读入磁道号使用冒泡法从小到大排序输入当前磁道号4..循环扫描算法（CSCAN）流程图：求平均寻道长度选择移动臂移动方向，开始扫描移动到最小（大）号，改向外（内）移动扫描未扫描的磁道输出移动的平均磁道数输出排好序的磁道序列开始结束输入磁道号使用冒泡法从小到大排序输入当前磁道号判断当前磁头在序列中的位置5主要函数列表函数原型功能入口、出口参数说明Voidsort(intarray[],intm)冒泡排序intarray[],intmvoidFCFS(intarray[],intm)先来先服务算法intarray[],intmvoidSSTF(intarray[],intm)最短寻道时间优先算法intarray[],intmvoidSCAN(intarray[],intm)扫描算法intarray[],intm求平均寻道长度选择与当前磁道距离最近的磁道进行扫描移动到最小（大）号，改向外（内）移动扫描未扫描的磁道输出移动的平均磁道数输出排好序的磁道序列判断当前磁头在序列中的位置结束开始输入磁道号使用冒泡法从小到大排序输入当前磁道号voidCSCAN(intarray[],intm)循环扫描算法intarray[],intmintmain系统界面6测试与分析首先从test.txt文本读取测试磁道号序列：905855393818150160184开始测试：1先来先服务算法2最短寻道时间优先算法（1）当前磁道号大于磁道序列中的最大的磁道号时（2）当前磁道号小于磁道序列中的最小的磁道号时（3）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号时3扫描算法（1）当前磁道号大于磁道序列中的最大的磁道号时（2）当前磁道号小于磁道序列中的最小的磁道号时（3）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号（磁头向外）时（4）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号（磁头向内）时4循环扫描算法（1）当前磁道号大于磁道序列中的最大的磁道号时（2）当前磁道号小于磁道序列中的最小的磁道号时（3）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号（磁头向外）时（4）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号（磁头向内）时关于测试结果的对比分析：移动的总道数平均寻道长度先来先服务算法23829最短寻道时间优先算法204221731924026扫描算法20422173192622923626循环扫描算法388431731930233330367用户使用说明用户使用时请注意：1、进入系统前，先到源程序目录下的text.txt设置好磁道号序列；2、系统输出你输入的磁道序列，用户核对输入数据；3、系统显示系统算法菜单；4、用户选择相应算法，回车；5、系统要求输入当前磁道号，用户输入磁道号，回车；6、系统输出磁头的扫描序列和平均寻道长度；7、用户继续选择系统菜单中的算法；8、当用户选择扫描算法时，需要输入当前移动臂的移动的方向，其中1表示向磁道号增加方向访问，0磁道号减小方向访问。8心得体会本次课程设计主要是理解四种磁盘调度的工作原理。在课程设计前的准备工作时，先划分好各功能模块，再逐步实现。先到先服务算法是最简单也是最基本的磁盘调度算法。最短寻道时间优先算法则是扫描算法和循环算法的基础，后者是继承与发展。起初做最短寻道时间优先算法，漏掉了当前磁道号大于数组边界的情况，通过画设计稿图，理清了思路后重新调试并最终实现了SSTF算法。SCAN和CSCAN算法主要在于对方向的把握，弄清楚移动方向就基本大功告成了。最后是主函数的调用，利用C语言的fopen函数来获取文本中的测试数据库。避免了手动输入的带来的不便性和输入错误。很高兴能在有限的时间内完成了磁盘调度算法系统课程设计和程序开发，今后将仍会继续努力学习操作系统，定期实践开发工作。9附录带注释的源程序。如果提交源程序软盘，可以只列出程序文件名清单。//源程序#includestdio.h#includestdlib.h#includemath.h#definemaxsize100//定义最大数组域//冒泡排序算法voidsort(intarray[],intm){inti,j;inttemp;for(i=0;im;i++)//磁道号排序{for(j=i+1;jm;j++)//对磁道号进行从小到大排列{if(array[i]array[j])//两磁道号之间比较{temp=array[i];array[i]=array[j];array[j]=temp;}}}for(i=0;im;i++)//输出排序后的磁道号数组{printf(%d,array[i]);}}//先来先服务调度算法（FCFS）voidFCFS(intarray[],intm){intsum=0,j,i;intavg;printf(\nFCFS调度结果:);for(i=0;im;i++)//输出FCFS磁盘调度结果{printf(%d,array[i]);}for(i=0,j=1;jm;i++,j++){sum+=abs(array[j]-array[i]);//总的移动距离，通过累加差值的绝对