一、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;
}
