操作系统磁盘调度算法

#include

#include

#define N 20

typedef struct

{

    int num;//磁道

    int flag;//1个标记量

}V,*v;

//*********************************************************************

void Initial(v *a,int n)

{//初始化磁道请求

    printf("请输入请求顺序（磁道范围是0 - 199）:\\n");

for(int i = 1;i <= n;i++)

    {

        a[i] = (v)malloc(sizeof(V));

            if(!a[i]) exit(-1);

     scanf("%d",&a[i]->num);

     a[i]->flag = 0;

    }

}

//***********************************************************************

void FCFS(v *a,int start,int n)

{//先到先服务算法

    int temp = start;

    float s = 0;

    printf("---------------------------FCFS调度算法----------------------------\\n");

for(int i = 1;i <= n; i++)

    {

     temp = abs(a[i]->num - temp);

        s += temp;

     a[i]->flag = i;

     temp = a[i]->num;

    }

    int temp2;

for(i = n;i >= 1;i--)

    {//冒泡排序，按照磁道访问的先后顺序重新排列数组a,用于输出调度顺序

     for(int j = 1;j < i;j ++)

        {

         if(a[j]->flag> a[j+1]->flag)

            {

             temp = a[j]->flag;

             temp2 = a[j]->num;

             a[j]->flag = a[j+1]->flag;

             a[j]->num = a[j+1]->num;

             a[j+1]->flag = temp;

             a[j+1]->num = temp2;

            }

        }

    }

    printf("调度序列为：\\n");

printf("%d—>",start);

for(i = 1;i <= n; i++)

    {

     printf("%d —> ",a[i]->num);

    }

    printf("\\n");

    printf("寻道长度是%f",s);printf("\\n");

    printf("平均寻道长度是%f",s/n);

    printf("\\n");

    printf("---------------------------FCFS调度算法----------------------------\\n");

}

//************************************************************************

int Find(v *a,int n,int start)

{//找到离开始磁道最近的一项，返回下标

    int p;

for(int i = 1;i < n;i++)

    {

     if((a[i]->num <= start) && (start <=a[i+1]->num ))

        {

         if(abs(a[i]->num - start) < abs(a[i+1]->num - start))

            {

                p = i;

            }

            else

            {

                p= i+1;

            }

        }

    }

    return p;

}

void SSTF(v *a,int start,int n)

{//最短寻道时间调度算法

    int temp;

    int pr,pl;//分别标记离磁头最近的那个磁道在数组中的下标的前一个和后一个

    float s = 0;    //用来计算寻道长度

    temp =  start;

    printf("---------------------------SSTF调度算法----------------------------\\n");

for(int i = n;i >= 1;i--)

    {//冒泡排序,把磁道按由小到大的顺序排列

     for(int j = 1;j < i;j ++)

        {

         if(a[j]->num > a[j+1]->num)

            {

             temp = a[j]->num;

             a[j]->num = a[j+1]->num;

             a[j+1]->num = temp;

            }

        }

    }

    printf("排序后\\n");

for(int j=1;j<=n;j++)

printf("%d ",a[j]->num);

    printf("\\n");

    int p,x;

    p = Find(a,n,start);

    x = p;

    pr = p + 1;

    pl = p - 1;

if(start <= a[1]->num)

    {//磁头在最左边

     s =(float)(a[1]->num-start);

        printf("调度序列为：\\n");

     printf("%d—>",start);

     for(i = 1;i <= n; i++)

        {

            if(i!=1)

            {

             s+=a[i]->num-a[i-1]->num;

            }

         printf("%d —> ",a[i]->num);

        }

        printf("\\n");

        printf("寻道长度为%f",s);

        printf("\\n");

        printf("平均寻道长度是%f",s/n);

        printf("\\n");

    }

else if(start >= a[n]->num)

    {//磁头在最右边

     s =(float)(start-a[n]->num);

        printf("调度序列为：\\n");

     printf("%d—>",start);

     for(i = n; i >= 1; i--)

        {

            if(i!=1)

            {

             s += a[i]->num-a[i-1]->num;

            }

         printf("%d —> ",a[i]->num);

        }

        printf("\\n");

        printf("寻道长度为%f",s);

        printf("平均寻道长度是%f",s/n);

        printf("\\n");

    }

    else

    {//磁头在中间

        printf("调度序列为：\\n");

     printf("%d—>",start);

     printf("%d —> ",a[p]->num);

     s = (float)(a[p]->num - start);

        while(1)

        {

         if(abs(a[pl]->num - a[p]->num) <= abs(a[p]->num - a[pr]->num))

            {

             s += a[p]->num-a[pl]->num;

                p = pl;

             printf("%d —> ",a[p]->num);

                pl--;

                if(pl==0)

                {

                 s += a[pr]->num-a[1]->num;

                 s += a[n]->num-a[pr]->num;

                 for(int i=pr;i<=n;i++)

                    {

                     printf(" %d—>",a[i]->num);

                    }

                    break;

                }

            }

            else

            {

             s += a[pr]->num-a[p]->num;

                p = pr;

             printf("%d —> ",a[p]->num);

                pr++;

                if(pr==n+1)

                {

                 s += a[n]->num-a[pl]->num;

                 s += a[pl]->num-a[1]->num;

                 for(int i=pl;i>=1;i--)

                    {

                     printf("%d —> ",a[i]->num);

                    }

                break;

                }

            }

        }

        printf("\\n");

        printf("寻道长度为%f",s);

        printf("\\n");

        printf("平均寻道长度是%f",s/n);

        printf("\\n");

    }    

    printf("---------------------------SSTF调度算法----------------------------\\n");

}

//**********************************************************************

void SCAN(v *a,int start,int n)

{//电梯算法

    int l = 0 ;//用于设置访问磁道的flag

    int temp,temp2;

for(int i = n;i >= 1;i--)

    {//冒泡排序,把磁道按由小到大的顺序排列

     for(int j = 1;j < i;j ++)

        {

         if(a[j]->num > a[j+1]->num)

            {

             temp = a[j]->num;

             a[j]->num = a[j+1]->num;

             a[j+1]->num = temp;

            }

        }

    }

    int p,x;

    p =  Find(a,n,start);

    x = p;

    float s = 0;

    int toleft,toright;

    printf("---------------------------SCAN调度算法----------------------------\\n");

if(abs(start - a[1]->num) < abs(a[n]->num - start))

        toleft = 1;//磁头离最左端的磁道近

    else

        toright = 1;//磁头离最右端的磁道近

    temp = start;

    if(toleft == 1)

    {//先向0磁道方向访问

        while(p != 0)

        {

         temp = abs(a[p]->num - temp);

            s += temp;

            l += 1;

         temp = a[p]->num;

         a[p]->flag = l;

            p--;

        }

     s += a[1]->num - 0;

        temp = 0;

        x = x + 1;

        while(x != n)

        {

         temp = abs(a[x]->num - temp);

            s += temp;

            l += 1;

         temp = a[x]->num;

         a[x]->flag =l;

            x++;

        }

     for(i = n;i >= 1;i--)

        {//冒泡排序，按照访问的顺序将数组重新排列

         for(int j = 1;j < i;j ++)

            {

             if(a[j]->flag> a[j+1]->flag)

                {

                 temp = a[j]->flag;

                 temp2 = a[j]->num;

                 a[j]->flag = a[j+1]->flag;

                 a[j]->num = a[j+1]->num;

                 a[j+1]->flag = temp;

                 a[j+1]->num = temp2;

                }

            }

        }

        printf("调度序列为：\\n");

     printf("%d—>",start);

     for(i = 1;i <= n; i++)

        {

         printf("%d —> ",a[i]->num);

        }

        printf("\\n");

        printf("寻道长度是%f",s);printf("\\n");

        printf("平均寻道长度是%f",s/n);

        printf("\\n");

    }

    if(toright == 1)

    {//先向199磁道方向访问

        while(p != n+1)

        {

         temp = abs(a[p]->num - temp);

            s += temp;l += 1;

         temp = a[p]->num;

         a[p]->flag = l;

            p++;

        }

     s += abs(199 - a[n]->num);

        temp = 199;

        x = x - 1;

        while(x != 0)

        {

         temp = abs(a[x]->num - temp);

            s += temp;

            l += 1;

         temp = a[x]->num;

         a[x]->flag =l;

            x--;

        }    

     for(i = n;i >= 1;i--)

        {//冒泡排序,按照访问的顺序将数组重新排列

         for(int j = 1;j < i;j ++)

            {

             if(a[j]->flag> a[j+1]->flag)

                {

                 temp = a[j]->flag;

                 temp2 = a[j]->num;

                 a[j]->flag = a[j+1]->flag;

                 a[j]->num = a[j+1]->num;

                 a[j+1]->flag = temp;

                 a[j+1]->num = temp;

                }

            }

        }

        printf("调度序列为：\\n");

     printf("%d—>",start);

     for(i = 1;i <= n; i++)

        {

         printf("%d —> ",a[i]->num);

        }

        printf("\\n");

        printf("寻道长度是%f",s);printf("\\n");

        printf("平均寻道长度是%f",s/n);

        printf("\\n");

    }

    printf("---------------------------SCAN调度算法----------------------------\\n");

}

//*************************************************************************

void CSCAN(v *a,int start,int n)

{//

    int temp,temp2;

    int l = 0;

for(int i = n;i >= 1;i--)

    {//冒泡排序

     for(int j = 1;j < i;j ++)

        {

         if(a[j]->num > a[j+1]->num)

            {

             temp = a[j]->num;

             a[j]->num = a[j+1]->num;

             a[j+1]->num = temp;

            }

        }

    }

    int p,x;

    p =  Find(a,n,start);

    x = p;

    float s = 0;

    temp = start;

    printf("---------------------------CSCAN调度算法----------------------------\\n");

if((n - p) >= p )

    {//右边的磁道数比左边的磁道数多

        while(p != n+1)

        {

         temp = abs(a[p]->num - temp);

            s += temp;l += 1;

         temp = a[p]->num;a[p]->flag = l;

            p++;

        }

     s += abs(199 - a[n]->num);

        temp = 0;

        x = x + 1;

        i = 1;

        while(i != x)

        {

         temp = abs(a[i]->num - temp);

            s += temp;l += 1;

         temp = a[i]->num;

         a[i]->flag = l;

            i++;

        }

     for(i = n;i >= 1;i--)

        {//冒泡排序,按照访问的顺序将数组重新排列

         for(int j = 1;j < i;j ++)

            {

             if(a[j]->flag> a[j+1]->flag)

                {

                 temp = a[j]->flag;

                 temp2 = a[j]->num;

                 a[j]->flag = a[j+1]->flag;

                 a[j]->num = a[j+1]->num;

                 a[j+1]->flag = temp;

                 a[j+1]->num = temp2;

                }

            }

        }

        printf("调度序列为：\\n");

     printf("%d—>",start);

     for(i = 1;i <= n; i++)

        {

         printf("%d —> ",a[i]->num);

        }

        printf("\\n");

        printf("寻道长度是%f",s);printf("\\n");

        printf("平均寻道长度是%f",s/n);

        printf("\\n");

    }

    else

    {//左边的磁道数比右边的磁道数多

        while(p != 0)

        {

         temp = abs(a[p]->num - temp);

            s += temp;l += 1;

         temp = a[p]->num;

         a[p]->flag = l;

            p--;

        }

     s += a[1]->num - 0;

        temp = 199;

        i = n;

        while(i != x)

        {

         temp = abs(a[i]->num - temp);

            s += temp;

         temp = a[i]->num;l += 1;

         a[i]->flag =l;

            i--;

        }

     for(i = n;i >= 1;i--)

        {//冒泡排序,按照访问的顺序将数组重新排列

         for(int j = 1;j < i;j ++)

            {

             if(a[j]->flag> a[j+1]->flag)

                {

                 temp = a[j]->flag;

                 temp2 = a[j]->num;

                 a[j]->flag = a[j+1]->flag;

                 a[j]->num = a[j+1]->num;

                 a[j+1]->flag = temp;

                 a[j+1]->num = temp2;

                }

            }

        }

        printf("调度序列为：\\n");

     printf("%d—>",start);

     for(i = 1;i <= n; i++)

        {

         printf("%d —> ",a[i]->num);

        }

        printf("\\n");

        printf("寻道长度是%f",s);printf("\\n");

        printf("平均寻道长度是%f",s/n);

        printf("\\n");

    }

    printf("---------------------------CSCAN调度算法----------------------------\\n");

}

//**************************************************************************

void main()

{

    int n;//

    v a[N];

    int start;//磁头开始的位置

    int choice;//用于标记操作的序号

    printf("******************************磁盘调度算法****************************\\n");

    printf("    ");printf("1.FCFS调度算法\\n");    

    printf("    ");printf("2.SSTF调度算法\\n");

    printf("    ");printf("3.SCAN调度算法\\n");

    printf("    ");printf("4.CSCAN调度算法\\n");        

    printf("    ");printf("5.退出\\n");

    printf("******************************磁盘调度算法****************************\\n");

    printf("请输入请求的柱面数 :");

    scanf("%d",&n);

    printf("请输入磁头开始的位置:");

    scanf("%d",&start);

    Initial(a,n);

    while(1)

    {

        printf("请选择你要的操作序号\\n");

        scanf("%d",&choice);

        switch(choice){

        case 1:FCFS(a,start,n);break;

        case 2:SSTF(a,start,n);break;

        case 3:SCAN(a,start,n);break;

        case 4:CSCAN(a,start,n);break;

        case 5:exit(-1);

        default:printf("你输入的操作序号有误！");

        }

        printf("\\n");

    }

}