磁盘调度算法设计报告.docx
《磁盘调度算法设计报告.docx》由会员分享,可在线阅读,更多相关《磁盘调度算法设计报告.docx(20页珍藏版)》请在冰点文库上搜索。
磁盘调度算法设计报告
操作系统课程设计报告
题目:
磁盘调度算法
院系:
信息学院
班级:
信管11-2
姓名:
王裕辰
学号:
1101051024
指导教师:
赵华
一、概述
本次设计的程序主要功能是模拟访问磁盘的过程,实现先来先服务调度算法、最短寻道时间调度算法、扫描算法、循环扫描算法四个磁盘调度算法,并根据输入的数据和所选择的调度算法输出每种调度算法的磁盘访问顺序,计算并输出四个算法的平均寻道长度。
本程序主要实现磁盘访问的顺序,输出四种不同的磁盘调度算法的磁盘访问结果,并计算出各自的平均寻道长度。
以此来对四种调度算法的性能进行评价。
二、设计的基本概念和原理
1、基本概念
(1)当前磁道号:
磁头当前时刻所在磁盘的磁道编号。
(2)被访问的下一个磁道号:
需要访问的下一个磁盘的磁道编号。
(3)移动距离:
磁头从当前磁道移动到被访问的下一个磁道号所需移动的磁道数。
2、基本原理
(1)先来先服务(FCFS,FirstComeFirstServed)
按照进程请求访问磁盘的先后次序进行从小到大排序,每次访问最先请求访问的磁道。
这样是每个进程的请求都能够依次地得到处理,不会出现某一进程的请求长期得不到满足的情况
(2)最短寻道时间优先(SSTF,ShortestSeekTimeFirst)
要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短。
磁头每次都移动到距离当前磁道距离最小的磁道上。
(3)扫描算法(SCAN)
将请求访问的磁道号进行排序(升序或降序),磁头按照磁道号从大到小或从小到达的顺序访问磁盘。
(4)循环扫描算法(CSCAN)
磁头从当前磁道从里向外(或从外向里)访问磁道,当访问到最外(或最里)的磁道并访问后,磁头立即返回最里的(或最外)的欲访问的磁道,即最小(或最大)的磁道号紧接着最大(或最小)磁道号构成循环,进行循环扫描。
三、总体设计
本程序才用了结构化程序设计方法,将程序进行模块化处理。
首先将进程访问磁盘的请求抽象为一个类,用用户所输入的数据来把每个对象来初始化。
然后分块地调用不同的函数实现不同的调度算法。
本程序包括以下三个模块:
(1)预定义及进程类定义模块
定义程序所用到的头文件和常量。
定义请求类的类成员,成员函数以及输出请求类的类成员的输出函数
(2)主程序模块
包括以下五个步骤
选择进程调度算法
输入请求
调用所选的磁盘调度算法
计算每个请求的移动距离
输出磁盘访问顺序和每个请求的移动距离,计算并输出所选算法的平均寻道长度
(3)其它函数模块
定义了四种调度算法和程序中调用的其他函数。
程序流程图如下图所示
四、详细设计
每个模块的代码及分析如下:
1、预定义及进程类定义模块
#include"stdafx.h"
#include
#include
#include
usingnamespacestd;
#defineStartnumber100//开始访问的磁道号
#defineMax100//进程最大值
classRequest
{
private:
intnumber,distance,difference;
//number-被访问的下一个磁道号distance-移动距离difference--被访问的下一个磁道与当前磁道的距离
public:
intgetnumber()//返回被访问的下一个磁道号
{
returnnumber;
}
intgetdistance()//返回移动距离
{
returndistance;
}
intgetdifference()//返回被访问的下一个磁道与当前磁道的距离
{
returndifference;
}
voidsetnumber(intt)//设置被访问的下一个磁道号
{
number=t;
}
voidsetdistance(intt)//设置移动距离
{
distance=t;
}
voidsetdifference(intt)//设置被访问的下一个磁道与当前磁道的距离
{
difference=t;
}
voidshow()const//输出被访问的下个磁道号和移动距离
{
cout<}
};
2、主程序模块
intmain(intargc,char*argv[])
{
inti,c,num,option,choice;
doubleaverdis;//平均寻道长度
Requestrequest[Max];//请求数组存放请求
while
(1)
{
cout<<"磁盘调度算法"<cout<<"1.先来先服务2.最短寻道时间优先"<cout<<"3.扫描算法4.循环扫描算法"<cout<<"0.退出"<cout<cout<<"请输入你选择的调度算法:
";
cin>>choice;//输入选择的调度算法
if(choice==0)
return0;
else
{
cout<<"请输入请求数量:
";
cin>>c;
for(i=0;i{
cout<<"请输入第"<
cout<<"被访问的下一个磁道号"<cin>>num;
request[i].setnumber(num);
}
if(choice==1)
FCFS(request,c);//调用先来先服务
if(choice==2)
{
SSTF(request,c);//调用SSTF
FCFS(request,c);//调用先来先服务计算移动距离
}
if(choice==3||choice==4)//若选择SCAN或CSCAN则需要选择访问方向
{
cout<<"选择访问方向:
"<cout<<"1.向磁道号增加方向2.向磁道号递减方向"<cout<<"你的选择是:
";
cin>>option;//选择访问方向
if(choice==3)
SCAN(request,c,option);//调用SCAN
if(choice==4)
CSAN(request,c,option);//调用CSCAN
FCFS(request,c);//调用先来先服务计算移动距离
}
averdis=calcuaverage(request,c);//计算平均寻道长度
cout<for(i=0;irequest[i].show();
cout<<"平均寻道长度为:
";
cout<}
}
return0;
}
3、其它函数模块
voidFCFS(Request*req,intcount)
{//先来先服务
inti,currentnumber;
for(i=0;i{
if(i==0)//第一个请求的移动距离为它的磁道号与Startnumber的差
{
req[i].setdistance(abs(req[i].getnumber()-Startnumber));
currentnumber=req[i].getnumber();
}
else//其他请求的移动距离为其磁道号与上一个请求磁道号的差
{
req[i].setdistance(abs(req[i].getnumber()-currentnumber));
currentnumber=req[i].getnumber();
}
}
}
doublecalcuaverage(Request*req,intcount)//求平均寻道长度
{
inti;
doubleaver;
aver=0;
for(i=0;i{
aver+=req[i].getdistance();
}
aver=aver/count;
returnaver;
}
voidasc(Request*req,intcount)//按磁道号递增排序
{
inti,j;
Requesttemp;
for(i=0;i{
for(j=i;j{
if(req[j].getnumber(){
temp=req[j];
req[j]=req[i];
req[i]=temp;
}
}
}
}
voiddec(Request*req,intcount)//按磁道号递减排序
{
inti,j;
Requesttemp;
for(i=0;i{
for(j=i;j{
if(req[j].getnumber()>req[i].getnumber())
{
temp=req[j];
req[j]=req[i];
req[i]=temp;
}
}
}
}
voidSSTF(Request*req,intcount)
{//最短寻道时间优先
inti,currentnumber,j,k,min,flagmin[Max],flag;
Requestmediareq[Max];
for(i=0;iflagmin[i]=0;
currentnumber=Startnumber;
k=0;
for(i=0;i{
//求所有磁道号与当前磁道的差
for(j=0;jreq[j].setdifference(abs(req[j].getnumber()-currentnumber));
//找磁道差的最小值,并把此请求放入中间数组中,其磁道作为当前磁道
for(j=0;j{
if(flagmin[j]==0)
{
min=req[j].getdifference();
flag=j;
break;
}
}
for(j=0;j{
if(req[j].getdifference(){
min=req[j].getdifference();
flag=j;//flag记录磁道差最小的请求号
}
}
flagmin[flag]=1;
mediareq[k++]=req[flag];//找到的请求放入中间数组中
currentnumber=req[flag].getnumber();//磁道号作为当前磁道
}
for(i=0;ireq[i]=mediareq[i];
}
voidSCAN(Request*req,intcount,intp)
{//扫描算法
inti,j,k,l;
Requestmediamax[Max],mediamin[Max];
j=0;
k=0;
for(i=0;i{
if(req[i].getnumber()>Startnumber)
mediamax[j++]=req[i];
if(req[i].getnumber()mediamin[k++]=req[i];
}
asc(mediamax,j);
dec(mediamin,k);
if(p==1)
{//向磁道号增加的方向访问,先访问大于开始磁道号的磁道,再访问小于Startnumber的
for(i=0;ireq[i]=mediamax[i];
for(i=j,l=0;ireq[i]=mediamin[l];
}
else
{//向磁道号减少的方向访问,先访问小于Startnumber的磁道,再访问大于Startnumber的
for(i=0;ireq[i]=mediamin[i];
for(i=k,l=0;ireq[i]=mediamax[l];
}
}
voidCSAN(Request*req,intcount,intp)
{
inti,j,k,l;
Requestmediamax[Max],mediamin[Max];
j=0;
k=0;
for(i=0;i{
if(req[i].getnumber()>Startnumber)
mediamax[j++]=req[i];
if(req[i].getnumber()mediamin[k++]=req[i];
}
if(p==1)//向磁道号增加的方向访问
{
asc(mediamin,k);//将小于Startnumber的磁道的请求按磁道号升序排序
asc(mediamax,j);//将大于Startnumber的磁道的请求按磁道号升序排序
for(i=0;ireq[i]=mediamax[i];
for(i=j,l=0;ireq[i]=mediamin[l];
}
else
{
dec(mediamin,k);//将小于于Startnumber的磁道的请求按磁道号降序排序
dec(mediamax,j);//将大于Startnumber的磁道的请求按磁道号降序排序
for(i=0;ireq[i]=mediamin[i];
for(i=k,l=0;ireq[i]=mediamax[l];
}
}
五、测试与数据分析
选择FCFS算法,输入以下请求信息:
被访问的下一个磁道号移动距离(磁道数)
5545
583
3919
1821
9072
16070
15010
38112
184146
可以得到先来先服务调度算法的平均寻道时间(应为55.3)。
选择最短寻道时间调度算法,再次输入上述请求信息。
可以得到SSTF的平均寻道时间(应为27.5)。
选择扫描算法,再次输入以上请求信息,选择向磁道号增加的方向访问,则得到扫描算法的平均寻道长度(应为27.8)。
选择循环扫描算法,再次输入上述请求信息,选择向磁道号增加的方向访问,得到循环扫描算法的平均寻道时间(应为35.8)
将上述四个调度算法得到的平均寻道时间进行比较,可以对这四种算法的性能进行分析和比较,对这四个磁盘调度算法有了更深入的理解。
六、完成的情况、简要的使用说明
本程序经过了调试,能够正常运行,并能够得到正确的结果。
但使用时应注意以下几个问题:
1、选择调度算法的时候只能输入0、1、2、3、4这五个数字,若输入其它字符将造成程序进入死循环。
2、进行扫描算法和循环扫描算法时,选择访问方向只能为1或2,若输入其它字符将造成程序进入死循环。
3、在输入请求信息之前,应确定请求的数目,并输入。
4、本程序需要逐个输入请求的信息,对于请求数目比较多的时候会花费较长的时间。
故本程序最好用于请求数目较少的情况。
5、程序中的开始磁道号(Startnumber)为常量,用户无法输入但可以在程序代码中进行修改。
七、结果分析
运行程序界面如如下图所示
选择1,输入五测试与数据分析中的数据,得到如下所示
选择2,再次输入上述数据,得到如下所示
选择3,再输入上述数据,选择向磁道号增加的方向访问,得到如下所示
选择4,输入上述数据,选择向磁道号增加的方向访问,得到如下所示
八、总结
本程序的最大特色为用户可以循环不断地选择调度算法,输入请求,得到每种算法的调度结果,以便用户可以对不同的磁盘调度算法进行比较和分析。
本程序能够模拟四种磁盘调度算法,计算出每个请求的移动距离和每种算法的访问顺序、平均寻道长度,便于加深对磁盘调度过程的理解,也能够更好地对四种算法的性能进行较为全面的分析。
本次课程设计首先让我对课本上的知识掌握的更加牢固,通过自己编写算法,模拟了磁盘调度过程,不但提高了我的编程能力,而且增强了我分析问题、解决问题的能力。
本程序由自己独立设计完成,虽然其间遇到了很多问题,但自己都能够顺利地解决,通过这个过程,感觉自己收获了很多。
在一开始做课程设计的时候,感觉无从下手,不知所措,毫无头绪,自己想起什么就写什么。
后来,我对课本上算法的描述仔细分析和理解,逐渐有了思路。
首先将程序的大致流程进行了规划和设计,然后将程序流程进行模块划分,接下来对每个模块进行分析,编写每个模块的代码。
最后所有模块完成后,将所有模块连接起来放入一个程序中,进行调试,直到程序没有错误,能够正确运行并能够得到正确的结果。
九、参考文献
【1】汤小丹等计算机操作系统西安电子科技大学出版社2007.5
【2】杜茂康等C++面向对象程序设计电子工业出版社2011.7