磁盘调度算法实验报告材料

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

2、进一步掌握先来先服务FCFS、最短寻道时间优先 SSTF、SCAN和循环SCAN算法的 实现方法。通过已知开始磁道数、访问磁道总数、磁道号访问序列、访问方 向及访问方式得到访问序列及移动距离和平均移动距离！(1) 输入的形式；int TrackOrderMaxNumber;/ 被访问的磁道号序列int direction;/寻道方向int Num;/ 访问的磁道号数目int start;/（2） 输出的形式；int MoveDistanceMaxNumber=0;/ 移动距离double AverageDistance=0;/ 平均寻道长度移动的序列！（3）程序所能达到的功能；模拟先来先服务F

3、CFS、最短寻道时间优先SSTF、SCAN和循环SCAN 算法的工作过程。假设有 n 个磁道号所组成的磁道访问序列， 给定开始磁道号 m 和磁头移动的方向（正向或者反向） ，分别利用不 同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离， 计算每种算法的平均寻道长度。（4）测试数据，包括正确的输入及其输出结果和含有错误的输入及其 输出结果。开始磁道号： 100磁道号方向：（0）和外（ 1）磁道号数目： 9页面序列： 55 58 39 18 90 160 150 38 1844、概要设计说明本程序中用到的所有抽象数据类型的定义、 主程序的流程以 及各程序模块之间的层次 （调用） 关系。i

4、nt TrackOrderMaxNumber;被访问的磁道号序列int MoveDista nceMaxNumber二0;/移动距离double AverageDista nce=0;平均寻道长度int directio n;寻道方向int Num;/访问的磁道号数目intstart;/开 始 磁 道 号流程图主因魏出门)5、详细设计实现程序模块的具体算法1 * S流程图装睛道号下标iL1oveDistancei| T rackOrder(i-Etart |>sta rt =Tr ackOr d eri 遴行下一个犠道誇i+r晞直号下标IT且其是 最小值Fst3rt=TrackOrder

5、fil进行下一个蹴道号i卄流 程 图SCANICS.VJ槪谨号下标ickOrder将其赦入.数爼已中并排序92AIJ加前向后CSAN的入魏组t中并排序内品卜:an orCSAI谚问数组b从前向后-SCAI从后向后访问数组b从后向前“到斷下一个晞道号I 直至挾出满足柔件的 ittii号6、调试分析(1) 调试过程中遇到的问题以及解决方法，设计与实现的回顾讨 论和分析；在scan_csAN法中在访问不同的数组时没有注意到上一个磁道号和要访问的磁道号的大小比较导致结果不对，后来在分析结果中找出原因。(2) 算法的性能分析(包括基本操作和其它算法的时间复杂度和空间复杂度的分析)及其改进设想;FCFS:

6、时间复杂度为0( 1)空间复杂度为：0(1)SSTF:时间复杂度为0(n八2)空间复杂度为：0(1)SCAN_CSAN时间复杂度为0(nA2)空间复杂度为：0(1)7、用户使用说明程序的使用说明，列出每一步的操作步骤(1 )输入开始磁道号(2) 输入访问磁道号总数(3) 输入访问磁道号序列序列(4) 选择算法(5) 选择方向(6) 得出结果8、测试结果卄序 人入入择顺45 冃青青青竣5口问聖i恥直号：100磁道号数目：*问前磁道号序列：=1-FCFS, 2-SSTF移动距离58 393-£CfiN,381184P 729 199 216016S 112 S4 146匚均寻道长度：55

7、.3333请塔J继续还是结束，0:继续；1:结束0请选择算法：1-FCFS, 2-SSTF, 3-SCAN. 4-循环SCAN： 2 務动顺序 移动距离7222 3 0 42 0 16 12 23 13 110 0 4 85988568 - ) u u Ik IL IL IL均寻道长度：46.7?8继续；结束2-SSTF, 3-SCAN, 4-循环SCAN： 3 ,0；增加；诚少： 0:向离 束FS方距 结FC间动 是还2号 续迭道继算磁序0 译译入顺5选选0 圭冃主冃主516010184249094£83255339163811820均寻道长度：27.77780：继续；1：结束02

8、-SSTF, 3-SCftN, 4-循坏SCAN： 3,0：增加；1：诚少： 1;向离 束FS方距 结FC问动 是-还号 继算黑 菱入顺1032一选选舅土冃主冃主0 8£ 5391638118201501321601W18424均寻道长度；27.5556少减*1ff一续P,増 用T 70 -0 2 " 一，向离 -一艮 S？LOJ -结FC问动 一是1-喜 一还.号 一继算幫 一羸入顺10 境舅 一青青士 PE. 08 32石 39 lfe918 2084166佃 24弓窃 10F均寻道低度；31-33339、存在问题在求移动距离时，若调用C + +的库函数求绝对值会更方便

9、!10、心得体会首先要明确磁盘调度的原理，画出算法流程图！这样在解决问题时更容易！11、附录程序源代码：#include <iostream.h>#define MaxNumber 100void FCFS(int TrackOrderMaxNumber,int MoveDistanceMaxNumber,double AverageDistance,int start,int Num)int i,temp=start,sum=0;cout<<" 移动顺序 移动距离 "<<endl;for(i=0;i<Num;i+)if(Track

10、Orderi>temp)MoveDistancei=TrackOrderi-temp;elseMoveDistancei=temp-TrackOrderi;sum+=MoveDistancei;temp=TrackOrderi;cout<<TrackOrderi<<" "<<MoveDistancei<<endl;cout<<endl;AverageDistance=sum*1.0/Num;cout<<" 平均寻道长度： "<<AverageDistance<

11、<endl;void SSTF(int TrackOrderMaxNumber,int MoveDistanceMaxNumber, double AverageDistance,int start,int Num)int temp=start, sum=0,s,count=0,min;int kindMaxNumber=0;cout<<" 移动顺序 移动距离 "<<endl;while(count<Num)for(int i=0;i<Num;i+)if(kindi=0)if(TrackOrderi>temp)min=Trac

12、kOrderi-temp;elsemin=temp-TrackOrderi;s=i;break;int temp1;for( i=0;i<Num;i+) /找出里此时磁道距离最近的磁道号if(TrackOrderi>temp) temp1=TrackOrderi-temp;elsetemp1=temp-TrackOrderi;if(temp1<min && kindi=0)min=temp1;s=i;MoveDistancecount=min; sum+=MoveDistances; temp=TrackOrders;cout<<TrackOrde

13、rs<<" "<<MoveDistances<<endl; kinds=1;count+;cout<<endl;AverageDistance=sum*1.0/Num;cout<<" 平均寻道长度： "<<AverageDistance<<endl;从小到大排序void paixu(int aMaxNumber,int n,int TrackOrderMaxNumber)/int sym=0;while(sym=0)int kind=0;for(int i=0;i<

14、n-1;i+)int s1=ai;int s2=ai+1;i f(TrackOrders1>TrackOrders2)int s=ai+1;ai+1=ai;ai=s;kind=1;if(kind=0)sym=1;void SCAN_CSAN(int TrackOrderMaxNumber,int MoveDistanceMaxNumber, double AverageDistance,int start,int Num,int direction,int chioce)int sum=0;int aMaxNumber,bMaxNumber;int temp=start;int i,nu

15、m1=0,num2=0;cout<<" 移动顺序 移动距离 "<<endl;for(i=0;i<Num;i+)/ 分类if(TrackOrderi> temp)anum1=i;num1+;elsebnum2=i;num2+;paixu(a,num1,TrackOrder);/ 将数组按从小到达排序 paixu(b,num2,TrackOrder);/ 将数组按从小到达排序int s;if(direction=0) / 访问方向向外for(i=0;i<num1;i+)先访问numl并从前往后访问s=ai;MoveDistances=T

16、rackOrders-temp;sum+=MoveDistances;temp=TrackOrders;cout<<TrackOrders<<" "<<MoveDistances<<endl;if(chioce=3)/SCAN 算法for(i=num2-1;i>=0;i-)/再访问num2并且从后往前访问s=bi;MoveDistances=temp-TrackOrders;sum+=MoveDistances;temp=TrackOrders;cout<<TrackOrders<<"

17、"<<MoveDistances<<endl;else /CSAN 算法s=b0;MoveDistances=temp-TrackOrders; sum+=MoveDistances;temp=TrackOrders;cout<<TrackOrders<<" "<<MoveDistances<<endl;for(i=1;i<num2;i+) / 再访问 num2 并且从前往后访问s=bi; MoveDistances=TrackOrders-temp;sum+=MoveDistances

18、;temp=TrackOrders;cout<<TrackOrders<<" "<<MoveDistances<<endl;else / 访问方向向for(i=num2-1;i>=0;i-)先访问num2并且从后往前访问s=bi;MoveDistances=temp-TrackOrders; sum+=MoveDistances;temp=TrackOrders; cout<<TrackOrders<<" "<<MoveDistances<<endl;i

19、f(chioce=3) /SCAN 算法for(i=0;i<num1;i+)/ 再访问 num1 并且从前往后访问s=ai;MoveDistances=TrackOrders-temp; sum+=MoveDistances;temp=TrackOrders;cout<<TrackOrders<<" "<<MoveDistances<<endl;else /CSAN 算法 s=anum1-1;MoveDistances=TrackOrders-temp; sum+=MoveDistances;temp=TrackOrde

20、rs; cout<<TrackOrders<<" "<<MoveDistances<<endl;f or(i=num1-2;i>=0;i-)/再访问 num1 并且从后往前访问 s=ai;MoveDistances=temp-TrackOrders; sum+=MoveDistances;temp=TrackOrders;cout<<TrackOrders<<" "<<MoveDistances<<endl;cout<<endl;AverageDistance=sum*1.0/Num;cout<<" 平均寻道长度： "<<AverageDistance<<endl;void main()int TrackOrderMaxNumber;/ 被访问的磁道号序列int MoveDistanceMaxNumber=0;/ 移动距离double AverageDistance=0;/ 平均寻道长度int direction;/ 寻道方向int Num;/ 访问的磁道号数目int start;/ 开始磁道号int