操作系统原理—磁盘调度算法
操作系统原理—磁盘调度算法
磁盘调度算法是操作系统中用于优化磁盘I/O操作的重要机制。本文将详细介绍四种常见的磁盘调度算法：先来先服务（FCFS）、最短寻道时间优先（SSTF）、扫描（SCAN）和循环扫描（C-SCAN）。通过具体的例子和计算过程，帮助读者理解这些算法的工作原理和优缺点。
一、四种磁盘调度算法
例：现有8个进程先后提出的磁盘I/O请求 ：98 138 37 122 14 124 65 67，当前磁头位置为53号磁道，磁头向内移动。分别采用FCFS算法、SSTF算法、SCAN算法以及C-SCAN算法，画出磁头移动的轨迹，计算平均寻道长度。
1. 先来先服务（FCFS）算法
根据进程请求访问磁盘的先后次序进行调度。
优点：公平、简单。每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。
缺点：由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。当请求到达顺序不连续时，会导致寻道时间不均匀，可能导致长时间等待。
服务序列 53 98 138 37 122 14 124 65 67
移动距离 0 45 40 101 85 108 110 59 2
移动总距离：550
平均寻道长度：550/8=68.75
2. 最短寻道时间优先（SSTF）算法
优点：选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道，以使每次的寻找时间最短。能提供比FCFS算法更好的性能。
缺点：需要频繁地移动磁头，可能导致频繁的寻道操作。总是选择最小寻找时间并不能保证平均寻找时间最小。
服务序列 53 65 67 37 14 98 122 124 138
移动距离 0 12 2 30 23 84 24 2 14
移动总距离：191
平均寻道长度：191/8=23.875
3. 扫描（SCAN）算法
SSTF算法会产生饥饿的原因在于：磁头有可能在一个小区域内来回来去地移动。为了防止这个问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法(SCAN)的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。
优点：在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。
缺点：需要处理边界情况，如从起始位置开始或从最后一个请求的位置开始。
对于先后到达的磁盘访问请求，电梯调度算法首先选择移臂方向，磁臂在该方向上移动的过程中依次处理途经的各个访问请求，直到该方向上再无请求时，改变移臂方向，依次处理相反方向上遇到的各个请求。如果同一柱面上有多个请求，还需进行旋转优化。
服务序列 53 65 67 98 122 124 138 37 14
移动距离 0 12 2 31 24 2 14 101 23
移动总距离：209
平均寻道长度：209/8=26.125
4. 循环扫描（C-SCAN）算法
在该算法中，磁头仅在一个移动方向上提供访问服务。
磁臂从磁盘开始端柱面至结束端柱面移动的过程中依次处理途经请求，然后，直接返回开始端柱面重复进行，归途中并不响应请求。开始端与结束端柱面构成了一个循环。
优点：在扫描算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动至起始端而不服务任何请求。避免了磁头频繁往复移动的问题，提高了效率。
缺点：仍然存在扫描方向和扫描过程中的请求处理规则的问题，这些因素会对其性能产生影响。
服务序列 53 65 67 98 122 124 138 14 37
移动距离 0 12 2 31 24 2 14 124 23
移动总距离：232
平均寻道长度：232/8=29
二、调度算法的选择原则
1）SSTF较为普遍且很有吸引力。
2）SCAN和C-SCAN对磁盘负荷较大的系统会执行得更好，这是因为它不可能产生饥饿问题。
3）对于任何调度算法，性能依赖于请求的类型和数量。
4）磁盘服务请求很大程度上收文件分配方法所影响。
5）磁盘调度算法应作为一个操作系统的独立模块。因为，如果有必要，可以方便替换成另外一种不同的算法。
6）SSTF或SCAN是比较合理地默认算法。
三、代码
#include <iostream>
#include <string>
#include <iomanip>
#include<math.h>
#include <algorithm>
using namespace std;
#define MAX 999999 //最大值
#define max_length 100 //存储长度
int begin_local=0; //当前位置
int length=0; //长度
int Node[max_length]= {0}; //存储信息
int Changed_Node[max_length]= {0}; //生成的数据
//大小判断函数
bool cmp(int a,int b)//int为数组数据类型
{
return a<b;//降序排列
}
//输出函数
void OUTPUT(string Algorithm_Name)
{
int All_length=0;
cout<<Algorithm_Name<<"算法:"<<endl;
cout<<"----------------------------------------------------------------"<<endl;
//服务序列
cout<<" 服务序列: ";
for( int i=0; i<=length; i++ )
cout << Changed_Node[i] <<"\t" ;
cout<<endl;
//单次移动距离
cout<<" 移动距离: ";
for( int i=0,temp=begin_local; i<=length; i++ )
{
cout << abs(Changed_Node[i]-temp) << "\t" ;
All_length+=abs(Changed_Node[i]-temp);
temp= Changed_Node[i];
}
cout<<endl;
//移动的距离与平均记录
cout<<" 移动的总距离："<<All_length<<endl;
printf(" 平均寻道长度：%.3f\n", (double)All_length/length);
cout<<"----------------------------------------------------------------\n"<<endl;
}
void FCFS() //先进先出
{
Changed_Node[0]=begin_local;
for (int i=0; i<length ; i++ ) Changed_Node[i+1]=Node[i];
OUTPUT("FCFS先进先出");
}
void SSTF() //最短服务时间优先
{
int Tag[max_length]= {0},temp=MAX,Now=0;
Changed_Node[0]=begin_local;//初始位置
for (int i=1; i<=length; i++)
{
for (int j=0,temp=MAX; j<length; j++ )
{//查找最小的值
if(abs(Node[j]-Changed_Node[i-1])<=temp&&Tag[j]==0)
{
Now=j;
temp=abs(Node[j]-Changed_Node[i-1]);
}
}
Changed_Node[i]=Node[Now];
Tag[Now]=1;//标记
}
OUTPUT("SSTF最短服务时间优先");
}
void SCAN() //SCAN扫描
{
int CopyNode[max_length]= {0},temp=1;
memcpy(CopyNode,Node,length*sizeof(int));//复制数组
sort(CopyNode,CopyNode+length,cmp); //排序数组
Changed_Node[0]=begin_local; //初始位置
for (int i=0; i<length ; i++ ) //正向扫描
{
if(CopyNode[i]>=begin_local) Changed_Node[temp++]=CopyNode[i];
}
for (int i=length-1; i>=0; i-- ) //反向扫描
{
if(CopyNode[i]<=begin_local) Changed_Node[temp++]=CopyNode[i];
}
OUTPUT("SCAN扫描算法");
}
void C_SCAN() //循环扫描
{
int CopyNode[max_length]= {0},temp=1;
memcpy(CopyNode,Node,length*sizeof(int)); //复制数组
sort(CopyNode,CopyNode+length,cmp); //排序数组
Changed_Node[0]=begin_local; //初始位置
for (int i=0; i<length ; i++ )//正向扫描1
{
if(CopyNode[i]>=begin_local) Changed_Node[temp++]=CopyNode[i];
}
for (int i=0; i<length ; i++ )//正向扫描2
{
if(CopyNode[i]<=begin_local) Changed_Node[temp++]=CopyNode[i];
}
OUTPUT("C_SCAN循环扫描");
}
void INPUT()
{
printf("\n请输入调度磁道数量: ");
scanf("%d",&length);
printf("请输入磁道调度序列: ");
for(int i=0; i<length; i++) scanf("%d",&Node[i]);
printf("请输入当前的磁道号: ");
scanf("%d",&begin_local);
cout<<endl;
}
int main()
{
INPUT(); //输入数据
FCFS(); //先进先出
SSTF(); //最短时间
SCAN(); //扫描
C_SCAN(); //单向扫描
return 0;
}
四、运行结果
五、总结
先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）和循环扫描算法（CSCAN）都是用于磁盘调度的算法。
综上所述，每种算法都有其优点和缺点。在选择适合特定应用场景的算法时，需要根据具体需求和环境因素进行权衡和考虑。