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

操作系统课程设计报告磁盘调度算法的模拟实现淮阴工学院操作系统课程设计报告选题名称: 磁盘调度算法的模拟实现 系（院）: 经济管理学院 专 业: 信息管理与信息系统 班 级: 姓 名: 学 号: 指导教师: 学年学期: 2014 2015 学年 第 1 学期2014年 12 月 21 日设计任务书课题名称磁盘调度算法的模拟实现设计目的1. 调研并熟悉磁盘调度的基本概念、排序算法与工作规程；2. 学习Visual C+中的图形化界面设计技术；3. 通过实际编程加深对基础知识的理解，提高实践能力；4. 学习开发资料的收集与整理，学会撰写课程设计报告。实验环境1. 微型电子计算机（PC）；2. 安装Windows 2000以上操作系统，Visual C+6.0开发工具。任务要求1. 利用课余时间去图书馆或上网查阅课题相关资料，深入理解课题含义及设计要求，注意材料收集与整理；2. 在第15周末之前完成预设计，并请指导教师审查，通过后方可进行下一步工作；3. 本课题主要实现能用各种排序算法实现对数据的排序，排序后显示排序结果。4. 结束后，及时提交设计报告（含纸质稿、电子稿），要求格式规范、内容完整、结论正确，正文字数不少于3000字（不含代码）。工作进度计划序号起止日期工 作 内 容12014.12.152014.12.16在预设计的基础上，进一步查阅资料，完善设计方案，形成书面材料。22014.12.172014.12.18设计总体方案，构建、绘制流程框图，编写代码，上机调试。32014.12.182014.12.19测试程序，优化代码，增强功能，撰写设计报告。42014.12.202014.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参考文献141 磁盘调度算法的基本概念设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+Mi+MN）/N其中Mi为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：寻找时间磁头在移动臂带动下移动到指定柱面所花的时间。延迟时间指定扇区旋转到磁头下所需的时间。传送时间由磁头进程读写完成信息传送的时间。其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱面上。所以各磁盘的编号按柱面顺序，每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘是，应采用一种最佳调度算法，以使各种进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标，是使磁盘的平均寻道时间最少。目前常用的磁盘帝调度算法有：先来先服务、最短寻道时间优先及扫描等算法。2 主要算法分析 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算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8层带到15层，然后电梯换成下行方向，把乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。3 各算法的流程图1. 先来先服务算法模块图3.1 先来先服务算法流程图2. 最短寻道时间优先算法模块开始结束图3.2 最短寻道时间优先算法流程图3. 扫描算法模块开始输出磁盘调度序列结束图3.3 扫描算法流程图4 调试分析及测试结果4.1 运行结果1. 开始界面图4.1 开始界面2. 运行先来先服务（FCFS）算法调度后程序结果如下：图4.2 FCFS运行结果3. 运行最短寻道时间优先（SSTF）算法调度程序结果如下：图4.3 SSTF运行结果4. 运行扫描（SCAN）算法调度程序结果如下：图4.4 SCAN向磁道号增加方向移动图4.5 SCAN向磁道号减小放向移动4.2 程序代码1. 先来先服务算法void FCFS(int array,int m)/ 先来先服务算法 int j,i,now; float sum = 0,avg; coutnow; sum=abs(now-array0); cout先来先服务算法(FCFS)调度后的序列为array0 ;/输出磁盘调度序列 for(i=0,j=1;jm;i+,j+) sum=sum+abs(arrayj-arrayi); coutarrayj ; /输出磁盘调度序列 avg=sum/(m); coutendl平均寻道长度：avgendl;/输出平均寻道长度2. 最短寻道时间优先算法void SSTF(int array,int m)/ 最短寻道时间优先算法 int temp; int k=1; int now,l,r; int i,j; float sum=0,avg=0; for(i=0;im;i+) for(j=i+1;jarrayj) /将磁道号从小到大排序 temp=arrayi; arrayi=arrayj; arrayj=temp; coutnow; cout最短寻道时间优先算法(SSTF)调度后的序列为;/输出磁盘调度序列 if(arraym-1=0;i-) coutarrayi=now) /若被访问的下一最小的磁道号不小于当前的磁道号 for(i=0;im;i+) coutarrayi ;/输出磁盘调度序列 sum=arrayi-now; now=arrayi; else /当前的磁道号的值在若所有被访问的下的磁道号之间 while(arrayknow) /确定当前磁道在已排的序列中的位置 k+; l=k-1; r=k; if(now-arrayl)=0) /先向磁道号减小方向访问 coutarrayl ; /输出磁盘调度序列 sum=sum+now-arrayl; now=arrayl; l=l-1; now=array0; for(j=r;jm;j+) /再向磁道号增加方向访问 coutarrayj ; /输出磁盘调度序列 sum+=arrayj-now; now=arrayj; else /先向磁道号增加方向访问 while(rm) coutarrayr=0;j-) /再向磁道号减小方向访问 coutarrayj ; /输出磁盘调度序列 sum+=now-arrayj; now=arrayj; avg=sum/(m); coutendl平均寻道长度：avgendl;/输出平均寻道长度3. 扫描算法void SCAN(int array,int m) /扫描算法 int temp; int k=1; int now,d,l,r; int i,j; float sum=0,avg=0; for(i=0;im;i+) for(j=i+1;jarrayj) /将磁道号从小到大排序 temp=arrayi; arrayi=arrayj; arrayj=temp; coutnow; coutd; /先要给出当前磁道号和移动臂的移动方向 cout扫描算法(SCAN)调度后的序列为; if(arraym-1=0;i-) coutarrayi=now) /若被访问的下一最小的磁道号不小于当前的磁道号 for(i=0;im;i+) coutarrayi ; /输出磁盘调度序列 sum=arrayi-now; now=arrayi; else /当前的磁道号的值在若所有被访问的下的磁道号之间 while(arrayk=0) coutarrayl ; /输出磁盘调度序列 sum=sum+now-arrayl; now=arrayl; l=l-1; now=array0; for(j=r;jm;j+) coutarrayj ; /输出磁盘调度序列 sum+=arrayj-now; now=arrayj; break; case 1: /先向磁道号增加方向访问 while(rm) coutarrayr=0;j-) coutarrayj ; /输出磁盘调度序列 sum+=now-arrayj; now=arrayj; break; default: cout输入有误endl; avg=sum/(m); coutendl平均寻道长度：avgendl;/输出平均寻道长度总 结通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学好不仅仅是要把书上的基本知识学好而且还要不断进行实践，将所学的跟实践操作结合起来才能更好地巩固所学，才能提高自己实践能力。通过这次的设计使我认识到只停留在表面理解问题是很难使问题得到很好的解决的，实践能力与理论知识同样重要。可以说此课程设计的理论难度并不大，各种流图设计特别是算法过程图的设计很容易忽略操作性细节，在实际调试中带来很大麻烦，需要特别注意，但是若要深入发掘其中的东西，并且实际去编程实现，就遇到了相当大的难度。因为与之涉及的很多方面并没有学过，需要自己去自学和实践检验。通过模拟磁盘调度及进程排队算法来加深对操作系统中各个磁臂调度算法概念的理解模拟磁盘调度算法，实现各种不同调度算法的过程，并计算各算法的平均寻道长度，以便于我们判断各种算法的优劣以及各种算法使用的场合。致 谢这次课程设计让我受益匪浅，我不仅加深了对操作系统的了解，进一步熟悉了C语言编程和Microsoft Visual C+ 6.0的使用，更加了解了很多之前在课本中和课程学习中并不了解和知道的知识，扩展了视野，丰富了体验。非常感谢在课程设计中殷路和高尚兵两位老师不厌其烦的讲解指导，同时我还要感谢同学们的热心帮助。参考文献1. 汤子瀛，哲凤屏，汤小丹. 计算机操作系统.西安电子科技大学出版社, 2005;2. 周敏，杨武，杨承玉. 计算机操作系统原理实验指导基于LINUX（Ver 3.0）.重庆工学院，2006;3. 谭浩强编著. C语言程序设计（第3版）.清华大学出版社，2005;4. 周湘贞，曾宪权.操作系统原理与实践教程.清华出版社; 5. 陈家骏.程序设计基础教程.机械工业出版社.附录：#include#include#include void FCFS(int array,int m)/ 先来先服务算法 int j,i,now; float sum = 0,avg; coutnow; sum=abs(now-array0); cout先来先服务算法(FCFS)调度后的序列为array0 ;/输出磁盘调度序列 for(i=0,j=1;jm;i+,j+) sum=sum+abs(arrayj-arrayi); coutarrayj ; /输出磁盘调度序列 avg=sum/(m); coutendl平均寻道长度：avgendl;/输出平均寻道长度/void SSTF(int array,int m)/ 最短寻道时间优先算法 int temp; int k=1; int now,l,r; int i,j; float sum=0,avg=0; for(i=0;im;i+) for(j=i+1;jarrayj) /将磁道号从小到大排序 temp=arrayi; arrayi=arrayj; arrayj=temp; coutnow; cout最短寻道时间优先算法(SSTF)调度后的序列为;/输出磁盘调度序列 if(arraym-1=0;i-) coutarrayi=now) /若被访问的下一最小的磁道号不小于当前的磁道号 for(i=0;im;i+) coutarrayi ;/输出磁盘调度序列 sum=arrayi-now; now=arrayi; else /当前的磁道号的值在若所有被访问的下的磁道号之间 while(arrayknow) /确定当前磁道在已排的序列中的位置 k+; l=k-1; r=k; if(now-arrayl)=0) /先向磁道号减小方向访问 coutarrayl ; /输出磁盘调度序列 sum=sum+now-arrayl; now=arrayl; l=l-1; now=array0; for(j=r;jm;j+) /再向磁道号增加方向访问 coutarrayj ; /输出磁盘调度序列 sum+=arrayj-now; now=arrayj; else /先向磁道号增加方向访问 while(rm) coutarrayr=0;j-) /再向磁道号减小方向访问 coutarrayj ; /输出磁盘调度序列 sum+=now-arrayj; now=arrayj; avg=sum/(m); coutendl平均寻道长度：avgendl;/输出平均寻道长度/void SCAN(int array,int m) /扫描算法 int temp; int k=1; int now,d,l,r; int i,j; float sum=0,avg=0; for(i=0;im;i+) for(j=i+1;jarrayj) /将磁道号从小到大排序 temp=arrayi; arrayi=arrayj; arrayj=temp; coutnow; coutd; /先要给出当前磁道号和移动臂的移动方向 cout扫描算法(SCAN)调度后的序列为; if(arraym-1=0;i-) coutarrayi=now) /若被访问的下一最小的磁道号不小于当前的磁道号 for(i=0;im;i+) coutarrayi ; /输出磁盘调度序列 sum=arrayi-now; now=arrayi; else /当前的磁道号的值在若所有被访问的下的磁道号之间