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

1、操作系统课程设计磁盘调度算法实践系 院： 信息工程学院学生姓名：耿万德 学 号：0934110135专 业：计算机科学与技术年 级：计科0901b完成日期：2011年12月指导教师：刘栓属性职务姓名学号班级组长耿万德0934110135计科0901b副组长梁光彩0934110149计科0901b成员杨少钶0943110114计科0901b一、课程设计的性质与任务1、加深对磁盘调度算法的理解，通过编程模拟不同磁盘调度算法的流程。2、培养学生能够独立进行知识综合，独立开发较大程序的能力。3、培养提高学生软件开发能力和软件的调试技术。4、培养学生开发大型程序的方法和相互合作的精神。5、培养学生的创新

2、意识。6、培养学生的算法设计和算法分析能力。7、培养学生对问题进行文字论述和文字表达的能力。二、课程设计的内容及其要求1、可利用先来先服务算法（fcfs即first come first served）、最短寻道时间优先算法（sstf即shortest seek time first）、扫描算法（scan）、循环扫描算法（cscan），来实现磁盘的访问顺序。2、根据磁盘调度算法的不同的特性做好软件实现的需求分析。3、可根据问题的实际需要，可模拟数据在磁道的存放位置。4、当系统运行时，能直观地、动态地反映当前磁盘状态及不同算法的平均寻道时间。5、要求在系统安全状态的前提下，用户指定需要访问的磁道

3、，软件自动模拟在不同算法情况下，磁盘寻道顺序和平均寻道时间。三、课程设计的时间安排 课程设计总时间：8学时四、课程设计的实验环境硬件环境：cpu intel(r) core2 duo e4600 2.40ghz，内存 ddr2 1.00gb，硬盘 7200转 160g ，光驱 16x dvd 软件环境：windows xp sp sp3, visual c+ 6.0 五、正文1、 实验程序的结构图（流程图）；先来先服务算法（fcfs）流程图:输入磁道号求平均寻道长度输出移动的平均磁道数按输入顺序将磁道序列输出开始结束 最短寻道时间优先算法（sstf）流程图: 求平均寻道长度选择与当前磁道距离最

4、近的磁道进行扫描移动到最小（大）号，改向外（内）移动扫描未扫描的磁道输出移动的平均磁道数输出排好序的磁道序列判断当前磁头在序列中的位置结束开始输入磁道号使用冒泡法从小到大排序输入当前磁道号扫描算法（scan）流程图：求平均寻道长度选择移动臂移动方向，开始扫描移动到最小（大）号，改向外（内）移动扫描未扫描的磁道输出移动的平均磁道数输出排好序的磁道序列开始结束输入磁道号使用冒泡法从小到大排序输入当前磁道号判断当前磁头在序列中的位置循环扫描算法（cscan）流程图：求平均寻道长度扫描到最大号后，直接移动到最小号从内向外扫描未扫描的磁道输出移动的平均磁道数输出排好序的磁道序列判断当前磁头在序列中的位置

5、规定移动臂单向反复的从内向外扫描开始结束输入磁道号使用冒泡法从小到大排序输入当前磁道号2、数据结构及信号量定义的说明；本系统划分为四个模块：先来先服务算法模块void fcfs(int array,int m)、最短寻道时间优先算法模块void sstf(int array,int m)、扫描算法模块void scan(int array,int m) 和循环扫描算法模块：void cscan(int array,int m) 。1 先来先服务算法模块：void fcfs(int array,int m)输入磁道号，按先来先服务的策略输出磁盘请求序列，求平均寻道长度，输出移动平均磁道数。2 最

6、短寻道时间优先算法模块：void sstf(int array,int m)将磁道号用冒泡法从小到大排序，输出排好序的磁道序列，输入当前磁道号，根据前磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。3 扫描算法模块：void scan(int array,int m)将磁道号用冒泡法从小到大排序，输出排好序的序列，输入当前磁道号，选择移动臂的移动方向，根据当前磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。4 循环扫描算法模块：void cscan(int array,int m)将磁道号用冒泡法从小到大排序，输出排好序的序列

7、，输入当前磁道号，规定移动臂单向反复的从内向外移动，根据当前磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。3、实验的步骤；输入的磁道序列为：12 4 54 7 23 452 141 162 354 21 471 256 45 11 25 3 689 5 241 先来先服务算法当前磁道号：任意（这里取25）平均寻道长度：197.6322 最短寻道时间优先算法（1）当前磁道号大于磁道序列中的最大的磁道号时当前磁道号：890平均寻道长度:46.6482（2）当前磁道号小于磁道序列中的最小的磁道号时当前磁道号：1平均寻道长度：36.2105（3）当前磁道号大于磁道序

8、列中的最小的磁道号且小于最大磁道号时 当前磁道号：255平均寻道长度：49.47373 扫描算法（1）当前磁道号大于磁道序列中的最大的磁道号时当前磁道号：890平均寻道长度:46.6842（2）当前磁道号小于磁道序列中的最小的磁道号时当前磁道号：1平均寻道长度:36.2105（3）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号（磁头向外）时当前磁道号：255平均寻道长度:58.9474（4）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号（磁头向内）时当前磁道号：255平均寻道长度:49.36844 循环扫描算法（1）当前磁道号大于磁道序列中的最大的磁道号时当前磁道号：890平均

9、寻道长度:82.7895（2）当前磁道号小于磁道序列中的最小的磁道号时当前磁道号：1平均寻道长度:36.2105（3）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号时当前磁道号：100平均寻道长度:67.31584、实验源程序关键算法；1先来先服务算法模块：void fcfs(int array,int m)主要代码：for(i=0,j=1;j<m;i+,j+) sum+=abs(arrayj-arrayi); ave=(float)(sum)/(float)(m);2 最短寻道时间优先算法模块：void sstf(int array,int m)主要代码：for(i=0;i&l

10、t;m;i+) /*使用冒泡法按从小到大顺序排列*/for(j=i+1;j<m;j+) if(arrayi>arrayj) temp=arrayi; arrayi=arrayj; arrayj=temp; if(arraym-1<=now) /*若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务*/ for(i=m-1;i>=0;i-) cout<<arrayi<<" " sum=now-array0;else if(array0>=now) /*若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各

11、请求服务*/ while(l>=0)&&(r<m) /*当前磁道在请求序列范围内*/ if(now-arrayl)<=(arrayr-now) /*选择与当前磁道最近的请求给予服务*/ cout<<arrayl<<" " sum+=now-arrayl; now=arrayl; l=l-1; 3 扫描算法模块：void scan(int array,int m)主要代码：if(d=0) /*选择移动臂方向向内，则先向内扫描*/ for(j=l;j>=0;j-) cout<<arrayj<<

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

13、的磁道*/ cout<<arrayj<<" " sum=-now-array0+2*arraym-1; ave=(float)(sum)/(float)(m);4 循环扫描算法模块：void cscan(int array,int m)主要代码：if(arraym-1<=now) /*若当前磁道号大于请求序列中最大者，则直接将移动臂移动到最小号磁道依次向外给予各请求服务 */ for(i=0;i<m;i+) cout<<arrayi<<" " sum=now-2*array0+arraym-1;

14、else if(array0>=now) /*若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务,此情况同最短寻道优先*/ for(i=0;i<m;i+) cout<<arrayi<<" " sum=arraym-1-now; for(j=0;j<r;j+) /*当扫描完最大号磁道，磁头直接移动到最小号磁道，再向外扫描未扫描的磁道*/ cout<<arrayj<<" " sum=2*arraym-1-now; ave=(float)(sum)/(float)(m);5、实验

15、运行图；算法首页1 先来先服务算法2最短寻道时间优先算法（1）当前磁道号大于磁道序列中的最大的磁道号时（2）当前磁道号小于磁道序列中的最小的磁道号时（3）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号时3 扫描算法（1）当前磁道号大于磁道序列中的最大的磁道号时（2）当前磁道号小于磁道序列中的最小的磁道号时（3）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号（磁头向外）时（4）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号（磁头向内）时4 循环扫描算法（1）当前磁道号大于磁道序列中的最大的磁道号时（2）当前磁道号小于磁道序列中的最小的磁道号时（3）当前磁道号大于磁道序列中

16、的最小的磁道号且小于最大磁道号时6、实验结果分析；本系统具有很强的健壮性，当输入错误数据类型时，系统提示用户输入的数据类型错误，让用户重新输入，保证系统的稳定性，不会因为用户的误操作而致使系统瘫痪；虽然是在dos状态下，但是本系统界面还是设计的比较漂亮的，具有比较好的交互性；对于软件中的重用代码，设计成一个函数，实现代码重用。本系统是在dos状态下进行编译执行的，没有图形化界面，可以设计出一个图形化界面，使用户操作更加简单，明了。用户使用时请注意：1、进入系统，用户根据提示依次输入磁道号，要结束时输入“0”，回车，输入磁盘号结束；2、系统输出你输入的磁道序列，用户核对输入数据3、系统显示系统算

17、法菜单；4、用户选择相应算法，回车；5、系统要求输入当前磁道号，用户输入磁道号，回车；6、系统输出磁头的扫描序列和平均寻道长度；7、用户继续选择系统菜单中的算法；8、当用户选择扫描算法时，需要输入磁道的寻道方向（1表示扫描磁道号大的方向，0表示扫描磁道号小的方向）；六、 结论（应当准确、完整、明确精练；也可以在结论或讨论中提出建议、设想、尚待解决问题等。）通过此次课程设计，我对操作系统的基础知识了解得更透彻了，同时对磁盘调度的四种算法先来先服务算法（fcfs）、最短寻道时间优先算法（sstf）、扫描算法（scan）、循环扫描算法（cscan）有了更深刻的理解和掌握，使我能够为磁盘调度选择适当的

18、算法，提高cpu工作效率。设计过程中遇到的困难在小组成员之间进行讨论，解决不了的问题，也在老师和同学的帮助下顺利解决并通过了验收，我深刻认识到算法的逻辑性对程序的重要影响，算法的准确度对程序运行结果的重要影响（例如，访问同样的磁道，在采用不同的算法，所用的平均寻道长度有明显差别），这对我以后在操作系统的学习中有极大帮。七、 参考文献计算机操作系统（第三版）汤小丹 梁红兵 哲凤平 汤子瀛 编著 西安电子科技大学出版社程序设计基础（第二版） 吴文虎 编著 清华大学出版社数据结构c语言描述 耿国华 主编 高等教育出版社八、 指导教师评语 签名： 年 月 日课程设计成绩附：1、课程设计的填写请按格式要

19、求做；2、文字内容宋体、五号、1.5倍行距；3、程序代码字体times new roman，五号、1.5倍行距； 附表：源程序代码#include<stdio.h>#include<stdlib.h>#include<iostream.h>#include<math.h>#define maxsize 1000/*判断输入数据是否有效*/int decide(char str) /判断输入数据是否有效 int i=0;while(stri!='0') if(stri<'0'|stri>'9

20、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)(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>cida

21、oj) temp=cidaoi; cidaoi=cidaoj; cidaoj=temp; cout<<"排序后的磁盘序列为：" for( i=0;i<m;i+) /输出排序结果 cout<<cidaoi<<" " cout<<endl; return cidao; /*先来先服务调度算法*/void fcfs(int cidao,int m) /磁道号数组，个数为m int now;/当前磁道号 int sum=0; /总寻道长度 int j,i;int a;char str100; float av

22、e; /平均寻道长度cout<<"磁盘请求序列为：" for( i=0;i<m;i+) /按先来先服务的策略输出磁盘请求序列 cout<<cidaoi<<" " cout<<endl; cout<<"请输入当前的磁道号：" b: cin>>str; /对输入数据进行有效性判断 a=decide(str); if(a=0) cout<<"输入数据的类型错误,请重新输入！"<<endl; goto b; else no

23、w=trans(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<<"平均寻道长度："<<ave&l

24、t;<endl;/*最短寻道时间优先调度算法*/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<<"请输入当前的磁道号：" c: cin>>str; /对输入数据进行有效性判断 a=decide(str); if(a=0) cout<<"输入数据的类型错误,请重新输入！"<<endl

25、; goto c; else now=trans(str,a); /输入当前磁道号 if(cidaom-1<=now) /若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务 cout<<"磁盘扫描序列为：" for(i=m-1;i>=0;i-) cout<<cidaoi<<" " sum=now-cidao0; if(cidao0>=now) /若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务 cout<<"磁盘扫描序列为：" for(

26、i=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) /当前磁道在请求序列范

27、围内 if(now-cidaol)<=(cidaor-now) /选择与当前磁道最近的请求给予服务 cout<<cidaol<<" " sum+=now-cidaol; 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<<" &q

28、uot; sum+=cidaom-1-cidao0; else /磁头移动到序列的最大号，返回内侧扫描仍未扫描的磁道 for(j=l;j>=0;j-) cout<<cidaoj<<" " sum+=cidaom-1-cidao0; ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均寻道长度： "<<ave<<endl;/*扫描调度算法*/void scan(int cidao,int m) /先要给出当前磁道号和移动臂的移动方向

29、 int k=1; int now,l,r,d; int i,j,sum=0; int a; char str100; float ave; cidao=bubble(cidao,m); /调用冒泡排序算法排序 cout<<"请输入当前的磁道号："d: cin>>str; /对输入数据进行有效性判断 a=decide(str); if(a=0) cout<<"输入数据的类型错误,请重新输入！"<<endl; goto d; else now=trans(str,a); /输入当前磁道号 if(cidaom-

30、1<=now) /若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务,此情况同最短寻道优先 cout<<"磁盘扫描序列为：" for(i=m-1;i>=0;i-) cout<<cidaoi<<" " sum=now-cidao0; if(cidao0>=now) /若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务,此情况同最短寻道优先 cout<<"磁盘扫描序列为：" for(i=0;i<m;i+) cout<<cid

31、aoi<<" " sum=cidaom-1-now; if(now>cidao0&&now<cidaom-1) /若当前磁道号大于请求序列中最小者且小于最大者 while(cidaok<now) k+; l=k-1; r=k; cout<<"请输入当前移动臂的移动的方向 (1 表示向外 ，0表示向内) : " cin>>d; if(d=0) /选择移动臂方向向内，则先向内扫描 cout<<"磁盘扫描序列为：" for(j=l;j>=0;j-) co

32、ut<<cidaoj<<" " /输出向内扫描的序列 for(j=r;j<m;j+) /磁头移动到最小号，则改变方向向外扫描未扫描的磁道 cout<<cidaoj<<" " /输出向外扫描的序列 sum=now-2*cidao0+cidaom-1; else /选择移动臂方向向外，则先向外扫描 cout<<"磁盘扫描序列为：" for(j=r;j<m;j+) cout<<cidaoj<<" " /输出向外扫描的序列 fo

33、r(j=l;j>=0;j-) /磁头移动到最大号，则改变方向向内扫描未扫描的磁道 cout<<cidaoj<<" " sum=-now-cidao0+2*cidaom-1; ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均寻道长度： "<<ave<<endl;/*循环扫描调度算法*/void cscan(int cidao,int m) int k=1; int now,l,r; int i,j,sum=0; int a; c

34、har str100; float ave; cidao=bubble(cidao,m); /调用冒泡排序算法排序 cout<<"请输入当前的磁道号：" e: cin>>str; /对输入数据进行有效性判断 a=decide(str); if(a=0) cout<<"输入数据的类型错误,请重新输入！"<<endl; goto e; else now=trans(str,a); /输入当前磁道号 if(cidaom-1<=now) /若当前磁道号大于请求序列中最大者，则直接将移动臂移动到最小号磁道依次向

35、外给予各请求服务 cout<<"磁盘扫描序列为：" for(i=0;i<m;i+) cout<<cidaoi<<" " sum=now-2*cidao0+cidaom-1; if(cidao0>=now) /若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务,此情况同最短寻道优先 cout<<"磁盘扫描序列为：" for(i=0;i<m;i+) cout<<cidaoi<<" " sum=cidaom-1-no

36、w; if(now>cidao0&&now<cidaom-1) /若当前磁道号大于请求序列中最小者且小于最大者 cout<<"磁盘扫描序列为：" while(cidaok<now) /单向反复地从内向外扫描 k+; l=k-1; r=k; for(j=r;j<m;j+) cout<<cidaoj<<" " /输出从当前磁道向外扫描的序列 for(j=0;j<r;j+) /当扫描完最大号磁道，磁头直接移动到最小号磁道，再向外扫描未扫描的磁道 cout<<cidao

37、j<<" " sum=2*cidaom-1+cidaol-now-2*cidao0; ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均寻道长度： "<<ave<<endl;void main() int a; int c; /菜单项 int cidaomaxsize; int i=0,count; char str100; cout<<"请输入磁道序列（0结束）："<<endl; a:cin>&

38、gt;str; /对输入数据进行有效性判断 a=decide(str); if(a=0) cout<<"输入数据的类型错误,请重新输入！"<<endl; goto a;/输入错误，跳转到a，重新输入 else cidaoi=trans(str,a); i+; while(cidaoi-1!=0) cin>>str; /对输入数据进行有效性判断 a=decide(str); if(a=0) cout<<"输入数据的类型错误,请重新输入！"<<endl; else cidaoi=trans(str,a); i+; count=i-1; /要访问的磁道数 cout<<"你输入的磁道序列为：" for(i=0;i<count;i+) cou