操作系统实验四 磁盘调度算法

1、操作系统实验四 磁盘调度算法实验四 磁盘调度一、实验目的：本实验要求学生模拟设计一个磁盘调度程序，观察调度程序的动态运行过程。通过实验让学生理解和掌握磁盘调度的职能。二、实验内容：对磁盘进行移臂操作，模拟磁盘调度算法并计算平均寻道时间三、实验准备：1.相关理论知识：（1）假设磁盘只有一个盘面，并且磁盘是可移动头磁盘。（3）磁盘是高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出工作，在现代计算机系统中往往同时会有若干个要求访问磁盘的输入输出要求。系统可采用一种策略，尽可能按最佳次序执行访问磁盘的请求。由于磁盘访问时间主要受寻道时间T的影响，为此需要采

2、用合适的寻道算法，以降低寻道时间。（2）磁盘是可供多个进程共享的存储设备，但一个磁盘每个时刻只能为一个进程服务。当有进程在访问某个磁盘时，其它想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出请求而处于等待状态时，可用磁盘调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。2.测试数据：磁盘读写请求队列：20，44，40，4，80，12，76当前磁头位置：50 试问采用FCFS、SSTF、SCAN磁盘调度算法时寻道顺序及平均寻道时间分别为多少？ 四、实验过程：1.流程图 SCAN算法（扫描算法）流程图：求平均寻道长度选择移动臂移动方向，开始扫描移动到最小（大）号，改

3、向外（内）移动扫描未扫描的磁道输出移动的平均磁道数输出排好序的磁道序列开始结束输入磁道号使用冒泡法从小到大排序输入当前磁道号判断当前磁头在序列中的位置2. 源代码#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'|s

4、tri>'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+) i

5、f(cidaoi>cidaoj) 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

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

7、 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+) /求平均寻道长度 sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均寻道长度：&qu

8、ot;<<ave<<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<<"输入数据的类型错误,请重新输入！&q

9、uot;<<endl; 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<<"磁盘扫

10、描序列为：" 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; while(l>=0)&&(r&l

11、t;m) /当前磁道在请求序列范围内 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&

12、lt;<" " 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) /先要

13、给出当前磁道号和移动臂的移动方向 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); /输入

14、当前磁道号 if(cidaom-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+)

15、 cout<<cidaoi<<" " 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=

16、l;j>=0;j-) cout<<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<<" &quo

17、t; /输出向外扫描的序列 for(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

18、,sum=0; int a; char 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) /若当前磁道号大于请求序列中最大者，则直

19、接将移动臂移动到最小号磁道依次向外给予各请求服务 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<<" "

20、 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+) /当扫描完最大号磁道，磁头直接移动到最小号磁道，再向外扫描未扫描的磁道 c

21、out<<cidaoj<<" " 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结束）："<<

22、endl; A:cin>>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 c

23、idaoi=trans(str,a); i+; count=i-1; /要访问的磁道数 cout<<"你输入的磁道序列为：" for(i=0;i<count;i+) cout<<cidaoi<<" " /输出磁道序列 cout<<endl; while(1) cout<<endl; cout<<"*"<<endl; cout<<" 系统菜单 "<<endl;cout<<"* *&q

24、uot;<<endl;cout<<"* 1. 先来先服务 *"<<endl;cout<<"* *"<<endl;cout<<"* 2. 最短寻道时间优先 *"<<endl;cout<<"* *"<<endl;cout<<"* 3. 扫描调度 *"<<endl;cout<<"* *"<<endl;cout<<"* 4. 循环扫描 *&q