操作系统磁盘调度算法优秀课程设计优质报告及代码.docx

淮阴工学院
操作系统课程设计汇报
选题名称: 磁盘调度算法模拟实现
系（院）: 经济管理学院
专 业: 信息管理和信息系统
班 级:
姓 名: 学 号:
指导老师:
年学期: ~ 年 第 1 学期
年 12 月 21 日

设计任务书
课题
名称
磁盘调度算法模拟实现
设计
目标
1. 调研并熟悉磁盘调度基础概念、排序算法和工作规程；
2. 学习Visual C++中图形化界面设计技术；
3. 经过实际编程加深对基础知识了解，提升实践能力；
4. 学习开发资料搜集和整理，学会撰写课程设计汇报。
试验
环境
1. 微型电子计算机（PC）；
2. 安装Windows 以上操作系统，Visual C++6.0开发工具。
任务
要求
1. 利用课余时间去图书馆或上网查阅课题相关资料，深入了解课题含义及设计要求，注意材料搜集和整理；
2. 在第15周末之前完成预设计，并请指导老师审查，经过后方可进行下一步工作；
3. 本课题关键实现能用多种排序算法实现对数据排序，排序后显示排序结果。
4. 结束后，立即提交设计汇报（含纸质稿、电子稿），要求格式规范、内容完整、结论正确，正文字数不少于3000字（不含代码）。
工作进度计划
序号
起止日期
工 作 内 容
1
.12.15~.12.16
在预设计基础上，深入查阅资料，完善设计方案，形成书面材料。
2
.12.17~.12.18
设计总体方案，构建、绘制步骤框图，编写代码，上机调试。
3
.12.18~.12.19
测试程序，优化代码，增强功效，撰写设计汇报。
4
.12.20~.12.21
提交软件代码、设计汇报，参与答辩，依据老师反馈意见，修改、完善设计汇报。
指导老师（签章）：
年 月 日

摘要：
磁盘是外设中一个很常见部分，所以，对磁盘数据寻道时间长短能够直接影响机器整体运行速度快慢。本设计为一个模拟磁盘调度算法磁盘调度模拟系统，能够模拟先来先服务（FCFS）算法、最短寻道时间（SSTF）算法、电梯（SCAN）算法、环形扫描（C_SCAN）算法及N_SCAN算法五个磁盘调度算法，输入为一组作业磁道请求，输出为按选择算法实施时磁头移动轨迹。其中，先来先服务（FCFS）算法、最短寻道时间（SSTF）算法、电梯（SCAN）算法为基础算法，环形扫描（C_SCAN）算法及N_SCAN算法为扩展算法。

关键字：磁盘调度；模拟；算法；选择；实施；
目录
1 磁盘调度算法基础概念 1
2 关键算法分析 2
2.1 先来先服务算法（FCFS） 2
2.2 最短寻道时间优先算法（SSTF） 2
2.3 扫描算法（SCAN） 2
3 各算法步骤图 3
4 调试分析及测试结果 5
4.1 运行结果 5
4.2 程序代码 7
总 结 12
致 谢 13
参考文件 14

1 磁盘调度算法基础概念
设备动态分配算法和进程调度相同，也是基于一定分配策略。常见分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是因为磁盘类旋转设备使用不妥造成。操作系统中，对磁盘访问要求来自多方面，常常需要排队。这时，对众多访问要求按一定次序响应，会直接影响磁盘工作效率，进而影响系统性能。访问磁盘时间因子由3部分组成，它们是查找（查找磁道）时间、等候（旋转等候扇区）时间和数据传输时间，其中查找时间是决定原因。所以，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等候策略。
平均寻道长度（L）为全部磁道所需移动距离之和除以总所需访问磁道数（N），即：L=（M1+M2+……+Mi+……+MN）/N
其中Mi为所需访问磁道号所需移动磁道数。
开启磁盘实施输入输出操作时，要把移动臂移动到指定柱面，再等候指定扇区旋转到磁头位置下，然后让指定磁头进行读写，完成信息传送。所以，实施一次输入输出所花时间有：
寻求时间——磁头在移动臂带动下移动到指定柱面所花时间。
延迟时间——指定扇区旋转到磁头下所需时间。
传送时间——由磁头进程读写完成信息传送时间。
其中传送信息所花时间，是在硬件设计就固定。而寻求时间和延迟时间是和信息在磁盘上位置相关。为了降低移动臂进行移动花费时间，每个文件信息不是按盘面上磁道次序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上各磁道被放满信息后，再放到下一个柱面上。所以各磁盘编号按柱面次序，每个柱面按磁道次序，每个磁道又按扇区次序进行排序。
磁盘是可供多个进程共享设备，当有多个进程全部要求访问磁盘是，应采取一个最好调度算法，以使多种进程对磁盘平均访问时间最小。因为在访问磁盘时间中，关键是寻道时间，所以，磁盘调度目标，是使磁盘平均寻道时间最少。现在常见磁盘帝调度算法有：先来先服务、最短寻道时间优先及扫描等算法。
2 关键算法分析
2.1 先来先服务算法（FCFS）
先来先服务（FCFS）调度:按先来后到次序服务，未作优化。
最简单移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问物理位置，而只是考虑访问者提出访问请求前后次序。比如，假如现在读写磁头正在50号柱面上实施输出操作，而等候访问者依次要访问柱面为130、199、32、159、15、148、61、99，那么，当50号柱面上操作结束后，移动臂将按请求前后次序先移到130号柱面，最终抵达99号柱面。
采取先来先服务算法决定等候访问者实施输入输出操作次序时，移动臂往返地移动。先来先服务算法花费寻求时间较长，所以实施输入输出操作总时间也很长。
2.2 最短寻道时间优先算法（SSTF）
最短寻求时间优先调度算法总是从等候访问者中挑选寻求时间最短那个请求先实施，而不管访问者到来前后次序。现在仍利用同一个例子来讨论，现在当50号柱面操作结束后，应该先处理61号柱面请求，然后抵达32号柱面实施操作，随即处理15号柱面请求，后继操作次序应该是99、130、148、159、199。
采取最短寻求时间优先算法决定等候访问者实施操作次序时，读写磁头总共移动了200多个柱面距离，和先来先服务、算法比较，大幅度地降低了寻求时间，所以缩短了为各访问者请求服务平均时间，也就提升了系统效率。
但最短查找时间优先（SSTF）调度，FCFS会引发读写头在盘面上大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）请求作为下一次服务对象。SSTF查找模式有高度局部化倾向，会推迟部分请求服务，甚至引发无限拖延（又称饥饿）。
2.3 扫描算法（SCAN）
SCAN 算法又称电梯调度算法。SCAN算法是磁头前进方向上最短查找时间优先算法，它排除了磁头在盘面局部位置上往复移动，SCAN算法在很大程度上消除了SSTF算法不公平性，但仍有利于对中间磁道请求。
“电梯调度”算法是从移动臂目前位置开始沿着臂移动方向去选择离目前移动臂最近那个柱访问者，假如沿臂移动方向无请求访问时，就改变臂移动方向再选择。这好比乘电梯，假如电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。她们要求是：陈生在2层等候去10层；伍生在5层等候去底层；张生在8层等候15层。因为电梯现在运动方向是向上，所以电梯形成是先把乘客张生从8层带到15层，然后电梯换成下行方向，把乘客伍生从5层带到底层，电梯最终再调换方向，把乘客陈生从2层送到10层。
不过，“电梯调度”算法在实现时，不仅要记住读写磁头目前位置，还必需记住移动臂目前前进方向。
3 各算法步骤图
1. 先来先服务算法模块

图3.1 先来先服务算法步骤图
2. 最短寻道时间优先算法模块
开始

结束

图3.2 最短寻道时间优先算法步骤图
3. 扫描算法模块
开始

输出磁盘
调度序列

结束

图3.3 扫描算法步骤图
4 调试分析及测试结果
4.1 运行结果
1. 开始界面

图4.1 开始界面
2. 运行先来先服务（FCFS）算法调度后程序结果以下：

图4.2 FCFS运行结果
3. 运行最短寻道时间优先（SSTF）算法调度程序结果以下：

图4.3 SSTF运行结果
4. 运行扫描（SCAN）算法调度程序结果以下：

图4.4 SCAN向磁道号增加方向移动

图4.5 SCAN向磁道号减小放向移动
4.2 程序代码
1. 先来先服务算法
void FCFS(int array[],int m)// 先来先服务算法
{
int j,i,now;
float sum = 0,avg;
cout<<"输入目前磁道号：";//输入目前磁道号
cin>>now;
sum=abs(now-array[0]);
cout<<"先来先服务算法(FCFS)调度后序列为"<<array[0]<<" ";//输出磁盘调度序列
for(i=0,j=1;j<m;i++,j++)
{
sum=sum+abs(array[j]-array[i]);
cout<<array[j]<<" "; //输出磁盘调度序列
}
avg=sum/(m);
cout<<endl<<"平均寻道长度："<<avg<<endl;//输出平均寻道长度
}
2. 最短寻道时间优先算法
void SSTF(int array[],int m)// 最短寻道时间优先算法
{
int temp;
int k=1;
int now,l,r;
int i,j;
float sum=0,avg=0;
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;
}
}
cout<<"请输入目前磁道号："; //输入目前磁道号
cin>>now;
cout<<"最短寻道时间优先算法(SSTF)调度后序列为";//输出磁盘调度序列
if(array[m-1]<=now) //若被访问下一最大磁道号小于目前磁道号
{
for(i=m-1;i>=0;i--)
{ cout<<array[i]<<" ";//输出磁盘调度序列
sum=now-array[i];
now=array[i];
}
}
else
{
if(array[0]>=now) //若被访问下一最小磁道号大于目前磁道号
{
for(i=0;i<m;i++)
{ cout<<array[i]<<" ";//输出磁盘调度序列
sum=array[i]-now;
now=array[i];
}
}
else //目前磁道号值在若全部被访问下磁道号之间
{
while(array[k]<now) //确定目前磁道在已排序列中位置
{ k++; }
l=k-1;
r=k;
if((now-array[l])<=(array[r]-now))
{
while(l>=0) //先向磁道号减小方向访问
{
cout<<array[l]<<" "; //输出磁盘调度序列
sum=sum+now-array[l];
now=array[l];
l=l-1;
}
now=array[0];
for(j=r;j<m;j++) //再向磁道号增加方向访问
{ cout<<array[j]<<" "; //输出磁盘调度序列
sum+=array[j]-now;
now=array[j];
}
}
else //先向磁道号增加方向访问
{
while(r<m)
{
cout<<array[r]<<" ";//输出磁盘调度序列
sum+=array[r]-now;
now=array[r];
r=r+1;
}
now=array[m-1];
for(j=l;j>=0;j--) //再向磁道号减小方向访问
{ cout<<array[j]<<" "; //输出磁盘调度序列
sum+=now-array[j];
now=array[j];
}
}
}
}
avg=sum/(m);
cout<<endl<<"平均寻道长度："<<avg<<endl;//输出平均寻道长度
}
3. 扫描算法
void SCAN(int array[],int m) //扫描算法
{
int temp;
int k=1;
int now,d,l,r;
int i,j;
float sum=0,avg=0;
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;
}
}
cout<<"请输入目前磁道号：";//输入目前磁道号
cin>>now;
cout<<"请输入目前移动臂移动方向(1 表示向磁道号增加方向,0 表示向磁道号减小方向): ";
cin>>d; //先要给出目前磁道号和移动臂移动方向
cout<<"扫描算法(SCAN)调度后序列为";
if(array[m-1]<=now) //若被访问下一最大磁道号小于目前磁道号
{
for(i=m-1;i>=0;i--)
{ cout<<array[i]<<" "; //输出磁盘调度序列
sum=now-array[i];
now=array[i];
}
}
else
{
if(array[0]>=now) //若被访问下一最小磁道号大于目前磁道号
{
for(i=0;i<m;i++)
{ cout<<array[i]<<" "; //输出磁盘调度序列
sum=array[i]-now;
now=array[i];
}
}
else //目前磁道号值在若全部被访问下磁道号之间
{
while(array[k]<now) //确定目前磁道在已排序列中位置
{ k++; }
l=k-1;
r=k;
switch(d)
{
case 0: //先向磁道号减小方向访问
{
while(l>=0)
{
cout<<array[l]<<" "; //输出磁盘调度序列
sum=sum+now-array[l];
now=array[l];
l=l-1;
}
now=array[0];
for(j=r;j<m;j++)
{ cout<<array[j]<<" "; //输出磁盘调度序列
sum+=array[j]-now;
now=array[j];
} break;
}
case 1: //先向磁道号增加方向访问
{
while(r<m)
{
cout<<array[r]<<" ";//输出磁盘调度序列
sum+=array[r]-now;
now=array[r];
r=r+1;
}
now=array[m-1];
for(j=l;j>=0;j--)
{ cout<<array[j]<<" "; //输出磁盘调度序列
sum+=now-array[j];
now=array[j];
}break;
}
default: cout<<"输入有误"<<endl;
}
}
}
avg=sum/(m);
cout<<endl<<"平均寻道长度："<<avg<<endl;//输出平均寻道长度
}

总 结
经过这次课程设计使我认识到要将操作系统这门计算机专业课学好不仅仅是要把书上基础知识学好而且还要不停进行实践，将所学跟实践操作结合起来才能愈加好地巩固所学，才能提升自己实践能力。经过这次设计使我认识到只停留在表面了解问题是极难使问题得到很好处理，实践能力和理论知识一样关键。能够说此课程设计理论难度并不大，多种流图设计尤其是算法过程图设计很轻易忽略操作性细节，在实际调试中带来很大麻烦，需要尤其注意，不过若要深入发掘其中东西，而且实际去编程实现，就碰到了相当大难度。因为和之包含很多方面并没有学过，需要自己去自学和实践检验。经过模拟磁盘调度及进程排队算法来加深对操作系统中各个磁臂调度算法概念了解模拟磁盘调度算法，实现多种不一样调度算法过程，并计算各算法平均寻道长度，方便于我们判定多种算法优劣和多种算法使用场所。

致 谢
这次课程设计让我受益匪浅，我不仅加深了对操作系统了解，深入熟悉了C语言编程和Microsoft Visual C++ 6.0使用，愈加了解了很多之前在书本中和课程学习中并不了解和知道知识，扩展了视野，丰富了体验。
很感谢在课程设计中殷路和高尚兵两位老师不厌其烦讲解指导，同时我还要感谢同学们热心帮助。

参考文件
[1]. 汤子瀛，哲凤屏，汤小丹. 《计算机操作系统》.西安电子科技大学出版社, ;
[2]. 周敏，杨武，杨承玉. 《计算机操作系统原理试验指导基于LINUX（Ver 3.0）》.重庆工学院，;
[3]. 谭浩强编著.《 C语言程序设计（第3版）》.清华大学出版社，;
[4]. 周湘贞，曾宪权.《操作系统原理和实践教程》.清华出版社;
[5]. 陈家骏.《程序设计基础教程》.机械工业出版社.

附录：
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
void FCFS(int array[],int m)// 先来先服务算法
{ int j,i,now;
float sum = 0,avg;
cout<<"输入目前磁道号：";//输入目前磁道号
cin>>now;
sum=abs(now-array[0]);
cout<<"先来先服务算法(FCFS)调度后序列为"<<array[0]<<" ";//输出磁盘调度序列
for(i=0,j=1;j<m;i++,j++)
{
sum=sum+abs(array[j]-array[i]);
cout<<array[j]<<" "; //输出磁盘调度序列
}
avg=sum/(m);
cout<<endl<<"平均寻道长度："<<avg<<endl;//输出平均寻道长度
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void SSTF(int array[],int m)// 最短寻道时间优先算法
{ int temp;
int k=1;
int now,l,r;
int i,j;
float sum=0,avg=0;
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;
}
}
cout<<"请输入目前磁道号："; //输入目前磁道号
cin>>now;
cout<<"最短寻道时间优先算法(SSTF)调度后序列为";//输出磁盘调度序列
if(array[m-1]<=now) //若被访问下一最大磁道号小于目前磁道号
{
for(i=m-1;i>=0;i--)
{ cout<<array[i]<<" ";//输出磁盘调度序列
sum=now-array[i];
now=array[i];
}
}
else
{
if(array[0]>=now) //若被访问下一最小磁道号大于目前磁道号
{
for(i=0;i<m;i++)
{ cout<<array[i]<<" ";//输出磁盘调度序列
sum=array[i]-now;
now=array[i];
}
}
else //目前磁道号值在若全部被访问下磁道号之间
{
while(array[k]<now) //确定目前磁道在已排序列中位置
{ k++; }
l=k-1;
r=k;
if((now-array[l])<=(array[r]-now))
{
while(l>=0) //先向磁道号减小方向访问
{
cout<<array[l]<<" "; //输出磁盘调度序列
sum=sum+now-array[l];
now=array[l];
l=l-1;
}
now=array[0];
for(j=r;j<m;j++) //再向磁道号增加方向访问
{ cout<<array[j]<<" "; //输出磁盘调度序列
sum+=array[j]-now;
now=array[j];
}
}
else //先向磁道号增加方向访问
{
while(r<m)
{
cout<<array[r]<<" ";//输出磁盘调度序列
sum+=array[r]-now;
now=array[r];
r=r+1;
}
now=array[m-1];
for(j=l;j>=0;j--) //再向磁道号减小方向访问
{ cout<<array[j]<<" "; //输出磁盘调度序列
sum+=now-array[j];
now=array[j];
}
}
}
}
avg=sum/(m);
cout<<endl<<"平均寻道长度："<<avg<<endl;//输出平均寻道长度
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void SCAN(int array[],int m) //扫描算法
{ int temp;
int k=1;
int now,d,l,r;
int i,j;
float sum=0,avg=0;
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;
}
}
cout<<"请输入目前磁道号：";//输入目前磁道号
cin>>now;
cout<<"请输入目前移动臂移动方向(1 表示向磁道号增加方向,0 表示向磁道号减小方向): ";
cin>>d; //先要给出目前磁道号和移动臂移动方向
cout<<"扫描算法(SCAN)调度后序列为";
if(array[m-1]<=now) //若被访问下一最大磁道号小于目前磁道号
{
for(i=m-1;i>=0;i--)
{ cout<<array[i]<<" "; //输出磁盘调度序列
sum=now-array[i];
now=array[i];
}
}
else
{
if(array[0]>=now) //若被访问下一最小磁道号大于目前磁道号
{
for(i=0;i<m;i++)
{ cout<<array[i]<<" "; //输出磁盘调度序列
sum=array[i]-now;
now=array[i];
}
}
else //目前磁道号值在若全部被访问下磁道号之间
{
while(array[k]<now) //确定目前磁道在已排序列中位置
{ k++; }
l=k-1;
r=k;
switch(d)
{
case 0: //先向磁道号减小方向访问
{
while(l>=0)
{
cout<<array[l]<<" "; //输出磁盘调度序列
sum=sum+now-array[l];
now=array[l];
l=l-1;
}
now=array[0];
for(j=r;j<m;j++)
{ cout<<array[j]<<" "; //输出磁盘调度序列
sum+=array[j]-now;
now=array[j];
} break;
}
case 1: //先向磁道号增加方向访问
{
while(r<m)
{
cout<<array[r]<<" ";//输出磁盘调度序列
sum+=array[r]-now;
now=array[r];
r=r+1;
}
now=array[m-1];
for(j=l;j>=0;j--)
{ cout<<array[j]<<" "; //输出磁盘调度序列
sum+=now-array[j];
now=array[j];
}break;
}
default: cout<<"输入有误"<<endl;
}
}
}
avg=sum/(m);
cout<<endl<<"平均寻道长度："<<avg<<endl;//输出平均寻道长度
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void main()
{
int i,m,n,flag=1,array[100];
cout<<"输入磁盘调度序列个数:";
cin>>m;
cout<<"分别输入磁盘调度序列:";
for(i=0;i<m;i++)
{ cin>>array[i]; }
do
{
cout<<"\t ┏━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl;
cout<<"\t ┃　　　　　　 磁盘调度算法 　 　 ┃"<<endl;
cout<<"\t ┃----------------------------------------------┃"<<endl;
cout<<"\t ┃　　　　 1. 先来先服务算法(FCFS) ┃"<<endl;
cout<<"\t ┃　　　　 2. 最短寻道时间优先算法(SSTF) ┃"<<endl;
cout<<"\t ┃　　　　 3. 扫描算法(SCAN) ┃"<<endl;
cout<<"\t ┃　　　　 0. 退出系统 ┃"<<endl;
cout<<"\t ┗━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl;
cout<<"选择以上算法：";
cin>>n;
switch(n)
{
case 0: { flag=0; break; } //终止程序
case 1:
{ FCFS(array,m); break; } //先来先服务算法(FCFS)
case 2:
{ SSTF(array,m); break; }//最短寻道时间优先算法(SSTF)
case 3:
{ SCAN(array,m); break; }//最短寻道时间优先算法(SCAN)
default: cout<<"输入有误，请重新输入:"<<endl;
}
}while(flag!=0);
}