操作系统实验之磁盘调度算法模拟（最短寻道时间优先SSTF 和扫描算法SCAN）

淩亂°似流年 2022-06-14 00:27 245阅读 0赞

# 操作系统实验之磁盘调度算法模拟（最短寻道时间优先SSTF 和 扫描算法SCAN） #

--------------------

*  最短寻道时间优先SSTF  
    
    
     *  要求每次访问的磁道与当前磁头所在的磁道距离最近、
     *  也就是每次访问距离磁头最近的磁道
 *  扫描算法SCAN  
    
    
     *  由里向外地访问，直到再无更外的磁道需要访问时，才将磁臂转向为自外向里移动
 *  [磁盘调度算法 详细介绍][Link 1]

### 模拟代码： ###

#include<stdio.h>
    #include<algorithm>
    #include<math.h>
    using namespace std;
    
    //定义磁盘号的范围（0 <= 磁盘号 < MAX_DISK_NUMBER)
    const int MAX_DISK = 200;
    //定义一个数组存储要访问的磁盘的序列号
    int Disk[MAX_DISK + 1];
    //DISK_NUMBER要访问的磁道的数量，
    int DISK_NUMBER = 0;
    //保存磁道的访问方向 DIRECTION 为 1 时从小到大， 为 0 时 从大到小；
    int DIRECTION = 1;
    //定义当前磁道号
    int CURRENT_DISK;
    
    //比较大小的方法，用于对 Disk[] 的排序
    int compare(int a,int b){
        return a > b;
    }
    
    //最短寻道时间优先（SSTF）
    //将当前的磁道号放入要访问的磁道号 Disk[] 中，排序后便可轻易找到其左右的要访问的磁道号
    void SSTF(){
        //定义三个变量，left标记 当前磁道 左边第一个微调度的磁道号在数组中的序号
        //right 标记 当前磁道 右边第一个未调度的磁道号在数组中的序号
        //now 当前磁道；
        int left,right,now;
        //定义寻道长度和平均寻道长度
        double length = 0,avg_length = 0;
        //根据磁道移动的方向不同对磁道号进行排序
        if(DIRECTION == 1)
            sort(Disk,Disk + DISK_NUMBER + 1);
        else
            sort(Disk,Disk + DISK_NUMBER + 1,compare);
    
    //    //输出排序后的Disk[]
    //    for(int i = 0; i < DISK_NUMBER; i++)
    //        printf("%d ",Disk[i]);
        for(int i = 0; i <= DISK_NUMBER; i++)
        {
            //找到当前磁道 左右边第一个未调度的磁道号在数组中的序号
            if(Disk[i] == CURRENT_DISK)
            {
                now = i;
                left = i -1;
                right = i + 1;
            }
        }
        //不断寻找距离 now 进的并输出，相应改变 now left right
        while(!(left == -1 && right == DISK_NUMBER + 1))
        {
            //如果左侧到了 Disk[] 外则把右边的顺序输出
            if(left <= -1)
            {
                length += fabs(Disk[right] - Disk[now]);
                for(int i = right; i <= DISK_NUMBER; i++)
                {
                    if(i > right)
                        length += fabs(Disk[i] - Disk[i - 1]);
                    printf("%d ",Disk[i]);
                }
                break;
            }
            //如果右侧到了 Disk[] 外则把左边的顺序输出
            if(right == DISK_NUMBER + 1)
            {
                length += fabs(Disk[now] - Disk[left]);
                for(int i = left; i >=0; i--)
                {
                    if(i < left)
                        length += fabs(Disk[i] - Disk[i + 1]);
                    printf("%d ",Disk[i]);
                }
                break;
            }
            //right 距离 <= left 向右走（不管方向为什么，都是往右走，因为方向不同时的排序方法不同，
            //根据方向区分左右距离相等时向左还是向右的话，效果与排序叠加，恰好得到了错误的序列）
            if(fabs(Disk[right] - Disk[now]) <= fabs(Disk[now] - Disk[left]))
            {
                length += fabs(Disk[right] - Disk[now]);
                printf("%d ",Disk[right]);
                now = right;
                right++;
            }
            else if(fabs(Disk[right] - Disk[now]) > fabs(Disk[now] - Disk[left]))
            {
                length += fabs(Disk[now] - Disk[left]);
                printf("%d ",Disk[left]);
                now = left;
                left--;
            }
        }
        //计算平均寻道时间
        avg_length = length / DISK_NUMBER;
        printf("平均寻道时间为：%lf",avg_length);
    }
    
    //扫描算法（SCAN）
    void SCAN()
    {
        //定义三个变量，left标记 当前磁道 左边第一个微调度的磁道号在数组中的序号
        //right 标记 当前磁道 右边第一个未调度的磁道号在数组中的序号
        //now 当前磁道；
        int left,right,now;
        //定义寻道长度和平均寻道长度
        double length = 0,avg_length = 0;
        //根据磁道移动的方向不同对磁道号进行排序
        if(DIRECTION == 1)
            sort(Disk,Disk + DISK_NUMBER + 1);
        else
            sort(Disk,Disk + DISK_NUMBER + 1,compare);
    
    //    //输出排序后的Disk[]
    //    for(int i = 0; i <= DISK_NUMBER; i++)
    //        printf("%d ",Disk[i]);
        for(int i = 0; i <= DISK_NUMBER; i++)
        {
            //找到当前磁道 左右边第一个未调度的磁道号在数组中的序号
            if(Disk[i] == CURRENT_DISK)
            {
                now = i;
                left = i -1;
                right = i + 1;
            }
        }
        length += fabs(Disk[now] - Disk[right]);
        //从now向DIRECTION方向移动
        for(int i = right; i <= DISK_NUMBER; i++)
        {
            if(i > right)
                length += fabs(Disk[i] - Disk[i -1]);
            printf("%d ",Disk[i]);
        }
        length += fabs(Disk[DISK_NUMBER] - Disk[left]);
        //走到DIRECTION方向尽头，返回扫描
        for(int i = left; i>=0; i--)
        {
            if(i < left)
                length += fabs(Disk[i] - Disk[i + 1]);
            printf("%d ",Disk[i]);
        }
        //计算平均寻道时间
        avg_length = length / DISK_NUMBER;
        printf("平均寻道时间为：%lf",avg_length);
    }
    
    int main()
    {
        printf("input the number of the disk\n");
        scanf("%d",&DISK_NUMBER);
        printf("input the Disk[]\n");
        for(int i = 0; i < DISK_NUMBER; i++)
            scanf("%d",&Disk[i]);
        printf("input the direction of the disk , right = 1 and left = 0\n");
        scanf("%d",&DIRECTION);
        printf("input the current disk\n");
        scanf("%d",&CURRENT_DISK);
        //把CURRENT_DISK加入Disk[]
        Disk[DISK_NUMBER] = CURRENT_DISK;
        printf("the answer of the SSTF is:\n");
        SSTF();
        printf("\nthe answer of the SCAN is:\n");
        SCAN();
        return 0;
    }

[Link 1]: http://baike.baidu.com/link?url=OVs5E8FaNkWKZyTCf3_rz0FazRotZe-Lallu03LJu7kGmtC7P6LT60mE0z77KEoLZ_qFYBBYFpPaFHSHS60BmmV_gOFhtw-NTmYQMHEKPxEvfdrOF6pny6bxXgKAQ2XFuNnk8619cnNKqtszKwB-f_