磁盘调度算法学生姓名:学生学号:专业班级:指导老师：2013年6月20日1、实验目的：通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。

2、问题描述：设计程序模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN 和循环SCAN算法的工作过程。

假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。

3、需求分析通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。

通过已知开始磁道数、访问磁道总数、磁道号访问序列、访问方向及访问方式得到访问序列及移动距离和平均移动距离！(1)输入的形式；int TrackOrder[MaxNumber];//被访问的磁道号序列 int direction;//寻道方向int Num;//访问的磁道号数目int start;//(2)输出的形式；int MoveDistance[MaxNumber]={0};//移动距离double AverageDistance=0;//平均寻道长度移动的序列！(3)程序所能达到的功能；模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的工作过程。

假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。

(4)测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。

开始磁道号：100磁道号方向：内（0）和外（1）磁道号数目：9页面序列：55 58 39 18 90 160 150 38 1844、概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。

int TrackOrder[MaxNumber];//被访问的磁道号序列int MoveDistance[MaxNumber]={0};//移动距离double AverageDistance=0;//平均寻道长度int direction;//寻道方向int Num;//访问的磁道号数目int start;//开始磁道号5、详细设计实现程序模块的具体算法。

6、调试分析(1)调试过程中遇到的问题以及解决方法，设计与实现的回顾讨论和分析；在SCAN_CSAN算法中在访问不同的数组时没有注意到上一个磁道号和要访问的磁道号的大小比较导致结果不对，后来在分析结果中找出原因。

(2)算法的性能分析(包括基本操作和其它算法的时间复杂度和空间复杂度的分析)及其改进设想；FCFS：时间复杂度为O（1）空间复杂度为：O(1)SSTF：时间复杂度为O（n^2）空间复杂度为：O(1)SCAN_CSAN：时间复杂度为O（n^2）空间复杂度为：O(1)7、用户使用说明程序的使用说明，列出每一步的操作步骤。

（1）输入开始磁道号（2）输入访问磁道号总数（3）输入访问磁道号序列序列（4）选择算法（5）选择方向（6）得出结果8、测试结果9、存在问题在求移动距离时，若调用Ｃ＋＋的库函数求绝对值会更方便！10、心得体会首先要明确磁盘调度的原理，画出算法流程图！这样在解决问题时更容易!11、附录程序源代码：#include <iostream.h>#define MaxNumber 100void FCFS(int TrackOrder[MaxNumber],int MoveDistance[MaxNumber], double AverageDistance,int start,int Num){int i,temp=start,sum=0;cout<<"移动顺序移动距离"<<endl;for(i=0;i<Num;i++){if(TrackOrder[i]>temp)MoveDistance[i]=TrackOrder[i]-temp;elseMoveDistance[i]=temp-TrackOrder[i];sum+=MoveDistance[i];temp=TrackOrder[i];cout<<TrackOrder[i]<<" "<<MoveDistance[i]<<endl;}cout<<endl;AverageDistance=sum*1.0/Num;cout<<"平均寻道长度："<<AverageDistance<<endl;}void SSTF(int TrackOrder[MaxNumber],int MoveDistance[MaxNumber], double AverageDistance,int start,int Num){int temp=start, sum=0,s,count=0,min;int kind[MaxNumber]={0};cout<<"移动顺序移动距离"<<endl;while(count<Num){for(int i=0;i<Num;i++){if(kind[i]==0){if(TrackOrder[i]>temp)min=TrackOrder[i]-temp;elsemin=temp-TrackOrder[i];s=i;break;}}int temp1;for( i=0;i<Num;i++) //找出里此时磁道距离最近的磁道号{if(TrackOrder[i]>temp)temp1=TrackOrder[i]-temp;elsetemp1=temp-TrackOrder[i];if(temp1<min && kind[i]==0){min=temp1;s=i;}}MoveDistance[count]=min;sum+=MoveDistance[s];temp=TrackOrder[s];cout<<TrackOrder[s]<<" "<<MoveDistance[s]<<endl;kind[s]=1;count++;}cout<<endl;AverageDistance=sum*1.0/Num;cout<<"平均寻道长度："<<AverageDistance<<endl;}void paixu(int a[MaxNumber],int n,int TrackOrder[MaxNumber])//从小到大排序{int sym=0;while(sym==0){int kind=0;for(int i=0;i<n-1;i++){int s1=a[i];int s2=a[i+1];i f(TrackOrder[s1]>TrackOrder[s2]){int s=a[i+1];a[i+1]=a[i];a[i]=s;kind=1;}}if(kind==0)sym=1;}}void SCAN_CSAN(int TrackOrder[MaxNumber],int MoveDistance[MaxNumber], double AverageDistance,int start,int Num,int direction,int chioce) {int sum=0;int a[MaxNumber],b[MaxNumber];int temp=start;int i,num1=0,num2=0;cout<<"移动顺序移动距离"<<endl;for(i=0;i<Num;i++)//分类{if(TrackOrder[i]> temp){a[num1]=i;num1++;}else{b[num2]=i;num2++;}}paixu(a,num1,TrackOrder);//将数组按从小到达排序paixu(b,num2,TrackOrder);//将数组按从小到达排序int s;if(direction==0) //访问方向向外{for(i=0;i<num1;i++)//先访问num1并从前往后访问{s=a[i];MoveDistance[s]=TrackOrder[s]-temp;sum+=MoveDistance[s];temp=TrackOrder[s];cout<<TrackOrder[s]<<" "<<MoveDistance[s]<<endl;}if(chioce==3)//SCAN算法{for(i=num2-1;i>=0;i--) //再访问num2并且从后往前访问{s=b[i];MoveDistance[s]=temp-TrackOrder[s];sum+=MoveDistance[s];temp=TrackOrder[s];cout<<TrackOrder[s]<<" "<<MoveDistance[s]<<endl;}}else //CSAN算法{s=b[0];MoveDistance[s]=temp-TrackOrder[s];sum+=MoveDistance[s];temp=TrackOrder[s];cout<<TrackOrder[s]<<" "<<MoveDistance[s]<<endl;for(i=1;i<num2;i++) //再访问num2并且从前往后访问{s=b[i];MoveDistance[s]=TrackOrder[s]-temp;sum+=MoveDistance[s];temp=TrackOrder[s];cout<<TrackOrder[s]<<" "<<MoveDistance[s]<<endl;}}}else //访问方向向内{for(i=num2-1;i>=0;i--)//先访问num2并且从后往前访问{s=b[i];MoveDistance[s]=temp-TrackOrder[s];sum+=MoveDistance[s];temp=TrackOrder[s];cout<<TrackOrder[s]<<" "<<MoveDistance[s]<<endl;}if(chioce==3) //SCAN算法{f or(i=0;i<num1;i++)//再访问num1并且从前往后访问{s=a[i];MoveDistance[s]=TrackOrder[s]-temp;sum+=MoveDistance[s];temp=TrackOrder[s];cout<<TrackOrder[s]<<" "<<MoveDistance[s]<<endl;}}else //CSAN算法{s=a[num1-1];MoveDistance[s]=TrackOrder[s]-temp;sum+=MoveDistance[s];temp=TrackOrder[s];cout<<TrackOrder[s]<<" "<<MoveDistance[s]<<endl;f or(i=num1-2;i>=0;i--)//再访问num1并且从后往前访问{s=a[i];MoveDistance[s]=temp-TrackOrder[s];sum+=MoveDistance[s];temp=TrackOrder[s];cout<<TrackOrder[s]<<" "<<MoveDistance[s]<<endl;}}}cout<<endl;AverageDistance=sum*1.0/Num;cout<<"平均寻道长度："<<AverageDistance<<endl;}void main(){int TrackOrder[MaxNumber];//被访问的磁道号序列int MoveDistance[MaxNumber]={0};//移动距离double AverageDistance=0;//平均寻道长度int direction;//寻道方向int Num;//访问的磁道号数目int start;//开始磁道号int kind=0,chioce;cout<<"请输入开始磁道号：";cin>>start;cout<<"请输入访问的磁道号数目：";cin>>Num;cout<<"请输入被访问的磁道号序列：";for(int i=0;i<Num;i++)cin>>TrackOrder[i];while(kind==0){cout<<"请选择算法：1-FCFS，2-SSTF，3-SCAN，4-循环SCAN: ";cin>>chioce;if(chioce==1)FCFS(TrackOrder,MoveDistance,AverageDistance,start, Num);else{if(chioce==2)SSTF(TrackOrder,MoveDistance,AverageDistance,start, Num);else{cout<<"请输入磁道号访问方向，0：增加；1：减少: ";c in>>direction;SCAN_CSAN(TrackOrder,MoveDistance, AverageDistance,start,Num,direction,chioce);}}cout<<"**********************************************"<<endl;cout<<"请选择继续还是结束，0：继续；1：结束 ";cin>>kind;}}。