操作系统原理：磁盘调度算法详解

创作时间:

作者:

@小白创作中心

操作系统原理：磁盘调度算法详解

引用

CSDN

https://blog.csdn.net/weixin_63455272/article/details/139607580

磁盘调度算法是操作系统中一个重要的概念，它决定了磁盘如何响应多个并发的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）算法

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）算法

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）算法

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）算法

C-SCAN算法规定磁头仅在一个移动方向上提供访问服务。

优点：在扫描算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动至起始端而不服务任何请求。避免了磁头频繁往复移动的问题，提高了效率。
缺点：仍然存在扫描方向和扫描过程中的请求处理规则的问题，这些因素会对其性能产生影响。

服务序列：53 65 67 98 122 124 138 14 37
移动距离：0 12 2 31 24 2 14 124 23

移动总距离：232
平均寻道长度：232/8=29

二、调度算法的选择原则

SSTF较为普遍且很有吸引力。
SCAN和C-SCAN对磁盘负荷较大的系统会执行得更好，这是因为它不可能产生饥饿问题。
对于任何调度算法，性能依赖于请求的类型和数量。
磁盘服务请求很大程度上收文件分配方法所影响。
磁盘调度算法应作为一个操作系统的独立模块。因为，如果有必要，可以方便替换成另外一种不同的算法。
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;
}