磁盘管理实验
一、实验目的
1、了解磁盘调度的策略和原理；
2、理解和掌握磁盘调度算法——先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、电梯扫描算法（SCAN）。
二、实验内容
1、模拟先来先服务法（First-Come, First-Served，FCFS），最短寻道时间优先法（Shortest Seek Time First， SSTF），电梯扫描算法（SCAN）三种磁盘调度算法；
2、对三种算法进行对比分析。
输入为一组请求访问磁道序列，输出为每种调度算法的磁头移动轨迹和移动的总磁道数。
思考题：
1、通过对每个算法进行时间复杂度分析对比，每个算法的效率如何？
2、若所有硬盘全部设计成电子硬盘，哪个磁盘调度算法最合适？
三、实验原理
1、先来先服务算法（FCFS）: 按先来后到次序服务，未作优化。最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。
2、最短寻道时间优先算法（SSTF）:最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（SSTF）调度，FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。
3、扫描算法（SCAN）：SCAN 算法又称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。
四、实验中用到的系统调用函数
实验只是模拟实现磁盘调度功能，不需要系统调用函数。
五、实验步骤
1、输入为一组请求访问磁道序列，该序列和所选磁道个数要求随机生成，输出为每种调度算法的磁头移动轨迹和移动的总磁道数；
2、输入磁道范围 0199，输入所选磁道个数0199；
3、画出主程序流程图；
4、 编写程序并调试；
5、 截屏输出实验结果；
6、 根据实验结果与理论课讲述的原理进行实验分析。
六、实验数据及源代码
#include<stdio.h> #include<time.h> #include<stdlib.h> #include<math.h> int length;//磁道序列长度 int start;//磁头初始位置 int *queue=NULL;//磁道序列 void init();//初始化数据 void QuickSort(int *queue,int low,int high);//快速排序 void delete();//释放内存 void FCFS();//FCFS 先来先服务算法 void SSTF();//SSTF 最短寻道时间优先算法 void SCAN();//SCAN 扫描算法 void main(){ init();//初始化数据 printf("*******************************\n"); FCFS();//FCFS算法 printf("\n*******************************\n"); SSTF();//SSTE算法 printf("\n*******************************\n"); SCAN();//SCAN算法 delete();//释放内存 } void init(){//初始化数据 srand((unsigned int)time(0)); start=rand()%200;//随机生成磁道初始位置 length=(rand()%11)+5;//磁道序列的长度初始化，范围为5-15 queue=(int*)malloc(sizeof(int)* length);//动态申请内存 for(int i=0;i<length;i++){ queue[i]=rand()%200;//初始化磁道序列 } printf("磁道序列为：");//输出磁道序列 for(int i=0;i<length;i++){ printf("->%d",queue[i]); } printf("\n\n"); } //快速排序 void QuickSort(int *queue,int low,int high){ if(low<high){ int a=low; int b=high; int c=queue[low]; while(a<b){ while(a<b&&queue[b]>=c){ b--; } if(a<b){ queue[a++]=queue[b]; } while(a<b&&queue[a]<c){ a++; } if(a<b){ queue[b--]=queue[a]; } } queue[a]=c; QuickSort(queue,low,a-1);//对左半部分进行递归 QuickSort(queue,a+1,high);//对右半部分进行递归 } } //释放内存 void delete(){ free(queue); printf("\n\n程序运行完毕，内存已释放！\n"); } //FCFS 先来先服务算法 void FCFS(){ int move=0;//磁道移动总数 int temp=start; //磁头初始位置是否在第一道要扫描的磁道上，以防止输出轨迹时重复 if(queue[0]==start){ printf("先来先服务算法,磁头初始位置为%d\n磁头移动轨迹为;",start); } else{ printf("先来先服务算法,磁头初始位置为%d\n磁头移动轨迹为：%d",start,start); } for(int i=0;i<length;i++){ printf("->%d",queue[i]);//输出移动轨迹 move+=abs(queue[i]-temp);//移动磁道数 temp=queue[i]; } printf("\n磁道移动总数为：%d",move);//输出磁道移动总数 } //SSTF 最短寻道时间优先算法 void SSTF(){ int move=0;//磁道移动总数 int flag=0;//记录磁头初始位置是否在第一道要扫描的磁道上，以防止输出轨迹时重复 QuickSort(queue,0,length-1);//快速排序 printf("最短寻道时间优先算法,磁头初始位置为%d\n磁头移动轨迹为;",start); int left,right,temp=start; //找到磁头初始位置左右的磁道下标 for(int i=0;i<length;i++){ if(queue[0]>temp){ left=0; right=-1; break; } else if(queue[i]>temp){ left=i-1; right=i; break; } else if(queue[i]==temp){ flag=1; left=i-1; right=i; break; } else{ left=length-2; right=length-1; } } if(right==length-1){//磁头初始位置的磁道号比队列中的磁道号都大 printf("%d",start); for(int i=length-1;i>=0;i--){ printf("->%d",queue[i]);//输出移动轨迹 move+=abs(queue[i]-temp);//计算移动磁道数 temp=queue[i]; } } else if(right==-1){//磁头初始位置的磁道号比队列中的磁道号都小 printf("%d",start); for(int i=0;i<length;i++){ printf("->%d",queue[i]);//输出移动轨迹 move+=abs(queue[i]-temp);//计算移动磁道数 temp=queue[i]; } } else{ if(flag!=1){//磁头初始位置不在第一道要扫描的磁道上 printf("%d",start); } while(!(left<0&&right>length-1)){ if(abs(queue[left]-temp)<abs(queue[right]-temp)&&left>=0){//向左走移动的磁道数少 printf("->%d",queue[left]);//输出移动轨迹 move+=abs(queue[left]-temp);//计算移动的磁道数 temp=queue[left]; left--; } else{//向右走移动的磁道数少 printf("->%d",queue[right]);//输出移动轨迹 move+=abs(queue[right]-temp);//计算移动的磁道数 temp=queue[right]; right++; } } } printf("\n磁道移动总数为：%d",move);//输出磁道移动总数 } //SCAN 扫描算法 void SCAN(){ int move=0;//磁道移动总数 QuickSort(queue,0,length-1);//快速排序 printf("扫描算法,磁头初始位置为%d\n磁头移动轨迹为：",start); int local;//记录磁头初始位置附近的磁道号 int temp=start; for(int i=0;i<length;i++){ if(queue[0]>temp){ local=0; break; } else if(queue[i]>=temp){ local=i; break; } else{ local=length-1; } } if(local==0){//磁头初始位置的磁道号比队列中的都要小 printf("%d",start); for(int i=0;i<length;i++){//直接向右输出排序好的队列 printf("->%d",queue[i]); move+=abs(queue[i]-temp);//计算移动的磁道数 temp=queue[i]; } } else if(local==length-1){//磁头初始位置的磁道号比队列中的都要大 printf("%d",start); for(int i=length-1;i>=0;i--){//直接向左输出排序好的队列 printf("->%d",queue[i]); move+=abs(queue[i]-temp);//计算移动的磁道数 temp=queue[i]; } } else{ if(local<=(length/2)){//定义磁头一开始的移动方向的条件 if(queue[local-1]!=start){//磁头初始位置不在第一道要扫描的磁道上 printf("%d",start);//输出磁头初始位置的磁道号 } for(int i=local-1;i>=0;i--){//向左走 printf("->%d",queue[i]);//输出移动轨迹 move+=abs(queue[i]-temp);//计算移动的磁道数 temp=queue[i]; } for(int j=local;j<length;j++){//向右走 printf("->%d",queue[j]); move+=abs(queue[j]-temp); temp=queue[j]; } } else{ if(queue[local]!=start){//磁头初始位置不在第一道要扫描的磁道上 printf("%d",start);//输出磁头初始位置的磁道号 } for(int i=local;i<length;i++){//向右走 printf("->%d",queue[i]);//输出移动轨迹 move+=abs(queue[i]-temp);//计算移动的磁道数 temp=queue[i]; } for(int j=local-1;j>=0;j--){//向左走 printf("->%d",queue[j]); move+=abs(queue[j]-temp); temp=queue[j]; } } } printf("\n磁道移动总数为：%d",move);//输出磁道移动总数 }
七、实验结果分析
折线图：
轨迹重复：
要实现这三个算法并不难，但是由于所有数据都要求随机输入，所以增加了很多的不确定性因素，因此要实现算法的严谨性就要增加较多的细节。我在调试过程中发现当磁头一开始的位置就位于第一道要访问的磁道上时，此时不需要再将初始位置加入到移动轨迹里面。所以我在每个算法里面都增加了相应的判断以避免出现这个问题。除此之外，在SSTF和SCAN算法中，当磁头位置在排序好的序列的前端或者后端时候可以直接作出顺序输出，当然需要加入一定的判断条件。
从上面的实验结果来看，FCFS算法的磁道移动数是最多的，这不难理解，因为采用这种算法时磁头是往复运动的；而SSTF与SCAN算法经常会出现移动磁道数相同的情况，因为当磁头初始位置在序列最左边或最右边时移动轨迹是一样的，除此之外，磁头初始磁道位于中间时候也有可能出现移动轨迹相同的情况。这也是较好理解的，因为两者都是对序列进行了排序，随机生成的数据若间隔较小时，SSTF算法往一边走以后一般都是跟这一边的下一个记录更近，因此就会像电梯算法一样扫描完一边后再返回到另一边。
SCAN算法优化：
上图对应的移动轨迹：
因为磁盘序列是确定的，所以我在算法的一个小细节中做了一点改进，在确定磁头一开始的移动方向中，我将条件local<=(length/2)修改为“abs(start-queue[0])<abs(start-queue[length-1])”。即一开始我是按照选好的分界点的位置来决定磁头移动的方向，当分界点在序列左半部分或中间时先向左扫描，在右半部分则先向右边扫描。改进后我是将分界点与两端点的距离来决定磁头一开始的移动方向，当分界点与序列首端点的距离比分界点与序列尾部端点的距离小时，则先向左边扫描；当分界点与序列尾部端点的距离比分界点与序列首部端点的距离小时，则先向右边扫描。可以看到这一改进还是挺有用的。但是实际中我们并不能决定磁头一开始的移动方向。
思考题：
1、通过对每个算法进行时间复杂度分析对比，每个算法的效率如何？
先来先服务算法的时间复杂度为O（n）；最短寻道时间优先算法的时间复杂度为O(nlogn)；扫描算法的时间复杂度为O(nlogn)。可以看到先来先服务算法虽然时间复杂度最低，但是其磁道移动数是最多的，可以看出其效率不高，仅应用在磁盘I/O较少的场合。最短寻道时间优先算法时间复杂度和扫描算法时间复杂度一样，在我的程序中可以看到他们的磁道移动总数差不多，但是最短寻道时间有可能出现“饿死”现象，且不能保证平均寻道时间最短；扫描算法总体来说寻道性能较好，虽然能避免“饿死”现象，但是不利于远离磁头一端的访问请求。
2、若所有硬盘全部设计成电子硬盘，哪个磁盘调度算法最合适？
因为电子硬盘读取速度极快而且不涉及磁盘调度臂的问题，所以应该使用时间复杂度最低的FIFS算法。
