磁盘调度算法程序课程设计报告

1、成绩金陂科扶骂院目磁盘调度算法程序设计课程名称操作系统课程设计院部名称信息技术学院专 业 计算机科学与技术班级Mil计算机科学与技术U学生姓名学号课程设计地点A205课程设计学时20指导教师李莉金陵科技学院教务处制目录一、课程设计的目的和要求21、目的22、要求2二、设计任务介绍及系统需求分析2.1任务介绍22. 2基本需求设计2三、概要设计33.1程序主要流程33.2程序的函数调用关系4四、详细设计54.1数据结构描述54.2各功能模块(或主要过程)分析54. 3各子程序流程分析74.3.1 FCFS()错误!未定义书签。43.2 SSTFQ错误!未定义书签。4.3.3 SCAN()错误!未

2、定义书签。五、调试与测试105.1程序运行初始界面105.2 键盘输入磁道105.3随机产生磁道105.4先来先服务算法105.5最短寻道时间优先算法105.6 扫描算法115.6.1先向外扫描115.6.2先向里扫描115.7退出程序11六、结论与体会12参考文献12附件：源程序清单14一、课程设计的目的和要求Li aw磁盘是经常使用的一种重要的外设，对磁盘数据的寻道时间的长短直接影响机器 的整体运行速度，本设计要求用C语言（或高级语言）编写程序模拟实现磁盘调 度的常用算法。以加深对磁盘调度常用算法的理解和实现技巧。1.2要求1）、设计一个函数完成先來先服务的磁盘调度功能。2）、设计一个函数

3、完成最短寻道时间优先的磁盘调度功能。3）、设计一个函数完成电梯算法的磁盘调度功能。二、系统需求分析2.1任务介绍1、可利用先来先服务算法（FCFS即first come first served）最短寻道时间 优先算法（SSTF即shortest seek time first）、扫描算法（SCAN）,來实现磁 盘的访问顺序。2、根据磁盘调度算法的不同的特性做好软件实现的需求分析。3、可根据问题的实际需要，可模拟数据在磁道的存放位置。4、当系统运行时，能直观地、动态地反映当前磁盘状态及不同算法的平均寻道 时间。5、要求在系统安全状态的前提下，用户指定需要访问的磁道，软件自动模拟在 不同算法情况

4、下，磁盘寻道顺序和平均寻道时间。2. 2基本需求设计系统主界面可以灵活选择某种算法，算法包括：先來先服务算法（FCFS）、 最短寻道时间优先算法（SSTF）、扫描算法（SCAN）o1、先来先服务算法（FCFS）这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进 行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不 会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化， 在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平 均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。2、最短寻道时间优先算法（SSTF）该算法选

5、择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最 近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证 平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导 致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求 将会无限期的被延迟，有些请求的响应时间将不可预期。3、扫描算法(SCAN)扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头 的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个 访问对象应是其欲访问的磁道既在当前磁道之外，乂是距离最近的。这样自里向 外地访问，直到再无更外的磁道需要访问才将

6、磁臂换向，自外向里移动。这时， 同样也是每次选择这样的进程來调度，即其要访问的磁道，在当前磁道之内，从 而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故 乂称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于 中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即 吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问 的频率仍低于中间磁道。三、概要设计3.1程序主要流程下图3-1为磁盘调度算法总流程图，程序运行开始，进入选择界面，输入磁道数, 然后依次调用decide ()函数和trans ()函数，再进入主循环界面，选择

7、调度算法, 直到选择4,程序执行完毕退出。图3-13. 2程序函数调用关系下图为磁盘调度算法的函数之间的调用关系，主函数调用子函数，子函数也可以 调用子函数，进行进程的初始化，排序等等。函数调用关系图，如图3-2：图3-2四、详细设计4.1数据结构描述本系统划分为三个模块：先來先服务算法模块void FCFS(int cidao, int m) 最短寻道时间优先算法模块void SSTF(int cidao, int m)、扫描算法模 块 void SCAN(int cidao,int m)。1.先来先服务算法模块:void FCFS (int cidao H, int m)输入磁道号，按先來

8、先服务的策略输出磁盘请求序列，求平均寻道长度，输 出移动平均磁道数。这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的 先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得 到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻 道进行优化，致使平均寻道时间可能较长。2 .最短寻道时间优先算法模块:void SSTF(int cidao, int m)将磁道号用冒泡法从小到大排序，输出排好序的磁道序列，输入当前磁道号, 根据前磁道在己排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出 移动的平均磁道数。该算法选择这样的进程，其要求访问的磁道与当前磁头所

9、在 的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻 道时间最短。3 .扫描算法模块：void SCAN(int cidao , int m)将磁道号用冒泡法从小到大排序，输出排好序的序列，输入当前磁道号，选 择移动臂的移动方向，根据当前磁道在己排的序列中的位置，选择扫描的顺序， 求出平均寻道长度，输出移动的平均磁道数。SCAN算法不仅考虑到欲访问的磁 道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在 自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在 当前磁道之外，乂是距离最近的。这样自里向外地访问，直到再无更外的磁道需 要访

10、问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程來调 度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这 种算法中磁头移动的规律颇似电梯的运行，故乂称为电梯调度算法。4.2各模块函数功能分析由于一开始我们要对键盘输入的磁道数和要使用的算法进行一次有效性的 判断，我使用了 int decide (char str),如果输入的信息不是09之间的数 都将被判定为不合法，合法后才能进行下一步。判断完合法性后，要将我们输入的字符转化为数字，这里我用了 int trans (char str,in t a)。当然系统自动生成的就不要使用以上两个函数了。一切都准备好后，开

11、始选择要调用哪个算法了，先來先服务调度算法我使用 7 void FCFS(int cidao, int m),这个算法主要完成按原來键盘输入的次序 或系统自动生成的次序来寻到，然后输出总的寻道长度和平均寻道长度。以下两个算法都要用到排序算法，这里我使用了冒泡排序法int *sort(int cidao, int m),将磁道数按从小到大的序列排好。最短寻道时间优先调度算法我使用了 void SSTF(int cidao, int m),在 排好序列磁道中选择离当前磁道最近的磁道开始寻道，然和再和相邻的两个磁道 进行比较，看离哪个更近；如果当前磁道是最大值或是最小值，直接按倒叙或是 正序寻道，最

12、后输出总的寻道长度和平均寻道长度。扫描调度算法我使用了 void SCAN(int cidao, int m),在排好序的磁道 序列中根据当前磁道数，选择是向外寻道还是向内寻道，如果当前磁道数是最大 值或是最小值，直接向内或向外寻道，最后也要输出总的寻道长度和平均寻道长 度。4. 3各子函数流程分析4. 3. 1 FCFS ()下图4-1为FCFS函数的流程图:图4-14. 3.2 SSTF ()下图4-1为FCFS函数的流程图:图4-24.3.3 SCANO下图4-1为FCFS函数的流程图:图4-3五、调试过程5.1运行程序初始界面运行程序，显示初始界面如图5-1所示，选择产生磁道的方式。F

13、:Microsoft Visual StudioMyProjectszhDebugzh.exe"二沁哪度嚴”图5-15. 2随机产生磁道输入1可随机产生磁道数，如图5-2所示。:黄关理迎进人磁盘调度喜蛊：r k-隠机严笙*2.薩盘输入«1随机产生的逋道序列为，92 47 98 54 42 27 15 27 56 78先寻调界FS先町 FC优CA 间(S>wa度面请选择算法:图5-25. 3軽输入磁道输入2进行键盘输入，并附带错误提醒功能，如图5-3所示。派餐衣迎敷磁盘调度建哇芒f 样.陆机产圭吨.薩盘输入*备输入磁道序列3结束）；44 55 66 77 88 99 1

14、00 zh输入数据的类型错误请重新输入！图5-35.4先来先服务算法输入1,选择先來先服务算法，如图5-4所示。随机产生的磁道序列为，15 88 50 60 ?4 12 19 15 64 27一FS先H)-FC优CA-(5S一务叫-服道度面一先寻调界:. 乗短香卄一先最扫退"笔扫寻寻 “卄选盘盘的均沖*1«2*3*4住（SSTF）8 88 85 5 9119 -9 9 2 2 1为为! 5 :列列度度 <冬50 60 ?4 12 19 15 64 2750 60 ?4 12 19 15 64 27图5-45. 5最短寻道时间优先算法输入2,选择最短寻道时间优先算法，如

15、图5-5所示。F)TSS十FS先町FC优cfi E 间(S 心务时 心服道度面 曲先寻调界 先最扫退15 12 27 50 60 64 74 8851912 : 列度度 吿序4- W1S道道 择扫寻寻 选盘的均 主恳皆3P-图5-55. 6扫描算法5.6. 1先向外扫描：输入3后，选择扫描算法，再输入1选择先向外扫描，如图5-6所示。（SSTF）先来先服务（FCFS） 霰規寻道时间优先 扫揃I度（scan） 退出界面0表:示向内12<1表示向外，74 88 19 15 156450拥7 4 - 6U 2 4 4 臂1 1 3动为； 移列度度 算羸道道 择入扫寻寻 选输盘的均 请请磁总平图

16、5-65.6.2先向里扫描：输入3后，选择扫描算法，再输入0选择先向里扫描，如图5-7所示。*1-先来先服务（FCFS）电.最短寻道时间优先（SSTF）*3-扫掖瘟匱（SCAN）网退出界面 请选择算法 3<1表示向外，0表示向内乂 0遠証入豈煎裕越管的移动的方向，.- 磁盘扫扌田序列为：19 15 15 12 27 50 60 64 74 88 总的寻道丧度 84平均寻道#度 8.4图5-75. 7退出程序输入4退出，如图5-8所示。*1-先来先服务(FCFS)*2 最短寻道時间优先(SSTF)*3.扫描谪度(SCAN)*4-退出界面XX1O< ME1CX ME1CX ME1CX

17、ME1CX ME1CX ME1CX MEJCX ME JCKX9J< MEJCX MEJCX MEJCX ME JCX)G3J<)G3J< X JCX X JCX X JCX X JCXX9C 请选择算法：4Press any kzy to continue.图5-8六、结论与体会这次操作系统的课程设计，从理论到实践，我学到很多很多的的东西，不仅 可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。 通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远 远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能 真正为社会服务，

18、从而提高自己的实际动手能力和独立思考的能力。本次实验首先要了解磁盘调度的工作原理及四种调度方法的工作原理。在课 程设计前的准备工作时，先把这部分工作做完了。在设计总的程序框架的时候， 要注意各功能模块的位置，尽量做到简洁、有序；各功能模块与主程序要正确衔 接。在设计的过程中遇到许多问题，我设计的是四种调度算法中的后两种。例如: 在最初程序设计时主要有两种构思：1）选用数据结构是链表的。2）选用数组。 我最初尝试了用链表，觉得方便易懂，但是在循环扫描处出现了些问题，后来乂 转变了设计思路，选用了数组，直接进行排序，然后再联系到各功能模块。至此，计算机操作系统课程设计算法己经完成。但由于这次设计的

19、时间比较仓促，其中不免会有些纱匕漏，在设计的过程中我也发现了自己的不足之处，对以前所学过的知识理解得不 够深刻，掌握得不够牢固，自身知识的很多漏洞，看到了自己的实践经验还是比 较缺乏，理论联系实际的能力还急需提高。比如说编语言掌握得不好，应用程序 编写不太会通过这次课程设计之后，一定把以前所学过的知识重新温故。在 此，也感谢在课程设计过程中帮我解惑的老师和同学。七. 参考文献1 汤小丹、汤子赢等.计算机操作系统.西安：西安电子科技人学出版社，2007.2 张丽芬.操作系统实验教程M.北京：清华大学出版社，2006.附件：源程序清单磁盘调度算法源程序清单#include<stdio.h&g

20、t;#include<stdlib.h> #include<iostieam.h>#include<math.h>存include <ctime>#defiiie maxsize 100mt decide(char str) /判断输入数据是否有效mt i=0;while(stri!='Or)if(stri<,0,|stri>'9,)return 0;break; return i;mt trans(char str,int a) /将字符串转换成数字mt sum=0;fbr(i=0:i<a;i-H-)sum=s

21、um+(mt)(stri-,0,)*pow(10.a-i-l); retuin sum;* 冒沁打t 岸符旳：*/mt *soH(int cidao.iiit m)mt ij;mt temp;for(i=0;i<m;i+) 使用冒泡法按从小到人顺序排列for(j=i+lj<m;j+) if(cidaoi>cidaoj) temp=cidaoi; cidaoi=cidaoj; cidaoj=temp;return cidao;void FCFS(iiit cidao,int m) /磁道号数组，个数为 m int now=20;当前磁道号mt sum=0; 总寻道长度float

22、 ave; /平均寻道长度cout«"磁盘请求序列为：”;for( i=0;i<m;i+) 按先来先服务的策略输出磁盘请求序列 cout«cidaoi«H ”;cout«endl;sum+=abs(cidao0-now); cout«"磁盘扫描序列为：”;for( i=0;i<m;i+) 输出磁盘扫描序列cout«cidaoi«H ”;fo】(i=Oj=lj<m;i+J+) /求平均寻道长度 sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float

23、)(m);cout«endl;cout«M总的寻道长度:,«sum«endl; cout«M平均寻道长度:,«ave«endl;void SSTF(int cidao.iiit m)mtk=l;mt now=20;mt Lr；mt ij,sum=0;float ave;cidao=son(cidaojn); 调用冒泡排序算法排序 if(cidaom-1 <=now) 若当前磁道号人于请求序列中最人者，则直接由外向内依次给予各请 求服务COU«磁盘扫描序列为：”;fbr(i=m-l ;i>=O;i)cou

24、t«cidaoi«,r ”；sum=now-cidao0;if(cidao0>=now) 若当前磁道号小T请求序列中最小者，则直接由内向外依次给予各请求 服务COU«磁盘扫描序列为：”;fbr(i=O:i<m;i+)cout«cidaoi«,r ”；sum=cidaom-1 -now;if(now>cidao0&&now<cidaom-l) /若当前磁道号人于请求序列中最小者且小于最人者cout«-磁盘扫描序列为：”；wlule(cidaok<noW) 确定当前磁道在已排的序列中的位置，后

25、面的算法都用到了，可以直 接复制后少量修改，节省时间。k卄；l=k-l;r=k;while(lA=O)&&(r<m) /当前磁道在请求序列范围内if(now-cidaol)<=(cidaor-now) /选择与当前磁道最近的请求给予服务cout«cidaol«M ”；sum+=now-cidaol;now=cidaol;1=1-1;elsecout«cidaor«M ”；sum+=cidaor-now;now=cidaor;r=r+l;lf(l=.l)/«头移动到序列的最小号，返回外侧扫描仍未扫描的磁道fbr(j=i

26、j<m;j-H-)cout«cidaoU«H ”；sum+=cidaom-1 -cidao0;else/磁头移动到序列的最大号，返回内侧打描仍未扫描的磁道for(j=l;j>=0;j-)cout«cidaoU«H ”；sum+=cidaom-1 -cidao0;ave=(float)(sum)/(float)(m);cout«endl;cout«"总的寻道长度:"«siim«endl;cout«"平均寻道长度：”ave«eiidl;严*扫描调 度算法*

27、*/void SCAN(iiit cidao,int m) /先要给出当前磁道号和移动臂的移动方向mt k=l;mt iiow=20;mt l,d;mt ij,sum=0;float ave;cidao=sort(cidao,m); 调用冒泡排序算法排序if(cidaom-1 <=now) 若当前磁道号人于请求序列中最人者，则直接由外向内依次给予各请 求服务，此情况同最短寻道优先coutvv”磁盘扫描序列为："fbr(i=m-l ;i>=0;i)cout«cidaoi«M ”；sum=now-cidao0;if(cidao0>=now) 若当前磁

28、道号小T请求序列中最小者,则直接由内向外依次给予各请求 服务，此情况同最短寻道优先coutvv”磁盘扫描序列为：" fbr(i=0:i<m:i+) cout«cidaoi«M ”；sum=cidaom-1 -now;if(now>cidao0&&now<cidaom-l) /若当前磁道兮人于请求序列中最小者且小于最人者while(cidaok <now)k+;l=k-l;r=k;cout«"请输入当前移动臂的移动的方向(1表示向外，0表示向内)："；ciii»d;if(d=O) 选择移

29、动臂方向向内，则先向内扫描cout«"磁盘扫描序列为：”；for(j=l;j>=0;j-)cout«cidaojv<"输出向内扫描的序歹!|for(j=rj<m;j-H-) 磁头移动到最小号，则改变方向向外扫描未打描的磁道cout«cidaojv<"输出向外扫描的序列sum=now-2 *cidao0+cidaom-l;else/选择移动臂方向向外，则先向外打描cout«"磁盘扫描序列为：”；fbr(j=ij<m;j-H-)cout«cidaojv<"输出向外

30、扫描的序歹!lfor(j=l;j>=0;j-) /磁头移动到最人号，则改变方向向内扫描未担描的磁道cout<<cidao|j<<" ”；sum=-now-cidao 0+2 *cidaom-l ;ave=(float)(sum)/(float)(m);cout«endl;cout«"总的寻道长度:"«sum«endl;cout«"平均寻道长度：”ave«eiidl;void mam()mt a.b;Ult c; 菜单项mt cidaomaxsize;mt i=0,count;char str!OO;cout«" * *欢迎进入磁盘调度算法* *"«endl;cout«M*l.随机产生*2.键盘输入*n«endl;cm»b;if(b=l)srand(unsigned)time(O);fbr( i=0;i<10;i+) cidaoi=randQ % maxsize;count=i; 要访问的磁道数cout«"随机产生的磁道序列为：”;fbr(i=0;i<co