一、FCFS算法

先来不及，先服务（First Come, First Served, FCFS）调度算法是最常见的磁盘调度算法，也是最简单的一种。对于该算法，磁头按照请求的顺序进行移动，直到到达请求队列中最后一个磁道，然后返回到最开始的磁道，继续访问其它磁道。假设有以下磁道请求序列：

47, 38, 25, 45, 15, 10

以磁道位置50为起点，按照FCFS算法来调度请求：

起点：50 -> 47 -> 38 -> 25 -> 45 -> 15 -> 10 -> 50

FCFS算法的优点是实现简单，但是缺点也很明显，它无法有效处理磁盘请求的顺序引起的长时间等待和不公平现象。

二、SSTF算法

最短寻道时间优先（Shortest Seek Time First, SSTF）调度算法是一种比较实用的磁盘调度算法，每次调度时，磁头选择与当前位置最近的未访问的磁道进行访问。继续以磁盘请求序列47, 38, 25, 45, 15, 10为例：假设当前磁头的位置为50，按照SSTF算法来调度请求：

50 -> 45 -> 38 -> 47 -> 25 -> 15 -> 10 -> 45

三、SCAN算法

扫描算法，也称电梯调度算法或上下行算法，磁头按照一个方向移动，直到到达磁道终点，然后磁头改变方向，继续移动，以此类推。假设有以下磁道请求序列，且磁头的当前位置为50：

47, 38, 25, 45, 15, 10

按照SCAN算法来调度请求：

50 -> 47 -> 38 -> 25 -> 10 -> 15 -> 45 -> 50

SCAN算法被广泛使用，因为它可以避免某些请求长时间等待，但是它也有自己的缺点，即如果请求队列中存在某些请求，那么这些请求需要等待到当前磁头的扫描结束，才能得到服务。

四、C-SCAN算法

循环扫描算法，也称为双向扫描算法，与SCAN算法类似，但磁头遇到边界时不返回原始位置，而是直接返回到另一个方向的边界，进行继续扫描，以此类推。假设有以下磁道请求序列，当前磁头位置为50：

47, 38, 25, 45, 15, 10

按照C-SCAN算法来调度请求：

50 -> 47 -> 38 -> 25 -> 10 -> 15 -> 45 -> 47 -> 50

五、LOOK算法

LOOK算法是SCAN算法的变体，磁头在访问请求之前，只是在当前扫描方向上进行，直到没有任何请求，然后改变扫描方向。假设有以下磁道请求序列，当前磁头位置为50：

47, 38, 25, 45, 15, 10

按照LOOK算法来调度请求：

50 -> 47 -> 38 -> 25 -> 15 -> 10 -> 45 -> 47

完整代码示例

以下代码实现了上述五种磁盘调度算法：

#include <stdio.h>
#include <stdlib.h>
#define MAX 5000
#define UP 1
#define DOWN -1
/** 全局变量 **/
int req[MAX];       // 磁盘请求序列
int n;              // 磁盘请求数量
int pos = 50;       // 当前磁头位置
int direction = UP; // 扫描方向
/** 辅助函数 **/
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
int abs(int a) {
    return a > 0 ? a : (-1 * a);
}
/** FCFS **/
void fcfs() {
    printf("FCFS: %d -> ", pos);
    int i;
    for (i = 0; i < n; i++) {
        printf("%d -> ", req[i]);
        pos = req[i];
    }
    printf("%d\n", pos);
}
/** SSTF **/
void sstf() {
    printf("SSTF: %d -> ", pos);
    int visited[MAX] = {0};  // 记录磁道是否被访问
    int i, j, min;
    for (i = 0; i < n; i++) {
        min = MAX;
        for (j = 0; j < n; j++) {
            if (!visited[j] && abs(req[j] - pos) < abs(min - pos)) {
                min = req[j];
            }
        }
        visited[j] = 1;
        printf("%d -> ", min);
        pos = min;
    }
    printf("%d\n", pos);
}
/** SCAN **/
void scan() {
    printf("SCAN: %d -> ", pos);
    int left = MAX, right = -1;
    int i, j;
    for (i = 0; i < n; i++) {
        if (req[i] > pos) {
            right = i;
            break;
        }
    }
    if (right == -1) {
        right = n;
        direction = DOWN;
    }
    for (i = right - 1; i >= 0; i--) {
        printf("%d -> ", req[i]);
        pos = req[i];
    }
    if (direction == UP) {
        printf("0 -> ");
        pos = 0;
    } else {
        printf("%d -> ", 99);
        pos = 99;
    }
    for (i = right; i < n; i++) {
        printf("%d -> ", req[i]);
        pos = req[i];
    }
    printf("%d\n", pos);
}
/** C-SCAN **/
void cscan() {
    printf("C-SCAN: %d -> ", pos);
    int left = MAX, right = -1;
    int i, j;
    for (i = 0; i < n; i++) {
        if (req[i] > pos) {
            right = i;
            break;
        }
    }
    if (right == -1) {
        right = n;
        direction = DOWN;
    }
    for (i = right - 1; i >= 0; i--) {
        printf("%d -> ", req[i]);
        pos = req[i];
    }
    printf("%d -> 0 -> ", 0);
    pos = 0;
    for (i = n - 1; i >= right; i--) {
        printf("%d -> ", req[i]);
        pos = req[i];
    }
    printf("%d\n", pos);
}
/** LOOK **/
void look() {
    printf("LOOK: %d -> ", pos);
    int left = MAX, right = -1;
    int i, j;
    for (i = 0; i < n; i++) {
        if (req[i] > pos) {
            right = i;
            break;
        }
    }
    if (right == -1) {
        right = n;
        direction = DOWN;
    }
    int last = right - 1;
    while (last >= 0 && req[last] == pos) {
        last--;
    }
    for (i = right - 1; i > last; i--) {
        printf("%d -> ", req[i]);
        pos = req[i];
    }
    printf("%d -> ", pos);
    if (direction == UP) {
        for (i = right; i < n; i++) {
            printf("%d -> ", req[i]);
            pos = req[i];
        }
    } else {
        for (i = last; i >= 0; i--) {
            printf("%d -> ", req[i]);
            pos = req[i];
        }
    }
    printf("%d\n", pos);
}
/** 主函数 **/
int main(int argc, char const *argv[]) {
    int i;
    n = atoi(argv[1]);
    for (i = 2; i < n + 2; i++) {
        req[i - 2] = atoi(argv[i]);
    }
    fcfs();
    sstf();
    scan();
    cscan();
    look();
    return 0;
}