操作系统磁盘调度算法实验报告(共26页)

1、操作系统原理课 程 设 计 报 告 书题 目：磁盘调度 专 业：网络工程 学 号： 学生姓名： 指导教师： 完成日期： 目录第一章 课程设计目的11.1编写目的1第二章 课程设计内容22.1设计内容22.1.1、先来先服务算法（FCFS）22.1.2、最短寻道时间优先算法（SSTF）22.1.3、扫描算法（SCAN）32.1.4、循环扫描算法（CSCAN）3第三章 系统概要设计43.1模块调度关系图43.2模块程序流程图43.2.1 FCFS算法53.2.2 SSTF算法63.2.3 SCAN算法73.2.4 CSCAN算法8第四章 程序实现94.1 主函数的代码实现94.2.FCFS算法的代

2、码实现114.3 SSTF算法的代码实现134.4 SCAN算法的代码实现154.5 CSCAN算法的代码实现17第五章 测试数据和结果20第六章 总结23第一章 课程设计目的1.1编写目的本课程设计的目的是通过磁盘调度算法设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解24第二章 课程设计内容2.1设计内容 系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、循环扫描算法（

3、CSCAN）。2.1.1、先来先服务算法（FCFS）这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。2.1.2、最短寻道时间优先算法（SSTF）该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户

4、的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。2.1.3、扫描算法（SCAN）扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运

5、行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。2.1.4、循环扫描算法（CSCAN）循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立

6、即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描第三章 系统概要设计3.1模块调度关系图该系统包含的各个模块及个模块之间的关系如下图：3.2模块程序流程图3.2.1 FCFS算法（先来先服务）流程图:3.2.2 SSTF算法（最短寻道时间优先算法）算法流程图：3.2.3 SCAN算法（扫描算法）流程图：3.2.4 CSCAN算法（循环扫描算法）流程图：第四章 程序实现4.1 主函数的代码实现主函数包含了系统的输入输出语句，及以及对输入输出有效性的判断，在C语言中不提倡使用go to语句；但是为了实现输入磁道号错误后能够重新输入，提高程序的可用性我仍然使用了go to语句

7、，主函数代码如下：void main()int a;int c; /菜单项int cidaomaxsize;int i=0,count;char str100;cout<<"请输入磁道序列（0结束）："<<endl;A:cin>>str; /对输入数据进行有效性判断 a=decide(str); if(a=0) cout<<"输入数据的类型错误,请重新输入！"<<endl; goto A;/输入错误，跳转到A，重新输入 else cidaoi=trans(str,a); i+; while(ci

8、daoi-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+) cout<<cidaoi<<" " /输出磁道序列 cout<<endl; while(1)

9、 cout<<endl; cout<<"*"<<endl; cout<<"* 系统菜单 *"<<endl; cout<<"*"<<endl; cout<<"* *"<<endl; cout<<"* 1. 先来先服务 *"<<endl; cout<<"* *"<<endl; cout<<"* 2. 最短

10、寻道时间优先 *"<<endl; cout<<"* *"<<endl; cout<<"* 3. 扫描调度 *"<<endl; cout<<"* *"<<endl; cout<<"* 4. 循环扫描 *"<<endl; cout<<"* *"<<endl; cout<<"* 5. 退出 *"<<endl; cout

11、<<"* *"<<endl; cout<<"*"<<endl; cout<<"*"<<endl;G:cout<<"请选择算法："F:cin>>str; /对输入数据进行有效性判断 a=decide(str); if(a=0) cout<<"输入数据的类型错误,请重新输入！"<<endl; goto F;/输入错误，跳转到F，重新输入 else c=trans(str,a); i

12、f(c=5) break; if(c>5) cout<<"数据输入错误！请重新输入"<<endl; goto G; switch(c) case 1: /使用FCFS算法 FCFS(cidao,count); break; case 2: /使用SSTF算法 SSTF(cidao,count); break; case 3: /使用SCAN算法 SCAN(cidao,count); break; case 4: /使用CSCAN算法 CSCAN(cidao,count); break; 4.2.FCFS算法的代码实现先来先服务算法比较容易实现，

13、代码如下：/*先来先服务调度算法*/void FCFS(int cidao,int m) /磁道号数组，个数为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<<"请输入当前的磁道号："

14、B: cin>>str; /对输入数据进行有效性判断 a=decide(str); if(a=0) cout<<"输入数据的类型错误,请重新输入！"<<endl; goto B; else now=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+)

15、 /求平均寻道长度 sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均寻道长度："<<ave<<endl;4.3 SSTF算法的代码实现最短寻道时间优先算法利用每一次寻道是时候都先寻找最容易找到的磁道。首先判断数据有效性，如果数据有效则调用排序算法对磁道序列进行排序，然后判断磁头所在的位置，按照算法内容进行寻道，最后算出平均寻道时间。/*最短寻道时间优先调度算法*/void SSTF(int cidao,int m)int k=

16、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; goto C; else now=trans(str,a); /输入当前磁道号 if(cidaom-1<=now) /若当前

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

18、-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<<ci

19、daol<<" " 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<<" " sum+=cidaom-1-cidao0; else /磁头移动到序列的最大号，返回内侧扫描仍未扫描的磁道 for(j=l;

20、j>=0;j-) cout<<cidaoj<<" " sum+=cidaom-1-cidao0; ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均寻道长度： "<<ave<<endl;4.4 SCAN算法的代码实现/*扫描调度算法*/void SCAN(int cidao,int m) /先要给出当前磁道号和移动臂的移动方向int k=1;int now,l,r,d;int i,j,sum=0;int a;char str10

21、0;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-1<=now) /若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务,此情况同最短寻道优先 cou

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

23、amp;&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-) cout<<cidaoj<<" " /输出向内扫描的序列 for(j=r;j&l

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

25、oj<<" " sum=-now-cidao0+2*cidaom-1; ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均寻道长度： "<<ave<<endl;4.5 CSCAN算法的代码实现/*循环扫描调度算法*/void CSCAN(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); /调用冒泡

26、排序算法排序cout<<"请输入当前的磁道号：" E: cin>>str; /对输入数据进行有效性判断 a=decide(str); if(a=0) cout<<"输入数据的类型错误,请重新输入！"<<endl; goto E; else now=trans(str,a); /输入当前磁道号 if(cidaom-1<=now) /若当前磁道号大于请求序列中最大者，则直接将移动臂移动到最小号磁道依次向外给予各请求服务 cout<<"磁盘扫描序列为：" for(i=0;i&

27、lt;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-now; 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+) /当扫描完最大号磁道，磁头直接