可视化磁盘调度算法

目录TOC\o"1-5"\h\z第一章课程设计的目的与要求 1\o"CurrentDocument"1.1课程设计的目的 1\o"CurrentDocument"1.2课程设计的要求 1\o"CurrentDocument"第二章课程设计的任务内容 2\o"CurrentDocument"2.1课程设计的任务 2\o"CurrentDocument"2.2课程设计的内容 2\o"CurrentDocument"2.3课程设计的原理 2\o"CurrentDocument"第三章详细设计说明 3\o"CurrentDocument"3.1模块描述 3\o"CurrentDocument"3.2性能 3\o"CurrentDocument"3.3输入项 4\o"CurrentDocument"3.4输出项 4\o"CurrentDocument"3.5算法 5\o"CurrentDocument"3.6流程逻辑 6\o"CurrentDocument"3.7接口 9\o"CurrentDocument"3.8限制条件 9\o"CurrentDocument"第四章软件使用说明 10\o"CurrentDocument"第五章课程设计心得与体会 13\o"CurrentDocument"附录1：参考文献 14\o"CurrentDocument"附录2：程序清单 15可视化仿真磁盘调度程序第一章课程设计的目的与要求1.1课程设计的目的课程设计是课程中重要的实践教学环节。其主要目的一方面使学生更透彻地理解操作系统的基本概念和原理，使之由抽象到具体；另一方面通过课程设计加强学生的实验手段与实践技能，培养学生独立分析问题、解决问题、应用知识的能力和创新精神。与实验教学相比，课程设计独立设课，具有更多的学时，给学生更多自行设计、自主实验的机会，充分放于让学生真正培养学生的实践动手能力，全面提高学生的综合素质。1.2课程设计的要求课程设计的要求是在深入理解操作系统基本原理的基础上，先确定设计方案，设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理，编程序实现系统，要求实现可视化的运行界面，界面应清楚地反映出系统的运行结果，确定测试方案，选择测试用例，对系统进程测试，运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并提交课程设计报告。第二章课程设计的任务内容2.1课程设计的任务磁盘调度课程设计的任务是理解磁盘调度相关理论和掌握多种磁盘调度算法。比如先来先服务算法、最短寻道时间优先算法、扫描算法和循环扫描算法等算法，了解各种算法对磁盘扫描的优化等级，并且比较各种算法的优缺点，从而扫描不同的磁盘序列时采用相应的算法，使得磁道扫描时间尽量最短。2.2课程设计的内容为了完成课程设计的任务，所以在课程设计的内容上要根据任务来设置，因此在课程设计的内容上对于磁盘调用的相应算法的优劣点，可以设置几组相同的数据对各种算法进行比较，得出各种算法的平均寻道时间，然后对数据进行比较从中得出各种算法的优劣点。2.3课程设计的原理磁盘可供多个进程共享，当有多个进程要求访问磁盘时，应采用一种调度算法，以使进程对磁盘的平均访问时间最小，由于在访问磁盘的时间中，主要是寻道时间，因此磁盘调度的目标就是使磁盘的平均寻道时间最短。设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。第三章详细设计说明3.1模块描述模块描述要求给出对该模块的简要描述，说明该模块应具有的功能，并且要求说明本模块的特点，比如模块是否有返回值等。图3-1所示为功能模块图：图3-1功能模块图系统主要模块分为四大模块，分别是先来先服务算法模块、最短寻道时间优先算法模块、扫描算法模块和循环扫描算法模块。当进入系统时，可以按系统提示输入相关数据，然后可以停止操作直接退出或者是选择相应的算法进行运算，最后输出运算结果。本组实验是做的先来先服务算法和最短寻到时间优先算法。3.2性能一个可靠安全的系统不仅要在理论上可以运行起来，同时在系统出错处理、系统漏洞、系统安全、系统精确度、灵活度及时间特性等系能上要有一定的要求，这样才可以保障用户数据的可靠性和安全性等基本需求。对于磁盘调度系统的性能来讲，系统的精确度为万分之一，输出数据精确到小数点后四位。

3.3输入项输入项要求是给出对每一个输入项的特性包括名称、标识、数据的类型格式、数据值的有效范围、输入的方式、数量和频度、输入媒体比如键盘或文件、输入数据的来源和安全保密条件等。输入项要求如表3.2所示：表3.2输入项特征输入项名称输入磁道的个数输入项标识数字型数据类型格式数据型数据有效范围1-1000数据输出方式字符型输入媒体键盘数据来源输入值数据安全保密条件无3.4输出项对于输出项要求给出对每一个输出项的特性、包括名称、标识、数据的类型和格式、数据值的有效范围、输出的形式、数量和频度、输出比如显示器或文件、对输出图形及符号的说明、安全保密条件等。输入项要求如表3.3所示：表3.3输出项特征输出项名称平均寻道长度输出项标识数字型数据类型格式最多保留四位小数数据有效范围大于1数据输出方式字符型输入媒体曰壬显示器数据安全保密条件无3.5算法先来先服务（FCFS）调度:按先来后到次序服务，未作优化。最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在50号柱面上执行输出操作，而等待访问者依次要访问的柱面为130、199、32、159、15、148、61、99，那么，当50号柱面上的操作结束后，移动臂将按请求的先后次序先移到130号柱面，最后到达99号柱面。采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。现在仍利用同一个例子来讨论，现在当50号柱面的操作结束后，应该先处理61号柱面的请求，然后到达32号柱面执行操作，随后处理15号柱面请求，后继操作的次序应该是99、130、148、159、199。采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了200多个柱面的距离，与先来先服务算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（SSTF）调度，FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延。SCAN算法又称电梯调度算法°SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客A、B、C在等候乘电梯。他们的要求是：A在2层等待去10层；B在5层等待去底层；C在8层等待15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客C从8层带到15层，然后电梯换成下行方向，把乘客B从5层带到底层，电梯最后再调换方向，把乘客A从2层送到10层。但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。为了减少SCAN算法造成的某些进程的请求被严重推迟，CSCAN算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。算法要求是详细说明本模块所选用的算法，具体的计算公式和计算步骤。访问磁盘的总时间由三部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，所以总的时间为T总时间=丁查找时间+T等待时间+T数据传输数据。对于求平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N）即公式为：L=（M1+M2+……+Mi+……+MN）/N其中Mi为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。延迟时间——指定扇区旋转到磁头下所需的时间。传送时间——由磁头进程读写完成信息传送的时间。3.6流程逻辑要求用图表比如流程图并辅以必要的说明来表示本模块的逻辑流程。如图3-7所示为先来先服务算法流程图：对于先来先服务算法，系统开始后，先进行系统的初始化，然后根据系统提示输入需要访问的磁盘的序列，判断序列是否为空的话，序列空的话退出系统，不是的话则输入当前磁道号，求出平均寻道时间，完成运算后，可以选择退出系统或是再次进行运算。图3-7先来先服务流程图如图3-8所示为最短寻道时间优先算法流程图:图3-8最短寻道时间优先算法流程图3.7接口在系统的最短寻道时间优先算法模块中，有一个子模块为冒泡算法模块。其中冒泡算法模块的参数赋值如下：模块全局变量为：intdecide(charstr[])//判断输入数据是否有效{inti=0;while(str[i]!='\0')其中初始值为i=03.8限制条件说明本程序运行中所受到的限制条件。由于计算机是有限精度有限容量的，所以对于磁道数的最大值，系统设置为1000。对于输出的数据精确度，系统精确到小数点后四位。第四章软件使用说明打开软件，如图4-1所示为系统界面图。请输.A,i必亘序列［&结束）1图4-1系统界面图根据提示输入磁道序列10、22、20、2、40、6、38。系统显示界面如图4-2所示:你输入的磁道序列为：值2220240638>000<>0000<>0000<>00<>0000<>0000<>0000<>00<>0000<>0000<於XXXNNX系亳充 NJOOCXNMMMMMM先来先服务**最短寻道时间优先«*3.退出HMMMMMJOCJOCJCJOCJOCJCJOCNNJOCKNJOCJOCNJOCJOCJCJOCNNJOCKNJOCNKNJOCJOCM：请诜禅翕夫: 图4-2输入磁道数后系统界面根据选项可以选择先来先服务算法或者是最短寻道时间优先算法，输入“1”选择的是先来先服务算法，选择“2”选择的是最短寻道时间优先算法。如图4-3所示的为选择先来先服务算法，输入当前磁道数为“20”。系统显示结果如下：读选建鬓法f磁盘请求序列为：102220240638读碗:、当煎的觎苴号/2临磁盘扫描序列为:F2220240638平均寻道畏度『20.8571KXIOOCJC系 MMMMMMuuuuu*u**1-先来先服务**二r最短寻道时间优先“**3.退出**R-TR-T R-TR-TR-TXNXXNXXXXXXNXXNJCXNXXXXXXNXXNJCXNXXXXXXNXXNJCXXXXXNXXNXXXXXXNXXNJCXNXXXXXXNXXNJCXNXXXXXXNXXNJCXXXX请选择算法: 图4-3先来先服务界面根据结果可以知道磁盘扫描的顺序为10、22、20、2、40、6、38。平均寻道时间为20.8571。当选择最短寻道时间有限算法，并且输入当前磁道数为20时，结果显示如图4-4所示：岸膏冒宙凝序列为：261928223840喻入当前的感道号：20盘扫描序列为：20221B62384日怦均寻道亲度：S.57143:MJCNX知JC亲亳无MMMMMMKMMMMMMKMMMMMMKMMKMMMMMMKMMMMMMKMMMMMMKMHMMMMK**1.先来先服务****2-最短寻■道时间优先****3-退出**MMMMMM请选择算法：图4-4最短寻道时间优先算法界面

从结果我们可以知道磁盘扫描的顺序为20、22、10、6、2、38、40。平均寻道时间为8.57143。和算法1相比较，算法2所用的时间要少。若是选择“3”，则是退出系统。图4-5退出算法界面第五章课程设计心得与体会首先课程设计是培养我们学生综合运用所学知识，发现，提出，分析和解决实际问题，锻炼实践能力的重要环节，是对实际工作能力的具体训练和考察过程.随着科学技术发展的日新日异，计算机已经成为当今生活必不可少的事务，在生活中可以说得是无处不在。计算机的编程语言虽然很多，然而自己掌握一种编程语言不仅对于以后的工作有了帮助而且让我们学会了许多新的东西，因此对于二十一世纪的大学生来说掌握计算机编程技术是十分重要的。回顾起此次磁盘调度的课程设计，我感慨颇多，从选择题目到查找资料，使我进一步了解磁盘的各种算法，虽然做的时间不是很长，但是可以学到许多东西，不仅可以巩固了以前所学过的知识，也知道曾经学习的不足，并加以改正。而且我也学到了很多在书本上所没有学到过的知识。通过这次课程设计我懂得了理论与实际相结合的重要性.在学习理论中，自己并没有学好书本上的知识，而平时也不注意，但当在实验中要用到时就感觉学的很少或者是不精通，不知道学了后又什么用，一些操作往往只知道大概而不懂得具体怎么做。通过完成实验让自己可以把以前的漏洞加以学习，对于学过的东西加以灵活运用。只有理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到各种各样的问题，不仅是磁盘算法的问题，也有在编程中出现的故障，经过不断的修改让自己掌握了许多东西。通过这次课程设计，把以前所学过的知识重新温故。附录1:参考文献[1].[美]AndrewS.TanenbaumAlbertS.Woodhull著.陈渝，谌卫军译，向勇审校.操作系统设计与实现.电子工业出版社.2006.⑵.张红光，李福才著.操作系统教程.高等教育出版社.2010.[3]陈龙等著.21天学通C++.人民邮电出版社.2009.附录2：程序清单#include<stdio.h>#include<stdlib.h>#include<iostream.h>#include<math.h>#definemaxsize1000/*********************判断输入数据是否有效**************************/intdecide(charstr[])//判断输入数据是否有效inti=0;while(str[i]!='\0')if(str[i]<'0'||str[i]>'9')return0;break;i++;returni;/******************将字符串转换成数字***********************/inttrans(charstr[],inta)//将字符串转换成数字inti;intsum=0;for(i=0;i<a;i++)sum=sum+(int)((str[i]-'0')*pow(10,a-i-1));}returnsum;/*********************冒泡排序算法**************************/int*bubble(intcidao[],intm){inti,j;inttemp;for(i=0;i<m;i++)//使用冒泡法按从小到大顺序排列for(j=i+1;j<m;j++){if(cidao[i]>cidao[j]){temp=cidao[i];cidao[i]=cidao[j];cidao[j]=temp;}}cout<<"排序后的磁盘序列为："；for(i=0;i<m;i++)//输出排序结果{cout<<cidao[i]<<"";cout<<endl;returncidao;/*********************先来先服务调度算法**************************/voidFCFS(intcidao[],intm)//磁道号数组，个数为mintnow;//当前磁道号intsum=0;//总寻道长度intj,i;inta;charstr[100];floatave;//平均寻道长度cout<<"磁盘请求序列为："；for(i=0;i<m;i++)//按先来先服务的策略输出磁盘请求序列{cout<<cidao[i]<<"";}cout<<endl;cout<<"请输入当前的磁道号："；B:cin>>str;//对输入数据进行有效性判断a=decide(str);if(a==0){cout<<"输入数据的类型错误，请重新输入！"<<endl;gotoB;}elsenow=trans(str,a);//输入当前磁道号sum+=abs(cidao[0]-now);coutvv"磁盘扫描序列为："；for(i=0;i<m;i++)〃输出磁盘扫描序列{coutvvcidao[i]vv"";}for(i=0,j=1;jvm;i++,j++)//求平均寻道长度{sum+=abs(cidao[j]-cidao[i]);ave=(float)(sum)/(float)(m);}cout<<endl;cout<<”平均寻道长度："<<ave<<endl;/**********************最短寻道时间优先调度算法********************/voidSSTF(intcidao[],intm){intk=1;intnow,l,r;inti,j,sum=0;inta;charstr[100];floatave;cidao=bubble(cidao,m);〃调用冒泡排序算法排序cout<<"请输入当前的磁道号："；C:cin>>str;//对输入数据进行有效性判断a=decide(str);if(a==0){cout<<"输入数据的类型错误，请重新输入！"<<endl;gotoC;}elsenow=trans(str,a);//输入当前磁道号if(cidao[m-1]<=now)//若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务cout<<"磁盘扫描序列为：”；for(i=m-1;i>=0;i--)cout<<cidao[i]<<”";sum=now-cidao[0];}if(cidao[0]>=now)//若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务{cout<<"磁盘扫描序列为：”；for(i=0;i<m;i++)cout<<cidao[i]<<"";sum=cidao[m-1]-now;}if(now>cidao[0]&&now<cidao[m-1])//若当前磁道号大于请求序列中最小者且小于最大者{cout<<"磁盘扫描序列为：”；while(cidao[k]<now)〃确定当前磁道在已排的序列中的位置，后面的算法都用到了，可以直接复制后少量修改，节省时间。{k++;}l=k-1;r=k;while((l>=0)&&(r<m))//当前磁道在请求序列范围内{if((now-cidao[l])<=(cidao[r]-now))〃选择与当前磁道最近的请求给予服务{cout<<cidao[l]<<"";sum+=now-cidao[l];now=cidao[l];l=l-1；}else{cout<<cidao[r]<<"";sum+=cidao[r]-now;now=cidao[r];r=r+1;}}if(l==-1)//磁头移动到序列的最小号，返回外侧扫描仍未扫描的磁道{for(j=r;j<m;j++){cout<<cidao[j]<<"";}sum+=cidao[m-1]-cidao[0];}else//磁头移动到序列的最大号，返回内侧扫描仍未扫描的磁道{for(j=l;j>=0;j--){cout<<cidao[j]<<"";}sum+=cidao[m-1]-cidao[0];}}ave=(float)(sum)/(float)(m);cout<<endl;cout<<"平均寻道长度："<<ave<<endl;}voidmain(){inta;intc;//菜单项intcidao[maxsize];inti=0,count;charstr[100];cout<<"请输入磁道序列(0结束)："<<endl;A:cin>>str;〃对输入数据进行有效性判断a=decide(str);if(a==0)