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

1、成绩 课程设计报告 题 目 磁盘调度算法程序设计 课 程 名 称 操作系统课程设计 院 部 名 称 信息技术学院 专 业 计算机科学与技术 班 级 09级计算机科学与技术(2) 学 生 姓 名 学 号 课程设计地点 a206 课程设计学时 20 指 导 教 师 金陵科技学院教务处制一、课程设计的目的和要求磁盘是经常使用的一种重要的外设，对磁盘数据的寻道时间的长短直接影响机器的整体运行速度，本设计要求用c语言（或高级语言）编写程序模拟实现磁盘调度的常用算法。以加深对磁盘调度常用算法的理解和实现技巧。编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度，要求设计主界面以灵活选择某算法，且以下算

2、法都要实现：1、先来先服务算法（fcfs）2、最短寻道时间优先算法（sstf）3、扫描算法（scan）二、课程设计环境要求1、硬件环境lenovo 计算机，intel® pentium® dual e2180 2.00ghz 2.00ghz，0.99gb的内存2、软件环境microsoft visual studio 6.0软件，microsoft office软件，microsoft windows xp系统。三、设计任务介绍及系统需求分析 在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的

3、还要快，因此我们有必要为每个磁盘设备建立一个等待队列。四、概要设计系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（fcfs）、最短寻道时间优先算法（sstf）、扫描算法（scan）。1、先来先服务算法（fcfs）这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。2、最短寻道时间优先算法（sstf）该算

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

5、自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。本系统划分为三个模块：先来先服务算法模块void fcfs(int array,int m)、最短寻道时间优先算法模块void sstf(int array,int m)、扫描算法模块void scan(in

6、t array,int m) 系统模块调用关系图： 磁盘调度模拟系统退出先来先服务算法最短寻道时间优先扫描算法五、详细设计1、功能模块设计（1） 先来先服务算法模块：void fcfs(int cidao,int m)输入磁道号，按先来先服务的策略输出磁盘请求序列，求平均寻道长度，输出移动平均磁道数。主要代码：now=printnow(); /输入当前磁道号cout<<"磁盘扫描序列为：" for( i=0;i<m;i+) /输出磁盘扫描序列 cout<<cidaoi<<" " for(i=0,j=1;j<

7、m;i+,j+) /求平均寻道长度 sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m); fcfs算法流程图: 输入磁道号求平均寻道长度输出移动的平均磁道数按输入顺序将磁道序列输出开始结束 算法优点：简单公平，每个进程的请求都能得到依次的处理，不会出现每一进程的请求长期得不到满足的情况；算法缺点：没有对寻道优化，当访问磁道差距较大且访问频繁时，该算法会导致平均寻道长度、平均寻道时间过长，效率降低。（2） 最短寻道时间优先算法模块：void sstf(int cidao,int m)将磁道号用从小到大排序，输出排好序的磁道序列，输入当前磁道号

8、，根据前磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。主要代码：now=printnow(); /输入当前磁道号 if(cidaom-1<=now) /若当前磁道号大于请求序列中最大者， sum=printout(cidao,now,m); if(cidao0>=now) sum=printin(cidao,now,m); if(now>cidao0&&now<cidaom-1) /若当前磁道号大于请求序列中最小者且小于最大者 cout<<"磁盘扫描序列为：" while(cidaok&

9、lt;now) /确定当前磁道在已排的序列中的位置，后面的算法都用到了，可以直接复制后少量修改，节省时间。 k+; l=k-1; r=k; while(l>=0)&&(r<m) /当前磁道在请求序列范围内 if(now-cidaol)<=(cidaor-now) /先向磁道减少的方向访问 sum=prints(cidao, now,m, l, r); else sum=printl(cidao, now, m, l, r);sstf算法流程图: 求平均寻道长度选择与当前磁道距离最近的磁道进行扫描移动到最小（大）号，改向外（内）移动扫描未扫描的磁道输出移动的平均

10、磁道数输出排好序的磁道序列判断当前磁头在序列中的位置结束开始输入磁道号使用冒泡法从小到大排序输入当前磁道号 要求访问的刺刀是当前磁头所在的磁道最近；算法优点：单次寻道时间最短；算法缺点：当磁道调用集中再两端时平均寻道时间不一定最短，可能导致一些请求无限推延，发生“饥饿”现象。（3） 扫描算法模块：void scan(int cidao,int m)将磁道号用冒泡法从小到大排序，输出排好序的序列，输入当前磁道号，选择移动臂的移动方向，根据当前磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。主要代码：now=printnow(); /输入当前磁道号 cout<

11、;<"请输入当前移动臂的移动的方向 (1 表示向外 ，0表示向内) : " cin>>d; if(cidaom-1<=now&&d=0) /若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务,此情况同最短寻道优 sum=printout(cidao,now,m); if(cidaom-1<=now&&d=1) /若当前磁道号大于请求序列中最大者，则直接由内向外依次给予各请求服务,此情况同最短寻道优 sum=printin(cidao,now,m); if(cidao0>=now&&a

12、mp;d=0) /若当前磁道号小于请求序列中最小者，则直接由外向内依次给予各请求服务,此情况同最短寻道优先 sum=printout(cidao,now,m); if(cidao0>=now&&d=1) /若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务,此情况同最短寻道优先 sum=printin(cidao,now,m); if(now>cidao0&&now<cidaom-1) /若当前磁道号大于请求序列中最小者且小于最大者 while(cidaok<now) k+; l=k-1; r=k; cout<<

13、;"请输入当前移动臂的移动的方向 (1 表示向外 ，0表示向内) : " cin>>d; if(d=0) /先向磁道号减小方向访问 sum=prints(cidao, now,m, l, r); if(d=1) /先向磁道号增加方向访问 sum=printl(cidao, now,m, l, r); ave=(float)(sum)/(float)(m); scan算法流程图： 求平均寻道长度选择移动臂移动方向，开始扫描移动到最小（大）号，改向外（内）移动扫描未扫描的磁道输出移动的平均磁道数输出排好序的磁道序列开始结束输入磁道号使用冒泡法从小到大排序输入当前磁道

14、号判断当前磁头在序列中的位置该算法不仅考虑到访问的磁道与当前磁道的距离，更优先考虑磁头当前的移动方向。例如当磁道正在自里向外移动时，scan算法所考虑的下一个访问对象，应是既在当前磁道外，有事距离最近的待访问磁道，这样自里向外的访问，直到再无更外磁道需要访问时，才将磁臂换向为自外向里移动。同样也是每次选择这样的进程来调度，即在当前位置内最近待访问磁道，这样磁头又逐步向里移动，直到再无更内磁道要访问；算法优点：缩短时间，兼顾公平，避免“饥饿”现象；算法缺点：不仅要记住读写磁头的当前位置，还必须记住移动方向。2、数据结构设计 定义数组str,存放输入的数据。用stri表示输入的第i+1个数据，数组

15、cidao和str意义一样。全局变量m，表示磁道最大个数，now表示当前磁道号，全局变量sum和ave，表示总寻道长度和平均寻道长度。变量i和j，表示第i+1和j+1磁道，变量k表示任意磁道。变量d表示选择移动臂移动方向，有两个取值1表示向外，0表示向内。3、函数功能描述（1）decide()函数原型： int decide（）decide（）函数用于判断输入数据是否有效，判断str输入的数据在0-9之间。（2）trans（）函数原型：int trans（）trans（）函数用于将字符串转换成数字，转换将每个stri转换后相加，将结果保存为sum。（3）*bubble（）函数原型 int *b

16、ubble（）*bubble（）函数是冒泡排序算法，用来对磁道进行从小到大，函数定义temp用来数据交换。在比较过程中，前面到大于后面就交换。（4）printnow()函数原型int printnow()printnow()函数主要是当前磁道输入，把输入值作为now值。（5）printout（）函数原型int printout（）直接由外向内依次给予各请求服务，输出磁道序列。（6）printin（）函数原型int printin（）直接由内向外依次给予各请求服务，输出磁道序列。（7）prints（）函数原型 int prints（）先向磁道减小的方向，再向增加的方向，输出磁道序列（7）prin

17、tl（）函数原型 int printl（）先向磁道增加的方向，再向减小的方向，输出磁道序列（8）fcfs()函数原型：void fcfs（）fcfs（）函数是先来先服务调度算法，函数输出提示性文字，输出函数序列，调用decide（）对输入数据进行有效性判断。最后利用for结构语句，输出总寻道长度和平均寻道长度。(9) sstf()函数原型 ：void sstf（）sstf（）函数是最短寻道时间优先调度算法，该函数调用函数bubble（），对磁道进行排序，函数从离当前磁道最短距离开始扫描。实现对最短寻道优先调度。同时函数会调用decide（）对输入数据进行判断。调用trans（）将结果赋给now

18、变量。(10) scan()函数原型：void scan()scan()函数是电梯算法，调用bubble（）函数，对磁道序列排序，调用decide（）对数据进行有效性判断，利用变量d选择磁头移动方向。（11）main（）函数原型：void main（）main（）函数是此次课设的主函数，主函数调用各个算法，实现课设各个算法的功能。六、调试过程1先来先服务调度(fcfs)输入磁道寻找范围序列234，输入磁道调度序列的个数12，产生随机磁道序列，选择磁道调度算法1，输入当前的磁道号：52。运行结果图：2、最短寻道时间优先调度(sstf) 选择算法2后，确认后，排序后的磁盘序列为：12 16 41

19、46 52 58 65 89 108 128 215 215，输入当前磁道号41.运行结果图：输入当前的磁道号：10。运行结果图：3扫描调度算法(scan) 选择算法3后，确认后，排序后的磁盘序列为：12 16 41 46 52 58 65 89 108 128 215 215，输入当前磁道号10.运行结果图：输入当前移动臂的移动的方向（1 表示向外，0 表示向内）,输入0，运行结果图若输入当前磁道号255，输入当前移动臂的移动的方向（1 表示向外，0 表示向内）,输入0，运行结果图若当前磁道输入为：255，输入当前移动臂的移动的方向（1 表示向外，0 表示向内）,入1，运行结果图输七、结论与

20、体会通过此次课程设计的实践，要把书本上的知识转换为现实中的成果，创新与不懈的努力是成功的重要因素。如果没有一定的耐心，这次的课程设计不能成功。 “磁盘调度”是我本学期操作系统课程设计的题目。在设计此程序的过程中，我遇到过许多问题，也学到了很多东西。本程序的设计实现主要是用c+语言实现，通过对程序算法的设计优化、输出显示的格式设计、输入过程中的异常处理等一些设计过程中的问题的考虑解决，在c+学习上也有了很大的进步。在程序设计中先后参考了很多网络资料，也参考了一些别人写的的程序，综合这些算法思想和自己的思路对程序做了很好的设计方式，对一些算法的优越性等也作了一些考虑。此外考虑最多的就是异常错误处理

21、的设计。在设置程序的显示优化时，发现暂停函数在不同的情况下执行顺序不同，如此等等。整个设计中最麻烦的就是整个程序模块的划分和各模块之间接口设计，编程中经常犯想当然的错误，编程中出现了不少奇怪的错误。再调试中尝试使用了分割法,对错误模块进行定位,再进行排查.课程设计的理论难度并不大，但是若要深入发掘其中的东西，并且实际去编程实现，就遇到了相当大的难度。因为与之涉及的很多方面并没有学过，需要自己去自学和实践检验。，通过模拟磁盘调度及进程排队算法来加深对操作系统中各个磁臂调度算法概念的理解。模拟磁盘调度算法(fcfs,sstf,scan,cscan)，实现各种不同调度算法的过程，并计算各算法的平均寻

22、道长度，以便于我们判断各种算法的优劣以及各种算法使用的      至此，计算机操作系统课程设计算法已经完成。此次设计基本完成了所规定的功能，但由于这次设计的时间比较仓促，其中不免会有些纰漏，比如在程序的实现上还不够严谨，出错处理不够完善等多方面问题，这些都有进一步改善。由于平时上课不是很认真许多概念没有理解清楚，导致在做设计时有点无从下手的感觉，只好边实验边看书直到弄懂概念后才开始做设计导致时间有点紧张，最终在同学和老师的指导下我完成了设计，此设计基本能够实现规定的要求但是还是不够完善，很多东西做的不够好，程序不够完善和严谨。此次课程设计中我学

23、到了很多东西，无论在理论上还是实践中，都得到不少的提高，这对于我以后的工作和学习都有一种巨大的帮助。参考文献：计算机操作系统(修订版) 汤子瀛 西安电子科技大学出版社 操作系统教程 方敏编 西安电子科技大学出版社 操作系统实用教程 任爱华 清华大学出版社 操作系统原理与实践教程  周湘贞、曾宪权 清华出版社 程序设计基础教程 陈家骏 机械工业出版社 c语言程序设计 田祥宏 西安电子科技大学出版社 c+语言程序设计 郑莉 、董源 清华大学出版社附件：程序源代码 #include<stdio.h>#include<stdlib.h>#include<iost

24、ream.h>#include<math.h>#define maxsize 1000/*判断输入数据是否有效*/int decide(char str) /判断输入数据是否有效 int i=0;while(stri!='0') if(stri<'0'|stri>'9')return 0;break;i+; return i; /*将字符串转换成数字*/int trans(char str, int a) /将字符串转换成数字int i;int sum=0;for(i=0;i<a;i+)sum=sum+(int

25、)(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<<cidao

26、i<<" " cout<<endl; return cidao;/*当前磁道输入*/ int printnow() char str10; int a,now; cout<<"请输入当前的磁道号：" a: cin>>str; a=decide(str); if(a=0) cout<<"输入数据的类型错误,请重新输入！"<<endl; goto a; else now=trans(str,a); return now; /*直接由外向内依次给予各请求服务*/ int

27、 printout(int cidao,int now,int m) int i; int sum=0; cout<<"磁盘扫描序列为：" for(i=m-1;i>=0;i-) cout<<cidaoi<<" " sum+=abs(now-cidaoi); now=cidaoi; return sum; /*直接由内向外依次给予各请求服务*/ int printin(int cidao,int now,int m) int i; int sum=0; cout<<"磁盘扫描序列为："

28、; for(i=0;i<m;i+) cout<<cidaoi<<" " sum+=abs(cidaom-1-now); now=cidaoi; return sum; /*先向磁道减小的方向，再向增加的方向*/ int prints(int cidao,int now,int m,int l,int r) int j; int sum=0; while(l>=0) cout<<cidaol<<" " sum+=now-cidaol; now=cidaol; l=l-1; now=cidao0;

29、for(j=r;j<m;j+) cout<<cidaoj<<" " sum+=cidaoj-now; now=cidaoj; return sum; /*先向磁道增加的方向，再向减小的方向*/int printl(int cidao,int now,int m,int l,int r)int j; int sum=0; while(r<m) cout<<cidaor<<" " sum+=cidaor-now; now=cidaor; r=r+1; now=cidaom-1; for(j=l;j&

30、gt;=0;j-) cout<<cidaoj<<" " /输出磁盘调度序列 sum+=now-cidaoj; now=cidaoj; return sum;/*先来先服务调度算法*/void fcfs(int cidao,int m) /磁道号数组，个数为m int now; float sum=0; /总寻道长度 int j,i; float ave; cout<<"磁盘请求序列为：" for( i=0;i<m;i+) /按先来先服务的策略输出磁盘请求序列 cout<<cidaoi<<&

31、quot; " cout<<endl; now=printnow(); /输入当前磁道号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<<"平均寻道长度："<

32、<ave<<endl;/*最短寻道时间优先调度算法*/void sstf(int cidao,int m) int k=1; int now,l,r; int sum; float ave; cidao=bubble(cidao,m); /调用冒泡排序算法排序 now=printnow(); /输入当前磁道号 if(cidaom-1<=now) /若当前磁道号大于请求序列中最大者， sum=printout(cidao,now,m); if(cidao0>=now) /若当前磁道号小于请求序列中最小者， sum=printin(cidao,now,m); if(n

33、ow>cidao0&&now<cidaom-1) /若当前磁道号大于请求序列中最小者且小于最大者 cout<<"磁盘扫描序列为：" while(cidaok<now) /确定当前磁道在已排的序列中的位置，后面的算法都用到了，可以直接复制后少量修改，节省时间。 k+; l=k-1; r=k; if(now-cidaol)<=(cidaor-now) /先向磁道减少的方向访问,zai向磁道增加的方向访问 sum=prints(cidao, now,m, l, r); else /先向磁道增加的方向访问，再向磁道减少的方向访问

34、sum=printl(cidao, now, m, l, r); ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均寻道长度： "<<ave<<endl;/*扫描调度算法*/void scan(int cidao,int m) /先要给出当前磁道号和移动臂的移动方向 int k=1; int now,l,r,d; int sum; float ave; cidao=bubble(cidao,m); /调用冒泡排序算法排序 now=printnow(); /输入当前磁道号 cou

35、t<<"请输入当前移动臂的移动的方向 (1 表示向外 ，0表示向内) : " cin>>d; if(cidaom-1<=now) /若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务,此情况同最短寻道优 sum=printout(cidao,now,m); if(cidao0>=now) /若当前磁道号小于请求序列中最小者，则直接由外向内依次给予各请求服务,此情况同最短寻道优先 sum=printin(cidao,now,m); if(now>cidao0&&now<cidaom-1) /若当前

36、磁道号大于请求序列中最小者且小于最大者 while(cidaok<now) k+; l=k-1; r=k; if(d=0) /先向磁道号减小方向访问 sum=prints(cidao, now,m, l, r);if(d=1) /先向磁道号增加方向访问 sum=printl(cidao, now,m, l, r); ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均寻道长度： "<<ave<<endl;/*主函数*/void main() int a; int c; /菜单项 int cidaomaxsize; int i=0; int m,n; char str10; cout<<"输入寻找的范围："<<endl; cin >>m; if(m>65536) cout<<"输入数据超出范围,请重新输入！"<<endl;cout<<"输入磁盘调度序列的个数: