磁盘调度算法FCFS和SSTF的算法思路

FCFS（First Come First Serve）磁盘调度算法是一种非常简单的调度算法，它按照磁盘请求的先后顺序进行处理，即先到先服务，不考虑寻道时间、旋转延迟时间等因素。这种算法优点是实现简单，缺点是平均寻道时间较长，可能会出现饥饿现象。

SSTF（Shortest Seek Time First）磁盘调度算法是一种根据磁头移动最小化寻道时间的算法，即每次选择离当前磁道最近的磁道进行访问，可以有效减少寻道时间和旋转延迟时间，提高磁盘访问效率。但这种算法可能会导致某些请求一直等待，从而造成饥饿现象。

以上两种算法的具体实现会根据不同的情况而有所差异，例如SSTF算法需要确定当前磁道位置和请求队列中的所有磁道位置，以便选择离当前位置最近的请求。而FCFS算法则只需要按照队列中的请求先后顺序依次处理即可。

相关问题

请帮我用c语言依次实现操作系统中磁盘调度算法FCFS算法和SSTF算法和SCAN算法和CSCAN算法。

以下是C语言实现FCFS、SSTF、SCAN、CSCAN四种磁盘调度算法的代码：

1. FCFS算法

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
    int n, i, j, head, sum = 0;
    printf("请输入磁盘请求数量：");
    scanf("%d", &n);
    int a[n];
    printf("请输入磁盘请求序列：");
    for(i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    printf("请输入磁头初始位置：");
    scanf("%d", &head);
    for(i = 0; i < n; i++)
    {
        sum += abs(head - a[i]);
        head = a[i];
    }
    printf("磁头移动距离为：%d\n", sum);
    return 0;
}

2. SSTF算法

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
    int n, i, j, head, sum = 0, min, index;
    printf("请输入磁盘请求数量：");
    scanf("%d", &n);
    int a[n], b[n];
    printf("请输入磁盘请求序列：");
    for(i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        b[i] = 0;
    }
    printf("请输入磁头初始位置：");
    scanf("%d", &head);
    for(i = 0; i < n; i++)
    {
        min = 1000000;
        for(j = 0; j < n; j++)
        {
            if(b[j] == 0 && abs(head - a[j]) < min)
            {
                min = abs(head - a[j]);
                index = j;
            }
        }
        b[index] = 1;
        sum += min;
        head = a[index];
    }
    printf("磁头移动距离为：%d\n", sum);
    return 0;
}

3. SCAN算法

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
    int n, i, j, head, sum = 0, min, index, flag = 0;
    printf("请输入磁盘请求数量：");
    scanf("%d", &n);
    int a[n], b[n];
    printf("请输入磁盘请求序列：");
    for(i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        b[i] = 0;
    }
    printf("请输入磁头初始位置：");
    scanf("%d", &head);
    for(i = 0; i < n; i++)
    {
        min = 1000000;
        for(j = 0; j < n; j++)
        {
            if(b[j] == 0 && abs(head - a[j]) < min)
            {
                if(flag == 0 && a[j] >= head)
                {
                    min = abs(head - a[j]);
                    index = j;
                }
                else if(flag == 1 && a[j] <= head)
                {
                    min = abs(head - a[j]);
                    index = j;
                }
                else if(flag == 0 && a[j] < head)
                {
                    min = abs(head - a[j]);
                    index = j;
                }
                else if(flag == 1 && a[j] > head)
                {
                    min = abs(head - a[j]);
                    index = j;
                }
            }
        }
        b[index] = 1;
        sum += min;
        head = a[index];
        if(flag == 0 && head == 0)
        {
            flag = 1;
        }
        else if(flag == 1 && head == 199)
        {
            flag = 0;
        }
    }
    printf("磁头移动距离为：%d\n", sum);
    return 0;
}

4. CSCAN算法

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
    int n, i, j, head, sum = 0, min, index, flag = 0;
    printf("请输入磁盘请求数量：");
    scanf("%d", &n);
    int a[n], b[n];
    printf("请输入磁盘请求序列：");
    for(i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        b[i] = 0;
    }
    printf("请输入磁头初始位置：");
    scanf("%d", &head);
    for(i = 0; i < n; i++)
    {
        min = 1000000;
        for(j = 0; j < n; j++)
        {
            if(b[j] == 0 && abs(head - a[j]) < min)
            {
                if(flag == 0 && a[j] >= head)
                {
                    min = abs(head - a[j]);
                    index = j;
                }
                else if(flag == 1 && a[j] <= head)
                {
                    min = abs(head - a[j]);
                    index = j;
                }
            }
        }
        b[index] = 1;
        sum += min;
        head = a[index];
        if(flag == 0 && head == 199)
        {
            flag = 1;
            sum += 199;
            head = 0;
        }
        else if(flag == 1 && head == 0)
        {
            flag = 0;
            sum += 199;
            head = 199;
        }
    }
    printf("磁头移动距离为：%d\n", sum);
    return 0;
}

假定有一个具有200个磁道（0-199磁道）的移动头磁盘，在完成了125磁道的请求后，当前正在磁道143处为一个请求服务。若请求队列请求的读写磁道为： 86，147，91，177，94，150，102，175，130，对于下列每种磁盘调度算法FCFS，SSTF,SCAN,C-SCAN，求磁头总寻道长度、平均寻道长度各是多少？

首先，我们需要将磁道请求按照访问顺序进行排序。

按照 FCFS 算法，磁头按照请求的先后顺序进行访问，因此磁头总寻道长度为：

125-86+147-86+147-91+177-91+177-94+150-94+150-102+175-102+175-130 = 1107

平均寻道长度为：1107/9 = 123

按照 SSTF 算法，磁头按照距离当前磁道最近的请求进行访问，因此我们需要先计算当前磁头位置与请求磁道的距离，然后按照距离从小到大进行排序。计算距离后，请求队列变为：

86，91，94，102，130，147，150，175，177

磁头总寻道长度为：

143-147+147-150+150-175+175-177+177-86+86-91+91-94+94-102+102-130 = 684

平均寻道长度为：684/9 = 76

按照 SCAN 算法，磁头按照一个方向进行访问，直到到达最后一个请求，然后改变方向继续访问，直到访问完所有请求。由于当前磁头位置在请求队列的中间，我们需要先将请求分为两部分，左边请求按照递减顺序排序，右边请求按照递增顺序排序。请求队列变为：

177，175，150，147，130，91，86，94，102

磁头总寻道长度为：

177-125+175-86+150-86+147-86+130-86+91-86+94-91+102-94 = 746

平均寻道长度为：746/9 = 83

按照 C-SCAN 算法，磁头按照一个方向进行访问，直到到达最后一个请求，然后磁头返回到最开始的磁道，继续访问剩余请求，直到访问完所有请求。和 SCAN 算法类似，我们需要将请求分为两部分，左边请求按照递减顺序排序，右边请求按照递增顺序排序。请求队列变为：

177，175，150，147，130，102，94，91，86

磁头总寻道长度为：

177-125+199-175+150-86+147-86+130-86+102-86+94-91+91-0+86-0 = 943

平均寻道长度为：943/9 = 105

因此，FCFS 的平均寻道长度是 123，SSTF 的平均寻道长度是 76，SCAN 的平均寻道长度是 83，C-SCAN 的平均寻道长度是 105。从结果可以看出，SSTF 算法的效果最好，FCFS 算法的效果最差。