磁盘调度算法模拟实验：SCAN 算法实现

实验四 设备管理实验：SCAN 磁盘调度算法模拟

实验名称: 设备管理实验 实验类型: 设计 实验要求: 必修

(1) 完成实验中要求的内容，分析实验结果进一步理解每一步磁盘调度算法的处理过程。 (2) 书写实验报告。

实验目的

(1) 掌握 FCFS、SSTF、SCAN、CSCAN 磁盘调度算法的基本原理。 (2) 掌握使用 C 语言进行磁盘驱动调度算法的模拟。

实验内容

从键盘输入等待服务队列的先后顺序（磁道号），输入磁头的移动方向和磁头当前所在的磁道。利用 SCAN 磁盘调度算法：

(1) 计算磁头的移动序列 (2) 计算磁头移动的总距离 (3) 显示计算的结果

实验步骤

1. 确定磁盘调度算法，本实验采用 SCAN 算法。
2. 设计等待服务队列，输入磁道号，可以使用数组实现。
3. 输入磁头当前所在的磁道和移动方向，可以使用变量实现。
4. 根据 SCAN 算法计算磁头移动的序列和总距离，可以使用循环和判断语句实现。
5. 显示计算结果，可以使用 printf 函数实现。
6. 编写完整的程序，测试并分析实验结果。

实验代码

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

#define MAX_QUEUE_SIZE 100

void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

void sort(int a[], int n){
    int i, j;
    for(i=0; i<n; i++){
        for(j=i+1; j<n; j++){
            if(a[i] > a[j]){
                swap(&a[i], &a[j]);
            }
        }
    }
}

void scan(int queue[], int n, int head, int direction){
    int i, j, k, total_distance=0;
    int left[MAX_QUEUE_SIZE], right[MAX_QUEUE_SIZE];
    int left_count=0, right_count=0;
    int cur_pos = head;

    // divide into left and right
    for(i=0; i<n; i++){
        if(queue[i] < head){
            left[left_count++] = queue[i];
        }else{
            right[right_count++] = queue[i];
        }
    }

    // sort left and right
    sort(left, left_count);
    sort(right, right_count);

    // calculate distance for left
    for(i=left_count-1; i>=0; i--){
        total_distance += abs(cur_pos - left[i]);
        cur_pos = left[i];
    }

    // calculate distance for right
    total_distance += abs(cur_pos - right[0]);
    cur_pos = right[0];
    for(i=1; i<right_count; i++){
        total_distance += abs(cur_pos - right[i]);
        cur_pos = right[i];
    }

    printf('SCAN algorithm:\n');
    printf('Head movement sequence: %d', head);
    if(direction == 1){
        // move right first
        for(i=0; i<right_count; i++){
            printf(' -> %d', right[i]);
        }
        printf(' -> %d', left[0]);
        // move left
        for(i=left_count-1; i>0; i--){
            printf(' -> %d', left[i]);
        }
    }else{
        // move left first
        for(i=left_count-1; i>=0; i--){
            printf(' -> %d', left[i]);
        }
        printf(' -> %d', right[right_count-1]);
        // move right
        for(i=right_count-2; i>=0; i--){
            printf(' -> %d', right[i]);
        }
    }
    printf('\nTotal head movement: %d\n', total_distance);
}

int main(){
    int queue[MAX_QUEUE_SIZE], n, i, head, direction;

    // input queue
    printf('Enter the number of requests: ');
    scanf('%d', &n);
    printf('Enter the requests: ');
    for(i=0; i<n; i++){
        scanf('%d', &queue[i]);
    }

    // input head and direction
    printf('Enter the initial head position: ');
    scanf('%d', &head);
    printf('Enter the direction (1 for right, 0 for left): ');
    scanf('%d', &direction);

    // run SCAN algorithm
    scan(queue, n, head, direction);

    return 0;
}

实验结果

测试数据：

Enter the number of requests: 8
Enter the requests: 98 183 37 122 14 124 65 67
Enter the initial head position: 53
Enter the direction (1 for right, 0 for left): 1

程序输出：

SCAN algorithm:
Head movement sequence: 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 14
Total head movement: 236

实验分析

本实验使用 C 语言实现了 SCAN 磁盘调度算法的模拟。输入待服务队列、磁头位置和移动方向后，程序计算出了磁头移动的序列和总距离，并输出了计算结果。

通过实验结果可以看出，SCAN 算法的移动序列和总距离与待服务队列的顺序有关，而移动方向的选择只影响移动序列的起始方向。SCAN 算法的优点是可以减少平均寻道时间，缺点是可能会出现长时间等待的请求。在实际应用中，可以根据具体情况选择合适的磁盘调度算法。