磁盘调度算法课程设计

1、操作系统课程设计操作系统原理课程设计报告题目：磁盘调度算法课程名称：操作系统 姓 名：肖丽玲、刘心语 学 号：1133050103 专 业：计算机科学与技术 学 校：衡阳师范学院 指导老师：王玉奇 日 期：2015.12.9 目录1课程设计目的11.1编写目的12课程设计内容12.1设计内容13课程设计方案23.1模块划分23.2模块调用关系图23.3子模块程序流程图24图解.74.1先来先服务图解74.2最短优先算法84.3扫描算法图解9 4.4循环扫描算法图解.95屏幕抓图116参考文献127总结137.1设计体会137.2结束语138程序源代码131课程设计目的1.1编写目的本课程设计的

2、目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解。2课程设计内容2.1设计内容 系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（fcfs）、最短寻道时间优先算法（sstf）、扫描算法（scan）、循环扫描算法（cscan）。1、先来先服务算法（fcfs）按访问请求到达的先后次序服务 优点：简单，公平；缺点：效率不高，相邻两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利。2、最短寻道时间优先算法

3、（sstf） 优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先 优点：改善了磁盘平均服务时间； 缺点：造成某些访问请求长期等待得不到服务3、扫描算法（scan） 克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向具体做法：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复4、循环扫描算法（cscan） 也称单向扫描算法。 电梯算法杜绝了饥饿，但当请求对磁道的分布是均匀时，磁头回头，近磁头端的请求很少（因为磁头刚经过），而远端

4、请求较多，这些请求等待时间要长一些。总是从0号柱面开始向里扫描。移动臂到达最后个一个柱面后，立即带动读写磁头快速返回到0号柱面。返回时不为任何的等待访问者服务。返回后可再次进行扫描3课程设计方案3课程设计方案3.1模块划分本系统划分为四个模块：先来先服务算法模块void fc(int a,int n)、最短寻道时间优先算法模块void ss(int a,int n)、扫描算法模块void sc(int a,int n) 和循环扫描算法模块：void cs(int a,int n) 磁盘调度模拟系统3.2模块调用关系图先来先服务算法最短寻道时间优先扫描算法循环扫描算法3.3子模块程序流程图fcf

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

6、寻道长度扫描到最大号后，直接移动到最小号从内向外扫描未扫描的磁道输出移动的平均磁道数输出排好序的磁道序列判断当前磁头在序列中的位置规定移动臂单向反复的从内向外扫描开始结束输入磁道号使用冒泡法从小到大排序输入当前磁道号4 图解4.1先来先服务算法磁盘访问序列：98，183，37，122，14，124，65，67磁头起始位置：53磁头扫描序列：98，183，37，122，14，124，65，67磁头走过的总道数：6404.2最短寻道时间优先(ssf)磁盘访问序列：98，183，37，122，14，124，65，67磁头起始位置：53磁头扫描序列：65，67，37，14，98，122，124，183

7、磁头走过的总道数：2364.3扫描算法磁盘访问序列：98，183，37，122，14，124，65，67磁头起始位置：53磁头扫描序列：37，14， 65，67 ， 98， 122， 124， 183磁头走过的总道数：2084.4 循环扫描调度算法磁盘访问序列：98，183，37，122，14，124，65，67磁头起始位置：53磁头扫描序列：65，67，98，122，124，183，14，37磁头走过的总道数：3225屏幕抓图6参考文献计算机操作系统(第二版) 陆丽娜 高等教育出版社 7总结7.1设计体会本系统具有很强的健壮性，当输入错误数据类型时，系统提示用户输入的数据类型错误，让用户重新

8、输入，保证系统的稳定性，不会因为用户的误操作而致使系统瘫痪；虽然是在dos状态下，但是本系统界面还是设计的比较漂亮的，具有比较好的交互性；对于软件中的重用代码，设计成一个函数，实现代码重用。本系统是在dos状态下进行编译执行的，没有图形化界面，可以设计出一个图形化界面，使用户操作更加简单，明了。7.2结束语通过此次课程设计，我对操作系统的基础知识了解得更透彻了，同时对磁盘调度的四种算法先来先服务算法（fcfs）、最短寻道时间优先算法（sstf）、扫描算法（scan）、循环扫描算法（cscan）有了更深刻的理解和掌握，使我能够为磁盘调度选择适当的算法，提高cpu工作效率。设计过程中遇到的困难在老

9、师和同学的帮助下顺利解决并通过了验收，我深刻认识到算法的逻辑性对程序的重要影响，算法的准确度对程序运行结果的重要影响，这对我以后在操作系统的学习中有极大帮助。8程序源代码#include#include#includevoid p()cout#endl; cout#菜单#endl; cout 1 先来先服务算法（fcfs） endl; cout 2 最短寻道时间优先算法（sstf） endl; cout 3 扫描算法（scan） endl; cout 4 循环扫描算法（cscan） endl; cout endl; cout#endl; cout#endl;/void star()int a1

10、00;int choose;int i,n;coutendl;coutn;/表示总共进程数coutendl;cout请输入这几个进程所在的磁道数:;for(i=0;iai;p();/输出界面函数void ff(int a,int n);void ss(int a,int n);void sc(int a,int n);void cs(int a,int n);coutchoose;while(choose)switch(choose)case 1: ff(a,n); /调用先来先服务算法的函数case 2: ss(a,n); case 3: sc(a,n); case 4: cs(a,n);

11、cinchoose;/void ff(int a,int n)int present,sum=0;float avg=0;cout请输入磁头当前所在磁道数:present;sum=present;if(sum=a0)sum=sum-a0;else sum=a0-sum;for(int i=1;in;i+)if(aiai-1)sum=sum+(ai-1-ai);else sum=sum+(ai-ai-1);avg=(float)sum/n;cout磁头扫描序列:;for(i=0;in;i+)coutai ;coutendl;cout总共访问磁道数:;coutsumendl;cout平均访问磁道数

12、:;coutavg;star();/void ss(int a,int n)int b100,i,j,k,temp,t;int present,sum=0;float avg=0;int min=3276; /假设当前磁头所在的磁道与进程所在的磁道相隔的间距cout请输入磁头当前所在磁道数:present;for(i=n-1;i=0;i-)ai+1=ai;a0=present;b0=present;for(i=0;in;i+)min=32767;temp=i;for(j=i+1;jn+1;j+)k=(aj-ai); k=abs(k); if(kmin) min=k; temp=j; bi+1=

13、atemp;if(temp!=i)t=atemp;atemp=ai+1;ai+1=t;cout磁头扫描序列:;for(i=1;i=n;i+)coutbi ;cout=b1)sum=sum-b1;else sum=b1-sum;for( i=2;i=n;i+)if(bibi-1)sum=sum+(bi-1-bi);else sum=sum+(bi-bi-1);cout总共访问磁道数:;coutsumendl;cout平均访问磁道数:;cout(float)sum/n;star();/void sc(int a,int n)int b100,i,j,k,sum=0,present,temp,cho

14、ose,t,z,x=0;cout请输入当前磁头所在磁道数present;int min=32767;/假设与当前磁头最近的进程相隔的磁道数present;for(i=0;in;i+) k=abs(ai-present); if(kmin) min=k; temp=i; z=atemp;/与当前磁头最近的进程cout选择0，向里寻道，选择1，向外寻道choose;while(choose!=1&choose!=0);if(choose=0)for(i=0;in-1;i+)for(j=i+1;jaj) t=ai; ai=aj; aj=t;for(i=0;in;i+)if(ai=z)break;t=

15、i;b0=at;for(i=t+1;i=0;i-)b+x=ai;cout磁头扫描序列:;for(i=0;in;i+)coutbi=b0)sum=sum-b0;else sum=b0-sum;for(int i=1;in;i+)if(bibi-1)sum=sum+(bi-1-bi);else sum=sum+(bi-bi-1);coutendl;cout总共访问磁道数:;coutsumendl;cout平均访问磁道数:;cout(float)sum/n;if(choose=1)/排序for(i=0;in-1;i+)for(j=i+1;jaj) t=ai; ai=aj; aj=t;/找到与磁头最近

16、的磁道for(i=0;i=0;i-)b+x=ai;for(i=t+1;i=b0)sum=sum-b0;else sum=b0-sum;for(int i=1;in;i+)if(bibi-1)sum=sum+(bi-1-bi);else sum=sum+(bi-bi-1);cout磁头扫描序列:;for(i=0;in;i+)coutbi ;coutendl;cout总共访问磁道数:;coutsumendl;cout平均访问磁道数:;cout(float)sum/n;star();/void cs(int a,int n)int i,j,present,t,k,choose,b100,x=0,su

17、m=0;/排序for(i=0;in-1;i+)for(j=i+1;jaj) t=ai; ai=aj; aj=t; coutpresent;for(i=0;ipresent)k=i;break;do coutchoose;while(choose!=0&choose!=1);if(choose=0)if(abs(ak-1-present)=abs(ak-present)for(j=k-1;jn;j+)bx+=aj; ; for(j=0;jk-1;j+) bx+=aj;elsefor(j=k;jn;j+) bx+=aj; for(j=0;jk;j+) bx+=aj;cout磁头扫描序列：;for(i=0;in;i+)coutbi ;sum=abs(b0-present);for(i=1;in;i+)sum=sum+abs(bi-bi-1);cout总共寻道:;coutsumendl;cout平均寻道:;cout(float)sum/n;if(choose=1)if(ab