磁盘调度实验报告

操作系统实验报告

磁

盘

调

度

实验六：磁盘调度算法

一．实验目的

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

二．实验属性

该实验为设计性实验。

三．实验仪器设备及器材

普通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

#include

#include

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

{ int j,i,now;

float sum = 0,avg;

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

cin>>now;

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

cout<<"先来先服务算法(FCFS)调度后的序列为"<

for(i=0,j=1;j

{

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

cout<

}

avg=sum/(m);

cout<

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

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

for(j=i+1;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<

sum=now-array[i];

now=array[i]; }}

else

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

{ cout<

sum=array[i]-now;

now=array[i]; }}

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

{ while(array[k]

{ k++; }

l=k-1;

r=k;

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

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

{cout<

sum=sum+now-array[l];

now=array[l];

l=l-1;}

now=array[0];

for(j=r;j

{ cout<

sum+=array[j]-now;

now=array}}

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

{ while(r

{ cout<

sum+=array[r]-now;

now=array[r];

r=r+1; }

now=array[m-1];

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

{ cout<

sum+=now-array[j];

now=array[j]; }

} }}

avg=sum/(m);

cout<

}

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

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

for(j=i+1;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<

sum=now-array[i];

now=array[i];}}

else

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

{ cout<

sum=array[i]-now;

now=array[i];}}

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

{ while(array[k]

{ k++; }

l=k-1;

r=k;

switch(d)

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

{ while(l>=0)

{ cout<

sum=sum+now-array[l];

now=array[l];

l=l-1;

}

now=array[0];

for(j=r;j

{ cout<

sum+=array[j]-now;

now=array[j];

} break;

}

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

{

while(r

{

cout<

sum+=array[r]-now;

now=array[r];

r=r+1;

}

now=array[m-1];

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

{ cout<

sum+=now-array[j];

now=array[j];

}break;

}

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

}

}

}

avg=sum/(m);

cout<

}

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

void main()

{

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

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

cin>>m;

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

for(i=0;i

{ cin>>array[i]; }

do

{

cout<<"0 终止"<

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

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

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

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<<"输入有误，请重新输入:"<

}

}while(flag!=0);

}

七、各算法的流程图

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