磁盘调度算法实验报告(二)

1、磁盘调度算法学生姓名:学生学号:专业班级:指导老师:2013年6月20日1、实验目的：通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS最短寻道时间优先SSTFSCA城口循环SCAN#法的实现方法。2、问题描述：设计程序模拟先来先服务FCFS最短寻道时间优先SSTFSCAN和循环SCANW法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向(正向或者反向)，分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。3、需求分析通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS最短寻道时间

2、优先SSTFSCA城口循环SCAN#法的实现方法。通过已知开始磁道数、访问磁道总数、磁道号访问序列、访问方向及访问方式得到访问序列及移动距离和平均移动距离！输入的形式；intTrackOrderMaxNumber;/被访问的磁道号序列intdirection;/寻道方向intNum;/访问的磁道号数目intstart;/输出的形式；intMoveDistanceMaxNumber=0;/移动距离doubleAverageDistance=0;/平均寻道长度移动的序列！程序所能达到的功能；模拟先来先服务FCFS最短寻道时间优先SSTFSCA恃口循环SCAN算法的工作过程。假设有n个磁道号所组成的

3、磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。 TOC o 1-5 h z 开始磁道号：100磁道号方向：内（0）和外（1）磁道号数目：9页面序列：555839189016015038184概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。intTrackOrderMaxNumber;/被访问的磁道号序列intMoveDistanceMaxNumber=0;/移动距

4、离doubleAverageDistance=0;/平均寻道长度intdirection;/寻道方向intNum;/访问的磁道号数目intstart;/开始磁流程图头文件主国物mon5、详细设计实现程序模块的具体算法FCFS3磁道号下标iMoveDistancei=I T r3ckOrderi-start |st3rt=TrackOrderil避行下一个磁道年i4+流程图SSTF磁道号下标T且其是 最小值F*利翁下一个磁道号|苜至找出满足条件的够道期st3rt=TrackOrderfi 进行下一个磁道号6、调试分析(1)调试过程中遇到的问题以及解决方法，设计与实现的回顾讨论和分析；在SCAN_

5、CSafe中在访问不同的数组时没有注意到上一个磁道号和要访问的磁道号的大小比较导致结果不对，后来在分析结果中找出原因。(2)算法的性能分析(包括基本操作和其它算法的时间复杂度和空间复杂度的分析)及其改进设想;FCFS:时间复杂度为O(1)空间复杂度为：O(1)SSTF:时间复杂度为O(nA2)空间复杂度为：0(1)SCAN_CSAN时间复杂度为O(nA2)空间复杂度为：0(1)7、用户使用说明程序的使用说明，列出每一步的操作步骤。(1)输入开始磁道号(2)输入访问磁道号总数(3)输入访问磁道号序列序列(4)选择算法(5)选择方向(6)得出结果8、测试结果动 OHt主口主目修5 I L I L

6、I L-fT60 ?0SB 16S 112S4 146开卷导序口问也。目序2- 10数号，离 =03FE距 号道磁FC动 道移 58 393-CfiN,381184平均寻道长度：55.3333请选J继续还是结束，0：继续；工：结束。请选择算法：1-FCFS,2-SSTF,3-SCAN.4-循环SCAN：2瑶动顺序移动距离9072均寻道长度：46.7778选选圭星里5继磁序。圣圣人质51道 束FS方距 结FC间动 是1-暮 还，号 续将道05继续；1:结束2-SSTF, 3-SCAN, 4-循环SCAN： 3,0；增加；1：减少 016010184249094583255339163811820

7、平均寻道长度：27.7778请选择继续还是结束，0：继续；1：结束0i青选举算法：l-FCFS,2-SSTF,3-SCftN.4一循环SCAN:3费硬入险1号毋可方回0：增加；1：减少，1移前顺序移动距离90105832553391638118261501321601018424与均寻道长度；27.5556X*-eGMC-GW*XXX*4F均寻道长度；31.3333HXHX KEKKKN HX K N 网网下-* 款*!请选择继续还是结束，也继绦L结束0请选择算法；1-FCFE , 2-SETF, 3-SCAH, 4-循环&C AN ;40S 一结少 减*1 J:1一续凡增 一嵌T- -4k

8、s E一 S01-0 2 于 一，。IJ禺一 一3 S1LOJ-3 3 一结FC间动 首Im 一还：号 一续法道 s1 一人顺10 金驾一 *44.ee 05 3 q 16 9 1 8 se 84 166 EH 24 EQ 10道醯了磁道号物可方向，弧增加11：减少二0穆勃顺序慈动距罔1541GEI18101B4241616636203?155165S39032平均寻道长度；35-77789、存在问题在求移动距离时，若调用C+的库函数求绝对值会更方便!10、心得体会首先要明确磁盘调度的原理，画出算法流程图！这样在解决问题时更容易！11、附录程序源代码：#include#defineMaxNum

9、ber100voidFCFS(intTrackOrderMaxNumber,intMoveDistanceMaxNumber,doubleAverageDistance,intstart,intNum)inti,temp=start,sum=0;cout移动顺序移动距离endl;for(i=0;itemp)MoveDistancei=TrackOrderi-temp;elseMoveDistancei=temp-TrackOrderi;sum+=MoveDistancei;temp=TrackOrderi;coutTrackOrderiMoveDistanceiendl;coutendl;Av

10、erageDistance=sum*Num;cout平均寻道长度：AverageDistanceendl;voidSSTF(intTrackOrderMaxNumber,intMoveDistanceMaxNumber,doubleAverageDistance,intstart,intNum)inttemp=start,sum=0,s,count=0,min;intkindMaxNumber=0;cout移动顺序移动距离endl;while(countNum)for(inti=0;itemp)min=TrackOrderi-temp;elsemin=temp-TrackOrderi;s=i;

11、break;inttemp1;for(i=0;itemp)temp1=TrackOrderi-temp;elsetemp1=temp-TrackOrderi;if(temp1min&kindi=0)min=temp1;s=i;MoveDistancecount=min;sum+=MoveDistances;temp=TrackOrders;coutTrackOrdersMoveDistancesendl;kinds=1;count+;coutendl;AverageDistance=sum*Num;cout平均寻道长度：AverageDistanceendl;从小到大排序voidpaixu(i

12、ntaMaxNumber,intn,intTrackOrderMaxNumber)/intsym=0;while(sym=0)intkind=0;for(inti=0;in-1;i+)ints1=ai;ints2=ai+1;ints=ai+1;ai+1=ai;ai=s;kind=1;if(kind=0)sym=1;voidSCAN_CSAN(intTrackOrderMaxNumber,intMoveDistanceMaxNumber,doubleAverageDistance,intstart,intNum,intdirection,intchioce)intsum=0;intaMaxNum

13、ber,bMaxNumber;inttemp=start;inti,num1=0,num2=0;cout移动顺序移动距离endl;for(i=0;itemp)anum1=i;num1+;elsebnum2=i;num2+;paixu(a,num1,TrackOrder);/将数组按从小到达排序paixu(b,num2,TrackOrder);/将数组按从小到达排序ints;if(direction=0)/访问方向向外for(i=0;inum1;i+)/先访问numl并从前往后访问s=ai;MoveDistances=TrackOrders-temp;sum+=MoveDistances;tem

14、p=TrackOrders;coutTrackOrdersMoveDistances=0;i-)/再访问num2并且从后往前访问s=bi;MoveDistances=temp-TrackOrders;sum+=MoveDistances;temp=TrackOrders;coutTrackOrdersMoveDistancesendl;else/CSAN算法s=b0;MoveDistances=temp-TrackOrders;sum+=MoveDistances;temp=TrackOrders;coutTrackOrdersMoveDistancesendl;for(i=1;inum2;i

15、+)/再访问num2并且从前往后访问s=bi;MoveDistances=TrackOrders-temp;sum+=MoveDistances;temp=TrackOrders;coutTrackOrdersMoveDistances=0;i-)/先访问num2并且从后往前访问s=bi;MoveDistances=temp-TrackOrders;sum+=MoveDistances;temp=TrackOrders;coutTrackOrdersMoveDistancesendl;if(chioce=3)/SCAN算法for(i=0;inum1;i+)/再访问num1并且从前往后访问s=a

16、i;MoveDistances=TrackOrders-temp;sum+=MoveDistances;temp=TrackOrders;coutTrackOrdersMoveDistancesendl;else/CSAN算法s=anum1-1;MoveDistances=TrackOrders-temp;sum+=MoveDistances;temp=TrackOrders;coutTrackOrdersMoveDistances=0;i-)/再访问numl并且从后往前访问s=ai;MoveDistances=temp-TrackOrders;sum+=MoveDistances;temp=

17、TrackOrders;coutTrackOrdersMoveDistancesendl;coutendl;AverageDistance=sum*Num;cout平均寻道长度：AverageDistanceendl;voidmain()intTrackOrderMaxNumber;/被访问的磁道号序列intMoveDistanceMaxNumber=0;/移动距离doubleAverageDistance=0;/平均寻道长度intdirection;/寻道方向intNum;/访问的磁道号数目intstart;/开始磁道号intkind=0,chioce;coutstart;coutNum;cout请输入被访问的磁道号序列：;for(inti=0;iTrackOrderi;while(ki