一、实验目的
1、 了解磁盘调度的策略和原理；
2、 理解和掌握磁盘调度算法——先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、电梯扫描算法（SCAN）。
二、实验内容
1、 模拟先来先服务法（First-Come, First-Served，FCFS），最短寻道时间优先法（Shortest Seek Time First， SSTF），电梯扫描算法（SCAN）三种磁盘调度算法；
2、 对三种算法进行对比分析。
3、 输入为一组请求访问磁道序列，输出为每种调度算法的磁头移动轨迹和移动的总磁道数。
三、实验原理
1、先来先服务算法（FCFS）: 按先来后到次序服务，未作优化。最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。 采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。
2、最短寻道时间优先算法（SSTF） : 最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（SSTF）调度，FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。
3、扫描算法（SCAN）： SCAN 算法又称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。
四、实验中用到的系统调用函数
实验只是模拟实现磁盘调度功能，不需要系统调用函数。
五、流程图
1、先来先服务算法（FCFS）
2、最短寻道时间优先算法（SSTF）
3、扫描算法（SCAN）
六、源代码
#include <stdio.h>
#include <stdlib.h>
#include<time.h>
int *queue; //请求磁盘服务队列
int start; //磁头最初位置
int n; //所选磁道个数
#define false 0
#define true 1
void init()
{
start=rand()%200; //磁道范围 0~200
n=rand()%6+10; //所选磁道个数10到15；
queue=(int*)malloc(sizeof(int)*n); //分配内存
for(int i=0;i<n;i++)
{
queue[i]=rand()%1000; //初始化队列
}
printf("磁头初始位置：%d",start);
printf("\n");
printf("请求磁盘服务队列：");
for(int i=0;i<n;i++)
{
printf("%d ",queue[i]);
}
printf("\n");
}
void FCFS()
{
int count=0; //移动的总磁道数
count+=abs(start-queue[0]);
for(int i=0;i<n-1;i++)
{
count+=abs(queue[i]-queue[i+1]); //计算移动的总磁道数
}
printf("\n");
printf("-----------先来先服务法(FCFS)-----------\n");
printf("磁头移动轨迹:%d->",start);
for(int i=0;i<n;i++)
{
printf("%d->",queue[i]);
}
printf("end\n");
printf("移动的总磁道数:%d\n",count);
}
void SSTF()
{
int count=0; //移动的总磁道数
int i,j;
int record[n]; //标记是否已经服务
int Service[n]; //记录磁头移动轨迹
int min; //距离磁头最小的距离
int index = 0; //下一个服务对象的下标
int temp=start; //磁头位置
for(i=0;i<n;i++)
{
record[i]=false; //初始化
}
for(i=0;i<n;i++)
{
min=1000; //每个循环都要给min赋一个最大值
for(j=0;j<n;j++)
{
if(record[j]==false) //如果没有服务过
{
if (abs(queue[j] - temp) < min) //找出距离磁头最近的磁道
{
min = abs(queue[j] - temp); //更新最小距离
index = j; //记录最近的磁道对应的下标
}
}
}
record[index] = true; //标记已服务
Service[i]= queue[index]; //记录磁头移动轨迹
temp = queue[index]; //更新磁头位置
}
//计算移动的总磁道数
count+=abs(start-Service[0]);
for(int i=0;i<n-1;i++)
{
count+=abs(Service[i]-Service[i+1]);
}
printf("\n");
printf("--------最短寻道时间优先法(SSTF)--------\n");
printf("磁头移动轨迹:%d->",start);
for(int i=0;i<n;i++)
{
printf("%d->",Service[i]);
}
printf("end\n");
printf("移动的总磁道数:%d\n",count);
}
//折半插入排序
void BInsertSort(int a[])
{
int low = 0;
int high = 0;
int mid;
int temp = 0;
for (int i=1; i<n; i++) {
low=0;
high=i-1;
temp=a[i];
//采用折半查找法判断插入位置，最终变量 low 表示插入位置
while (low<=high)
{
mid=(low+high)/2;
if (a[mid]>temp)
{
high=mid-1;
}
else
{
low=mid+1;
}
}
//有序表中插入位置后的元素统一后移
for (int j=i; j>low; j--)
{
a[j]=a[j-1];
}
a[low]=temp;//插入元素
}
}
void SCAN()
{
int temp[n]; //记录从小到大排序后的请求磁盘服务队列
int count=0; //移动的总磁道数
int index=0;
int i;
for(i=0;i<n;i++)
{
temp[i]=queue[i]; //初始化
}
BInsertSort(temp); //调用排序算法
for(i=0;i<n;i++)
{
if(temp[i]>=start)
{
index=i; //请求访问磁道大于磁头磁道时，index赋值为对应下标
break;
}
}
if(start>=temp[n-1]) //当磁道大于所有请求访问磁道时，index赋值为n-1
index=n-1;
printf("\n");
printf("--------------电梯法(SCAN)--------------\n");
printf("\n");
if(index==0) //磁头所在磁道最小
{
printf("磁头所在磁道最小，磁头只会向道号大的方向移动\n");
printf("磁头移动轨迹:%d->",start);
for(i=0;i<n;i++)
{
printf("%d->",temp[i]);
}
printf("end\n");
count+=abs(start-temp[0]);
for(i=0;i<n-1;i++)
{
count+=abs(temp[i]-temp[i+1]);
}
printf("移动的总磁道数:%d\n",count);
printf("\n");
}
else if((index==n-1)&&(start>=temp[n-1])) //磁头所在磁道最大
{
printf("磁头所在磁道最大，磁头只会向道号小的方向移动\n");
printf("磁头移动轨迹:%d->",start);
for(i=n-1;i>=0;i--)
{
printf("%d->",temp[i]); //输出磁头移动轨迹
}
printf("end\n");
count+=abs(start-temp[n-1]);
for(i=n-1;i>0;i--)
{
count+=abs(temp[i]-temp[i-1]); //计算移动的总磁道数
}
printf("移动的总磁道数:%d\n",count);
printf("\n");
}
else
{
printf("磁头最初正向道号小的方向移动\n");
printf("磁头移动轨迹:%d->",start);
for(i=index-1;i>=0;i--) //输出磁道号比磁头初始磁道小的队列
{
printf("%d->",temp[i]);
}
for(i=index;i<n;i++) //输出磁道号比磁头初始磁道大的队列
{
printf("%d->",temp[i]);
}
printf("end\n");
//计算移动的总磁道数
count+=abs(start-temp[index-1]);
for(i=index-1;i>0;i--)
{
count+=abs(temp[i]-temp[i-1]);
}
count+=abs(temp[0]-temp[index]);
for(i=index;i<n-1;i++)
{
count+=abs(temp[i]-temp[i+1]);
}
printf("移动的总磁道数:%d\n",count);
printf("\n");
/
printf("磁头最初正向道号大的方向移动\n");
printf("磁头移动轨迹:%d->",start);
for(i=index;i<n;i++) //输出磁道号比磁头初始磁道大的队列
{
printf("%d->",temp[i]);
}
for(i=index-1;i>=0;i--) //输出磁道号比磁头初始磁道小的队列
{
printf("%d->",temp[i]);
}
printf("end\n");
count=0;
//计算移动的总磁道数
count+=abs(start-temp[index]);
for(i=index;i<n-1;i++)
{
count+=abs(temp[i]-temp[i+1]);
}
count+=abs(temp[n-1]-temp[index-1]);
for(i=index-1;i>0;i--)
{
count+=abs(temp[i]-temp[i-1]);
}
printf("移动的总磁道数:%d\n",count);
printf("\n");
}
}
int main()
{
srand((unsigned int)time(NULL));
init(); //初始化
FCFS(); //先来先服务法
SSTF(); //最短寻道时间优先法
SCAN(); //电梯法
free(queue);
}
七、实验结果及分析
FCFS算法的移动的总磁道数远远高于其他两种算法，FCFS算法基于先来先服务原则，经常出现磁头在整个磁盘大幅度移动，导致每次磁道请求移动的磁道数大，导致磁头移动的总磁道数大。
在该程序中请求队列已经固定，所以SSTF算法表现良好，但如果是在实际中，操作系统的访问是动态申请的，这时就非常容易陷入高度局部化，即距离磁头较远的请求服务得不到满足。
SCAN算法考虑到操作系统的动态申请访问，避免了SSTF中高度局部化的缺点，在磁道来回扫描，遇到所需的磁道时就进行服务，磁头仅移动到每个方向上有服务请求的最远的道上。算法中磁头位置有三种情况：最小，最大，在请求队列范围内，前面两种情况磁头只会向一个方向移动，最后一种情况磁头可以向道号小方向，也可以向道号大方向移动。
八、思考题
1、通过对每个算法进行时间复杂度分析对比，每个算法的效率如何？
FCFS算法直接从请求序列读出数据，只需要计算磁头移动的总磁道数，故时间复杂度为O(n)。
SSTF算法要求选择的下一个请求距当前磁头所在位置有最小的寻道时间，每次都需要遍历n次获得最小值对应的磁道，一共需要执行n次，故时间复杂度为O(n²)。
SCAN算法调用快速排序对请求队列进行排序，折半插入排序时间复杂度平均情况为O(nlog2n)，再根据磁头位置的三种情况：最小，最大，在请求队列范围内，分开计算。整个算法的时间复杂度为O(nlog2n)。
FCFS算法虽然时间复杂度小，效率最高，但是平均寻道长度显著高于其他两个算法，对磁盘移动臂的消耗大。SSTF算法可能会导致距离磁头较远的请求服务很久才能得到回应。SCAN算法则弥补了SSTF的缺陷。
2、若所有硬盘全部设计成电子硬盘，哪个磁盘调度算法最合适？
因为电子硬盘不需要像机械硬盘一样寻道，所以先来先服务算法最合适。