实验5 磁盘调度算法

一、实验目的

        通过该实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN算法。

二、实验要求

        假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（磁道号增加或减少），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。

        接收用户输入磁道数n和磁盘访问序列，选择磁盘调度算法：1-FCFS、2-SSTF、3-SCAN算法。输入开始磁盘号m和磁头移动方向，输出磁盘调度算法的模拟过程，如调度顺序，计算并输出平均寻道长度。

三、实验代码--磁盘调度算法.cpp

1.FCFS算法

类似于队列，故可以采用数组储存磁道序列后顺序输出：

#include"stdio.h"
#include <math.h>
#include <stdlib.h>
//先来先服务调度算法
void FCFS(int a[],int n)
{
    int sum=0,i,m;
    double avg;
    printf("\n请输入开始的磁道号： ");
    scanf("%d",&m);
    printf("\nFCFS 调度结果: ");
    for(i=0;i<n;i++) printf("%d ",a[i]);
    printf("\n");
    sum=abs(m-a[0]);
    for(i=1;i<n;i++) sum+=abs(a[i]-a[i-1]); 
    avg=(double)sum/n;//计算平均寻道长度
    printf("平均寻道长度： %.2f \n",avg);
}

2.SSTF算法

SSTF算法需要事先将磁道序列冒泡排序，先找到开始磁道号在有序数组中的位置，然后要求访问的磁道与开始磁头所在的磁道距离最近。小于开始磁道号的逆序输出，大于开始磁道号的顺序输出。

//最短寻道时间优先调度算法
void SSTF(int a[],int n){
    int temp;//数组元素交换中介 
    int k=1;
    int m,left,right;
    int i,j,sum=0;
    double avg;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++) //对磁道号进行从小到大排列
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    printf("排序后磁道数组为：\n");
    for( i=0; i<n; i++) //输出排序后的磁道号数组
        printf("%d ",a[i]);
    printf("\n请输入开始的磁道号： ");
    scanf("%d",&m);
    printf("\nSSTF 调度结果: ");
    if(a[n-1]<=m)//如果整个数组里的数都小于开始磁道号
    {
        for(i=n-1; i>=0; i--) //将数组磁道号从大到小输出
            printf("%d ",a[i]);
        sum=m-a[0];
    }
    else if(a[0]>=m)//如果整个数组里的数都大于开始磁道号
    {
        for(i=0; i<n; i++) //将磁道号从小到大输出
            printf("%d ",a[i]);
        sum=a[n-1]-m;
    }
    else
    {
        while(a[k]<m)//逐一比较以确定 K 值
        {
            k++;
        }
        left=k-1;
        right=k;
//确定开始磁道在已排的序列中的位置
        while((left>=0)&&(right<n))
        {
            if((m-a[left])<=(a[right]-m))//判断最短距离
            {
                printf("%d ",a[left]);
                sum+=m-a[left];
                m=a[left];
                left=left-1;
            }
            else
            {
                printf("%d ",a[right]);
                sum+=a[right]-m;
                m=a[right];
                right=right+1;
            }
        }
        if(left=-1)
        {
            for(j=right; j<n; j++)//顺序输出 
            {
                printf("%d ",a[j]);
            }
            sum+=a[n-1]-a[0];
        }
        else
        {
            for(j=left; j>=0; j--)//逆序输出 
            {
                printf("%d ",a[j]);
            }
            sum+=a[n-1]-a[0];//计算移动距离
        }
    }
    printf("\n"); 
    avg=(double)sum/n;
    printf(" 平均寻道长度： %.2f \n",avg);
}

3.SCAN算法

//最短寻道时间优先调度算法
void SSTF(int a[],int n){
    int temp;//数组元素交换中介 
    int k=1;
    int m,left,right;
    int i,j,sum=0;
    double avg;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++) //对磁道号进行从小到大排列
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    printf("排序后磁道数组为：\n");
    for( i=0; i<n; i++) //输出排序后的磁道号数组
        printf("%d ",a[i]);
    printf("\n请输入开始的磁道号： ");
    scanf("%d",&m);
    printf("\nSSTF 调度结果: ");
    if(a[n-1]<=m)//如果整个数组里的数都小于开始磁道号
    {
        for(i=n-1; i>=0; i--) //将数组磁道号从大到小输出
            printf("%d ",a[i]);
        sum=m-a[0];
    }
    else if(a[0]>=m)//如果整个数组里的数都大于开始磁道号
    {
        for(i=0; i<n; i++) //将磁道号从小到大输出
            printf("%d ",a[i]);
        sum=a[n-1]-m;
    }
    else
    {
        while(a[k]<m)//逐一比较以确定 K 值
        {
            k++;
        }
        left=k-1;
        right=k;
//确定开始磁道在已排的序列中的位置
        while((left>=0)&&(right<n))
        {
            if((m-a[left])<=(a[right]-m))//判断最短距离
            {
                printf("%d ",a[left]);
                sum+=m-a[left];
                m=a[left];
                left=left-1;
            }
            else
            {
                printf("%d ",a[right]);
                sum+=a[right]-m;
                m=a[right];
                right=right+1;
            }
        }
        if(left=-1)
        {
            for(j=right; j<n; j++)//顺序输出 
            {
                printf("%d ",a[j]);
            }
            sum+=a[n-1]-a[0];
        }
        else
        {
            for(j=left; j>=0; j--)//逆序输出 
            {
                printf("%d ",a[j]);
            }
            sum+=a[n-1]-a[0];//计算移动距离
        }
    }
    printf("\n"); 
    avg=(double)sum/n;
    printf(" 平均寻道长度： %.2f \n",avg);
}

///扫描算法
void SCAN(int a[],int n){
    int i,j,sum=0;
    double avg;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++) //对磁道号进行从小到大排列
        {
            if(a[i]>a[j])
            {
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    printf("排序后的磁道数组为：\n");
    for(i=0;i<n;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n请输入开始的磁道号： ");
    int m;
    scanf("%d",&m);
    printf("\nSCAN 调度结果：");
    int pos;
    for(i=0;i<n;i++)
    {
        if(a[i]>=m)//找到比开始磁道号大的数 
        {
            pos=i;
            sum+=abs(a[i]-m);
            break;
        }
    }
    for(i=pos;i<n;i++)
    {
        if(i!=pos)//顺着磁头方向顺序输出 
            sum+=abs(a[i]-a[i-1]);
        printf("%d ",a[i]);
    }
    if(pos>=1)
        sum+=abs(a[n-1]-a[pos-1]);
    for(i=pos-1;i>=0;i--)//逆着磁头方向顺序输出 
    {
        if(i)
            sum+=abs(a[i]-a[i-1]);
        printf("%d ",a[i]);
    }
    avg=(double)sum/n;
    printf("\n 平均寻道长度：%.2f\n",avg);
}

4.主函数

int main(){
    int choose;
    int count;
    int cidao[100];//定义磁道号数组
    int i=0;
    int n;
    printf("请先输入磁道数量： \n");
    scanf("%d",&n);
    printf("请先输入磁道序列： \n");
    for(i=0; i<n; i++)
    {
        scanf("%d",&cidao[i]);
    }
    
    
    printf("\n");
    while(1)
    {
        
        printf("1.先来先服务算法(FCFS) \n");
        printf("2.最短寻道时间优先算法(SSTF) \n");
        printf("3.扫描算法(SCAN)\n");
        printf("4.退出\n");
        printf("\n");
        printf("请选择调度算法： ");
        scanf("%d",&choose);
        
        switch(choose)//算法选择
        {
        case 1:
            FCFS(cidao,n);//先进先出算法
            printf("\n");
            break;
        case 2:
            SSTF(cidao,n);//最短服务时间优先算法
            printf("\n");
            break;
        case 3:
            SCAN(cidao,n);//扫描算法
            printf("\n");
            break;
        case 4:
            exit(0);
        }
    }
    return 0;
}

四、实验图例

1.FCFS算法

2.SSTF算法