操作系统磁盘调度算法课程设计报告及代码

淮阴工学院操作系统课程设计报告选题名称:磁盘调度算法的模拟实现系（院）:经济管理学院专业:信息管理与信息系统班级:姓名:学号:指导教师:学年学期:2014~2015学年第1学期2014年12月21日《操作系统课程设计报告——磁盘调度算法的模拟实现》设计任务书课题名称磁盘调度算法的模拟实现设计目的1.调研并熟悉磁盘调度的基本概念、排序算法与工作规程；2.学习VisualC++中的图形化界面设计技术；3.通过实际编程加深对基础知识的理解，提高实践能力；4.学习开发资料的收集与整理，学会撰写课程设计报告。实验环境1.微型电子计算机（PC）；2.安装Windows2000以上操作系统，VisualC++6.0开发工具。任务要求1.利用课余时间去图书馆或上网查阅课题相关资料，深入理解课题含义及设计要求，注意材料收集与整理；2.在第15周末之前完成预设计，并请指导教师审查，通过后方可进行下一步工作；3.本课题主要实现能用各种排序算法实现对数据的排序，排序后显示排序结果。4.结束后，及时提交设计报告（含纸质稿、电子稿），要求格式规范、内容完整、结论正确，正文字数不少于3000字（不含代码）。工作进度计划序号起止日期工作内容12014.12.15~2014.12.16在预设计的基础上，进一步查阅资料，完善设计方案，形成书面材料。22014.12.17~2014.12.18设计总体方案，构建、绘制流程框图，编写代码，上机调试。32014.12.18~2014.12.19测试程序，优化代码，增强功能，撰写设计报告。42014.12.20~2014.12.21提交软件代码、设计报告，参加答辩，根据教师反馈意见，修改、完善设计报告。指导教师（签章）：年月日《操作系统课程设计报告——磁盘调度算法的模拟实现》摘要：磁盘是外设中一个很常用的部分，所以，对磁盘数据的寻道时间的长短可以直接影响机器的整体运行速度的快慢。本设计为一个模拟磁盘调度算法的磁盘调度模拟系统，能够模拟先来先服务（FCFS）算法、最短寻道时间（SSTF）算法、电梯（SCAN）算法、环形扫描（C_SCAN）算法及N_SCAN算法五个磁盘调度算法，输入为一组作业的磁道请求，输出为按选择的算法执行时的磁头移动轨迹。其中，先来先服务（FCFS）算法、最短寻道时间（SSTF）算法、电梯（SCAN）算法为基本算法，环形扫描（C_SCAN）算法及N_SCAN算法为扩展算法。关键字：磁盘调度；模拟；算法；选择；执行；《操作系统课程设计报告——磁盘调度算法的模拟实现》目录1磁盘调度算法的基本概念................................................................................12主要算法分析...................................................................................................22.1先来先服务算法（FCFS）..................................................................................22.2最短寻道时间优先算法（SSTF）......................................................................22.3扫描算法（SCAN）............................................................................................23各算法的流程图...............................................................................................34调试分析及测试结果.....................................................................................54.1运行结果.............................................................................................................54.2程序代码............................................................................................................7总结.................................................................................................................12致谢.................................................................................................................13参考文献.............................................................................................................14《操作系统课程设计报告——磁盘调度算法的模拟实现》11磁盘调度算法的基本概念设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+……+Mi+……+MN）/N其中Mi为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。延迟时间——指定扇区旋转到磁头下所需的时间。传送时间——由磁头进程读写完成信息传送的时间。其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱面上。所以各磁盘的编号按柱面顺序，每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘是，应采用一种最佳调度算法，以使各种进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标，是使磁盘的平均寻道时间最少。目前常用的磁盘帝调度算法有：先来先服务、最短寻道时间优先及扫描等算法。《操作系统课程设计报告——磁盘调度算法的模拟实现》22主要算法分析2.1先来先服务算法（FCFS）先来先服务（FCFS）调度:按先来后到次序服务，未作优化。最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在50号柱面上执行输出操作，而等待访问者依次要访问的柱面为130、199、32、159、15、148、61、99，那么，当50号柱面上的操作结束后，移动臂将按请求的先后次序先移到130号柱面，最后到达99号柱面。采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。2.2最短寻道时间优先算法（SSTF）最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。现在仍利用同一个例子来讨论，现在当50号柱面的操作结束后，应该先处理61号柱面的请求，然后到达32号柱面执行操作，随后处理15号柱面请求，后继操作的次序应该是99、130、148、159、199。采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了200多个柱面的距离，与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（SSTF）调度，FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。2.3扫描算法（SCAN）SCAN算法又称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。《操作系统课程设计报告——磁盘调度算法的模拟实现》3“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8层带到15层，然后电梯换成下行方向，把乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。3各算法的流程图1.先来先服务算法模块图3.1先来先服务算法流程图《操作系统课程设计报告——磁盘调度算法的模拟实现》42.最短寻道时间优先算法模块图3.2最短寻道时间优先算法流程图开始结束《操作系统课程设计报告——磁盘调度算法的模拟实现》53.扫描算法模块图3.3扫描算法流程图4调试分析及测试结果4.1运行结果结束开始输出磁盘调度序列《操作系统课程设计报告——磁盘调度算法的模拟实现》61.开始界面图4.1开始界面2.运行先来先服务（FCFS）算法调度后程序结果如下：图4.2FCFS运行结果3.运行最短寻道时间优先（SSTF）算法调度程序结果如下：图4.3SSTF运行结果《操作系统课程设计报告——磁盘调度算法的模拟实现》74.运行扫描（SCAN）算法调度程序结果如下：图4.4SCAN向磁道号增加方向移动图4.5SCAN向磁道号减小放向移动4.2程序代码1.先来先服务算法voidFCFS(intarray[],intm)//先来先服务算法{intj,i,now;floatsum=0,avg;cout输入当前的磁道号：;//输入当前磁道号cinnow;sum=abs(now-array[0]);cout先来先服务算法(FCFS)调度后的序列为array[0];//输出磁盘调度序列for(i=0,j=1;jm;i++,j++){sum=sum+abs(array[j]-array[i]);coutarray[j];//输出磁盘调度序列}《操作系统课程设计报告——磁