操作系统实验报告

磁盘调度

                            实验六：磁盘调度算法

一．实验目的

复习模拟实现一种磁盘调度算法，进一步加深对磁盘调度效率的理解。

二．实验属性

该实验为设计性实验。

三．实验仪器设备及器材

普通PC386以上微机

四．实验要求

本实验要求2学时完成。

本实验要求完成如下任务：

（1） 建立相关的数据结构，作业控制块、已分配分区及未分配分区

（2） 实现一个分区分配算法，如最先适应分配算法、最优或最坏适应分配算法

（3） 实现一个分区回收算法

（4） 给定一批作业/进程，选择一个分配或回收算法，实现分区存储的模拟管理

实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告（参见附录A），并要求用正规的实验报告纸和封面装订整齐，按时上交。

五 .主要算法分析

各个算法分析

 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层。

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

六、程序代码

#include<iostream.h>

#include<stdio.h>

#include<stdlib.h>

 void FCFS(int array[],int m)// 先来先服务算法

{    int j,i,now;

        float sum = 0,avg;

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

     cin>>now;

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

     cout<<"先来先服务算法(FCFS)调度后的序列为"<<array[0]<<" ";//输出磁盘调度序列

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

        {

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

         cout<<array[j]<<" ";     //输出磁盘调度序列

        }

     avg=sum/(m);

     cout<<endl<<"平均寻道长度："<<avg<<endl;//输出平均寻道长度}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void SSTF(int array[],int m)// 最短寻道时间优先算法

{     int temp;

      int k=1;

      int now,l,r;

      int i,j;

         float sum=0,avg=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;} }

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

      cin>>now;

         cout<<"最短寻道时间优先算法(SSTF)调度后的序列为";//输出磁盘调度序列

      if(array[m-1]<=now)  //若被访问的下一最大的磁道号不大于当前的磁道号

         { 

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

         { cout<<array[i]<<" ";//输出磁盘调度序列

                 sum=now-array[i];

                 now=array[i]; }}

      else

         {f(array[0]>=now)  //若被访问的下一最小的磁道号不小于当前的磁道号

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

          {  cout<<array[i]<<" ";//输出磁盘调度序列

             sum=array[i]-now;

                      now=array[i]; }}

        else  //当前的磁道号的值在若所有被访问的下的磁道号之间

              { while(array[k]<now) //确定当前磁道在已排的序列中的位置

                 {  k++;    }

           l=k-1;

           r=k;

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

                 { while(l>=0)    //先向磁道号减小方向访问

                       {cout<<array[l]<<" "; //输出磁盘调度序列

                sum=sum+now-array[l];

                now=array[l];

                l=l-1;}

                       now=array[0];

                       for(j=r;j<m;j++)  //再向磁道号增加方向访问

                       {  cout<<array[j]<<" "; //输出磁盘调度序列

                          sum+=array[j]-now;

                          now=array}}

                 else   //先向磁道号增加方向访问

                 { while(r<m)

              { cout<<array[r]<<" ";//输出磁盘调度序列

                 sum+=array[r]-now;

                 now=array[r];

                 r=r+1; }

                       now=array[m-1];

                       for(j=l;j>=0;j--)  //再向磁道号减小方向访问

                       {  cout<<array[j]<<" ";  //输出磁盘调度序列

                          sum+=now-array[j];

                          now=array[j]; }

                 } }}

    avg=sum/(m);

    cout<<endl<<"平均寻道长度："<<avg<<endl;//输出平均寻道长度

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void SCAN(int array[],int m)  //扫描算法

{     int temp;

      int k=1;

      int now,d,l,r;

      int i,j;

         float sum=0,avg=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;

              }

         }

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

      cin>>now;

         cout<<"请输入当前移动臂的移动的方向(1 表示向磁道号增加方向,0 表示向磁道号减小方向): ";

      cin>>d;       //先要给出当前磁道号和移动臂的移动方向

         cout<<"扫描算法(SCAN)调度后的序列为";

      if(array[m-1]<=now)   //若被访问的下一最大的磁道号不大于当前的磁道号

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

         { cout<<array[i]<<" "; //输出磁盘调度序列

                 sum=now-array[i];

                 now=array[i];}}

      else  

         {if(array[0]>=now) //若被访问的下一最小的磁道号不小于当前的磁道号

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

          {  cout<<array[i]<<" "; //输出磁盘调度序列

             sum=array[i]-now;

                      now=array[i];}}

        else  //当前的磁道号的值在若所有被访问的下的磁道号之间

              { while(array[k]<now)  //确定当前磁道在已排的序列中的位置

                 {  k++;    }

           l=k-1;

           r=k;

                 switch(d)

                 { case 0:       //先向磁道号减小方向访问

                      { while(l>=0)

                        {       cout<<array[l]<<" "; //输出磁盘调度序列

                sum=sum+now-array[l];

                now=array[l];

                l=l-1;

                        }

                        now=array[0];

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

                        {  cout<<array[j]<<" "; //输出磁盘调度序列

                          sum+=array[j]-now;

                          now=array[j];

                        } break;

                      }

                 case 1:   //先向磁道号增加方向访问

                 {

                       while(r<m)

              {

                 cout<<array[r]<<" ";//输出磁盘调度序列

                 sum+=array[r]-now;

                 now=array[r];

                 r=r+1;

                       }

                       now=array[m-1];

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

                       {  cout<<array[j]<<" ";  //输出磁盘调度序列

                          sum+=now-array[j];

                          now=array[j];

                       }break;

                 }

                 default: cout<<"输入有误"<<endl;

                 }

              }

         }

    avg=sum/(m);

    cout<<endl<<"平均寻道长度："<<avg<<endl;//输出平均寻道长度

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void main()

{ 

     int i,m,n,flag=1,array[100];

     cout<<"输入磁盘调度序列的个数:";

        cin>>m;

     cout<<"分别输入磁盘调度序列:";

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

        {  cin>>array[i];  }

        do

        {

           cout<<"0 终止"<<endl;

           cout<<"1 先来先服务算法(FCFS)"<<endl;

           cout<<"2 最短寻道时间优先算法(SSTF)"<<endl;

           cout<<"3 最短寻道时间优先算法(SCAN)"<<endl;

        cout<<"选择以上的算法：";

              cin>>n;

           switch(n)

              {

                 case 0: { flag=0;  break; } //终止程序

                 case 1:

                      {  FCFS(array,m); break; } //先来先服务算法(FCFS)

                 case 2:

                     {  SSTF(array,m); break; }//最短寻道时间优先算法(SSTF)

           case 3:

                     {  SCAN(array,m); break; }//最短寻道时间优先算法(SCAN)

                 default: cout<<"输入有误，请重新输入:"<<endl;

              }

        }while(flag!=0);

}

七、各算法的流程图

1．.先来先服务算法流程图   

         

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

3. 扫描算法流程图

八．课程设计运行结果

一. 运行后的开始界面如下：

二、运行各个算法结果如下

1．运行先来先服务（FCFS）算法调度后程序结果如下：

2．运行最短寻道时间优先（SSTF）算法调度程序结果如下：

3．运行扫描（SCAN）算法调度程序结果如下：

5．选择退出后程序界面如下：

九．心得体会

整个设计中最麻烦的就是整个程序模块的划分和各模块之间接口设计，编程中经常犯想当然的错误，编程中出现了不少奇怪的错误。再调试中尝试使用了分割法,对错误模块进行定位,再进行排查.通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学好不仅仅是要把书上的基本知识学好而且还要不断进行实践，将所学的跟实践操作结合起来才能更好地巩固所学，才能提高自己实践能力.通过这次的设计使我认识到只停留在表面理解问题是很难使问题得到很好的解决的，实践能力与理论知识同样重要。可以说此课程设计的理论难度并不大，但是若要深入发掘其中的东西，并且实际去编程实现，就遇到了相当大的难度。因为与之涉及的很多方面并没有学过，需要自己去自学和实践检验。，通过模拟磁盘调度及进程排队算法来加深对操作系统中各个磁臂调度算法概念的理解。模拟磁盘调度算法(FCFS,SSTF,SCAN,CSCAN)，实现各种不同调度算法的过程，并计算各算法的平均寻道长度，以便于我们判断各种算法的优劣以及各种算法使用的场合。