淘小兔

操作系统：磁盘调度算法

分类：知识

操作系统课程的相关实验

6个实验相关的代码下载地址：http://download.csdn.net/detail/houchaoqun_xmu/9865648

 

磁盘调度算法

 

一、概念介绍和案例解析

先来先服务(FCFS，First Come First Served)：

  这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。
  此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。
  下图示出了有9个进程先后提出磁盘I/O请求时，按FCFS算法进行调度的情况。这里将进程号(请求者)按他们发出请求的先后次序排队。这样，平均寻道距离为55.3条磁道，与后面即将讲到的几种调度算法相比，其平均寻道距离较大，故FCFS算法仅适用于请求磁盘I/O的进程数目较少的场合。 

操作系统：磁盘调度算法

  • 最短寻道时间优先(SSTF，Shortest Seek Time First)：

  该算法选择这样的进程：其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。但这种算法不能保证平均寻道时间最短。
  下图示出了按SSTF算法进行调度时，各进程被调度的次序、每次磁头移动的距离，以及9次调度磁头平均移动的距离。
  比较图5-25和图5-26可以看出，SSTF算法的平均每次磁头移动距离明显低于FCFS的距离，因而SSTF较之FCFS有更好的寻道性能，故过去曾一度被广泛采用。 

操作系统：磁盘调度算法

  • 扫描(SCAN)算法：

1) 进程“饥饿”现象
  SSTF算法虽然能获得较好的寻道性能，但却可能导致某个进程发生“饥饿”(Starvation)现象。
  因为只要不断有新进程的请求到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必然优先满足。
  对SSTF算法略加修改后所形成的SCAN算法，即可防止老进程出现“饥饿”现象。 
2) SCAN算法
  该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动。这时，同样也是每次选择这样的进程来调度，即要访问的磁道在当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现象。
  由于在这种算法中磁头移动的规律颇似电梯的运行，因而又常称之为电梯调度算法。图 5-27示出了按SCAN算法对9个进程进行调度及磁头移动的情况。 

操作系统：磁盘调度算法

  • 循环扫描(CSCAN)算法：

  SCAN算法既能获得较好的寻道性能，又能防止“饥饿”现象，故被广泛用于大、中、小型机器和网络中的磁盘调度。
  但SCAN也存在这样的问题：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该进程必须等待，待磁头继续从里向外，然后再从外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被大大地推迟。
  为了减少这种延迟，CSCAN算法规定磁头单向移动，例如，只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问的磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。
  采用循环扫描方式后，上述请求进程的请求延迟将从原来的2T减为T + Smax，其中，T为由里向外或由外向里单向扫描完要访问的磁道所需的寻道时间，而Smax是将磁头从最外面被访问的磁道直接移到最里面欲访问的磁道(或相反)的寻道时间。图5-28示出了CSCAN算法对9个进程调度的次序及每次磁头移动的距离。 

操作系统：磁盘调度算法

二、实验介绍

知识兔

 

  • 问题描述：

 

  设计程序模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。

 

  • 程序要求：

 

1）利用先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法模拟磁道访问过程。

2）模拟四种算法的磁道访问过程，给出每个磁道访问的磁头移动距离。

3）输入：磁道个数n和磁道访问序列，开始磁道号m和磁头移动方向（对SCAN和循环SCAN算法有效），算法选择1-FCFS，2-SSTF，3-SCAN，4-循环SCAN。

4）输出：每种算法的平均寻道长度。

 

三、程序设计和程序开发

  • 算法思想：

1）先来先服务(FCFS，FirstCome First Served)：根据进程请求访问磁盘的先后次序进行调度此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。

2）最短寻道时间优先(SSTF，ShortestSeek Time First)：该算法选择这样的进程：其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。但这种算法不能保证平均寻道时间最短。

3）扫描(SCAN)算法：算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。

4）循环扫描(CSCAN)算法：CSCAN算法规定磁头单向移动，例如，只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问的磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。

核心算法：

void FCFS(){cout<<"******* 你选择了FCFS算法 ***********************************"<<endl;initial();MoveDistance[0] = getPositive(TrackOrder[0],StartTrack);totalDistance = MoveDistance[0];VisitOrder[0] = TrackOrder[0];for (int i=1;i<TrackNum;i++){MoveDistance[i] = getPositive(TrackOrder[i],TrackOrder[i-1]);totalDistance += MoveDistance[i];VisitOrder[i] = TrackOrder[i];}AverageDistance = totalDistance*1.0/TrackNum;display();cout<<"******* FCFS算法结束     ***********************************"<<endl;}
void SSTF(){cout<<"******* 你选择了SSTF算法 ***********************************"<<endl;initial();int CurrentTrack = StartTrack;  //int i,j,pointMin;int disTemp[MaxNumber];for (i = 0;i<TrackNum;i++){for (j = 0;j<TrackNum;j++){if (!isVisited[j]){disTemp[j] = getPositive(TrackOrder[j],CurrentTrack);}elsedisTemp[j] = 10000;  //表示无穷远，即访问过的磁道就不再访问}pointMin = 0;for (j = 0;j<TrackNum;j++){if (disTemp[pointMin] > disTemp[j]){pointMin = j;   //指向最小的位置}}VisitOrder[i] = TrackOrder[pointMin];  //给访问序列赋值MoveDistance[i] = getPositive(TrackOrder[pointMin],CurrentTrack);  //计算每次的移动距离totalDistance += MoveDistance[i];   //累计移动距离CurrentTrack = TrackOrder[pointMin];   //改变当前的磁道号isVisited[pointMin] = true;  //将当前的磁道号设置为已访问}AverageDistance = totalDistance*1.0/(TrackNum);display();cout<<"******* SSTF算法结束     ***********************************"<<endl;}
void SCAN(){/*算法思想：1. SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的   直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动2. 本程序先将磁道序列从小到大进行排序，再进行相应的处理，时间复杂度为取决于排序算法的时间复杂度*/cout<<"******* 你选择了SCAN算法 ***********************************"<<endl;cout<<"******* 请选择头移动方向 *******"<<endl;cout<<"******* 0表示向磁道增加的方向访问 *******"<<endl;cout<<"******* 1表示向磁道减小的方向访问 *******"<<endl;cout<<"direction = ";cin>>direction;initial();int TrackOrderIndex[MaxNumber],SortTrackOrder[MaxNumber];int i,j,temp,tempIndex;for (i = 0;i<TrackNum;i++){TrackOrderIndex[i] = i;SortTrackOrder[i] = TrackOrder[i];}for (i = TrackNum - 1;i>0;i--){for (j = 0;j<i;j++){if (SortTrackOrder[j]>=SortTrackOrder[j+1]){//更新排序后的磁道号temp = SortTrackOrder[j];SortTrackOrder[j] = SortTrackOrder[j+1];SortTrackOrder[j+1] = temp;//更新排序后的磁道号索引值tempIndex = TrackOrderIndex[j];TrackOrderIndex[j] = TrackOrderIndex[j+1];TrackOrderIndex[j+1] = tempIndex;}//if}//for}//for   获得排序后的磁道号以及对应的原来的索引值int point = 0;while(StartTrack>=SortTrackOrder[point]){point++;}  //找到当前对应的：既在当前磁道之外，又是距离最近的磁道号索引值pointint count = 0; int currentTrack = StartTrack;if (direction == 0)  //向磁道增加的方向访问{cout<<"            向磁道增加的方向访问"<<endl;for (i = point;i<TrackNum;i++){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}for (i = point - 1;i>=0;i--){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}}//ifelse if (direction == 1){cout<<"            向磁道减小的方向访问"<<endl;for (i = point - 1;i>=0;i--){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}for (i = point;i<TrackNum;i++){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}}//elsefor (i = 0;i<TrackNum;i++){totalDistance += MoveDistance[i];}AverageDistance = (totalDistance*1.0)/TrackNum;display();cout<<"******* SCAN算法结束     ***********************************"<<endl;}
void ImprovedSCAN(){cout<<"******* 你选择了ImprovedSCAN算法 ***********************************"<<endl;cout<<"******* 请选择头移动方向 *******"<<endl;cout<<"******* 0表示向磁道增加的方向访问 *******"<<endl;cout<<"******* 1表示向磁道减小的方向访问 *******"<<endl;cin>>direction;initial();int TrackOrderIndex[MaxNumber],SortTrackOrder[MaxNumber];int i,j,temp,tempIndex;for (i = 0;i<TrackNum;i++){TrackOrderIndex[i] = i;SortTrackOrder[i] = TrackOrder[i];}for (i = TrackNum - 1;i>0;i--){for (j = 0;j<i;j++){if (SortTrackOrder[j]>=SortTrackOrder[j+1]){//更新排序后的磁道号temp = SortTrackOrder[j];SortTrackOrder[j] = SortTrackOrder[j+1];SortTrackOrder[j+1] = temp;//更新排序后的磁道号索引值tempIndex = TrackOrderIndex[j];TrackOrderIndex[j] = TrackOrderIndex[j+1];TrackOrderIndex[j+1] = tempIndex;}//if}//for}//for   获得排序后的磁道号以及对应的原来的索引值int point = 0;while(StartTrack>=SortTrackOrder[point]){point++;}  //找到当前对应的：既在当前磁道之外，又是距离最近的磁道号索引值pointint count = 0; int currentTrack = StartTrack;if (direction == 0)  //向磁道增加的方向访问{cout<<"            向磁道增加的方向访问"<<endl;for (i = point;i<TrackNum;i++){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}for (i =0;i<point;i++){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}}//ifelse if (direction == 1){cout<<"            向磁道减小的方向访问"<<endl;for (i = 0;i<point;i++){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}for (i = point;i<TrackNum;i++){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}}//elsefor (i = 0;i<TrackNum;i++){totalDistance += MoveDistance[i];}AverageDistance = (totalDistance*1.0)/TrackNum;display();cout<<"******* ImprovedSCAN算法结束     ***********************************"<<endl;}

四、实验结果分析

实验数据：

1078 30 9 15 102 140 156 54 45 125100

实验结果：

操作系统：磁盘调度算法

操作系统：磁盘调度算法

五、实验源码

// 操作系统_实验六（磁盘调度算法）.cpp : 定义控制台应用程序的入口点。//#include <iostream>#include <fstream>#include <iomanip>using namespace std;const int MaxNumber=100;int TrackNum;int StartTrack;int TrackOrder[MaxNumber];int VisitOrder[MaxNumber];bool isVisited[MaxNumber];int MoveDistance[MaxNumber];int totalDistance;double AverageDistance;bool direction;void input();void initial();int getPositive(int num1,int num2);void FCFS();void SSTF();void SCAN();void ImprovedSCAN();void display();void input(){ifstream readData;readData.open("data2.txt");readData>>TrackNum;  //磁道个数for (int i=0;i<TrackNum;i++){readData>>TrackOrder[i];   //磁道访问序列}readData>>StartTrack;  //开始磁道号cout<<"文件信息如下："<<endl;cout<<"磁道个数TrackNum = "<<TrackNum<<endl;cout<<"磁道访问序列：";for (int i=0;i<TrackNum;i++){cout<<TrackOrder[i]<<" ";}cout<<endl;cout<<"开始磁道号StartTrack = "<<StartTrack<<endl;cout<<"****************开始******************"<<endl;}int getPositive(int num1,int num2){if (num1 - num2>0){return (num1 - num2);}elsereturn (num2 - num1);}void initial(){for (int i=0;i<TrackNum;i++){MoveDistance[i] = 0;VisitOrder[i] = TrackOrder[i];isVisited[i] = false;}totalDistance = 0;AverageDistance = 0;}void FCFS(){cout<<"******* 你选择了FCFS算法 ***********************************"<<endl;initial();MoveDistance[0] = getPositive(TrackOrder[0],StartTrack);totalDistance = MoveDistance[0];VisitOrder[0] = TrackOrder[0];for (int i=1;i<TrackNum;i++){MoveDistance[i] = getPositive(TrackOrder[i],TrackOrder[i-1]);totalDistance += MoveDistance[i];VisitOrder[i] = TrackOrder[i];}AverageDistance = totalDistance*1.0/TrackNum;display();cout<<"******* FCFS算法结束     ***********************************"<<endl;}void SSTF(){cout<<"******* 你选择了SSTF算法 ***********************************"<<endl;initial();int CurrentTrack = StartTrack;  //int i,j,pointMin;int disTemp[MaxNumber];for (i = 0;i<TrackNum;i++){for (j = 0;j<TrackNum;j++){if (!isVisited[j]){disTemp[j] = getPositive(TrackOrder[j],CurrentTrack);}elsedisTemp[j] = 10000;  //表示无穷远，即访问过的磁道就不再访问}pointMin = 0;for (j = 0;j<TrackNum;j++){if (disTemp[pointMin] > disTemp[j]){pointMin = j;   //指向最小的位置}}VisitOrder[i] = TrackOrder[pointMin];  //给访问序列赋值MoveDistance[i] = getPositive(TrackOrder[pointMin],CurrentTrack);  //计算每次的移动距离totalDistance += MoveDistance[i];   //累计移动距离CurrentTrack = TrackOrder[pointMin];   //改变当前的磁道号isVisited[pointMin] = true;  //将当前的磁道号设置为已访问}AverageDistance = totalDistance*1.0/(TrackNum);display();cout<<"******* SSTF算法结束     ***********************************"<<endl;}void SCAN(){/*算法思想：1. SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的   直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动2. 本程序先将磁道序列从小到大进行排序，再进行相应的处理，时间复杂度为取决于排序算法的时间复杂度*/cout<<"******* 你选择了SCAN算法 ***********************************"<<endl;cout<<"******* 请选择头移动方向 *******"<<endl;cout<<"******* 0表示向磁道增加的方向访问 *******"<<endl;cout<<"******* 1表示向磁道减小的方向访问 *******"<<endl;cout<<"direction = ";cin>>direction;initial();int TrackOrderIndex[MaxNumber],SortTrackOrder[MaxNumber];int i,j,temp,tempIndex;for (i = 0;i<TrackNum;i++){TrackOrderIndex[i] = i;SortTrackOrder[i] = TrackOrder[i];}for (i = TrackNum - 1;i>0;i--){for (j = 0;j<i;j++){if (SortTrackOrder[j]>=SortTrackOrder[j+1]){//更新排序后的磁道号temp = SortTrackOrder[j];SortTrackOrder[j] = SortTrackOrder[j+1];SortTrackOrder[j+1] = temp;//更新排序后的磁道号索引值tempIndex = TrackOrderIndex[j];TrackOrderIndex[j] = TrackOrderIndex[j+1];TrackOrderIndex[j+1] = tempIndex;}//if}//for}//for   获得排序后的磁道号以及对应的原来的索引值int point = 0;while(StartTrack>=SortTrackOrder[point]){point++;}  //找到当前对应的：既在当前磁道之外，又是距离最近的磁道号索引值pointint count = 0; int currentTrack = StartTrack;if (direction == 0)  //向磁道增加的方向访问{cout<<"            向磁道增加的方向访问"<<endl;for (i = point;i<TrackNum;i++){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}for (i = point - 1;i>=0;i--){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}}//ifelse if (direction == 1){cout<<"            向磁道减小的方向访问"<<endl;for (i = point - 1;i>=0;i--){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}for (i = point;i<TrackNum;i++){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}}//elsefor (i = 0;i<TrackNum;i++){totalDistance += MoveDistance[i];}AverageDistance = (totalDistance*1.0)/TrackNum;display();cout<<"******* SCAN算法结束     ***********************************"<<endl;}void ImprovedSCAN(){cout<<"******* 你选择了ImprovedSCAN算法 ***********************************"<<endl;cout<<"******* 请选择头移动方向 *******"<<endl;cout<<"******* 0表示向磁道增加的方向访问 *******"<<endl;cout<<"******* 1表示向磁道减小的方向访问 *******"<<endl;cin>>direction;initial();int TrackOrderIndex[MaxNumber],SortTrackOrder[MaxNumber];int i,j,temp,tempIndex;for (i = 0;i<TrackNum;i++){TrackOrderIndex[i] = i;SortTrackOrder[i] = TrackOrder[i];}for (i = TrackNum - 1;i>0;i--){for (j = 0;j<i;j++){if (SortTrackOrder[j]>=SortTrackOrder[j+1]){//更新排序后的磁道号temp = SortTrackOrder[j];SortTrackOrder[j] = SortTrackOrder[j+1];SortTrackOrder[j+1] = temp;//更新排序后的磁道号索引值tempIndex = TrackOrderIndex[j];TrackOrderIndex[j] = TrackOrderIndex[j+1];TrackOrderIndex[j+1] = tempIndex;}//if}//for}//for   获得排序后的磁道号以及对应的原来的索引值int point = 0;while(StartTrack>=SortTrackOrder[point]){point++;}  //找到当前对应的：既在当前磁道之外，又是距离最近的磁道号索引值pointint count = 0; int currentTrack = StartTrack;if (direction == 0)  //向磁道增加的方向访问{cout<<"            向磁道增加的方向访问"<<endl;for (i = point;i<TrackNum;i++){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}for (i =0;i<point;i++){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}}//ifelse if (direction == 1){cout<<"            向磁道减小的方向访问"<<endl;for (i = 0;i<point;i++){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}for (i = point;i<TrackNum;i++){VisitOrder[count] = SortTrackOrder[i];MoveDistance[count] = getPositive(VisitOrder[count],currentTrack);currentTrack = VisitOrder[count];count++;}}//elsefor (i = 0;i<TrackNum;i++){totalDistance += MoveDistance[i];}AverageDistance = (totalDistance*1.0)/TrackNum;display();cout<<"******* ImprovedSCAN算法结束     ***********************************"<<endl;}void display(){cout<<setw(16)<<"从"<<StartTrack<<"号磁道开始"<<setw(4)<<endl;cout<<setw(2)<<"被访问的下一个磁道号   "<<setw(6)<<"   移到距离（磁道数）"<<setw(4)<<endl;for (int i=0;i<TrackNum;i++){cout<<setw(10)<<VisitOrder[i]<<setw(24)<<MoveDistance[i]<<setw(8)<<endl;}cout<<"平均寻找长度 AverageDistance= "<<AverageDistance<<endl;}int main(){input();int chooseAlgorithm;int IsContinue = 1;while(IsContinue){cout<<"******* 请选择算法 *******"<<endl;cout<<"******* 1-FCFS     *******"<<endl;cout<<"******* 2-SSTF     *******"<<endl;cout<<"******* 3-SCAN     *******"<<endl;cout<<"******* 4-循环SCAN *******"<<endl;cout<<"chooseAlgorithm = ";cin>>chooseAlgorithm;switch(chooseAlgorithm){case 1:FCFS();break;case 2:SSTF();break;case 3:SCAN();break;case 4:ImprovedSCAN();break;default:cout<<"******* 警告：请输入正确的选择！ *******"<<endl;break;}cout<<"******* 是否继续选择算法？ *******"<<endl;cout<<"******* 0代表退出 ******* "<<endl;cout<<"******* 1代表继续 ******* "<<endl;cout<<"IsContinue = ";cin>>IsContinue;}cout<<"****************结束******************"<<endl;return 0;}

 

下载仅供下载体验和测试学习，不得商用和正当使用。

下载体验

请输入密码查看内容！

如何获取密码？

 

点击下载