《操作系统课设--磁盘调度算法.docx》由会员分享，可在线阅读，更多相关《操作系统课设--磁盘调度算法.docx（30页珍藏版）》请在课桌文档上搜索。
1、计算操作系统课程设计报告姓名：崔玲玲班级：软件111学号：201101014103指导老师：夏辉丽1 .操作系统课程设计任务描述21 .1先来先效劳算法(FCFS)22 .2最短寻道时间优先算法(SSTF)2L3扫描算法(SCAN)21.4循环扫描算法(CSCAN)22 .问题定义与需求分析32. 1输入的形式33. 2输入值的范围34. 3输出的形式35. 4程序所能到达的功能36. 5测试数据33 .概要设计及流程图41 .1子模块的调用关系43 .2个别函数的参数43. 3主要的流程图44 .问题实现及代码64. 1先来先效劳算法的实现65. 2最短寻道时间优先算法的实现66. 3扫描算
2、法的实现87. 4循环扫描算法的实现85 .调试分析96 .测试101 .1测试数据106 .2测试界面Il7 .课设总结138 .参考文献139 .源代码141.操作系统课程设计任务描述本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，这里主要实现磁盘调度的四种算法，分别是先来先效劳算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法。1.l先来先效劳算法(FCFS)这是一种比拟简单的磁盘调度算法，它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某
3、一进程的请求长期得不到满足的情况。1.2最短寻道时间优先算法(SSTF)该算法要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比拟好的吞吐量，但却不能保证平均寻道时间最短，对用户的效劳请求的响应时机不是均等的。1.3扫描算法(SCAN)扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，等请求到磁道的外部边缘时，磁道调换方向，开始从最小号磁道依次向最大号磁道效劳。这样很好的防止了饥饿现象的出现。吞吐量较大，平均响应时间较小。其缺点是对用户的效劳请求的响应时机不是均等的，因而导致响应时间的变化幅度很大
4、。1.4循环扫描算法(CSCAN)循环扫描算法是对扫描算法的改良，不同于循环扫描的是循环扫描算法规定磁头单向移动，也就是当磁头到达磁盘的边缘时，磁头那么直接返回到磁盘的另一边缘，继续做原来请求方向进行效劳。此算法解决了扫描算法的缺点，也同时具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小不过，磁道两端的访问频率仍低于磁道中间的访问频率。2.问题定义与需求分析2.1 输入的形式磁道号数组的输入：定义一个数组，intCidaO口,先提示用户输入磁道号串的个数n,然后依次输入n个磁道号(磁道号中间可用空格或回车键隔开)，输入完毕后回车键结束输入，运行下一步。2.2 输入值的范围数据的大小
5、：全局变量maxsiZe=100O,磁道数组CidaOmaxsize的大小就是IOo0,输入时有大小提示，大于最大值时那么也只能保存前IOoO个数据。关于intnow,表示的是当前的磁道号，程序运行时会让用户在每种算法中都输入当前的磁道号now,如果输入了除数字以外的字符，那么提示错误，让用户重新输入。2. 3输出的形式用户输入磁道数组后，程序会显示用户输入的数组，按用户的输入顺序输出，输出形式是一横行，如果是排序之后的，那么输出排序后的磁道号。3. 4程序所能到达的功能程序的main函数实现了程序的运行模式，运行后首先会显示磁盘调度算法系统的系统名称，紧接着下面就是系统菜单，在系统菜单里，可
6、以供用户选择6个选项：L输入磁道号2.先来先效劳3.最短寻道时间优先4.扫描调度5.循环扫描6.退出系统，由用户输入磁道号串后，可以连续选择不同的调度算法，不过每种调度算法都会提示用户重新输入当前的磁道号而不用再输入磁道号串，操作起来比拟方便；在扫描和循环扫描算法中，还会让用户选择磁道的请求方向，向内还是向外；选择系统退出时，系统会提示是否真的退出(yesno),如果手动输入大写的YES或是小写的yes系统都会退出，如果输入的是其他字符系统那么调用main(),继续磁盘调度的算法操作。4. 5测试数据由于定义的磁道数组和当前磁道号的数据类型都是整形数，所以用cin.fail。函数检验错误，如果
7、有数据类型错误的错误，再用cin.clear。进行错误去除，接着再用一个Cin.ignore。函数忽略掉输入的错误数据，最后用goto返回，继续进行数组数据的输入，这样可以有效的防止用户手误输错的情况。3.概要设计及流程图3.1 子模块的调用关系本程序主要分为八大模块，除了系统菜单里的六个选择项之外，还有排序函数PaiXU(),主函数mian().在主函数里，有用户选择输入，算法以及退出，用SWitCh函数控制，去调用外部的函数FCFS(),SSTF(),SCAN(),CSCAN(),shuru()和Exit()分别进行算法实现。其中用到排序的算法SSTF(),SCANO和CSCAN()都在函
8、数里调用了PaiXU()进行排序。3.2 个别函数的参数四个算法函数和ShUrU()函数都用参数，像FCFS(intcidao口,intm),CidaO口是磁道数组，函数实现的时候函数里的参数可以不同于intcidao,结果都是对的，因为其根本都是对主函数里的intCidaOIjTlaXSize进行操作的；intm是指磁道号的个数，输入函数ShUrU()完成给m以及磁道号串的赋值，因为输入函数规定了磁道的大小和各个磁道号。5. 3主要的流程图主函数主要是实现功能的选择，流程图如图1所示。先来先效劳函数的流程很简单，用户输入磁道号串后，选择菜单功能2即调用先来先效劳磁盘调度算法，用户再输入当前磁
9、道号，系统会显示磁盘寻求序列也就是磁道的输入顺序,然后依次给予效劳，最后在求和，输出平均值，本设计报告省略了此算法的流程图。最短寻道时间优先算法的实现不同于先来先效劳算法，它需要调用排序函数来给磁道号排序，然后在效劳，流程图如图2所示。扫描算法的实现流程图如图3所示：循环扫描算法是基于扫描算法实现的，与之不同的是循环扫描算法当原来的磁头访问到磁到边缘后，磁头直接跳到磁盘的另一边缘，然后按原来的寻求方向继续给磁道效劳，此处省略了流程图。函数调用功能实现图2最短寻道时间优先算法流程图图3扫描算法流程图4.问题实现及代码4.1 先来先效劳算法的实现voidFCFS(intcidao,intm),输入
10、磁道号，按先来先效劳的策略输出磁盘请求序列,求平均寻道长度，输出移动平均磁道数。主要代码：fbr(i=O,j=l;jm;i+,j+)(sum+=abs(arrayIj-arrayi);ave=(float)(sum)(float)(m);)6. 2最短寻道时间优先算法的实现voidSSTF(intcidao,intm),将磁道号用冒泡法从小到大排序,输出排好序的磁道序列，输入当前磁道号，根据前磁道在已排的序列中的位置，分三种情况进行访问总长度计算，第三种是比拟找到离now最近的磁道号坐标，按找到的磁道号方向访问，然后反过来访问其他未访问的，算出寻道总长度，输出移动的平均磁道长度。主要代码：(1
11、)当前磁道号大于请求序列中最大者时，直接从大到小依次给予各请求效劳if(cidaom-1=now)(COUt=O;i-)coutcidaoi=now)COUtVV”磁盘扫描序列为：”；for(i=0;im;i+)coutcidaoin,;sum=cidaom-1-now;)(3)当前磁道号大于请求序列中最小者且小于最大者时while(cidaoknow)先确定当前磁道在已排的序列中的位置k+;/k为离now最近的磁道坐标)l=k-l;/1为now左边的磁道坐标r=k;r为now右边的磁道坐标if(now-cidaol)=(cidaor-now)选择与当前磁道最近的请求给予效劳(coutcida
12、old;if(d=0)选择移动臂向磁道号减小的方向扫描(COUt=0;j-)(coutcidaojn,;输出向外扫描的磁道序列)fbr(j=r;jm;j+)/磁头移动到最小号，那么改变方向向内扫描未扫描的磁道coutcidaoj=0;j-)coutcidaofjr;j-)(coutcidaofj=0;j-)(coutcidaojll;j-)(coutcidaoj,;)sum=now-cidao0+cidaofm-l-cidao0+cidaom-l-cidaor;)5 .调试分析运行过程中，发现第一种先来先效劳算法，当输入的磁道号只有一个的时候，计算的平均值出错，是随机数，经过缜密的考虑才发现，
13、这种情况应该作为特殊情况来考虑，所以，我在总长度计算的代码中增加了一种特殊情况。代码如下：if(m=l)/m是磁道号的个数ave=(float)(sum)(float)m;COUtVV”平均寻道长度：,aveendl;在输入函数里，我想要获取输入函数里规定的磁道号个数n,想把n传到主函数里，供其他算法例如FCFS(Cidao,m)中的m使用，经过老师帮我调试才完成了这一功能，解决方法是：在输入函数里定义一个参数ShUrU(EtCidao),把输入函数定义成Et类型，returnn(这里的n也指磁道号个数)，在主函数里，定义一个intm,再把SWitCh函数里的输入函数赋值给m,m=shuru(
14、cidao),这样就有效的解决了问题。6 .测试6.1 测试数据测试数据:30501020604011)先来先效劳算法当前磁道号：30平均寻道长度：21.66(2)最短寻道时间优先算法当前磁道号大于磁道序列中的最大的磁道号时当前磁道号：70平均寻道长度：10当前磁道号小于磁道序列中的最小的磁道号时当前磁道号：5平均寻道长度：9.16当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号时当前磁道号：35平均寻道长度：12.5(3)扫描算法当前磁道号大于磁道序列中的最大的磁道号时当前磁道号：70平均寻道长度：10 当前磁道号小于磁道序列中的最小的磁道号时当前磁道号：5平均寻道长度:9.16 当前
15、磁道号大于磁道序列中的最小的磁道号且小于最大磁道号(磁头向外)当前磁道号：35平均寻道长度：12.5 当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号(磁头向内)当前磁道号：35平均寻道长度：12.5(4)循环扫描算法当前磁道号大于磁道序列中的最大的磁道号时当前磁道号：70平均寻道长度：18.33当前磁道号小于磁道序列中的最小的磁道号时当前磁道号：5平均寻道长度：9.16 当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号(磁头向外)当前磁道号：30平均寻道长度：15 当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号(磁头向内)当前磁道号：30平均寻道长度：156.2测试界面(
16、1)系统界面，运行程序以后，直接显示系统界面，请用户选择功能，如图4所示:图4主界面选择功能1,表示输入磁道号串，输入之前先控制磁道号的个数n,如图5所示：XX6.退出系统XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=请选择：松远择工输入：漕籀入超!串号的个数（小于1。）n：6请依次输入6个磁道号：305010206040您鹑瞿兽普官务普塔5010206040图5数据的输入(3)如果用户输入信息错误，在输入当前磁道号时输入了字母h,系统会提示用户输入信息类型错误，并要求用户重新输入，如图6所示：XX6.退出系统XXXXXXXXXXXXX
17、XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX扫遍前类 了的当据选误 调 tbS 曹的型!I 10 20 30海上新输入t40 SH GW图6错误提示(4)根据输入的磁道号串，选择功能3,调用最短寻道时间优先调度算法，算法自动调用排序函数给输入的磁道号排序，然后输入当前磁道号5,最后根据算法输出寻求序列，算出平均寻道时间，如图7所示：XX5.循环扫描XXXXXXXX6.退出系统XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX最磁刖序长 了的当描道 辑入扫寻 H短堂道心间优先调度算法：盘序列为：102030405
18、0的腹道号：5歹IJ为：102030405060度：9.16667按任意键重新选择葬法一图7最短寻道时间优先调度算法(5)选择功能5,系统调用循环扫描调度算法，先排序，再输入当前磁道号，如果当前磁道号大于最大的磁道号或者小于最小的磁道号，算法那么直接输出寻求序列；这里当前磁道号输入30,在最大磁道号和最小磁道号中间，那么继续选择当前磁道移动方向，选择向外移动，结果如图8所示：5.循环扫描6-退出系统XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX请选择：松遒提工延处担璜迥度算法：排序后的磁盆序列为：102030405060董埴仄当前的旗直号：30根愈扫
19、描序列为I清输入当前移动臂的移动的方向1表示向内，。表示向外)：0302010605040平均寻道长度：15请按任意键重新选择笄法一图8循环扫描调度算法(6)功能选择6,选择是否退出系统，如果确定退出，那么输入大写或小写y,输入其他任何数据那么是确认退出，确认退出如图9所示:7XXXXXXXX5 .循环扫描6 .退出系统TVTTXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX请选择：3选揉工谓中是否福克退出(yn)?y谢谢使用，再见！人一：PreSSanykeytoCOntine图9退出系统7 .课设总结本次的操作系统课程设计，老师共给
20、了六大题目，我觉得我在擦盘调度这一块学习的还比拟扎实，理论知识理解的也不错，所以，我就选择了磁盘调度算法的实现。本程序没有实现对效劳过的磁道进行记录，根据磁盘调度算法的思想，是需要实现这一功能的，这样才能有利于对新来的进程进行效劳，不至于把程序写死，本算法简化了磁盘调度算法，只是简单地模拟了对现有磁道号串的请求效劳。磁盘调度算法总共分为四大算法，在算法思想上都有一一介绍她们各自的优缺点。可是,理论知识理解的好并不代表算法就能很好的实现，因此，在算法实现的过程中感觉还是比拟吃力的，算法的整体是用一个简单的数组进行数据定义的，每个被调用的不同的算法的函数里都含有两个参数，一个是intcidao,一
21、个是intm,难点在于要非常清楚的明白这两个参数是怎么样被赋值的？它们之间的关系又是怎么样的？起初我也搞不懂，根本不知道怎么去用代码表达，后来经过老师的细心讲解，我才知道磁道的个数可以直接用输入函数里的返回值进行赋值，这样修改正程序在结构上就没有什么问题了；除此之外的难点就是磁道长度的计算，他之所以难是因为它比拟复杂，考虑到的情况非常之多，经过我不断的调试和错误的发现和改正，才终于写成了现在的比拟完整的程序。通过这次的课程，让我再一次认识到，我现在所掌握的关于程序实现的知识还非常之少,像程序中防止输入错误的所用到的函数，我在之前都没有见过，不过，这次的使用让我很熟练地知道了它的用法。本程序没有
22、用可视化界面实现，因为这方面内容我不了解，我想我以后会抽空学习的，因为毕竟对它比拟感兴趣。8 .参考文献汤小丹，梁红兵，哲凤屏，汤子瀛.计算机操作系统M.西安电子科技大学出版社.2007.194-1962郑秋生.C+程序设计教程M.电子工业出版社.20073严蔚敏.数据结构M.清华大学出版社.20079 .源代码ttincludettincludettincludeinclude#includeSdefinemaxsize1000main();int*paixu(intcidao,intm)冒泡算法(inti,j,temp;for(i=0;im;i+)使用冒泡法按从小到大顺序排列for(j=i
23、+l;jcidaoj)temp=cidaoi;cidaoi=cidaoj;cidaoj=temp;)COUt排序后的磁盘序列为：；for(i=O;im;i+)输出排序结果(coutcidaoi*)coutendl;returncidao;)先来先效劳调度算法voidFCFS(intcidao,intm)磁道号数组，个数为mintnow;当前磁道号intj,i;intsum=O;总寻道长度floatave;平均寻道长度COUt“你选择了先来先效劳调度算法”Xendl;COUt磁盘请求序列为：；for(i=0;im;i+)按先来先效劳的算法输出磁盘请求序列(coutcidaoiz,：)coutno
24、w;if(cin.fail()(COUt输入数据类型错误！请重新输入：endl;cin.clear();去除以上错误cin.ignore();忽略刚刚流中的字符gotoA;)sum+=abs(cidao0-now);/sum=sum(第一个磁道号)-(当前磁道)ICoUt。磁盘扫描序列为：；for(i=0;im;i+)输出磁盘扫描序列(coutcidaoiz,；)if(m=l)(ave=(float)(sum)/(float)m;COUt平均寻道长度：aveendl;else(for(i=0,j=l;jm;i+,j+)求平均寻道长度(sum=abs(cidaoj-cidaoi);ave=(fl
25、oat)(sum)/(float)(m);)coutendl;CoUt平均寻道长度：aveendl;)/最短寻道时间优先调度算法voidSSTF(intcidao,intm)inti,j;intnow,1,r;intk=l,sum=O;floatave;COUt你选择了最短寻道时间优先调度算法：now;if(cin.failO)COUt输入数据类型错误！请重新输入：endl;cin.cIear();去除以上错误cin.ignore()；忽略刚刚流中的字符gotoB;假设当前磁道号大于请求序列中最大者，那么直接从大到小依次给予各请求效劳if(cidaom-1=now)(CoUt=0;i一)cou
26、tcidaoi=now)(CoUt。磁盘扫描序列为：；for(i=0;im;i+)coutcidaoizz；sum=cidaom-1-now;)假设当前磁道号大于请求序列中最小者且小于最大者if(now=cidao0)(cout磁盘扫描序列为：；while(cidaok=O)&(rm)当前磁道在请求序列范围内选择与当前磁道最近的请求给予效劳if(now-cidao1)-(cidaor-now)coutcidaol,”;sum+=now-cidaol;now=cidaol;1=1-1;)else(coutcidaor*”;sum+=cidaor-now;now=cidaor;r=r+l;)if(
27、l-1)磁头移动到序列的最小号，返回外侧扫描还未扫描的磁道(for(j=r;jm;j+)(COUtcidaoj=0;j)(coutcidaoj*;)sum+=cidaom-l-cidao0;ave=(float)(sum)/(float)(m);coutendl;COUt平均寻道长度：aveendl;扫描调度算法voidSCAN(intcidao,intm)先给出当前磁道号和移动臂的移动方向(inti,j;intnow,1,r;intk=l,sum=0;floatave;CoUt你选择了扫描调度算法：cndl;cidao=paixu(cidao,m);调用冒泡排序算法排序CoUtnow;if(
28、cin.fail()(cout输入数据类型错误！请重新输入：“endl;cin.clear();去除以上错误cin.ignore();忽略刚刚流中的字符gotoC;)假设当前磁道号大于请求序列中最大者，那么直接由大到小依次给予各请求效劳if(cidaom-1=now)(COUt=0;i)coutcidaoi=now)(COUt磁盘扫描序列为：；for(i=0;im;i+)coutcidaoizz；sum=cidaom-1-now;)假设当前磁道号大于请求序列中最小者且小于最大者时if(now=cidao0)(while(cidaoknow)(k+;)l=k-l;r=k;intd;COUt请输入
29、当前移动臂的移动的方向(1表示向内，O表示向外)：“d;if(d!=l&d!=0)(COUt数据输入错误，请重新输入：“endl;gotoE;)if(d=O)选择移动臂向磁道号减小的方向扫描(cout=0;j)(coutcidaojz,z;输出向外扫描的磁道序列)磁头移动到最小号，那么改变方向向内扫描未扫描的磁道for(j=r;jm;j+)(COUtcidaoj；输出向内扫描的序列)sum=now-cidaoO+cidaom-l-cidao0;else选择移动臂向磁道号增加的方向扫描cout磁盘扫描序列为：；for(j=r;j=0;j)(coutcidaojz;输出向外扫描的序列)sum=ci
30、daom-1-now+cidaom-l-cidao0;ave=(float)(sum)/(float)(m);coutendl;COUt久”平均寻道长度：avcendl;循环扫描调度算法voidCSCAN(intcidao,intm)(inti,j;intnow,1,r;intk=l,sum=0;floatave;cout你选择了循环扫描调度算法：endl;cidao=paixu(cidao,m);调用冒泡排序算法排序COUtnow;if(cin.fail()(CoUt输入数据类型错误！请重新输入：endl;cin.clear();去除以上错误cin.ignore()；忽略刚刚流中的字符got
31、oD;假设当前磁道号大于请求序列中最大者，移动臂直接从大到小依次给予请求效劳if(cidaom-1=now)(COUt磁盘扫描序列为：；for(i=0;im;i+)COUtcidaoi=now)COUt磁盘扫描序列为：；for(i=0;im;i+)coutcidaoi/z；sum=cidaonr1-now;)假设当前磁道号大于请求序列中最小者且小于最大者if(now=cidao0)(CoUtX磁盘扫描序列为：；while(cidaokd;if(d!=l&d!=0)(COUt数据输入错误，请重新输入：=0;j)(CoUtcidaojr;j)(coutcidaojA，；)sum+=now-cida
32、o0+cidaom-l-cidao0+cidaom-l-cidaor+1;)else(for(j=l;j=0;j)(coutcidaojl;j)(coutcidaojzzsum+=now-cidao0+cidaom-l-cidao0+cidaom-l-cidaor;)else选择移动臂向磁道号增加的方向扫描(for(j=r;jm;j+)coutcidaojz*z;输出从当前磁道向内扫描的序列)当扫描完最大号磁道，磁头直接移动到最小号磁道从小到大依次为效劳的磁道给予效劳for(j=0;jr;j+)(coutcidaoj,)sum=cidaom-1-now+cidaonrl-cidao0+cida
33、ol-cidao0;)ave=(float)(sum)/(float)(m);coutendl;COUtX平均寻道长度：avcXcndl;)voidExit()(charch;COUt“你选择了退出endl”是否确定退出(yn)?,zch;if(ch=三,Y,IIch=三,y,)(CoUt谢谢使用，再见！zendl;)else(CoUt你选择了返回主界面式Cndl;system(,zpausezz);systemCzclszz);main();)intshuru(intcidao)intn;COUt你选择了输入:*endl;CoUt”请输入磁道串号的个数(小于100o)n：zzn;CoUtG请
34、依次输入n个磁道号：endl;H:for(inti=0;icidaoi;if(cin.fail()(COUt输入数据类型错误！请重新输入：endl;cin.clear();去除以上错误cin.ignore();忽略刚刚流中的字符gotoH;CoUt你输入的磁道序列为：；for(i=0;in;i+)coutcidaoizr输出磁道序列)returnn;)intmain()intcidaomaxsize;intcode;选择算法intm;CoUttt=ttendl;coutzztt欢送使用磁盘调度算法ttendl;coutzztt=tt*end1;do(coutttXXXXXXXXXXXXXXXX
35、XXXXXXXXXXXXXXXXXXXttendl;coutzzttXXXXXX系统菜单XXXXXttendl;coutzztXtxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxXtt*endl;coutzzttXXXXttzzendl;coutzzt1.输入磁道号XXtt4,endl;COUtttXXXXttzendl;coutttXX2.先来先效劳XXttendl;coutvttXXXXttzzendl;CoUtttXX3.最短寻道时间优先XXttzendl;coutzzttXXXXttzzendl;coutttXX4.扫描调度XXttz,endl;cout*ttXXXXttz*endl;CoUtttXX5.循环扫描XXttzzendl;coutttXXXXttvendl;coutzzttXX6.退出系统XXttzzendl;COUtttXXXXttzrendl;coutttXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXttzzendl;coutzz=
