操作系统+磁盘调度算法

1、目录目录 11课程设计目的 . 21.1 编写目的 22课程设计内容 . 22.1 设计内容 23课程设计方案 . 33.1 模块划分 33.2 模块调用关系图 53.3 子模块程序流程图 54测试数据和结果 . 104.1 测试数据 104.2 测试结果 114.3 测试抓图 115参考文献 . 146总结 156.1 设计体会 156.2 结束语 157程序使用说明书 . 158程序源代码 . 151 课程设计目的1.1编写目的本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象 化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最 短寻道

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

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

4、问， 直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内， 从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。 此算法基本上克服了最短寻道时间优先算法的 服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小， 但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。4、循环扫描算法(CSCAN循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对

5、较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况， 循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时， 磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。3 课程设计方案3.1模块划分本系统划分为四个模块：先来先服务算法模块void FCFS(i nt array,i nt m)、最短寻道时间优先算法模块void SSTF(i nt array,i nt m)、扫描算法模块void SCAN(i ntarray,i nt m)和循环扫描算法模块：void CSCAN(i n

6、t array,i nt m)1先来先服务算法模块：void FCFS(i nt array,i nt m)输入磁道号，按先来先服务的策略输出磁盘请求序列，求平均寻道长度，输出移动平 均磁道数。主要代码：for(i=0,j=1;jm;i+,j+)sum+=abs(arrayj_arrayi);ave=(float)(sum)/(float)(m);2最短寻道时间优先算法模块：void SSTF(i nt array,i nt m)将磁道号用冒泡法从小到大排序，输出排好序的磁道序列，输入当前磁道号，根据前 磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道 数。使用冒

7、泡法按从小到大顺序排列*/若当前磁道号大于请求序列中最大者，则直接由 外向内依次给予各请求服务*/主要代码：for(i=0;im;i+)/*for(j=i+1;jarrayj) temp=arrayi; arrayi=arrayj; arrayj=temp;if(arraym-1=0;i-)coutarrayi=now) /*若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务 */当前磁道在请求序列范围内*/if( no w-arrayl)=(arrayr-no w) /*coutarrayl=0)&(r=0;j-) coutarrayj ; /*输出向内扫描的序列 */for

8、(j=r;jm;j+) /*磁头移动到最小号，则改变方向向外扫描未扫描的磁道*/coutarrayj ; /*输出向外扫描的序列 */sum=no w-2*array0+arraym-1;else /*选择移动臂方向向外，则先向外扫描*/for(j=r;jm;j+) coutarrayj=0;j-)/*磁头移动到最大号，则改变方向向内扫描未扫描的磁道*/coutarrayj;sum=-no w_array0+2*arraym_1;ave=(float)(sum)/(float)(m);4 循环扫描算法模块：void CSCAN(i nt array,i nt m)将磁道号用冒泡法从小到大排序，

9、输出排好序的序列， 输入当前磁道号，规定移动臂单向反复的从内向外移动，根据当前磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。主要代码：if(arraym-1=now) /*若当前磁道号大于请求序列中最大者，则直接将移动臂移动到最小号磁道依次向外给予各请求服务*/for(i=0;im;i+) coutarrayi=no w) /*for(i=0;im;i+) coutarrayi;sum=arraym-1-now;for(j=0;jr;j+)/*coutarrayj;sum=2*arraym-1-now;ave=(float)(sum)/(float)(m);

10、3.2模块调用关系图3.3子模块程序流程图FCFS算法流程图：.专业资料.SSTF算法流程图SCAN 算法流程图:CSCAN 算法流程图:输入磁道号使用冒泡法从小到大排序输出排好序的磁道序列输入当前磁道号规定移动臂单向反 复的从内向外扫描扫描到最大号后，直接 移动到最小号从内向外 扫描未扫描的磁道r1求平均寻道长度JJVL-1输出移动的平均磁道数14 测试数据和结果4.1测试数据1先来先服务算法输入磁道序列：55 58 39 18 90 160 150 38 184当前磁道号：1002最短寻道时间优先算法（1）当前磁道号大于磁道序列中的最大的磁道号时输入磁道序列：55 58 39 18 90

11、160 150 38 184当前磁道号：200（2）当前磁道号小于磁道序列中的最小的磁道号时输入磁道序列：55 58 39 18 90 160 150 38 184当前磁道号：0（3 ）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号时输入磁道序列：55 58 39 18 90 160 150 38 184当前磁道号：1003扫描算法（1）当前磁道号大于磁道序列中的最大的磁道号时输入磁道序列：55 58 39 18 90 160 150 38 184当前磁道号：200（2）当前磁道号小于磁道序列中的最小的磁道号时输入磁道序列：55 58 39 18 90 160 150 38 184当前

12、磁道号：0（3）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号（磁头向外）时输入磁道序列：55 58 39 18 90 160 150 38 184当前磁道号：100（4）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号（磁头向内）时输入磁道序列：55 58 39 18 90 160 150 38 184当前磁道号：1004循环扫描算法（1）当前磁道号大于磁道序列中的最大的磁道号时输入磁道序列：55 58 39 18 90 160 150 38 184当前磁道号：200（2）当前磁道号小于磁道序列中的最小的磁道号时输入磁道序列：55 58 39 18 90 160 150 38

13、184当前磁道号：0（3 ）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号时输入磁道序列：55 58 39 18 90 160 150 38 184当前磁道号：1004.2测试结果1先来先服务算法平均寻道长度：55.32最短寻道时间优先算法（1）当前磁道号大于磁道序列中的最大的磁道号时平均寻道长度：20.2（2）当前磁道号小于磁道序列中的最小的磁道号时平均寻道长度：27.5（3 ）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号时平均寻道长度：20.43扫描算法（1）当前磁道号大于磁道序列中的最大的磁道号时平均寻道长度：20.2（2）当前磁道号小于磁道序列中的最小的磁道号时 平均

14、寻道长度：27.8（3）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号（磁头向外）时 平均寻道长度：27.5（4）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号（磁头向内）时 平均寻道长度：20.44循环扫描算法（1）当前磁道号大于磁道序列中的最大的磁道号时 平均寻道长度：38.6（2）当前磁道号小于磁道序列中的最小的磁道号时 平均寻道长度：35.8（3 ）当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号时 平均寻道长度：20.44.3测试抓图1输入磁道序列（0结束）：55 58 39 18 90 160 150 38 184 ，输出序列:2选择先来先服务算法，得出结果:

15、3选择最短寻道时间优先算法，输入当前磁道号100,得出结果:4选择扫描算法，输入当前磁道号100,选择向外移动，得出结果:100，选择向内移动，得出结杲:IHI尔議;木甲1414. 14 14 M .M Mit M.宣-M-M1 -先来先服务JCJC-M*2.最畑寻道时间优先WMMM3-扫描调度MM仁循坏押描*5-退出Jt*WHfKICK5选择扫描算法，输入当前磁道号-盘的移列度 盍幕序长 雷当当描道 售入入尊 请曲Is趕平8； 18 3S 39 5S 58 90 1SB 160 1S4；1BB_移功的方向（1表示向外，。袤示冋内：0；90 石 SS 39 38 18 150 1G0 1842

16、7-55566选择循环扫描算法，输入当前磁道号100,得出结果:7选择退出:豪*MMif E X JC JfrM3 X JC KJKXKJCKHKKJKXKJCKHKKJKXK JC JC ML X1C JCxtjcxx jCKKBEiWIBifaitKBEaff iMEMEMMEMiMjMaff iM BE 屛 Mi iM 梵 B 开 Mi BE 屛 Mi iM 梵 B 开 Mi BE 屛 Mi iM iEBlEJe MEliE 汪 请选择鼻法；Tress any ke/ to continue5 参考文献计算机操作系统（修订版）操作系统教程操作系统实用教程（第二版）操作系统原理与实践教程程

17、序设计基础教程汤子瀛方敏编任爱华周湘贞、曾宪权陈家骏西安电子科技大学出版社西安电子科技大学出版社 清华大学岀版社清华出版社机械工业出版社6 总结6.1设计体会本系统具有很强的健壮性，当输入错误数据类型时，系统提示用户输入的数据类型错误， 让用户重新输入，保证系统的稳定性，不会因为用户的误操作而致使系统瘫痪；虽然是在 dos状态下，但是本系统界面还是设计的比较漂亮的，具有比较好的交互性；对于软件中的 重用代码，设计成一个函数，实现代码重用。本系统是在dos状态下进行编译执行的， 没有图形化界面，可以设计出一个图形化界面，使用户操作更加简单，明了。6.2结束语通过此次课程设计， 我对操作系统的基础

18、知识了解得更透彻了，同时对磁盘调度的四种算法一一先来先服务算法（FCFS、最短寻道时间优先算法（SSTF、扫描算法（SCAN、循 环扫描算法（CSCAN有了更深刻的理解和掌握，使我能够为磁盘调度选择适当的算法，提 高CPU工作效率。设计过程中遇到的困难在老师和同学的帮助下顺利解决并通过了验收，我深刻认识到算法的逻辑性对程序的重要影响，算法的准确度对程序运行结果的重要影响，这对我以后在操作系统的学习中有极大帮助。7程序使用说明书用户使用时请注意：1、 进入系统，用户根据提示依次输入磁道号，要结束时输入“0”，回车，输入磁盘号 结束；2、系统输出你输入的磁道序列，用户核对输入数据3、系统显示系统算

19、法菜单；4、用户选择相应算法，回车；5、系统要求输入当前磁道号，用户输入磁道号，回车；6、系统输出磁头的扫描序列和平均寻道长度；7、用户继续选择系统菜单中的算法；8、 当用户选择扫描算法时，需要输入磁道的寻道方向（1表示扫描磁道号大的方向，0表示扫描磁道号小的方向）；8 程序源代码#in clude#in clude#in clude#in clude#defi ne maxsize 1000/*int decide(char str) / int i=0;判断输入数据是否有效*判断输入数据是否有效while(stri!=O)if(stri9) return 0; break;i+;retur

20、n i;/*将字符串转换成数*/int tran s(char str,i nt a) /将字符串转换成数字int i;int sum=0;for(i=0;ia;i+)sum=sum+(i nt)(stri-0)*pow(10,a-i-1);return sum;/*冒泡排序算法 *int *bubble(i nt cidao,i nt m)int i,j;int temp;for(i=0;im;i+) /使用冒泡法按从小到大顺序排列for(j=i+1;jcidaoj)temp=cidaoi;cidaoi=cidaoj;cidaoj=temp;cout排序后的磁盘序列为：;输出排序结果for(

21、 i=O;im;i+) /coutcidaoicoute ndl;retur n cidao;/*先来先服卩务调度算导法*void FCFS(i nt cidao,i nt m) /磁道号数组，个数为 mint now;/ 当前磁道号int sum=0; /总寻道长度int j,i;int a;char str1OO;float ave; /平均寻道长度cout磁盘请求序列为：;for( i=0;im;i+) /按先来先服务的策略输出磁盘请求序列coutcidaoi;coute ndl;coutstr; /对输入数据进行有效性判断a=decide(str);if(a=0)cout输入数据的类型

22、错误，请重新输入！ endl;goto B;elseno w=tra ns(str,a); /输入当前磁道号sum+=abs(cidao 0-no w);cout磁盘扫描序列为：;for( i=0;im;i+) /输出磁盘扫描序列coutcidaoi;for(i=0,j=1;jm;i+,j+) /求平均寻道长度sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m);coute ndl;cout平均寻道长度：avee ndl;/*最短寻道时间优先调度算法*void SSTF(int cidao,int m)int k=1;int no w,l,r

23、;int i,j,sum=0;int a;char str1OO;float ave;cidao=bubble(cidao,m); II调用冒泡排序算法排序coutstr; II对输入数据进行有效性判断a=decide(str);if(a=0)cout输入数据的类型错误，请重新输入！endl;goto C;elseno w=tra ns(str,a); II输入当前磁道号if(cidaom-1=now) II若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务cout=0;i-)coutcidaoi=now) II若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务

24、cout磁盘扫描序列为：;for(i=0;im;i+)coutcidaoicidao0&n owcidaom-1) II若当前磁道号大于请求序列中最小者且小于cout 磁盘扫描序列为：;后面的算法都用while(cidaok=0)&(rm) /当前磁道在请求序列范围内if( no w-cidaol)=(cidaor-no w) /选择与当前磁道最近的请求给予服务coutcidaol;sum+=no w-cidaol;no w=cidaol;1=1-1;elsecoutcidaor;sum+=cidaor-now;no w=cidaor;r=r+1;if(l=-1) /磁头移动到序列的最小号，返

25、回外侧扫描仍未扫描的磁道for(j=r;jm;j+)coutcidaoj=0;j-)coutcidaoj;sum+=cidaom-1-cidao0;ave=(float)(sum)/(float)(m);coute ndl;cout平均寻道长度：avee ndl;/*void SCAN(int cidao,int m) /int k=1;int now,l,r,d;int i,j,sum=0;int a;char str1OO;float ave;cidao=bubble(cidao,m); /coutstr; /对输入数据进行有效性判断a=decide(str);if(a=0)cout输入数

26、据的类型错误，请重新输入！endl;goto D;elseno w=tra ns(str,a); /输入当前磁道号if(cidaom-1=now) /若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务，此情况同最短寻道优先cout=0;i-)coutcidaoi=now) /若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务，此情况同最短寻道优先cout磁盘扫描序列为：;for(i=0;im;i+)coutcidaoicidao0&n owcidaom-1) /若当前磁道号大于请求序列中最小者且小于while(cidaok now)k+;l=k-1;r=k;co

27、ut d;if(d=0) II选择移动臂方向向内，则先向内扫描for(j=l；j=0;j-)coutcidaoj ; IIfor(j=r;jm;j+) IIcoutcidaoj ; IIcout 磁盘扫描序列为：;输出向内扫描的序列磁头移动到最小号，则改变方向向外扫描未扫描的磁道输出向外扫描的序列sum=no w-2*cidao0+cidaom-1;else II选择移动臂方向向外，则先向外扫描cout磁盘扫描序列为：;for(j=r;jm;j+)coutcidaoj=0;j-) II磁头移动到最大号，则改变方向向内扫描未扫描的磁道coutcidaoj;sum=-no w-cidao0+2*c

28、idaom-1;ave=(float)(sum)I(float)(m);coute ndl;cout 平均寻道长度:未*avee ndl;循环扫描调度算法*void CSCAN(int cidao,int m) int k=1;int no w,l,r;int i,j,sum=0;int a;char str100;float ave;cidao=bubble(cidao,m); /调用冒泡排序算法排序coutstr; /对输入数据进行有效性判断a=decide(str);if(a=0)cout输入数据的类型错误，请重新输入！endl;goto E;elseno w=tra ns(str,a)

29、; /输入当前磁道号if(cidaom-1=now) /若当前磁道号大于请求序列中最大者，则直接将移动臂移动到最小号磁道依次向外给予各请求服务cout磁盘扫描序列为：;for(i=0;im;i+)coutcidaoi=no w) /若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务，此情况同最短寻道优先cout磁盘扫描序列为：;for(i=0;im;i+)coutcidaoicidao0&no wcidaom-1) /若当前磁道号大于请求序列中最小者且小于最大者II.5单向反复地从内向外扫描输出从当前磁道向外扫描的序列当扫描完最大号磁道，磁头直接移动到最小号磁道，再向cout磁盘扫描序列为: while(cidaok now) /k+;l=k-1;r=k;for(j=r;jm;j+)cout