磁碟調度演算法

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