模拟磁盘调度算法操作系统课程设计

1、某某大学课程设计报告操作系统课程名称:设计题目：模拟磁盘调度算法系 别：计算机系专 业：计算机科学与技术组 别：学生姓名：学 号:起止日期：指导教师：目录第一章 需求分析 11.1 课程设计的简介 11.2 课程设计的目的 11.3 磁盘调度主要思想 11.4 课程设计内容 2第二章 概要设计 32.1 设计思想 32.2 数据结构 32.3 模块调用关系图 32.4 子模块程序流程图 5第三章 详细设计 63.1 模块划分 6第四章 代码测试 94.1 先来先服务 94.1 最短寻道时间优先 114.1 扫描算法 12第五章 心得体会 13第六章 致谢 13参考文献 13附源代码 1第一章

2、需求分析1.1 课程设计的简介这是一个用VC+6.0为工具、C+为编程语言而实现模拟先来先服务算法（FCFS、最短寻道时间优先算法（SSTF、扫描算法（SCAN的一个磁盘调度程 序。该程序设计系统主界面可以灵活选择某种算法并算出磁头移动的总磁道数以 及平均磁道数。1.2 课程设计的目的本课程设计的目的是通过设计一个磁盘调度模拟系统， 从而使磁盘调度算法 更加形象化，容易使人理解， 使磁盘调度的特点更简单明了， 能使使用者加深对 先来先服务算法（FCFS、最短寻道时间优先算法（SSTF、扫描算法（SCAN等 磁盘调度算法的理解。1.3 磁盘调度主要思想 设备的动态分配算法与进程调度相似，也是基于

3、一定的分配策略的。常用的分配策略有先请求先分配、 优先级高者先分配等策略。 在多道程序系统中， 低效 率通常是由于磁盘类旋转设备使用不当造成的。 操作系统中，对磁盘的访问要求 来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直 接影响磁盘的工作效率， 进而影响系统的性能。 访问磁盘的时间因子由 3 部分构 成，它们是查找（查找磁道） 时间、等待（旋转等待扇区） 时间和数据传输时间， 其中查找时间是决定因素。 因此，磁盘调度算法先考虑优化查找策略， 需要时再 优化旋转等待策略。平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道 数（N）,即： L=（M1+M2

4、十+Mi+MN /N。其中Mi为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时, 要把移动臂移动到指定的柱面, 再等待指定 扇区的旋转到磁头位置下,然后让指定的磁头进行读写,完成信息传送。因此, 执行一次输入输出所花的时间有：寻找时间磁头在移动臂带动下移动到指定柱面所花的时间延迟时间指定扇区旋转到磁头下所需的时间。 传送时间由磁头进程读写完成信息传送的时间。 其中传送信息所花的时间， 是在硬件设计就固定的。 而寻找时间和延迟时间 是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间， 每个文件的信息不是按盘面上的磁道 顺序存放满一个盘面后， 再放到下一个盘面上。 而是按柱

5、面存放， 同一柱面上的 各磁道被放满信息后， 再放到下一个柱面上。 所以各磁盘的编号按柱面顺序 （从 0 号柱面开始），每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。1.4 课程设计内容 系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF、扫描算法（SCA）并计算及比较磁头移动总磁 道数和平均磁道数。1.4.1 、先来先服务算法（ FCFS、 这是一种比较简单的磁盘调度算法。 它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不 会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道

6、进行优化， 在对磁盘的访问请求比较多的情况下， 此算法将降低设备服务的吞吐量， 致使平 均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。1.4.2 、最短寻道时间优先算法（ SSTF、 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短， 该算法可以得到比较好的吞吐量， 但却不能保证 平均寻道时间最短。 其缺点是对用户的服务请求的响应机会不是均等的， 因而导 致响应时间的变化幅度很大。 在服务请求很多的情况下， 对内外边缘磁道的请求 将会无限期的被延迟，有些请求的响应时间将不可预期。1.4.3 、扫描算法（ SCAN、 扫描算法不仅考虑到欲

7、访问的磁道与当前磁道的距离， 更优先考虑的是磁头的当前移动方向。 例如，当磁头正在自里向外移动时， 扫描算法所选择的下一个 访问对象应是其欲访问的磁道既在当前磁道之外， 又是距离最近的。 这样自里向 外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时， 同样也是每次选择这样的进程来调度， 即其要访问的磁道， 在当前磁道之内， 从 而避免了饥饿现象的出现。 由于这种算法中磁头移动的规律颇似电梯的运行， 故 又称为电梯调度算法。 此算法基本上克服了最短寻道时间优先算法的服务集中于 中间磁道和响应时间变化比较大的缺点， 而具有最短寻道时间优先算法的优点即 吞吐量较大， 平均响应时间

8、较小， 但由于是摆动式的扫描方法， 两侧磁道被访问 的频率仍低于中间磁道。第二章 概要设计2.1 设计思想本次课程设计我们是以面向对象的思想为主，利用 Visual C 为工具实 现模拟磁盘调度。程序主要是利用冒泡排序函数、FCFS函数、SSTF函数、SCAN函数、CSCA函数实现函数的功能。禾U用菜单式的选择界面，方便的用户操作。 最终对每一种模拟磁盘调度输出磁头平均移动的磁道数以及总磁道数。2.2 数据结构该程序主要是利用7个函数。Panduan ()函数：对输入的字符进行判断是否合法，zhuanhua ()函数：对输入合法的字符进行转化，bubble ()函数：对 输入的磁道进行冒泡排序

9、，FCFS()函数，即先来先服务函数，SSTF()函数： 最短最短寻道时间函数，SCAN()函数：扫描函数，CSCAN )函数：循环扫描 函数。各函数之间有点可以相互调用，共同实现要求。本程序主要用到的数据结构为数组、字符串，包括对字符串的合法性判断， 利用数组算磁头移动的总磁道数，平均移动磁道数。2.3 模块调用关系图图2-1磁盘调度模拟系统2.4子模块程序流程图先来先服务算法（FCFS流程图：FCFS算法流程图-开始输入磁道号按输入顺序将 序列输岀与磁道求平均寻道长度"动平输岀移动旳平 道数L均磁1结束最短寻道时间优先算法（SSTF）流程图243扫描算法(SCAN流程图开始输入磁

10、道号调用冒泡排序函数SCAN 算法流程图输出排好序的磁道一 序列 输入当前磁道号判断当前磁头在序 列中的位置选择与当前磁道距离最近 的磁道进行扫描移动到最小(人丿号，改向外"(内)移动扫描未扫描的磁道1求平均寻道长度求总寻道长度结束第三章详细设计3.1模块划分本系统划分为四个模块：先来先服务算法模块int FCFS(i nt array,i ntm)、最短寻道时间优先算法模块int SSTF(int array,int m)、扫描算法模块int SCAN(int array,int m)3.1.1 先来先服务算法模块：int FCFS(i nt array,i nt m)输入磁道号，

11、按先来先服务的策略输出磁盘请求序列，求平均寻道长度，输出移动平均磁道数。主要代码：for(i=0,j=1;j<m;i+,j+)sum+=abs(arrayj-arrayi);ave=(float)(sum)/(float)(m);3.1.2 最短寻道时间优先算法模块：int SSTF(i nt array,i nt m)将磁道号用冒泡法从小到大排序， 输出排好序的磁道序列， 输入当前磁道号，根据前磁道在已排的序列中的位置， 动的平均磁道数。主要代码： for(i=0;i<m;i+) /*for(j=i+1;j<m;j+)if(arrayi>arrayj)temp=arr

12、ayi;arrayi=arrayj;arrayj=temp;if(arraym-1<=now) /*大者，则直接由外向内依次给予各请求服务 for(i=m-1;i>=0;i-)cout<<arrayi<<" "sum=now-array0;elseif(array0>=now) /*小者，则直接由内向外依次给予各请求服务while(l>=0)&&(r<m) /*选择扫描的顺序， 求出平均寻道长度， 输出移使用冒泡法按从小到大顺序排列 */若当前磁道号大于请求序列中最*/if(now-arrayl)<

13、=(arrayr-now) /*若当前磁道号小于请求序列中最*/当前磁道在请求序列范围内 */选择与当前磁道最近的请求给予服务 */cout<<arrayl<<" "sum+=now-arrayl;now=arrayl;l=l-1;3.1.3 扫描算法模块： int SCAN(int array,int m) 将磁道号用冒泡法从小到大排序， 输出排好序的序列， 输入当前磁道号， 选 择移动臂的移动方向，根据当前磁道在已排的序列中的位置，选择扫描的顺序， 求出平均寻道长度，输出移动的平均磁道数。主要代码： if(d=0) /* 选择移动臂方向向内，则先

14、向内扫描 */for(j=l;j>=0;j-)cout<<arrayj<<" " /* 输出向内扫描的序列 */for(j=r;j<m;j+) /*磁头移动到最小号， 则改变方向向外扫描未扫描的磁道*/cout<<arrayj<<" " /* 输出向外扫描的序列 */sum=now-2*array0+arraym-1;else /* 选择移动臂方向向外，则先向外扫描 */for(j=r;j<m;j+)cout<<arrayj<<" " /* 输出

15、向外扫描的序列 * 、/* 磁头移动到最大号， 则改变方向向内for(j=l;j>=0;j-)扫描未扫描的磁道*/coutvvarrayjvv""sum=-no w-array0+2*arraym-1;ave=(float)(sum)/(float)(m);第四章测试4.1先来先服务算法输入磁道序列：65 78 34 23 87 100 18 26当前磁道号：80磁盘扫描序列为：65 78 34 23 87 100 18 26平均寻到长度：31.25磁头移动总磁道数：2504.2最短寻道时间优先算法(1)当前磁道号大于磁道序列中的最大的磁道号时3243d 07 55

16、232430?88砧口础-2. :道.31数 为磁为列的列蠱 序前序舌心 求当描道动 盘聾均头输入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列为：18 23 26 34 65 78 87 100当前磁道号：200磁盘扫描序列为100 87 78 65 34 26 23 18平均寻到长度：22.75磁头移动总磁道数：182001?887564362328132624356000 0 712 8为号10 列道* 農为：道 盘的列脣 磁前序養 的当描道动 后入扫書(2)当刖磁道号小于磁道序列中的最小的磁道号时输入磁道序列：65 78 34 23 87 100 18 26

17、排序后的磁道序列为：18 23 26 34 65 78 87 100当前磁道号：10磁盘扫描序列为：18 23 26 34 65 78 87 100平均扫描长度：11.25磁道移动总磁道数：90436232 5 02 9 为号1B1-: 列道：丄教 蛊为希 盘的列富 磁前序 的当描道动 后入扫一62328 01 134 65 78 8765 78 87 100100(3)当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号时输入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列为：18 23 26 34 65 78 87 100当前磁道号：80磁盘扫描序列为：78 8

18、7 100 65 34 26 23 18平均扫描长度：13.25磁道移动总磁道数：106I!二盘的列匮 磁前序舌心 的当描道动 后入扫書均头为号78洌道.:18 23 ；8087 1002510634 6587 10034 26 23 1S4.3扫描算法(1)当前磁道号大于磁道序列中的最大的磁道号时输入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列为：18 23 26 34 65 78 87 100当前磁道号：200磁盘扫描序列为100 87 78 65 34 26 23 18平均寻到长度：22.75磁头移动总磁道数：182(2)当前磁道号小于磁道序列中的最小的磁道

19、号时输入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列为：18 23 26 34 65 78 87 100当前磁道号：10磁盘扫描序列为：18 23 26 34 65 78 87 100平均扫描长度：11.25磁道移动总磁道数：90序后的磁盘序列为 18 23 26 34 65 78 87 100 输入当前苗磁道号0盘扫描序列为】18 23 26 34 65 78 87 100(3)当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号(磁头向外)时输入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列为：18 23 26 34 65 78

20、87 100当前磁道号：80请输入当前移动臂的移动的方向(1表示向外，0表示向内)：1磁盘扫描序列为：87 100 78 65 34 26 23 18平均寻到长度：12.75磁道移动总磁道数：1023向65方?80力08 0 2 移丄7516 为口咼872. 列道臂：丄数 霍动为，道 一盘的移列蠱 礒煎刖序舌心 的当当描道动 、/FI入入扫睦 一 头62328i34 65 78 87 100<1表示向外，®表示向内：134 26 23 18O为聶 盘阿列專 前序首 的当描道动 后入扫一 葫为号87列道-t 18 :801002S231826 34 佔?8 87 10023 26

21、 34 65 78请选择算法，5Press any key to cont inuej. i*n *第五章 心的体会通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学好不 仅仅是要把书上的基本知识学好而且还要不断进行实践， 将所学的跟实践操作结 合起来才能更好地巩固所学，才能提高自己实践能力 . 通过这次的设计使我认识 到只停留在表面理解问题是很难使问题得到很好的解决的， 实践能力与理论知识 同样重要。可以说此课程设计的理论难度并不大， 但是若要深入发掘其中的东西， 并且实际去编程实现， 就遇到了相当大的难度。 因为与之涉及的很多方面并没有 学过，需要自己去自学和实践检验。通过本次课

22、程设计，通过模拟磁盘调度及进程排队算法来加深对操作系统中 各个磁臂调度算法概念的理解。模拟磁盘调度算法（FCFS,SSTF,SCAN,CSCAN实 现各种不同调度算法的过程， 并计算各算法的平均寻道长度， 以便于我们判断各 种算法的优劣以及各种算法使用的场合。对 VC+6.0的应用也更加得心应手。第六章 致谢感谢陕粉丽老师和本组成员在这次系统开发过程中对我的帮助参考文献1 计算机操作系统 高等教育出版社，作者：孙钟秀，费翔林，骆斌 等编著2 VC+深入详解 电子工业出版社作者：孙鑫，余指导教师评语：指导教师签名：年月日成绩 评 疋项目权重成绩1、设计过程中出勤、学习态度等方面0.12、设计技术

23、水平0.43、安全程度及可操作程度0.24、设计报告书写及图纸规范程度0.3总成绩教研室审核意见：教研室主任签字：年月日教学院（系）审核意见：主任签字：年月日附源代码#include<stdio.h>#include<stdlib.h>#include<iostream.h>#include<math.h> const int maxsize=1000;int panduan(char str);int zhuanhua(char str,int a);int *bubble(int cidao,int m);int FCFS(int cidao

24、,int m);void SSTF(int cidao,int m);void SCAN(int cidao,int m);int main()int a;int c;int cidaomaxsize;int i=0,count;char str100;cout<<" 请输入磁道序列( 0 结束)： "<<endl; bei1:cin>>str;a=panduan(str);if(a=0)"<<endl;"<<endl;cout<<" 输入数据的类型错误 ,请重新输入！ g

25、oto bei1;elsecidaoi=zhuanhua(str,a);i+;while(cidaoi-1!=0)cin>>str;a=panduan(str);if(a=0)cout<<" 输入数据的类型错误 ,请重新输入！ else cidaoi=zhuanhua(str,a); i+; count=i-1; cout<<" 你输入的磁道序列为： " for(i=0;i<count;i+)cout<<cidaoi<<" " cout<<endl; while(1)

26、 cout<<endl;cout<<"|"<<endl;cout<<"|(*A_A*)系统菜单(*A_A*)|"<<endl;cout<<"|"<<endl;cout<<"|"<<endl;cout<<"|1. 先来先服务|"<<endl;cout<<"|"<<endl;cout<<"|2. 最短寻道

27、时间优先|"<<endl;cout<<"|"<<endl;cout<<"|3. 扫描调度|"<<endl;cout<<"|"<<endl;cout<<"|4. 退出|"<<endl;cout<<"|"<<endl;cout<<"|"<<endl;cout<<"|"<<e

28、ndl;bei7:cout<<" 请选择算法：bei6:cin>>str;a=panduan(str);if(a=0)cout<<" 输入数据的类型错误 ,请重新输入！ "<<endl; goto bei6;elsec=zhuanhua(str,a);if(c=5)break;if(c>5)cout<<" 数据输入错误！请重新输入 "<<endl; goto bei7;switch(c)case 1:FCFS(cidao,count); break;case 2:SS

29、TF(cidao,count); break;case 3:SCAN(cidao,count); break; return 0;/*判断输入数据是否有效 */ int panduan(char str) int i=0;while(stri!='0')if(stri<'0'|stri>'9') return 0; break;i+; return i;/*将字符串转换成数字 */int zhuanhua(char str,int a)int i;int sum=0; for(i=0;i<a;i+) sum=sum+(int)(

30、stri-'0')*pow(10,a-i-1);return sum;*冒泡排序算法 *int *bubble(int cidao,int m)int i,j;int temp;for(i=0;i<m;i+)for(j=i+1;j<m;j+)if(cidaoi>cidaoj)temp=cidaoi;cidaoi=cidaoj; cidaoj=temp;cout<<" 排序后的磁盘序列为：for( i=0;i<m;i+)cout<<cidaoi<<" "cout<<endl;re

31、turn cidao;/*先来先服务调度算法 */int FCFS(int cidao,int m) int now;int sum=0;int j,i;int a;char str100;float ave;cout<<" 磁盘请求序列为： "for( i=0;i<m;i+) cout<<cidaoi<<" "cout<<endl;cout<<" 请输入当前的磁道号： "bei2: cin>>str;a=panduan(str);if(a=0)cout&l

32、t;<" 输入数据的类型错误 ,请重新输入！ "<<endl; goto bei2;elsenow=zhuanhua(str,a);sum+=abs(cidao0-now);cout<<" 磁盘扫描序列为： "for( i=0;i<m;i+)cout<<cidaoi<<" "for(i=0,j=1;j<m;i+,j+)sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m);cout<<endl;cout<

33、;<" 平均寻道长度： "<<ave<<endl;cout<<" 磁头移动总磁道数： "<<sum<<endl; return 0;*最短寻道时间优先调度算法 */void SSTF(int cidao,int m) int k=1;int now,l,r;int i,j,sum=0;int a; char str100; float ave;cidao=bubble(cidao,m);cout<<" 请输入当前的磁道号： " bei3: cin>&g

34、t;str;a=panduan(str);if(a=0)cout<<" 输入数据的类型错误 ,请重新输入！ "<<endl; goto bei3;elsenow=zhuanhua(str,a);if(cidaom-1<=now)cout<<" 磁盘扫描序列为：for(i=m-1;i>=0;i-)cout<<cidaoi<<" "sum=now-cidao0; if(cidao0>=now)cout<<" 磁盘扫描序列为： " for(i

35、=0;i<m;i+) cout<<cidaoi<<" " sum=cidaom-1-now; if(now>cidao0&&now<cidaom-1)cout<<" 磁盘扫描序列为： " while(cidaok<now)k+; l=k-1; r=k;while(l>=0)&&(r<m) if(now-cidaol)<=(cidaor-now) cout<<cidaol<<" " sum+=now-ci

36、daol; now=cidaol;l=l-1;else cout<<cidaor<<" " sum+=cidaor-now; now=cidaor; r=r+1; if(l=-1) for(j=r;j<m;j+) cout<<cidaoj<<" " sum+=cidaom-1-cidao0;elsefor(j=l;j>=0;j-)cout<<cidaoj<<" " sum+=cidaom-1-cidao0;ave=(float)(sum)/(float)(m);cout<<endl;cout<<" 平均寻道长度： "<<ave<<endl; cout<<" 磁头移动总磁道数： "<<sum<<endl;*扫