吉林大学操作系统上机实验五（磁盘引臂调度算法(scan算法）实现）

本次实验无参考，从头开始实现。

一.实验内容

1. 模拟实现任意一个磁盘引臂调度算法，对磁盘进行移臂操作
2. 列出基于该种算法的磁道访问序列，计算平均寻道长度。

二.实验设计

1. 假设磁盘只有一个盘面，并且磁盘是可移动头磁盘。
2. 磁盘是可供多个进程共享的存储设备，但一个磁盘每个时刻只能为一个进程服务。当有进程在 访问某个磁盘时，其它想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程 提出输入输出请求而处于等待状态时，可选用适当的磁盘调度算法从若干个等待访问者中选择 一个进程，让它访问磁盘。为此设置“驱动调度”进程。
3. “初始化”进程建立一张“进程请求 I/O”表，列出等待访问磁盘的进程要求访问的磁道，表的格式如下：

三.实验准备  

1. 扫描算法（SCAN）

图一  SCAN算法

1. SCAN算法是一种用于磁盘调度的算法，旨在优化磁盘臂的移动，以减少磁盘访问的平均等待时间。SCAN算法也被称为ELEVATOR算法，因为它模仿了电梯（升降机）的行为：磁盘臂在磁盘的一端开始移动，沿着一个方向移动直到到达另一端，然后反向移动，服务沿途的所有请求，直到回到起始端。
2. 选择方向：磁盘臂可以往一个方向移动，比如从磁盘的外围磁道向内移动，或者从内向外移动。这个方向通常是由磁盘臂上次移动的方向决定，或者是根据请求的分布情况来设定。
3. 服务请求：磁盘臂在移动过程中，会服务所有沿移动方向的未服务请求。
4. 到达端点：当磁盘臂到达磁盘的一端时，它会反向移动，同时继续服务沿新移动方向的请求。
5. 重复过程：磁盘臂会继续在磁盘的两端之间移动，服务所有请求，直到所有请求都被服务完毕。
6. 减少寻址时间：由于磁盘臂只在两个方向上移动，可以减少磁盘臂的移动距离，从而减少寻址时间。
7. 防止请求饥饿：与SSTF算法相比，SCAN算法可以确保所有请求最终都会被服务，因为磁盘臂会在两个方向上移动。
8. 磁头震荡：虽然SCAN算法可以减少磁盘臂的移动距离，但如果请求集中在磁盘的一端，可能会导致磁盘臂在两端之间频繁移动，造成磁头震荡。
9. 响应时间不均：请求的响应时间可能会因为它们在磁盘上的位置而有所不同，位于磁盘两端和中间的请求可能会有不同的响应时间。

 四.代码

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

// SCAN 算法的核心函数
int SCAN(int* cyc_list, int* cyc_order, int n, int start, int dir) {
    int sum, max_int, min_value, index, tag[100] = { 0 };
    sum = 0; 
    int x_max = cyc_list[0], x_min = cyc_list[0];
    for (int i = 1; i < n; i++) {
        if (cyc_list[i] > x_max) {
            x_max = cyc_list[i];
        }
        if (cyc_list[i] < x_min) {
            x_min = cyc_list[i];
        }
    }
    int turn = 0;
    for (int i = 0; i < n; i++) {
        max_int = 9999;
        for (int j = 0; j < n; j++) {
            if (dir == 1 && cyc_list[j] > start && tag[j] == 0) {
                // cyc_list表示待执行柱面
                min_value = cyc_list[j] - start;
                if (min_value < max_int) {
                    max_int = min_value;
                    index = j; // 记录距离最小的待执行柱面号的索引
                }
            }
            else if (dir == 0 && cyc_list[j] < start && tag[j] == 0) {
                min_value = abs(cyc_list[j] - start);
                if (min_value < max_int) {
                    max_int = min_value;
                    index = j; // 记录距离最小的待执行柱面号的索引
                }
            }
        }
        // 判断是否需要转向
        
        if (dir == 1 && turn == 0 && cyc_list[index] == x_max) {
            dir = 0;
            if (i != n - 1) sum += 2 * (500 - x_max);`
            turn = 1;
        }
        else if (turn == 0 && cyc_list[index] == x_min) {
            dir = 1;
            if (i != n - 1) sum += 2 * x_min;
        }
        sum += max_int; // 累积磁头移动轨道数
        tag[index] = 1;
        cyc_order[i] = cyc_list[index];
        start = cyc_list[index];
    }
    return sum;
}

// SCAN
void main() {
    int cyc_list[100], cyc_order[100], n, start, dir, ans = 0;
    printf("请输入磁臂初始移动方向（1向内，0向外）：");//1向大数走，0向小数走
    scanf("%d", &dir);
    printf("请输入初始柱面和待执行柱面数量：");
    scanf("%d%d", &start, &n);
    printf("请输入待执行柱面：");
    for (int i = 0; i < n; i++) {
        scanf("%d", &cyc_list[i]);
    }
    ans = SCAN(cyc_list, cyc_order, n, start, dir);
    printf("SCAN走道顺序为：");
    for (int i = 0; i < n; i++) {
        printf("%d", cyc_order[i]);
        if (i + 1 != n) {
            printf(" -> ");
        }
    }
    printf("\n");
    printf("磁头走过总道数为：%d\n", ans);
    float res = (float)ans / n;
    printf("平均寻道长度: %.1f\n", res);
}

具体实现：

main函数中录入必要数据。

SCAN函数执行具体选取。

x_max和x_min分别记录输入数据中最大柱面和最小柱面。

int x_max = cyc_list[0], x_min = cyc_list[0];
for (int i = 1; i < n; i++) {
    if (cyc_list[i] > x_max) {
        x_max = cyc_list[i];
    }
    if (cyc_list[i] < x_min) {
        x_min = cyc_list[i];
    }
}

 每一次选取时，都选取在磁头移动方向上，距离上次位置（start）最近且未被选取过（tag=0）的点。

max_int = 9999;
for (int j = 0; j < n; j++) {
    if (dir == 1 && cyc_list[j] > start && tag[j] == 0) {
        // cyc_list表示待执行柱面
        min_value = cyc_list[j] - start;
        if (min_value < max_int) {
            max_int = min_value;
            index = j; // 记录距离最小的待执行柱面号的索引
        }
    }
    else if (dir == 0 && cyc_list[j] < start && tag[j] == 0) {
        min_value = abs(cyc_list[j] - start);
        if (min_value < max_int) {
            max_int = min_value;
            index = j; // 记录距离最小的待执行柱面号的索引
        }
    }
}

每次选取后，若开始时向内，则判断是否未转向过且选取点是最大点，若是，则转向。如果该点不是最后一个点，则磁头总移动距离需另外加上移到边界又再次移动到该点的距离。开始时向外类似处理。

// 判断是否需要转向
if (dir == 1 && turn == 0 && cyc_list[index] == x_max) {
    dir = 0;
    if (i != n - 1) sum += 2 * (500 - x_max);`
    turn = 1;
}
else if (turn == 0 && cyc_list[index] == x_min) {
    dir = 1;
    if (i != n - 1) sum += 2 * x_min;
}

选取完成后，累积磁头移动轨道数，将该点访问标志（tag）置1，将该点加入序列，更新上次位置（start）为该点柱面数。

sum += max_int; // 累积磁头移动轨道数
tag[index] = 1;
cyc_order[i] = cyc_list[index];
start = cyc_list[index];

五.运行结果

TIPS：模拟硬盘一共有500柱面。