1

操作系统课程设计---磁盘调度算法

目 录

一 .课程设计目的......................................................................................................... 2

二 .课程设计要求......................................................................................................... 2

三 .课程设计原理......................................................................................................... 2

四 .主要算法分析......................................................................................................... 3

五．程序代码................................................................................................................... 2

六. 各算法的流程图 .................................................................................................................... 9

七．课程设计运行结果.............................................................................................. 12

一. 运行后的开始界面........................................................................................ 11

二、运行各个算法结果....................................................................................... 12

三．输入错误后程序界面................................................................................... 13

八．心得体会.............................................................................................................. 14

九．参考文献.............................................................................................................. 14

1

2

操作系统课程设计---磁盘调度算法

一 .课程设计目的

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

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

二 .课程设计要求

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

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

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

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

三 .课程设计原理

磁盘调度主要思想

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

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

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

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

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

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

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

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

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

2

3

操作系统课程设计---磁盘调度算法

四 .主要算法分析

各个算法分析

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;

3

4

操作系统课程设计---磁盘调度算法

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

4

5

操作系统课程设计---磁盘调度算法

{

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;

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[j];

}

}

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];

5

6

操作系统课程设计---磁盘调度算法

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) //若被访问的下一最小的磁道号不小于当前的磁道号 {

6

7

操作系统课程设计---磁盘调度算法

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];

7

8

操作系统课程设计---磁盘调度算法

}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);

}

六、各算法的流程图

8

9

操作系统课程设计---磁盘调度算法

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

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

9

10

操作系统课程设计---磁盘调度算法

3. 扫描算法流程图

10

七．课程设计运行结果

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

12

操作系统课程设计---磁盘调度算法

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

1．运行先来先服务（

FCFS）算法调度后程序结果如下：

2．运行最短寻道时间优先（

SSTF）算法调度程序结果如下：

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

12

13

操作系统课程设计

---磁盘调度算法

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

三．输入错误后程序界面如下：

在选择算法时，如果输入数字不在

0~3之间，出错界面如下：

13

14

操作系统课程设计---磁盘调度算法

八．心得体会

整个设计中最麻烦的就是整个程序模块的划分和各模块之间接口设计，编程中经常犯想当然的错误，编程中出现了不少奇怪的错误。再调试中尝试使用了分割法,对错误模块进行定位,再进行排查.

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

九．参考文献

[1].汤子瀛，哲凤屏，汤小丹编著. 计算机操作系统.西安电子科技大学出版社, 2005

[2]. 周敏，杨武，杨承玉编著. 计算机操作系统原理实验指导 基于LINUX（Ver 3.0）. 重庆：重庆工学院，2006

[3]. 谭浩强编著. C语言程序设计（第3版）.清华大学出版社，2005

[4].

14