磁盘调度算法实验报告文档                     

1.依次输入9个磁道数：40 90 170 38 110 20 144 48 59

2.选择调度算法：

先来先服务算法访问顺序和平均寻道长度：

最短寻道时间优先的访问顺序和平均寻道长度：

扫描算法的磁道访问顺序和平均寻道长度：

1．移动壁由里向外

2．移动壁由外向里

循环算法的磁道访问顺序和平均寻道长度：

1.移动壁由里向外

2.移动壁由外向里

源代码为：

#include<stdio.h>

#include<math.h>

void FCFS(int b[],int n,int init)  //先来先服务

{

    int i,s,sum;

    int a[20];

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

      a[i]=b[i];

    s=init;

    sum=0;

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

    {

        printf("第%d次访问的磁道:%d\n",i+1,a[i]);

        sum+=abs(s-a[i]);

       s=a[i];

    }

    printf("平均寻道长度:%f\n",sum*1.0/n);

}

void SSTF(int b[],int n,int k) //最短寻道法

{

    int i,j,s,sum=0,p;

    int a[20];

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

      a[i]=b[i];

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

    {

       s=a[0];

       p=0;

       for(j=0;j<=i;j++)

         if(abs(a[j]-k)<abs(s-k))

         {

            s=a[j];

            p=j;

         }

       a[p]=a[i];

       printf("第%d次访问的磁道:%d\n",n-i,s);

       sum+=abs(s-k);

       k=s;

    }

    printf("平均寻道长度:%f\n",sum*1.0/n);

}

void SCAN1(int b[],int n,int k)  //扫描算法

{

    int i,j,s,sum=0,p,biaoji;

    int a[20];

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

      a[i]=b[i];

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

    {

       biaoji=0;

       for(j=0;j<=i;j++)

         if(a[j]-k<0)

         {

            biaoji=1;

            p=j;

            break;

         }

       if(biaoji==1)

       {

           s=a[p];

           for(j=0;j<=i;j++)

             if(a[j]<k&&k-a[j]<k-s)

             {

                s=a[j];

                p=j;

             }

           a[p]=a[i];

           printf("第%d次访问的磁道:%d\n",n-i,s);

           sum+=k-s;

           k=s;

       }

       else

       {

           s=a[0];

           for(j=0;j<=i;j++)

             if(a[j]-k<=s-k)

             {

                s=a[j];

                p=j;

             }

           a[p]=a[i];

           printf("第%d次访问的磁道:%d\n",n-i,s);

           sum+=abs(k-s);

           k=s;

       }

    }

    printf("平均寻道长度:%f\n",sum*1.0/n);

}

void SCAN2(int b[],int n,int k)  //循环算法

{

    int i,j,s,sum=0,p,biaoji;

    int a[20];

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

      a[i]=b[i];

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

    {

       biaoji=0;

       for(j=0;j<=i;j++)

         if(a[j]-k>0)

         {

            biaoji=1;

            p=j;

            break;

         }

       if(biaoji==1)

       {

           s=a[p];

           for(j=0;j<=i;j++)

             if(a[j]>k&&a[j]-k<s-k)

             {

                s=a[j];

                p=j;

             }

           a[p]=a[i];

           printf("第%d次访问的磁道:%d\n",n-i,s);

           sum+=s-k;

           k=s;

       }

       else

       {

           s=a[0];

           for(j=0;j<=i;j++)

             if(k-a[j]<=k-s)

             {

                s=a[j];

                p=j;

             }

           a[p]=a[i];

           printf("第%d次访问的磁道:%d\n",n-i,s);

           sum+=abs(k-s);

           k=s;

       }

    }

    printf("平均寻道长度:%f\n",sum*1.0/n);

}

void C_SCAN(int array[],int m)

{

    int temp;

    int k=1;

    int now,l,r,d;

    int i,j,sum=0;

    int avg;

    for(i=0;i<m;i++)

    {

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

       {

           if(array[i]>array[j])//对磁道号进行从小到大排列

           {

              temp=array[i];

              array[i]=array[j];

              array[j]=temp;

           }

       }

    }

   

    printf("请输入当前的磁道号：");

    scanf("%d",&now);

    if(array[m-1]<=now)//判断整个数组里的数是否都小于当前磁道号

    {  

       printf("CSCAN调度结果:  ");

       for(i=0;i<m;i++)

       {  

           printf("%d  ",array[i]);//将磁道号从小到大输出

       }

       sum=now-array[0]+array[m-1];//计算移动距离

    }

    else if(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号

    {  

       printf("CSCAN调度结果:  ");

       for(i=0;i<m;i++)

       {  

           printf("%d  ",array[i]);//将磁道号从小到大输出

       }

       sum=array[m-1]-now;//计算移动距离

    }

    else

    {

       while(array[k]<now)//逐一比较以确定K值

       {

           k++;

       }

       l=k-1;

        r=k;

       printf("*************循环算法**************\n");

       printf("1.移动臂由里向外   2.移动臂由外向里\n");

       printf("***********************************\n");

       printf("请在下面输入您的选择:");

       scanf("%d",&d);

       printf("CSCAN调度结果:  ");

       if(d==0)

       {

           for(j=l;j>=0;j--)

           {

              printf("%d  ",array[j]);

           }

           for(j=m-1;j>=r;j--)

           {

              printf("%d  ",array[j]);

           }

           sum=2*(array[m-1]-array[0])-array[r]+now;//计算移动距离

       }//磁道号减小方向

       else

       {

           for(j=r;j<m;j++)

           {

              printf("%d  ",array[j]);

           }

           for(j=0;j<r;j++)

           {

              printf("%d  ",array[j]);

           }

           sum=2*(array[m-1]-array[0])+array[r-1]-now;//计算移动距离

       }

    }//磁道号增加方向

    avg=sum/m;

    printf("\n平均寻道长度： %d \n",avg);

}

void main()

{

    int a[20];

    int i,n,k,k1,init;

    printf("请输入需要访问的磁道总数：");

    scanf("%d",&n);

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

    {

       printf("需要访问的磁道%d:",i+1);

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

    }

    printf("请输入指针所在磁道:");

    scanf("%d",&init);

    k=1;

    while(k)

    {

       printf("*********************************************\n");

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

       printf("1.先来先服务(FCFS)   2.最短寻道时间优先(SSTF)\n");

       printf("3.扫描算法  (SCAN)   4.循环算法(C-SCAN)      \n");

        printf("*********************************************\n");

       printf("请在下面输入您的选择:");

       scanf("%d",&k);

       switch(k)

       {

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

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

           case 3:k1=1;

             while(k1)

             {

              printf("*************扫描算法**************\n");

               printf("1.移动臂由里向外   2.移动臂由外向里\n");

               printf("0.返回上一层                       \n");

              printf("***********************************\n");

               printf("请在下面输入您的选择:");

               scanf("%d",&k1);

               switch(k1)

               {

                  case 1:SCAN1(a,n,init);break;

                  case 2:SCAN2(a,n,init);break;

               }

             }

             break;

           case 4:C_SCAN(a,n,init);break;

       }

    }

}

第二篇：磁盘调度实验报告

一.课程设计目的和要求

操作系统是计算机系统的一个重要系统软件。我们在本课程的实验过程中，了解实际操作系统的工作过程，在实践中加深对操作系统原理的理解。

本实验设计的目的是通过设计一个磁盘调度模拟系统，以加深对FCFS、最短寻道时间以及电梯等磁盘调度算法的理解。让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。

课程设计要求

⑴模拟一个磁盘调度算法；

⑵要求能够模拟FCFS、最短寻道时间、电梯算法三个磁盘调度算法；

⑶输入为一组作业的磁道请求；

⑷输出为按选择的算法执行时的磁头移动轨迹。

二．系统需求分析

磁盘调度主要思想：

设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。

平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+……+Mi+……+MN）/N

其中Mi为所需访问的磁道号所需移动的磁道数。

启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：

寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。

延迟时间——指定扇区旋转到磁头下所需的时间。

传送时间——由磁头进程读写完成信息传送的时间。

其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱面上。所以各磁盘的编号按柱面顺序（从0号柱面开始），每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。

磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘是，应采用一种最佳调度算法，以使各种进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标，是使磁盘的平均寻道时间最少。目前常用的磁盘帝调度算法有：先来先服务、最短寻道时间优先及扫描等算法。

三 概要设计

系统流程图

系统模块图

函数调用关系图

四、详细设计

(1)先来先服务算法（FCFS）

先来先服务（FCFS）调度:按先来后到次序服务，未作优化。

最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在50号柱面上执行输出操作，而等待访问者依次要访问的柱面为130、199、32、159、15、148、61、99，那么，当50号柱面上的操作结束后，移动臂将按请求的先后次序先移到130号柱面，最后到达99号柱面。

采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。

.先来先服务算法流程图

 

(2)最短寻道时间优先算法（SSTF）

最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。现在仍利用同一个例子来讨论，现在当50号柱面的操作结束后，应该先处理61号柱面的请求，然后到达32号柱面执行操作，随后处理15号柱面请求，后继操作的次序应该是99、130、148、159、199。

采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了200多个柱面的距离，与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。

但最短查找时间优先（SSTF）调度，FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。

最短寻道时间优先算法流程图

(3)电梯算法（SCAN）

SCAN 算法又称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。

“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8层带到15层，然后电梯换成下行方向，把乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。

但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。

 电梯算法流程图

五、调试过程

将15 25 35 45保存在cidao.txt文件中，运行程序，得到运行结果图如下：

六、结论与体会

通过这次课程设计，我对磁盘调度算法有了更深的认识，我学会了用C语言编写这个算法，当然这当中我遇到了许多问题，这更使我认识到要将操作系统这门计算机专业的课学好不仅仅是要把书上的基本知识学好而且还要不断进行实践，将所学的跟实践操作结合起来才能更好地巩固所学，提高自己的能力。

七、参考文献

1．《计算机操作系统》 汤小丹等 西安电子科技大学出版社

2．《操作系统设计教程》 张丽芬等 清华大学出版社 20##年

附件：源程序清单

磁盘调度系统源程序清单

#include"stdio.h"

#include"stdlib.h"

#include"iostream.h"

#include <iomanip.h>

#define maxsize 100

/*先来先服务调度算法*/

void FCFS(int array[],int m)

{

int sum=0,j,i,now;

for(i=0;i<m;i++)

{

cout<<array[i]<<" ";

}

cout<<" 请输入当前磁道号: ";

cin>>now;

for(i=0,j=1;j<m;i++,j++)

{   if(i==0) sum=abs(now-array[i]);

sum+=abs(array[j]-array[i]);

}

cout<<"移动的总道数："<<sum<<endl;

}

/*最短寻道时间优先调度算法*/

void ShortPath(int array[],int m)

{

int temp;

int k=1;

int now,l,r;

int i,j,sum=0;

for(i=0;i<m;i++)

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

{

if(array[i]>array[j])

{

temp=array[i];

array[i]=array[j];

array[j]=temp;

}

}

for(i=0;i<m;i++)

{

cout<<array[i]<<" ";

}

cout<<"请输入当前的磁道号：";

cin>>now;

if(array[m-1]<=now)

{

for(i=m-1;i>=0;i--)

cout<<array[i]<<" ";

sum=now-array[0];

}

else

if(array[0]>=now)

{

for(i=0;i<m;i++)

cout<<array[i]<<" ";

sum=array[m-1]-now;

}

else

{

while(array[k]<now)

{

k++;

}

l=k-1;

r=k;

/*确定当前磁道在已排的序列中的位置，后面的算法都用到了，可以直接复制后再进行少量修改，节省时间。*/

while((l>=0)&&(r<m))

{

if((now-array[l])<=(array[r]-now))

{

cout<<array[l]<<" ";

sum+=now-array[l];

now=array[l];

l=l-1;

}

else

{cout<<array[r]<<" ";

sum+=array[r]-now;

now=array[r];

r=r+1;

}

}

if(l==-1)

{

for(j=r;j<m;j++)

{

cout<<array[j]<<" ";

sum+=array[j]-now;

now=array[j];

}

}

else

{

for(j=1;j>=0;j--)

{

cout<<array[j]<<" ";

sum+=abs(array[j]-now);

now=array[j];

}

}

}

cout<<"移动的总道数："<<sum<<endl;

}

/*电梯调度算法*/

void Elevator(int array[],int m)/*先</A>要给出当前磁道号和移动臂的移动方向*/

{

int temp;

int k=1;

int now,l,r,d;

int i,j,sum=0;

for(i=0;i<m;i++)

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

{

if(array[i]>array[j])

{

temp=array[i];

array[i]=array[j];

array[j]=temp;

}

}

for(i=0;i<m;i++)

{

cout<<array[i]<<" ";

}

cout<<"请输入当前的磁道号: ";

cin>>now;

if(array[m-1]<=now)

{

for(i=m-1;i>=0;i--)

cout<<array[i]<<" ";

sum=now-array[0];

}

else

if(array[0]>=now)

{

for(i=0;i<m;i++)

cout<<array[i]<<" ";

sum=array[m-1]-now;

}

else

{

while(array[k]<now)

{

k++;

}

l=k-1;

r=k;

cout<<"请输入当前移动臂移动的方向(1表示向内，0表示向外)：";

cin>>d;

if(d==0)

{

for(j=1;j>=0;j--)

{

cout<<array[j]<<" ";

}

for(j=r;j<m;j++)

{

cout<<array[j]<<" ";

}

sum=now-2*array[0]+array[m-1];

}

else

{

for(j=r;j<m;j++)

{

cout<<array[j]<<" ";

}

for(j=1;j>=0;j--)

{

cout<<array[j]<<" ";

}

sum=-now-array[0]+2*array[m-1];

}

}

cout<<"移动的总道数: "<<sum<<endl;

}

//主程序

int main()

{

int c;

FILE *fp;

int cidao[maxsize];

int i=0,count;

fp=fopen("cidao.txt","r+");

if(fp==NULL)

{

cout<<"文件打不开!"<<endl;

//exit(0);

}

else

while(!feof(fp))

{

fscanf(fp,"%d",&cidao[i]);

i++;

}

count=i;

for(i=0;i<count;i++)

{

cout<<cidao[i]<<" ";

}

cout<<endl;

while(1)

{

cout<<endl<<"系统的菜单如下："<<endl;

cout<<" 1.先来先服务"<<"  2.最短寻道时间优先"<<"  3.电梯调度";

cout<<endl;

cout<<" 4.退出";

cout<<endl;

cout<<"请选择调度算法：";

cin>>c;

if(c>3)

break;

switch(c)

{

case 1:

FCFS(cidao,count);

break;

case 2:

ShortPath(cidao,count);

break;

case 3:

Elevator(cidao,count);

break;

}

}

getchar();

return 0;｝