操作系统专业课程设计磁盘调度算法.doc

前 言
摘要：本课程设计目标是经过设计一个磁盘调度模拟系统，从而使磁盘调度算法愈加形象化，使磁盘调度特点更简单明了，这里关键实现磁盘调度四种算法，分别是：1、先来先服务算法（FCFS） 2、最短寻道时间优先算法（SSTF） 3、扫描算法（SCAN） 4、循环扫描算法（CSCAN）。 开启磁盘实施输入输出操作时，要把移动臂移动到指定柱面，再等候指定扇区旋转到磁头位置下，然后让指定磁头进行读写，完成信息传送；所以，实施一次输入输出所花时间有： 寻求时间——磁头在移动臂带动下移动到指定柱面所花时间。 延迟时间——指定扇区旋转到磁头下所需时间。 传送时间——由磁头进程读写完成信息传送时间，寻道时间——指计算机在发出一个寻址命令，到对应目标数据被找到所需时间；其中传送信息所花时间，是在硬件设计时固定，而寻求时间和延迟时间是和信息在磁盘上位置相关；然后设计出磁盘调度设计方法，包含算法思绪、步骤，和要用到关键数据结构、函数模块及其之间调用关系等，并给出具体算法设计，对编码进行了测试和分析。 最终进行个人总结和设计体会。

关键词：最短寻道时间优先算法、扫描算法、总寻道长度.

目 录
前 言 2
2. 课程设计任务及要求 4
2.1 设计任务 4
2.2 设计要求 4
3. 算法及数据结构 5
3.1算法总体思想（步骤） 5
3.2 实现过程中用到数据结构 6
3.3 实现过程中用到系统调用 11
4. 程序设计和实现 11
4.1 最短寻道时间优先算法（SSTF）模块 11
4.1.1程序步骤图 11
4.1.2 程序说明 13
4.1.3 程序关键代码 13
4.2扫描算法（SCAN）模块 14
4.2.1 程序步骤图 14
4.2.2 程序说明 16
4.2.3 程序关键代码 16
4.3 试验结果 17
5. 结论 26
6. 参考文件 26
7. 收获、体会和提议 27
2. 课程设计任务及要求
2.1 设计任务
1.熟悉并掌握磁盘调度算法管理系统设计方法，加强对所学多种调度算法及对应算法特点了解。
2.掌握磁盘调度基础概念，深刻体会各个算法优缺点，和算法间相同点。
2.2 设计要求
1)定义和算法相关数据结构，如PCB、队列等；
2） 实现2种不一样调度算法（可使用伪代码或步骤图进行分析）；
3） 算法实施结束时，应给出总寻道长度；
4） 磁道访问序列随机生成，且要满足一定数量要求（不少于100个）；
5）系统实现必需提供一定交互性，所需测试数据应该以文件形式提供或由用户在测试过程中给出，不可将测试数据“写死”在系统实现代码中；
6）必需给出足够注释，注释量不得少于代码量二分之一；
7）对于系统中所使用到系统调用（API函数），必需给出函数定义原型、使用方法，参数较为复杂，还应该给出参数具体描述；

3. 算法及数据结构
3.1算法总体思想（步骤）

开始
输入磁道个数

生成随机磁道号
用户输入所选择算法进行磁盘调度
输入数字为1-2？
输出排序后磁盘序列
用户输入目前磁道号
显示磁盘调度次序
输入为3？
退出程序
结束
总步骤图

Y N

Y N

3.2 实现过程中用到数据结构
1.最短寻道时间优先（SSTF）

（从100号磁道开始）
被访问下一个磁道号
移动距离（磁道数）
55
45
58
3
39
19
18
21
90
72
160
70
150
10
38
112
184
146
平均寻道长度：55.3
图a SSTF调度算法示例图
ciidao[]={55,58,39,18,90,160,150,38,184}（可随机生成多个）

用户输入目前磁道号now，比较目前磁道到每个磁道移动距离，选择最短距离磁道进行移动。now指向目前磁道号，计算寻道长度sum。
用冒泡法对磁道数组进行排序

返回内侧（外侧）扫描
将目前磁道号和剩下没有访问磁道号进行比较，反复上述操作。并计算平均寻道长度ave。

图b SSTF算法步骤示例图

原磁道号随机组成数组：cidao[]={55,58,39,18,90,160,150,38,184}；
排序后数组={18,38,39,5,58,90,150,160,184}；
输入目前磁道号：now=100；

38
39 39
55 55 55
58 58 58 58
90 90 90 90 90
now值:100 90 58 55 39
184
160 160
150 150 150
18 18 18 18
38 38 38 38
39 39 39 39
55 55 55 55
58 58 58 58
90 90 90 90
now值：18 150 160 184
图c SSTF算法队列示意图(按磁道访问次序)

2.扫描（SCAN）算法
（从100号磁道开始，向磁道号增加方向访问）
被访问下一个磁道号
移动距离（磁道数）
150
50
160
10
184
24
90
94
58
32
55
3
39
16
38
1
18
20
平均寻道长度：27.8
图d SCAN算法示例图
原磁道号随机组成数组：cidao[]={55,58,39,18,90,160,150,38,184}；
排序后数组={18,38,39,5,58,90,150,160,184}；
输入目前磁道号：now=100；
选择磁道移动方向；
以磁道号增加方向移动为例：

55
58 58
90 90 90
184 184 184 184
160 160 160 160 160
150 150 150 150 150 150
now值：100 150 160 184 90 58
18
38 38
39 39 39
55 55 55
58 58 58
90 90 90
184 184 184
160 160 160
150 150 150
now值:55 39 38
图e SCAN算法队列示意图（按磁道访问次序）

3.3 实现过程中用到系统调用

系统模块调用关系图
磁盘调度算法模拟系统
最短寻道时间优先
扫描算法
退出

4. 程序设计和实现
4.1 最短寻道时间优先算法（SSTF）模块
4.1.1程序步骤图

输入磁道号串
用冒泡法将磁道号从大到小排序
判定now大小
调用SSTF()函数
输入目前磁道号now
开始
结束
优先服务离now最近 磁道移动方向，再掉头服务
计算总寻道长度，并输出移动平均寻道长度
直接从大到小给磁道服务
直接从小到大给磁道服务
找到离now寻道时间最短磁道

now<=cidao[0] cidao[0]<now<cidao[m-1] now>=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;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;
}
}
if(array[m-1]<=now) /*若目前磁道号大于请求序列中最大者，则直接由外向内依次给各请求服务*/
{
for(i=m-1;i>=0;i--)
cout<<array[i]<<" ";
sum=now-array[0];
}
else
if(array[0]>=now) /*若目前磁道号小于请求序列中最小者，则直接由内向外依次给各请求服务*/
while((l>=0)&&(r<m)) /*目前磁道在请求序列范围内*/
{
if((now-array[l])<=(array[r]-now)) /*选择和目前磁道最近请求给服务*/
{
cout<<array[l]<<" ";
sum+=now-array[l];
now=array[l];
l=l-1;
}

4.2扫描算法（SCAN）模块
4.2.1 程序步骤图

开始
输入磁道号串
调用SCAN（）函数
调用冒泡排序法进行排序
输入目前磁道号now
从磁道最外端开始向内扫描
计算总寻道长度，并输出平均寻道长度
从磁道最内端开始向外扫描

向内扫描
向外扫描

选择磁道扫描方向

结束

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<<array[j]<<" "; /*输出向内扫描序列*/
}
for(j=r;j<m;j++) /*磁头移动到最小号，则改变方向向外扫描未扫描磁道*/
{
cout<<array[j]<<" "; /*输出向外扫描序列*/
}
sum=now-2*array[0]+array[m-1];
}
else /*选择移动臂方向向外，则先向外扫描*/
{
for(j=r;j<m;j++)
{
cout<<array[j]<<" "; /*输出向外扫描序列*/

}
for(j=l;j>=0;j--) /*磁头移动到最大号，则改变方向向内扫描未扫描磁道*/
{
cout<<array[j]<<" ";
}
sum=-now-array[0]+2*array[m-1];
}
ave=(float)(sum)/(float)(m);
4.3 试验结果
运行界面截图及对应代码
1. 主界面
void display(){
cout<<"\n\n\n\n Operating Systems Curriculum Design\n";
cout<<"\n ╔———————————————————————————————╗";
cout<<"\n │ │";
cout<<"\n │ 名称: 磁盘调度 │";
cout<<"\n │ │";
cout<<"\n │ 工具: Visual Studio │";
cout<<"\n │ │";
cout<<"\n │ 班级:1205 │";
cout<<"\n │ │";
cout<<"\n │ 作者:施静 │";
cout<<"\n │ │";
cout<<"\n │ 学号： │";
cout<<"\n │ │";
cout<<"\n ╚———————————————————————————————╝\n";
system("pause");
system("cls");

2. 序言 提醒用户此程序实现算法
cout<<"【载入完成】"<<endl<<endl;
cout<<" 序言"<<endl<<endl;
cout<<" 欢迎使用『磁盘调度算法系统』，本程序实现了常见磁盘调度算法以下所表示：\n\n";
cout<<" ①最短寻道时间优先（SSTF）：最短寻道时间优先算法要求访问磁盘和目前磁头所在\n";
cout<<" 磁盘距离最近，以使每次寻道时间最短。\n\n";
cout<<" ②扫描算法(SCAN)电梯调度：扫描算法不仅考虑到欲访问磁道和目前磁道距离\n";
cout<<" 更优先考虑是磁头目前移动方向。\n\n";
system("pause");
system("cls");//清屏

3. 用户选择所使用算法（先随机生成101个磁道号）
void showMenu(int cidao[],int n){
int choice;
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<<endl;
while(true){
cout<<"现在您选择算法号是（1-3）：";
cin>>choice;
switch(choice){ /*case 1:
FCFS(a,n);
break;*/
case 1:
SSTF(cidao,n);
break;
case 2:
SCAN(cidao,n);
break;
case 3:
cout<<"\n要退出系统了欢迎使用本系统\n";
exit(0);
}

}
}
}

4. 最短寻道时间优先算法
/**********************最短寻道时间优先调度算法********************/
void SSTF(int cidao[],int m)
{
system("cls");
int k=1;
int now,l,r;
int i,j,sum=0;
int a;
char str[100];
float ave;
cidao=bubble(cidao,m); //调用冒泡排序算法排序
cout<<"请输入目前磁道号：";
C: cin>>str; //对输入数据进行有效性判定
a=decide(str);
if(a==0)
{
cout<<"输入数据类型错误,请重新输入！"<<endl;
goto C;
}
else
now=trans(str,a); //输入目前磁道号
if(cidao[m-1]<=now) //若目前磁道号大于请求序列中最大者，则直接由外向内依次给各请求服务
{
cout<<"磁盘扫描序列为：";
for(i=m-1;i>=0;i--)
cout<<cidao[i]<<" ";
sum=now-cidao[0];
}
if(cidao[0]>=now) //若目前磁道号小于请求序列中最小者，则直接由内向外依次给各请求服务
{
cout<<"磁盘扫描序列为：";
for(i=0;i<m;i++)
cout<<cidao[i]<<" ";
sum=cidao[m-1]-now;
}
if(now>cidao[0]&&now<cidao[m-1]) //若目前磁道号大于请求序列中最小者且小于最大者
{
cout<<"磁盘扫描序列为：";
while(cidao[k]<now) //确定目前磁道在已排序列中位置，后面算法全部用到了，能够直接复制后少许修改，节省时间。
{
k++;
}
l=k-1;
r=k;
while((l>=0)&&(r<m)) //目前磁道在请求序列范围内
{
if((now-cidao[l])<=(cidao[r]-now)) //选择和目前磁道最近请求给服务
{
cout<<cidao[l]<<" ";
sum+=now-cidao[l];
now=cidao[l];
l=l-1;
}
else
{
cout<<cidao[r]<<" ";
sum+=cidao[r]-now;
now=cidao[r];
r=r+1;
}
}
if(l==-1) //磁头移动到序列最小号，返回外侧扫描仍未扫描磁道
{
for(j=r;j<m;j++)
{
cout<<cidao[j]<<" ";
}
sum+=cidao[m-1]-cidao[0];
}
else //磁头移动到序列最大号，返回内侧扫描仍未扫描磁道
{
for(j=l;j>=0;j--)
{
cout<<cidao[j]<<" ";
}
sum+=cidao[m-1]-cidao[0];
}
}
ave=(float)(sum)/(float)(m);//求平均寻道长度
cout<<endl;
cout<<"总寻道长度： "<<sum<<endl;
cout<<"平均寻道长度： "<<ave<<endl;
cout<<"请按任意键返回系统菜单"<<endl;
getch();
showMenu(cidao,m); //回到主界面

}

最短寻道时间优先（SSTF）算法实现界面

（2） 扫描（SCAN）算法
/*****************************扫描调度算法*******************************/
void SCAN(int cidao[],int n)//先要给出目前磁道号和移动臂移动方向
{
int temp;
int i,j;
int now;
int sum;
for(i=0;i<n;i++) //给磁道号排序
for(j=i+1;j<n;j++){
if(cidao[i]>cidao[j]){
temp=cidao[i];
cidao[i]=cidao[j];
cidao[j]=temp;
}
}
cout<<"\n按非递减次序排列好磁道: \n";
for(i=0;i<n;i++) //输出排好序磁道号
cout<<cidao[i]<<" ";
cout<<endl;
cout<<"\n请输入目前磁道号: ";
cin>>now; //用户自定义目前磁道号
if(cidao[n-1]<=now)
{
for(i=n-1;i>=0;i--)
cout<<cidao[i]<<" ";
sum=now-cidao[0];
}
else //cidao[n-1]>now
if(cidao[0]>=now){
for(i=0;i<n;i++)
cout<<cidao[i]<<" ";
sum=cidao[n-1]-now;
}
else //cidao[0]<now && cidao[n-1]>now
{
int pointer;
int location=1;
int left,right;
while(cidao[location]<now)
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<<cidao[j]<<" ";
for(j=right;j<n;j++)
cout<<cidao[j]<<" ";
sum=now+cidao[n-1]-2*cidao[0];
cout<<endl;
}
if(pointer==1)//磁头向右移动到最大号，再改变方向向内扫描未扫描磁道
{
for(j=right;j<n;j++)
cout<<cidao[j]<<" ";
for(j=left;j>=0;j--)
cout<<cidao[j]<<" ";
sum=2*cidao[n-1]-now-cidao[0];//求总寻道长度
cout<<endl;
}
}
else{