一、實驗目的
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、若所有硬碟全部設計成電子硬碟，哪個磁盤排程算法最合适？
因為電子硬碟不需要像機械硬碟一樣尋道，是以先來先服務算法最合适。