磁盘调度实验报告

1、 操作系统实验报告操作系统实验报告 磁磁 盘盘 调调 度度 实验六：磁盘调度算法实验六：磁盘调度算法 一实验目的一实验目的 复习模拟实现一种磁盘调度算法，进一步加深对磁盘调度效率的理解。 二实验属性二实验属性 该实验为设计性实验。 三实验仪器设备及器材三实验仪器设备及器材 普通 PC386 以上微机 四实验要求四实验要求 本实验要求 2 学时完成。 本实验要求完成如下任务： （1） 建立相关的数据结构，作业控制块、已分配分区及未分配分区 （2） 实现一个分区分配算法，如最先适应分配算法、最优或最坏适应分配算法 （3） 实现一个分区回收算法 （4） 给定一批作业/进程，选择一个分配或回收算法，实

2、现分区存储的模拟管理 实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写并完 成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后 认真书写符合规范格式的实验报告（参见附录 A） ，并要求用正规的实验报告纸和封面装订 整齐，按时上交。 五五 . .主要算法分析主要算法分析 各个算法分析各个算法分析 1.先来先服务算法（先来先服务算法（FCFS） 先来先服务（FCFS）调度:按先来后到次序服务，未作优化。 最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求 访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现

3、在读写磁头 正在 50 号柱面上执行输出操作，而等待访问者依次要访问的柱面为 130、199、32、159、15、148、61、99，那么，当 50 号柱面上的操作结束后，移动臂 将按请求的先后次序先移到 130 号柱面，最后到达 99 号柱面。 采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。 先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。 2.最短寻道时间优先算法（最短寻道时间优先算法（SSTF） 最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行 的，而不管访问者到来的先后次序。现在仍利用同一个例子来讨论，现在当

4、 50 号柱面的 操作结束后，应该先处理 61 号柱面的请求，然后到达 32 号柱面执行操作，随后处理 15 号柱面请求，后继操作的次序应该是 99、130、148、159、199。 采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了 200 多个柱面的距离，与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了 为各访问者请求服务的平均时间，也就提高了系统效率。 但最短查找时间优先（SSTF）调度，FCFS 会引起读写头在盘面上的大范围移动，SSTF 查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF 查找模 式有高度局部化的倾向，会推迟一

5、些请求的服务，甚至引起无限拖延（又称饥饿） 。 3.扫描算法（扫描算法（SCAN） SCAN 算法又称电梯调度算法。SCAN 算法是磁头前进方向上的最短查找时间优先算 法，它排除了磁头在盘面局部位置上的往复移动，SCAN 算法在很大程度上消除了 SSTF 算法的不公平性，但仍有利于对中间磁道的请求。 “电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近 的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好 比乘电梯，如果电梯已向上运动到 4 层时，依次有 3 位乘客陈生、伍生、张生在等候乘电 梯。他们的要求是：陈生在 2 层等待去 10 层；伍

6、生在 5 层等待去底层；张生在 8 层等待 15 层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从 8 层带到 15 层， 然后电梯换成下行方向，把乘客伍生从 5 层带到底层，电梯最后再调换方向，把乘客陈生 从 2 层送到 10 层。 但是， “电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂 的当前前进方向。 六、程序代码六、程序代码 #include #include #include void FCFS(int array,int m)/ 先来先服务算法 int j,i,now; float sum = 0,avg; coutnow; sum=abs(

7、now-array0); cout先来先服务算法(FCFS)调度后的序列为array0 ;/输出磁盘调度序列 for(i=0,j=1;jm;i+,j+) sum=sum+abs(arrayj-arrayi); coutarrayj ; /输出磁盘调度序列 avg=sum/(m); coutendl平均寻道长度：avgendl;/输出平均寻道长度 / void SSTF(int array,int m)/ 最短寻道时间优先算法 int temp; int k=1; int now,l,r; int i,j; float sum=0,avg=0; for(i=0;im;i+) for(j=i+1;

8、jarrayj) /将磁道号从小到大排序 temp=arrayi;arrayi=arrayj;arrayj=temp; coutnow; cout最短寻道时间优先算法(SSTF)调度后的序列为;/输出磁盘调度序列 if(arraym-1=0;i-) coutarrayi=now) /若被访问的下一最小的磁道号不小于当前的磁道号 for(i=0;im;i+) coutarrayi ;/输出磁盘调度序列 sum=arrayi-now; now=arrayi; else /当前的磁道号的值在若所有被访问的下的磁道号之间 while(arrayknow) /确定当前磁道在已排的序列中的位置 k+; l

9、=k-1; r=k; if(now-arrayl)=0) /先向磁道号减小方向访问 coutarrayl ; /输出磁盘调度序列 sum=sum+now-arrayl; now=arrayl; l=l-1; now=array0; for(j=r;jm;j+) /再向磁道号增加方向访问 coutarrayj ; /输出磁盘调度序列 sum+=arrayj-now; now=array else /先向磁道号增加方向访问 while(rm) coutarrayr=0;j-) /再向磁道号减小方向访问 coutarrayj ; /输出磁盘调度序列 sum+=now-arrayj; now=arra

10、yj; avg=sum/(m); coutendl平均寻道长度：avgendl;/输出平均寻道长度 / void SCAN(int array,int m) /扫描算法 int temp; int k=1; int now,d,l,r; int i,j; float sum=0,avg=0; for(i=0;im;i+) for(j=i+1;jarrayj) /将磁道号从小到大排序 temp=arrayi; arrayi=arrayj; arrayj=temp; coutnow; coutd; /先要给出当前磁道号和移动臂的移动方向 cout扫描算法(SCAN)调度后的序列为; if(arra

11、ym-1=0;i-) coutarrayi=now) /若被访问的下一最小的磁道号不小于当前的磁道号 for(i=0;im;i+) coutarrayi ; /输出磁盘调度序列 sum=arrayi-now; now=arrayi; else /当前的磁道号的值在若所有被访问的下的磁道号之间 while(arrayk=0) coutarrayl ; /输出磁盘调度序列 sum=sum+now-arrayl; now=arrayl; l=l-1; now=array0; for(j=r;jm;j+) coutarrayj ; /输出磁盘调度序列 sum+=arrayj-now; now=arra

12、yj; break; case 1: /先向磁道号增加方向访问 while(rm) coutarrayr=0;j-) coutarrayj ; /输出磁盘调度序列 sum+=now-arrayj; now=arrayj; break; default: cout输入有误endl; avg=sum/(m); coutendl平均寻道长度：avgendl;/输出平均寻道长度 / void main() int i,m,n,flag=1,array100; coutm; cout分别输入磁盘调度序列:; for(i=0;iarrayi; do cout0 终止endl; cout1 先来先服务算法(

13、FCFS)endl; cout2 最短寻道时间优先算法(SSTF)endl; cout3 最短寻道时间优先算法(SCAN)endl; coutn; switch(n) case 0: flag=0; break; /终止程序 case 1: FCFS(array,m); break; /先来先服务算法(FCFS) case 2: SSTF(array,m); break; /最短寻道时间优先算法(SSTF) case 3: SCAN(array,m); break; /最短寻道时间优先算法(SCAN) default: cout输入有误，请重新输入:endl; while(flag!=0);

14、七、各算法的流程图七、各算法的流程图 1.先来先服务算法流程图先来先服务算法流程图 输入当前磁道号 now 磁头移动距离 sum=abs(now- array0) 磁头移动总距离 Sum+=abs(arrayj- arrayi) 输出磁盘调度序列 arrayj 目前的位置变为当前 的位置 j+ jm 输出平均寻道长度 avg=sum/(m) 2. 最短寻道时间优先算法流程图最短寻道时间优先算法流程图 3. 扫描算法流程图扫描算法流程图 将磁道号从小到大排序 输入当前磁道号 now arraym- 1=0 输出磁盘调度 序列 arrayj (array0 =now 磁头移动总距离 sum=now

15、-arrayi 目前的位置变为 当前的位置 now=arrayi now=arrayi im 确定当前磁道在已 排的序列中的位置 now- arrayl)=(arra yr-now 先向磁道号 减小方向访 问，再向磁 道号增加方 向访问 输出磁盘 调度序列 先向磁道号 增加方向访 问，再向磁 道号减小方 向访问 输出磁盘 调度序列 输出平均寻道长度 avg=sum/(m) 将磁道号从小到大排序 输入当前磁道号 now, 移动臂的移动的方向 arraym- 1=0 (array0 =now 输出磁盘调度 序列 arrayj im 磁头移动总距离 sum=arrayi-now 确定当前磁道在已 排

16、的序列中的位置 switch(d ) case 0:移动臂 向磁道号减小 方向访问 case 1:移动臂 向磁道号增加 方向访问 访问 输出磁盘 调度序列 输出磁盘 调度序列 输出平均寻道长度 avg=sum/(m) 八课程设计运行结果八课程设计运行结果 一一. 运行后的开始界面如下：运行后的开始界面如下： 二、运行各个算法结果如下二、运行各个算法结果如下 1运行先来先服务（FCFS）算法调度后程序结果如下： 2运行最短寻道时间优先（SSTF）算法调度程序结果如下： 3运行扫描（SCAN）算法调度程序结果如下： 5选择退出后程序界面如下： 九心得体会九心得体会 整个设计中最麻烦的就是整个程序模块的划分和各模块之间接口设计，编程中经常犯 想当然的错误，编程中出现了不少奇怪的错误。再调试中尝试使用了分割法,对错误模块进 行定位,再进行排查.通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学 好不仅仅是要把书上的基本知识学好而且还要不断进行实践，将所学的跟实践操作结合起 来才能更好地巩固所学，才能提高自己实践能力.通过这