磁盘驱动调度算法.docx
《磁盘驱动调度算法.docx》由会员分享，可在线阅读，更多相关《磁盘驱动调度算法.docx（27页珍藏版）》请在冰点文库上搜索。
磁盘驱动调度算法
操作系统课程设计
题目：
磁盘驱动调度算法模拟
班级:
姓名：
学号：
指导教师:
成绩:
2014年6月
1、课程设计目标
1．进一步加深对磁盘驱动调度算法的理解。
2．编程实现“先来先服务”、“最短寻道时间优先”、“电梯调度”、“循环扫描”算法。
二、课题内容
1．假设一个磁盘具有4个盘片，每个盘片有100个磁道，每道有8个扇区，模拟格式化时对柱面和扇区进行编号的过程。
2．设计若干磁道访问请求，要求用户输入线性块号，系统能将其转换为对应的磁道号（柱面号），并计算出分别采用“先来先服务”、“最短寻道时间优先”、“电梯调度”、“循环扫描”算法的寻道总长度。
3．提供可视化且简洁清晰的用户界面，能直观且动态地描述磁头移动。
三、设计思路
（一）系统概要设计
1.整体模块设计图
磁盘驱动调度算法模拟
菜单显示
CSCAN算法
沿磁道减小方向
SSTF算法
SCAN
算法
FCFS算法
沿磁道增加方向
沿磁道减小方向
沿磁道增加方向
2.相关知识
磁盘调度：
当有多个进程都请求访问磁盘时，采用一种适当的驱动调度算法，使各进程对磁盘的平均访问（主要是寻道）时间最小。
目前常用的磁盘调度算法有：
1）先来先服务2）最短寻道时间优先3）扫描算法4）循环扫描算法等
3.算法思想介绍
（1）先来先服务算法（FCFS）
即先来的请求先被响应。
FCFS策略看起来似乎是相当"公平"的，但是当请求的频率过高的时候FCFS策略的响应时间就会大大延长。
FCFS策略为我们建立起一个随机访问机制的模型，但是假如用这个策略反复响应从里到外的请求，那么将会消耗大量的时间。
为了尽量降低寻道时间，看来我们需要对等待着的请求进行适当的排序，而不是简单的使用FCFS策略。
这个过程就叫做磁盘调度管理。
有时候FCFS也被看作是最简单的磁盘调度算法。
（2）最短寻道时间优先算法（SSTF）
最短时间优先算法选择这样的进程。
要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。
（3）电梯调度算法（SCAN）
电梯（SCAN）调度算法:
该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。
例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道，既在当前磁道之外，又是距离最近的。
这样自里向外的访问，直至再无更外的磁道需要访问时，才将磁道换向自外向里移动。
这时，同样也是每次选择这样的进程来调度，也就是要访问的当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现像。
（4）循环扫描算法（CSCAN）
循环扫描（CSCAN）算法：
当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该里程就必须等待，为了减少这种延迟，CSCAN算法规定磁头单向移动，而本实验过程中我们所设计的是磁头从里向外移动，而从外向里移动时只须改方向而已，本实验未实现。
但本实验已完全能演示循环扫描的全过程。
（2）系统详细设计
1.数据结构设计
本系统采用数组a[3200]保存用户输入的线性块号，用数组array[100]保存将线性块号转换为磁道号。
2.模块接口设计
（1）各函数原型为：
voidmain（）;//主函数
intmenu（）;//菜单界面
voidFCFS（）;//FCFS算法
voidSSTF（）;//SSTF算法
voidSCAN（）;//SCAN算法
voidCSCAN（）;//CSCAN算法
（2）系统界面切换的实现
利用清屏函数system（"cls"）实现屏幕切换，在从本界面返回上一界面时，根据提示输入即可，例如：
cout<<"输入任意键返回主菜单"<cin>>c;
则输入输入任意键都能返回上一界面，在main（）函数中用do-while语句实现各函数的循环调用，以使各功能能够重复实现，直至用户退出系统为止。
3.流程图
（1）主函数
（2）界面函数
（3）先来先服务算法（FCFS）
（4）最短寻道时间优先算法（SSTF）
（5）电梯调度算法（SCAN）
（6）循环扫描算法（CSCAN）
四、源代码
#include//导入库函数
#include
#include
#include
#definemaxsize100//最大的磁道号
#definemax3200//最大块号
intmenu（）//菜单界面
{
system（"cls"）;//清屏函数
intx;
cout<cout<cout<"<cout<cout<cout<cout<cout<cout<<"请输入您想选择的操作:
（1-5）"<cin>>x;
returnx;
}
voidFCFS（）//FCFS算法
{
system（"cls"）;
charc;
intsum=0,j,i,m=0;
intavg;
inta[max]={0},array[maxsize]={0};
cout<<"请输入线性块号,以-1结束:
"<for（;;m++）
{
cin>>a[m];
array[m]=a[m]/32;//将线性块号转换为磁道号
if（a[m]==-1）break;
}
cout<<"磁道号为:
"<for（i=0;i{printf（"%d",array[i]）;
}
printf（"\nFCFS调度结果:
"）;
for（i=0;i{
printf（"%d",array[i]）;
}
for（i=0,j=1;j{
sum+=abs（array[j]-array[i]）;//累计总的移动距离
}
avg=sum/（m-1）;//计算平均寻道长度
printf（"\n移动的总道数：
%d\n",sum）;
printf（"平均寻道长度：
%d\n",avg）;
cout<<"输入任意键返回上一菜单"<cin>>c;
}
voidSSTF（）//SSTF算法
{
system（"cls"）;
charc;
inttemp;
intk=1;
intnow,l,r;
inti,j,sum=0,m=0;
intavg;
inta[max]={0},array[maxsize]={0};
cout<<"请输入线性块号,以-1结束:
"<for（;;m++）
{
cin>>a[m];
array[m]=a[m]/32;//将线性块号转换为磁道号
if（a[m]==-1）break;
}
cout<<"磁道号为:
"<for（i=0;i{printf（"%d",array[i]）;
}
for（i=0;i{
for（j=i+1;j{
if（array[i]>array[j]）//两磁道号之间比较
{
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
}
printf（"\n排序后的磁道号为:
"）;
for（i=0;i{
printf（"%d",array[i]）;
}
printf（"\n请输入当前的磁道号：
"）;
scanf（"%d",&now）;
printf（"\nSSTF调度结果:
"）;
if（array[m-1]<=now）//判断整个数组里的数是否都小于当前磁道号
{
for（i=m-1;i>=0;i--）//将数组磁道号从大到小输出
printf（"%d",array[i]）;
sum=now-array[0];//计算移动距离
}
elseif（array[0]>=now）//判断整个数组里的数是否都大于当前磁道号
{
for（i=0;iprintf（"%d",array[i]）;
sum=array[m-1]-now;//计算移动距离
}
else
{
while（array[k]{
k++;
}
l=k-1;
r=k;
//确定当前磁道在已排的序列中的位置
while（（l>=0）&&（r{
if（（now-array[l]）<=（array[r]-now））//判断最短距离
{
printf（"%d",array[l]）;
sum+=now-array[l];//计算移动距离
now=array[l];
l=l-1;
}
else
{
printf（"%d",array[r]）;
sum+=array[r]-now;//计算移动距离
now=array[r];
r=r+1;
}
}
if（l=-1）
{
for（j=r;j{
printf（"%d",array[j]）;
}
sum+=array[m-1]-array[0];//计算移动距离
}
else
{
for（j=l;j>=0;j--）
{
printf（"%d",array[j]）;
}
sum+=array[m-1]-array[0];//计算移动距离
}
}
avg=sum/m;
printf（"\n移动的总道数：
%d\n",sum）;
printf（"平均寻道长度：
%d\n",avg）;
cout<<"输入任意键返回上一菜单"<cin>>c;
}
voidSCAN（）//SCAN算法
{//先要给出当前磁道号和移动臂的移动方向
system（"cls"）;
charc;
inttemp;
intk=1;
intnow,l,r,d;
inti,j,sum=0,m=0;
intavg;
inta[max]={0},array[maxsize]={0};
cout<<"请输入线性块号,以-1结束:
"<for（;;m++）
{
cin>>a[m];
array[m]=a[m]/32;//将线性块号转换为磁道号
if（a[m]==-1）break;
}
cout<<"磁道号为:
"<for（i=0;i{printf（"%d",array[i]）;
}
for（i=0;i{
for（j=i+1;j{
if（array[i]>array[j]）//对磁道号进行从小到大排列
{
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
}
printf（"\n排序后的磁道号为:
"）;
for（i=0;i{
printf（"%d",array[i]）;//输出排序后的磁道号数组
}
printf（"\n请输入当前的磁道号：
"）;
scanf（"%d",&now）;
if（array[m-1]<=now）//判断整个数组里的数是否都小于当前磁道号
{
printf（"\nSCAN调度结果:
"）;
for（i=m-1;i>=0;i--）
{
printf（"%d",array[i]）;//将数组磁道号从大到小输出
}
sum=now-array[0];//计算移动距离
}
elseif（array[0]>=now）//判断整个数组里的数是否都大于当前磁道号
{
printf（"\nSCAN调度结果:
"）;
for（i=0;i{
printf（"%d",array[i]）;//将磁道号从小到大输出
}
sum=array[m-1]-now;//计算移动距离
}
else
{
while（array[k]{
k++;
}
l=k-1;
r=k;
printf（"\n请输入当前移动臂的移动的方向（1磁道号增加方向，0磁道号减小方向）:
"）;
scanf（"%d",&d）;
printf（"\nSCAN调度结果:
"）;
if（d==0）
{
for（j=l;j>=0;j--）
{
printf（"%d",array[j]）;
}
for（j=r;j{
printf（"%d",array[j]）;
}
sum=now-2*array[0]+array[m-1];//计算移动距离
}//磁道号减小方向
else
{
for（j=r;j{
printf（"%d",array[j]）;
}
for（j=l;j>=0;j--）
{
printf（"%d",array[j]）;
}
sum=-now-array[0]+2*array[m-1];//计算移动距离
}//磁道号增加方向
}
avg=sum/m;
printf（"\n移动的总道数：
%d\n",sum）;
printf（"平均寻道长度：
%d\n",avg）;
cout<<"输入任意键返回上一菜单"<cin>>c;
}
voidCSCAN（）//CSCAN算法
{
system（"cls"）;
charc;
inttemp;
intk=1;
intnow,l,r,d;
inti,j,sum=0,m=0;
intavg;
intarray[maxsize]={0},a[max]={0};
cout<<"请输入线性块号,以-1结束:
"<for（;;m++）
{
cin>>a[m];
array[m]=a[m]/32;//将线性块号转换为磁道号
if（a[m]==-1）break;
}
cout<<"磁道号为:
"<for（i=0;i{printf（"%d",array[i]）;
}
for（i=0;i{
for（j=i+1;j{
if（array[i]>array[j]）//对磁道号进行从小到大排列
{
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
}
printf（"\n排序后的磁道号为:
"）;
for（i=0;i{
printf（"%d",array[i]）;//输出排序后的磁道号数组
}
printf（"\n请输入当前的磁道号：
"）;
scanf（"%d",&now）;
if（array[m-1]<=now）//判断整个数组里的数是否都小于当前磁道号
{
printf（"\nCSCAN调度结果:
"）;
for（i=0;i{
printf（"%d",array[i]）;//将磁道号从小到大输出
}
sum=now-array[0]+array[m-1];//计算移动距离
}
elseif（array[0]>=now）//判断整个数组里的数是否都大于当前磁道号
{
printf（"\nCSCAN调度结果:
"）;
for（i=0;i{
printf（"%d",array[i]）;//将磁道号从小到大输出
}
sum=array[m-1]-now;//计算移动距离
}
else
{
while（array[k]{
k++;
}
l=k-1;
r=k;
printf（"\n请输入当前移动臂的移动的方向（1磁道号增加方向，0磁道号减小方向）:
"）;
scanf（"%d",&d）;
printf（"\nCSCAN调度结果:
"）;
if（d==0）
{
for（j=l;j>=0;j--）
{
printf（"%d",array[j]）;
}
for（j=m-1;j>=r;j--）
{
printf（"%d",array[j]）;
}
sum=2*（array[m-1]-array[0]）-array[r]+now;//计算移动距离
}//磁道号减小方向
else
{
for（j=r;j{
printf（"%d",array[j]）;
}
for（j=0;j{
printf（"%d",array[j]）;
}
sum=2*（array[m-1]-array[0]）+array[r-1]-now;//计算移动距离
}
}//磁道号增加方向
avg=sum/m;
printf（"\n移动的总道数：
%d\n",sum）;
printf（"平均寻道长度：
%d\n",avg）;
cout<<"输入任意键返回上一菜单"<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<"<cout<exit（0）;
}
default:
{
cout<<"输入菜单号有误，请重新输入，按回车键结束!
"<getchar（）;
getchar（）;
}
}
}
}
五、运行与测试
1.菜单界面
2.FCFS算法
3.SSTF算法
4.SCAN算法
（1）沿磁道号增加方向
（2）沿磁道号减小方向
5.CSCAN算法
（1）沿磁道号增加方向
（2）沿磁道号减小方向
7.退出界面
六、心得体会
本次课程设计，我做的是磁盘驱动调度算法模拟。
在平时上课的时候，我
已经学过了磁盘驱动调度算法的理论，因此课程设计时，只需要将其变成可运行的实际代码即可。
我选择了C++语言，来编写这次的程序。
由于C++是上个学期学的，所以有些遗忘，在实际的编写过程中，我又重新去翻阅了C++的资料，然后将算法变成代码。
由于这次的算法比较简单，除了最短寻道时间优先这个算法稍微复杂些，因为它每次都需要寻找距离当前磁道距离最短的磁道，所以每次都需要去判断距离当前磁道最短的距离，略微花了我一些时间。
通过这次课程设计，我不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。
我明白了复习的重要性，所谓“温故而知新”，不能学了后面的东西就将前面的忘了，应该有空的时候就多看看以前学过的知识。
同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，自身知识的很多漏洞，看到了自己的实践经验还是比较缺乏，理论联系实际的能力还急需提高。
相信这次课程设计的收获会让我在以后学习生活中受益匪浅！
升级会员 