磁盘驱动调度算法

操作系统课程设计

题目：磁盘驱动调度算法模拟

班级：

姓名：

学号：

指导教师：

成绩：

2014年6月

一、课程设计目标

1.进一步加深对磁盘驱动调度算法的理解。

2.编程实现“先来先服务”、“最短寻道时间优先”、“电梯调度”、“循

环扫描”算法。

二、课题内容

1.假设一个磁盘具有4个盘片;每个盘片有100个磁道,每道有8个扇区,模拟

格式化时对柱面和扇区进行编号的过程。

2.设计若干磁道访问请求,要求用户输入线性块号,系统能将其转换为对应的

磁道号（柱面号），并计算出分别采用“先来先服务”、“最短寻道时间优先”、

“电梯调度”、“循环扫描”算法的寻道总长度。

3.提供可视化且简洁清晰的用户界面,能直观且动态地描述磁头移动。

三、设计思路

（一）系统概要设计

1.整体模块设计图

磁盘驱动调度算法模拟

菜单显示F

C

F

S

算

法

S

C

A

\

算

法

S

s

T

E

算

法

C

S

c

A

\

算

法

沿

磁

道

增

加

方

向

沿

磁

道

减

小

方

向

沿

磁

道

增

加

方

向

沿

磁

道

减

小

方

向

2.相关知识

磁盘调度：当有多个进程都请求访问磁盘时,采用一种适当的驱动调度算法，使

各进程对磁盘的平均访问(主要是寻道)时间最小。目前常用的磁盘调度算法有：1)

先兴先服务2)最短寻道时间优先3)扫描算法4)循环扫描算法等

3.算法思想介绍

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

即先来的请求先被响应。FCFS策略看起来似乎是相当〃公平〃的,但是当请求

的频率过高的时候FCFS策略的响应时间就会大大延长。FCFS策略为我们建立起一

个随机访问机制的模型,但是假如用这个策略反复响应从里到外的请求,那么将会消

耗大量的时间。为了尽量降低寻道时间,看来我们需要对•等待着的请求进行适当的

排序，而不是简单的使用FCFS策略。这个过程就叫做磁盘调度管理。有时候FCFS

也被看作是最简单的磁盘调度算法。

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

最短时间优先算法选择这样的进程。要求访问的磁道，与当前磁头所在的磁道

距离最近，以使每次的寻道时间最短。

(3)电梯调度算法(SCAN)

电梯(SCAN)调度算法:该算法不仅考虑到欲访问的磁道与当前磁道间的距离，

更优先考虑的是磁头当前的移动方向。例如，当磁头正在刍里向外移动时，SCAN算

法所考虑的卜.一个访问对象,应是其欲访问的磁道，既在当前磁道之外，又是距离最

近的。这样自里向外的访问，直至再无更外的磁道需要访问时，才将磁道换向自外向

里移动。这时，同样也是每次选择这样的进程来调度,也就是要访问的当前位置内距

离最近者,这样,磁头又逐步地从外向里移动,直至再无更里面的破道要访问，从而避

免了出现“饥饿”现像。

(4)循环扫描算法(CSCAN)

循环扫描(CSCAN)算法:当磁头刚从里向外移动而越过了某一磁道时，恰好又有

一进程请求访问此磁道,这时,该里程就必须等待,为了减少这种延迟，CSCAN算法

规定磁头单向移动，而本实蛤过程中我们所设计的是磁头从里向外移动，而从外向里

移动时只须改方向而己本实验未实现。但本实验已完全能演示循环扫描的全过

程。

(二)系统详细设计

1.数据结构设计

本系统采用数组a[3200]保存用户输入的线性块号,用数组array[100]保存将

线性块号转换为磁道号。

2.模块接口设计

(1)各函数原型为:

voidmain();//主函数

intmenu();//菜世界面

voidFCESO;//FCFS算法

voidSSTFO;//SSTF算法

voidSCANO://SCAN算法

voidCSCANO;//CSCAN算法

(2)系统界面切换的实现

利用清屏函数system(〃cls〃)实现屏幕切换,在从本界面返回上一界面时,根

据提不输入即叱例如：

cout<<〃输入任意键返回主菜单〃<<endl;

cin»c;

则输入输入任意键都能返回上一界面,在main。函数中用do-while语句实现

各函数的循环调用，以使各功能能够重复实现,直至用户退出系统为止。

3.流程图

(1)主函数

开始

调用menu()函数

输入选择X

调用SSTF()函数2

调用FCFSO

函数

调用SCANO

函数

调用CSANO

函数

退出(跳出

循环)

345

1

错误信息提

示

默认

⑵界面函数

开始

调用清屏函数

输出“磁盘驱动调度算法模拟”

输出“算法选择：”

输出“1.先来先服务算法(FCFS)”

输出“2.最短寻道时间优先算法(SSTF)”

输出“3.电梯调度算法(SCAN)”

输出“4.循环扫描算法(CSCAN)”

输出“5.退出”

输出“请输入您想选择的操作：(1-5)”

输入x

返回X

结束

(3)先来先服务算法(FCFS)

开始

调用清屏函数

为总和sum赋初值为0

为磁道数组a和块号数组array赋初值为0

输入线性块号并将其转换为对应的磁道号

i=0

i<m

是

输出磁道号

否

i++

输出FCFS调度结果：

累计总的移动距离

计算平均寻道长度

输出移动的总道数和平均寻道长度

输出“输入任意键返回上一菜单”

输入c

结束

(4)最短寻道时间优先算法(SSTF)

四、源代码

^include<stdio.h>〃导入库困数

^include<stdlib.h>

#include<iostream.h>

^include<iomanip.h>

ttdefinemaxsize100〃最大的磁道号

^definemax3200//最大块号

intmenuO//菜单界面

system("cis");〃清屏函数

intx;

cout<<cndl;

cout«setfi11('*')«setw(26)«1«'\b«磁盘驱动调度算法模拟

,，«setfill(**')«setw(25)<〈'«endl;

couc<<setfillC')<<setw(37)<<"算法选择：“<<endl;

cout<<setfill(1')«setw(49)<C1.先来先服务算法(FCFS)"«endl;

cout<<setfi11('')«setw(55)<<"2.最短寻道时间优先算法(SSTF)”«endl;

cout«setfill(,，)«setw(47)«，，3.电梯调度算法(SCAN)“<<endl;

cout«setfillC')«setw(48)<<"4.循环扫描算法(CSCAN)”<<endl;

cout<<setfi11('')«setw(33)<<"5.退出"<<endl;

coutX〈"请输入您想选择的操作:(1-5)，，<<endl;

cin»x;

returnx;

)

voidFCFS()//FCFS算法

(

system(，，cls，/);

charc;

intsum=0,j,i,m=0;

intavg;

inta[max]={0},array[maxsize]={0};

coui<〈〃请输入线性块号，以-1结束：”<endl;

for(;;m++)

(

cin»a[m];

array[m]=a[m]/32;〃将线性块号转换为磁道号if(a[m]==T)break;

)

coul<<〃磁道号为:"<<endl;〃输出磁道号

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

{printf('%d”,array[i]);

)

printf("\nFCFS调度结果：“);

for(i=0;i<m;i++)〃输出FCFS磁盘调度结果{

printf(w%darray[i]);

)

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

(

sum+=abs(array[j]-array[i]);〃累计总的移动距离

}

avg=sum/(m-l);〃计算平均寻道长度printf("\n移动的总道数:为d

,sum);

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

cout<<〃输入任意键返回上一菜单〃。endl;

cin»c;

)

voidSSTFO//SSTF算法

(

system(〃cls");

charc;

inttemp;

intk=l;

intnow,1,r;

inti,j,sum=0,m=0;

intavg;

inta[max]={0},array[maxsize]={0};

coui＜〈〃请输入线性块号，以-1结束：〃《endl;

for(;;m++)

(

cin»a[m];

array[m]=a[m]/32;〃将线性块号转换为磁道号

if(a[m]==-l)break：

)

cout<<"磁道号为：〃<<endl;〃输出磁道号

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

{printf(^d〃，array[i]);

}

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

(

for(j=i+l;j<m;j++)〃对磁道号进行从小到大排列

(

if(array[i]>array[j])〃两磁道号之间比较

(

temp=array[i];

array[i]=array[j];

array[j]=temp;

)

}

)

printfC\n排序后的磁道号为:〃)；

for(i=O;i<m;i++)〃输出排序后的磁道号数组

(

printf(^%darray⑴)；

}

printf(〃\n请输入当前的磁道号：〃)；

scanf("机T,&now);

printf("\nSSTF调度结果：〃)；

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

for(i=m-l;i>=O;i-)〃将数组磁道号从大到小输出

printfC*%darray[i]);

sum=now-array[0];〃计算移动距离

}

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

for(i=0;i<m;i++)〃将磁道号从小到大输出

printf("%darray[i]);

sum=array[m-1]-now：〃计算移动距离

)

else

(

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

(

k++;

)

l=k-l;

r=k;

〃确定当前磁道在已排的序列中的位置

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

(

if((now-array[1])<=(array[r]-now))〃判断最短距离

(

printf(黑darraytl]);

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

now=array[1];

1=1-1;

)

else

(

printf("%darray[r]);

sum+二array[r]-now;〃计算移动距离

now:array[r];

r=r+l;

)

)

if(l=-D

(

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

(

printf("/darray[j]);

}

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

)

else

(

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

(

printf(*%darray[j]);

)

sum+=array-array[0];〃计算移动距离

)

)

avg=sum/m;

printf(,z\n移动的总道数:%d\n,z,sum);

printf("平均寻道长度:％d\n〃，avg);

cout”〃输入任意键返回上一菜单〃<<endl;

cin»c;

}

voidSCANO〃SCAN算法

{〃先要给出当前磁道号和移动臂的移动方向sysl加(〃cls");

charc;

inttemp;

intk=l;

intnow,1,r,d;

inti,j,sum=0,m=0;

intavg;

inta[max]={0},array[maxsize]={0};

coutX〈”请输入线性块号，以T结束："<<endl;

for(;;m++)

(

cin»a[m];

array[m]=a[m]/32;〃将线性块号转换为磁道号

if(a[m]==-l)break;

)

cout<<“磁道号为："<<endl;〃输出磁道号

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

{printf(^d”,array[i]);

)

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

(

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

(

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

(

temp:array[i];

array[i]=array[j];

array[j]=temp;

}

}

)

printf(〃\n排序后的磁道号为:〃)；

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

printf(线d〃,array[i]);〃输出排序后的磁道号数组

)

printf(〃\n请输入当前的磁道号:〃)；

scanf&now);

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

printfC\nSCAN调度结果：〃)；

for;i>=0;i­)

(

printf(级d〃,array[i]);〃将数组磁道号从大到小输出

)

sum=now-array[0];〃计算移动距离

}

elseif(array[01>=now)〃判断整个数组里的数是否都大于当前磁道号

(

printf(〃\nSCAN调度结果：〃)；

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

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

)

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

)

else

(

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

(

k++;

)

l=k-l;

r=k;

printf(^\n请输入当前移动臂的移动的方向(1磁道号增加方向,0磁道号减

小方向)：〃)；

scanf(“刎"，&d);

printf（〃\nSCAN调度结果："）;

if(d==O)

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

(

printf(^%darray[j]);

}

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

(

printf(，z%darray[j]);

)

sum=now-2*array[0]+array[mT];〃计算移动距离

}//磁道号减小方向else

(

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

(

printf("/darray[j]);

}

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

printfC，%darray[j]);

｝

sum二-now-array[0]+2*array[m-1];〃计算移动距离｝〃磁道号增加方向)

avg=sum/m;

printf(w\n移动的总道数:%d\n",sum);

printf("平均寻道长度:％d\n*,avg);

cout<<“输入任意键返回上一菜单"Gendl;cin»c;

)

voidCSCANO〃CSCAN算法｛

system(^cIs*);

charc;

inttemp;

intk=l;

intnow,1,r,d;

inti,j,sum=0,m=0;

intavg：

intarray[maxsize]={0},a[max]={0};

cout<<〃请输入线性块号，以T结束:〃<<endl;

for(;;m++)

(

cin»a[m];

array[m]=a[m]/32;〃将线性块号转换为磁道号

if(a[m]==-l)break;

)

cout<<"磁道号为:"<<endl;〃输出磁道号

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

{printf",array[i]);

}

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

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

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

temp=arra}r[i];

array[i]=array[j];

array[j]=temp;

}

)

)

printf("\n排序后的嵌道号为:〃)；

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

(

printf("机1”,array[i]);〃输出排序后的磁道号数组

}

printf(〃\n请输入当前的磁道号：〃)；

，，，，

scanf(%d,&now);

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

printf(，?\nCSCAN调度结果：”)；

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

printf(飞d”,array[i]);〃将磁道号从小到大输出

}

sum=now-arreiy[0]+array[m-l];〃计算移动距离

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

(

printf(*XnCSCAN调度结果：“);

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

(

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

)

sum=array[ni-l]-now;〃计算移动距离

}

else

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

k++;

)

l=k-l;

r=k;

printf(〃\n请输入当前移动臂的移动的方向(1磁道号增加方向,0磁道号减

小方向)：”)；

scanf("先d",&d);

printf(*\nCSCAN调度结果：〃)；

if(d==0)

(

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

(

printf(*%darray[j]);

)

for(j=m-l;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(w%d”,array[j]);

)

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

(

printfC*%d”,array[j]);

}

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

)

}〃磁道号增加方向

avg=sum/m;

printf(w\n移动的总道数:%d\n",sum);

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

cout<<〃输入任意键返回上一菜单〃<<endl;

cin»c;

)

voidmain()//主函数

(

intx,i;

for(i=0;;i++)

(

x=menu();

switch(x)

(

case1:FCFS();break;

case2:SSTF();break;

case3:SCAN();break;

case4:CSCAN();break;

case5:{cout«setfi11('*')«setw(35)«1«>\b'<<"正在退

出!*«setfillC♦*)«setw(35)«'**«end