操作系统课程设计磁盘调度算法.docx
《操作系统课程设计磁盘调度算法.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计磁盘调度算法.docx（35页珍藏版）》请在冰点文库上搜索。
操作系统课程设计磁盘调度算法
前言
摘要：
本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，使磁盘调度的特点更简单明了，这里主要实现磁盘调度的四种算法，分别是：
1、先来先服务算法〔FCFS〕2、最短寻道时间优先算法〔SSTF〕3、扫描算法〔SCAN〕4、循环扫描算法〔CSCAN〕。
启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进展读写，完成信息传送；因此，执行一次输入输出所花的时间有：
寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。
延迟时间——指定扇区旋转到磁头下所需的时间。
传送时间——由磁头进程读写完成信息传送的时间，寻道时间——指计算机在发出一个寻址命令，到相应目标数据被找到所需时间；其中传送信息所花的时间，是在硬件设计时固定的，而寻找时间和延迟时间是与信息在磁盘上的位置有关；然后设计出磁盘调度的设计方式，包括算法思路、步骤，以与要用到的主要数据结构、函数模块与其之间的调用关系等，并给出详细的算法设计，对编码进展了测试与分析。
最后进展个人总结与设计体会。
关键词：
最短寻道时间优先算法、扫描算法、总寻道长度.
2.课程设计任务与要求
2.1设计任务
1.熟悉并掌握磁盘调度算法管理系统的设计方法，加强对所学各种调度算法与相应算法的特点了解。
2.掌握磁盘调度的根本概念，深刻体会各个算法的优缺点，以与算法间的相似点。
2.2设计要求
1）定义与算法相关的数据结构，如PCB、队列等；
2）实现2种不同的调度算法〔可使用伪代码或流程图进展分析〕；
3）算法执行完毕时，应给出总的寻道长度；
4）磁道访问序列随机生成，且要满足一定的数量要求〔不少于100个〕；
5〕系统实现必须提供一定的交互性，所需测试数据应当以文件形式提供或者由用户在测试过程中给出，不可将测试数据“写死〞在系统实现代码中；
6〕必须给出足够的注释，注释量不得少于代码量的一半；
7〕对于系统中所使用到的系统调用〔API函数〕，必须给出函数的定义原型、使用方法，参数较为复杂的，还应该给出参数的具体描述；
3.算法与数据结构
3.1算法的总体思想〔流程〕
总流程图
YN
YN
3.2实现过程中用到的数据结构
1.最短寻道时间优先〔SSTF〕
〔从100号磁道开始〕
被访问的下一个磁道号
移动距离〔磁道数〕
55
45
58
3
39
19
18
21
90
72
160
70
150
10
38
112
184
146
图aSSTF调度算法示例图
用冒泡法对磁道数组进展排序
返回侧〔外侧〕扫描
图bSSTF算法流程示例图
原磁道号随机组成的数组：
cidao[]={55,58,39,18,90,160,150,38,184}；
排序后的数组={18,38,39,5,58,90,150,160,184}；
输入当前磁道号：
now=100；
38
3939
555555
58585858
9090909090
now值:
10090585539
184
160160
150150150
18181818
38383838
39393939
55555555
58585858
90909090
now值：
18150160184
图cSSTF算法队列示意图（按磁道访问顺序）
2.扫描〔SCAN〕算法
〔从100号磁道开始，向磁道号增加方向访问〕
被访问的下一个磁道号
移动距离〔磁道数〕
150
50
160
10
184
24
90
94
58
32
55
3
39
16
38
1
18
20
图dSCAN算法示例图
原磁道号随机组成的数组：
cidao[]={55,58,39,18,90,160,150,38,184}；
排序后的数组={18,38,39,5,58,90,150,160,184}；
输入当前磁道号：
now=100；
选择磁道移动方向；
以磁道号增加的方向移动为例：
55
5858
909090
184184184184
160160160160160
150150150150150150
now值：
1001501601849058
18
3838
393939
555555
585858
909090
184184184
160160160
150150150
now值:
553938
图eSCAN算法队列示意图〔按磁道访问顺序〕
3.3实现过程中用到的系统调用
系统模块调用关系图
4.程序设计与实现
4.1最短寻道时间优先算法〔SSTF〕模块
now<=cidao[0]cidao[0]=cidao[m-1]
4.1.2程序说明
算法分析
①优点：
相较于先来先服务算法〔FCFS〕有更好的寻道性能，使每次的寻道时间最短。
缺点：
易造成某个进程发生“饥饿〞现象。
②最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。
例如，如果现在读写磁头正在100号柱面上执行输出操作，而等待访问者依次要访问的柱面为55,58,39,18,90,160,150,38,184，那么，当100号柱面的操作完毕后，应该先处理90号柱面的请求，然后到达58号柱面执行操作，随后处理55号柱面请求，后继操作的次序应该是39,38,18,150,160,184.采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动多个柱面的距离，与先来先服务、算法比拟，大幅度地减少了寻找时间，具有更好的寻道性能，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。
但最短查找时间优先〔SSTF〕调度，FCFS会引起读写头在盘面上的大围移动，SSTF查找距离磁头最短〔也就是查找时间最短〕的请求作为下一次服务的对象。
SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延〔又称饥饿〕。
③算法流程：
输入磁头初始磁道号，序列长度，磁道号序列。
选择磁盘调度算法〔最短寻道时间优先调度（SSTF）〕或〔扫描调度算法（SCAN）〕中的任意一个，假设选择SSTF，如此输出各进程被调度的顺序，并计算总的寻道长度和平均寻道长度，选择关闭如此完毕磁盘调度。
4.1.3程序关键代码
for（i=0;ifor（j=i+1;j{
if（array[i]>array[j]）
{
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
if（array[m-1]<=now）/*假设当前磁道号大于请求序列中最大者，如此直接由外向依次给予各请求服务*/
{
for（i=m-1;i>=0;i--）
cout<sum=now-array[0];
}
else
if（array[0]>=now）/*假设当前磁道号小于请求序列中最小者，如此直接由向外依次给予各请求服务*/
while（（l>=0）&&（r{
if（（now-array[l]）<=（array[r]-now））/*选择与当前磁道最近的请求给予服务*/
{
cout<sum+=now-array[l];
now=array[l];
l=l-1;
}
扫描算法〔SCAN〕模块
4.2.1程序流程图
d=1
d=0
4.2.2程序说明
算法分析
①优点：
排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。
缺点：
新进来的访问此磁道的进程的请求会被大推迟。
增加延迟。
②SCAN算法又称电梯调度算法。
SCAN算法是磁头前进方向上的最短查找时间优先算法。
注：
“电梯调度〞算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。
这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客一、二、三在等候乘电梯。
他们的要：
一在2层等待去10层；二在5层等待去底层；三在8层等待去15层。
由于电梯目前运动方向是向上，所以电梯的形成是先把乘客三从8层带到15层，然后电梯换成下行方向，把乘客二从5层带到底层，电梯最后再调换方向，把乘客一从2层送到10层。
我们仍用前述的同一例子来讨论采用“电梯调度〞算法的情况。
由于磁盘移动臂的初始方向有两个，而该算法是与移动臂方向有关，所以分成两种情况来讨论。
这里是：
移动臂先由里向外移动，再由外向里移动。
开始时，，在100号柱面执行操作的读写磁头的移动臂方向是由里向外，趋向32号柱面的位置，因此，当访问100号柱面的操作完毕后，沿臂移动方向最近的柱面是150号柱面。
所以应先为150号柱面的访问者服务，然后是为160号柱面的访问者服务。
之后，由于在向外移方向已无访问等待者，故改变移动臂的方向，由外向里依次为各访问者服务。
在这种情况下为等待访问者服务的次序是184,90,58,55,39,38,18。
③算法流程：
输入磁头初始磁道号，序列长度，磁道号序列。
选择磁盘调度算法〔最短寻道时间优先调度（SSTF）〕或〔扫描调度算法（SCAN）〕中的任意一个，假设选择SCAN，如此需要选择磁头移动方向是“向磁道号增加方向访问〞或“向磁道号减少方向访问〞，之后，输出各进程被调度的顺序，并计算总的寻道长度和平均寻道长度，选择关闭如此完毕磁盘调度。
4.2.3程序关键代码
if（d==0）/*选择移动臂方向向，如此先向扫描*/
{
for（j=l;j>=0;j--）
{
cout<}
for（j=r;j{
cout<}
sum=now-2*array[0]+array[m-1];
}
else/*选择移动臂方向向外，如此先向外扫描*/
{
for（j=r;j{
cout<}
for（j=l;j>=0;j--）/*磁头移动到最大号，如此改变方向向扫描未扫描的磁道*/
{
cout<}
sum=-now-array[0]+2*array[m-1];
}
ave=（float）（sum）/（float）（m）;
4.3实验结果
运行界面截图与相应代码
1.主界面
voiddisplay（）{
cout<<"\n\n\n\nOperatingSystemsCurriculumDesign\n";
cout<<"\n╔———————————————————————————————╗";
cout<<"\n││";
cout<<"\n│名称:
磁盘调度│";
cout<<"\n││";
cout<<"\n│工具:
VisualStudio2010│";
cout<<"\n││";
cout<<"\n│班级:
1205│";
cout<<"\n││";
cout<<"\n│施静│";
cout<<"\n││";
cout<<"\n│学号：
211214020│";
cout<<"\n││";
cout<<"\n╚———————————————————————————————╝\n";
system（"pause"）;
system（"cls"）;
2.前言提示用户此程序实现的算法
cout<<"【载入完成】"<cout<<"前言"<cout<<"欢迎使用『磁盘调度算法系统』，本程序实现了常用的磁盘调度算法如下所示：
\n\n";
cout<<"①最短寻道时间优先〔SSTF〕：
最短寻道时间优先算法要求访问的磁盘与当前磁头所在的\n";
cout<<"磁盘距离最近，以使每次的寻道时间最短。
\n\n";
cout<<"②扫描算法（SCAN）电梯调度：
扫描算法不仅考虑到欲访问的磁道与当前磁道的距离\n";
cout<<"更优先考虑的是磁头的当前移动方向。
\n\n";
system（"pause"）;
system（"cls"）;//清屏
3.用户选择所使用的算法〔先随机生成101个磁道号〕
voidshowMenu（intcidao[],intn）{
intchoice;
while（true）{
cout<<"请您选择喜欢的算法来实现调度（输入1-3）:
";
cout<<"\n╔—————————————╗";
cout<<"\n││";
cout<<"\n│1.最短寻道时间优先（SSTF）|";
cout<<"\n││";
cout<<"\n│2.扫描算法（SCAN）│";
cout<<"\n││";
cout<<"\n│3.退出（EXIT）│";
cout<<"\n││";
cout<<"\n╚—————————————╝\n";
cout<while（true）{
cout<<"现在您选择的算法号是〔1-3〕：
";
cin>>choice;
switch（choice）{/*case1:
FCFS（a,n）;
break;*/
case1:
SSTF（cidao,n）;
break;
case2:
SCAN（cidao,n）;
break;
case3:
cout<<"\n要退出系统了欢迎使用本系统\n";
exit（0）;
}
}
}
}
4.最短寻道时间优先算法
/**********************最短寻道时间优先调度算法********************/
voidSSTF（intcidao[],intm）
{
system（"cls"）;
intk=1;
intnow,l,r;
inti,j,sum=0;
inta;
charstr[100];
floatave;
cidao=bubble（cidao,m）;//调用冒泡排序算法排序
cout<<"请输入当前的磁道号：
";
C:
cin>>str;//对输入数据进展有效性判断
a=decide（str）;
if（a==0）
{
cout<<"输入数据的类型错误,请重新输入！
"<gotoC;
}
else
now=trans（str,a）;//输入当前磁道号
if（cidao[m-1]<=now）//假设当前磁道号大于请求序列中最大者，如此直接由外向依次给予各请求服务
{
cout<<"磁盘扫描序列为：
";
for（i=m-1;i>=0;i--）
cout<sum=now-cidao[0];
}
if（cidao[0]>=now）//假设当前磁道号小于请求序列中最小者，如此直接由向外依次给予各请求服务
{
cout<<"磁盘扫描序列为：
";
for（i=0;icout<sum=cidao[m-1]-now;
}
if（now>cidao[0]&&now{
cout<<"磁盘扫描序列为：
";
while（cidao[k]{
k++;
}
l=k-1;
r=k;
while（（l>=0）&&（r{
if（（now-cidao[l]）<=（cidao[r]-now））//选择与当前磁道最近的请求给予服务
{
cout<sum+=now-cidao[l];
now=cidao[l];
l=l-1;
}
else
{
cout<sum+=cidao[r]-now;
now=cidao[r];
r=r+1;
}
}
if（l==-1）//磁头移动到序列的最小号，返回外侧扫描仍未扫描的磁道
{
for（j=r;j{
cout<}
sum+=cidao[m-1]-cidao[0];
}
else//磁头移动到序列的最大号，返回侧扫描仍未扫描的磁道
{
for（j=l;j>=0;j--）
{
cout<}
sum+=cidao[m-1]-cidao[0];
}
}
ave=（float）（sum）/（float）（m）;//求平均寻道长度
cout<cout<<"总的寻道长度：
"<cout<<"平均寻道长度：
"<cout<<"请按任意键返回系统菜单"<getch（）;
showMenu（cidao,m）;//回到主界面
}
最短寻道时间优先〔SSTF〕算法实现界面
（2）扫描〔SCAN〕算法
/*****************************扫描调度算法*******************************/
voidSCAN（intcidao[],intn）//先要给出当前磁道号和移动臂的移动方向
{
inttemp;
inti,j;
intnow;
intsum;
for（i=0;ifor（j=i+1;jif（cidao[i]>cidao[j]）{
temp=cidao[i];
cidao[i]=cidao[j];
cidao[j]=temp;
}
}
cout<<"\n按非递减顺序排列好的磁道:
\n";
for（i=0;icout<cout<cout<<"\n请输入当前的磁道号:
";
cin>>now;//用户自定义当前磁道号
if（cidao[n-1]<=now）
{
for（i=n-1;i>=0;i--）
cout<sum=now-cidao[0];
}
else//cidao[n-1]>now
if（cidao[0]>=now）{
for（i=0;icout<sum=cidao[n-1]-now;
}
else//cidao[0]now
{
intpointer;
intlocation=1;
intleft,right;
while（cidao[location]location++;
left=location-1;
right=location;
cout<<"\n请输入当前磁头想要移动的方向（1磁道号增加方向，0磁道号减小方向）:
";
loop:
cin>>pointer;
cout<<"\n磁盘调度顺序为:
\n";
if（pointer==0||pointer==1）{
if（pointer==0）//磁头向左移动到最小号，再改变方向向外扫描未扫描的磁道
{
for（j=left;j>=0;j--）
cout<for（j=right;jcout<sum=now+cidao[n-1]-2*cidao[0];
cout<}
if（pointer==1）//磁头向右移动到最大号，再改变方向向扫描未扫描的磁道
{
for（j=right;jcout<for（j=left;j>=0;j--）
cout<sum=2*cidao[n-1]-now-cidao[0];//求总寻道长度
cout<}
}
else{
cout<<"\n输入不合法!
!
请输入0或1:
\n";
gotoloop;
}
}
cout<<"\n\n需要移动的总磁道数为:
"<cout<<"请按任意键返回系统菜单"<getch（）;
showMenu（cidao,n）;//回到主界面
5.结论
〔1〕用户界面友好，采用了选择菜单模式，用户只需按“回车键〞即可再现主界面；结构清晰，操作简单易懂，界面清爽整洁；
〔2〕控制变量比照，各磁盘调度算法均对同一组随机磁道号进展调度，但并不会改变随机磁道容，保证了平均寻道长度比照的真实性、有效性。
〔3〕各种算法都有优点，也各有不足，需要权衡利弊，使用才能达到最好的效果。
6.参考文献
《计算机操作系统（修订版）》汤子瀛电子科技大学
《操作系统教程》方敏编电子科技大学
《数据结构〔C++版〕》王红梅、胡明、王涛编著清华大学
7.收获、体会和建议
在做本次课程设计之前，对于磁盘调度，我完全没有概念。
通过努力以与结合教师之前讲的容，我终于深刻理解了磁盘调度算法的涵。
在研究自己所选的两种算法的同时，对磁盘调度的四种算法——先来先服务算法〔FCFS〕、最短寻道时间优先算法〔SSTF〕、扫描算法〔SCAN〕、循环扫描算法〔CSCAN〕都有了更深刻的理解和掌握，使我能够为磁盘调度选择适当的算法，提高CPU工作效率。
设计过程中遇到的困难在教师和同学的帮助下顺利解决并通过了验收，我深刻认识到算法的逻辑性对程序的重要影
升级会员 