专业课程设计磁盘调度算法及代码的实现.doc

专业课程设计磁盘调度算法及代码的实现

课程设计报告

《计算机操作系统》

课程设计题目： 磁盘调度算法

学生姓名：
专 业:
班 级:
学 号:
指导教师：

2014年01月10日
目 录
1.需求分析 …………………………………………………………………………01
2. 总体设计及分类简介 …………………………………………………………01
1）先来先服务（FCFS）算法……………………………………………………01
2）最短寻道时间优先（SSTF）算法……………………………………………01
3）扫描调度（SCAN）算法………………………………………………………01
4）循环扫描（C-SCAN）算法……………………………………………………01
3.课程设计目的 ……………………………………………………………………01
4.课程设计要求……………………………………………………………………02
5.详细设计及算法流程图…………………………………………………………02
1）总流程图………………………………………………………………………02
2）先来先服务（FCFS）算法流程图……………………………………………03
3）最短寻道时间优先（SSTF）算法流程图……………………………………04
4）扫描调度（SCAN）算法流程图………………………………………………05
5）循环扫描（C-SCAN）算法流程图……………………………………………06
6.课程设计具体步骤………………………………………………………………07
1）定义函数部分主要代码………………………………………………………07
2）先来先服务（FCFS）算法部分主要代码……………………………………07
3）最短寻道时间优先（SSTF）算法部分主要代码……………………………07
4）扫描调度（SCAN）算法部分主要代码………………………………………09
5）循环扫描（C-SCAN）算法部分主要代码……………………………………09
7.课程设计结果显示 ………………………………………………………………10
1）先来先服务（FCFS）算法测试结果…………………………………………10
2）最短寻道时间优先（SSTF）算法测试结果…………………………………11
3）扫描调度（SCAN）算法测试结果……………………………………………12
4）循环扫描（C-SCAN）算法测试结果…………………………………………13
8.课程设计总结 ……………………………………………………………………14
9.心得体会 …………………………………………………………………………15
10.参考资料 ………………………………………………………………………15
磁盘调度算法
一.需求分析
编译程序运用磁盘的四种调度算法实现对磁盘的调度，四种算法分别为先来先服务（FCFS）算法，最短寻道时间优先（SSTF）算法，扫描调度（SCAN）算法，循环扫描（C-SCAN）算法。
二．总体设计及分类简介
磁盘调度中常用的有四种算法，功能分别如下：
1.先来先服务（FCFS）算法。即先来的请求先被响应。FCFS策略看起来似乎是相当"公平"的，但是当请求的频率过高的时候FCFS策略的响应时间就会大大延长。FCFS策略为我们建立起一个随机访问机制的模型，但是假如用这个策略反复响应从里到外的请求，那么将会消耗大量的时间。为了尽量降低寻道时间，看来我们需要对等待着的请求进行适当的排序，而不是简单的使用FCFS策略。这个过程就叫做磁盘调度管理。有时候FCFS也被看作是最简单的磁盘调度算法。
2. 最短寻道时间优先（SSTF）算法。要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。
3.扫描调度（SCAN）算法。该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道，既在当前磁道之外，又是距离最近的。这样自里向外的访问，直至再无更外的磁道需要访问时，才将磁道换向自外向里移动。这时，同样也是每次选择这样的进程来调度，也就是要访问的当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现像。
4.循环扫描（C-SCAN）算法。当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该里程就必须等待，为了减少这种延迟，CSCAN算法规定磁头单向移动，而本实验过程中我们所设计的是磁头从里向外移动，而从外向里移动时只须改方向而已，本实验未实现。但本实验已完全能演示循环扫描的全过程。
三．课程设计目的
1.熟悉并掌握磁盘管理系统的设计方法，加深对所学各种磁盘调度算法及其算法的特点的了解。
2.掌握磁盘调度的基本概念，比较各种磁盘调度算法的优劣
四.课程设计要求
从课程设计的目的出发，通过设计工作的各个环节，达到以下设计要求：
1.对系统进行功能模块分析、控制模块分析正确；
2.系统设计要实用；
3.编程简练，可用，功能全面,具有较好的健壮性；
4.说明书、流程图要清楚。
五. 详细设计及算法流程图
1. 总流程图
输入磁道的个数
输入所需功能的前置编号
开始
输入数字为1~4？
输入当前磁道号
退出
数字为0？
输入错误
结果显示
结束

2. 先来先服务（FCFS）算法流程图
开始
sum=0,j,i,first=0,now
i=0;i<n;i++
确定磁头所在位置
计算sum i=0,j=1;j<n;i++,j++
first+=abs(a[j]-a[i])
sum+=first+abs(now-a[0])
移动的总磁道数
结束

3. 最短寻道时间优先（SSTF）算法流程图
开始
for(i=0;i<n;i++)cout<<a[i]<<”";sum=a[n-1]-now;
i=0;i<n;i++
j=i+1;j<n;j++
int temp;int k=1;int now,l,r;
int i,j,sum=0;
for(i=n-1;i>=0;i--)cout<<a[i]<<"";sum=now-a[0];
递增顺序的磁道显示
a[i]>a[j]
if(a[n-1]<=now)
if(a[0]>=now)
while(a[k]<now)// while(l>=0)&&(r<n)
移动的总道数
结束

4. 扫描调度（SCAN）算法流程图
for(j=i+1;j<n;j++)
按递增顺序排好的磁道
for(i=0;i<n;i++)
int a[],int n
开始
for( i=0;i<n;i++)
if(a[n-1]<=now)
if(a[0]>=now)
Int d;
while(a[k]<now)循环
确定磁头访问的方向
移动的总道数
结束
循环
循环

5. 循环扫描（C-SCAN）算法流程图
int a[],int n
for(i=0;i<n;i++)循环
for(i=0;i<n;i++)循环
按递增顺序排好的磁道
for(i=0;i<n;i++)循环
开始
if(a[n-1]<=now)
if(a[0]>=now)
磁头位置在两侧磁道之间
确定磁头访问的方向
移动的总道数
结束

六．课程设计具体步骤
1.定义函数部分主要代码
#include<iostream>
#include<ctime>
using namespace std;
void FCFS(int a[],int n);
void SSTF(int a[],int n);
void SCAN(int a[],int n);
void CSCAN(int a[],int n);
2. 先来先服务（FCFS）算法部分主要代码
void FCFS(int a[],int n)
{
int sum=0,j,i,first=0,now;
cout<<"请输入当前磁道号：";
cin>>now;//确定当前磁头所在位置
cout<<"磁盘调度顺序为："<<endl;
for( i=0;i<n;i++){
cout<<a[i]<<" ";
}
for(i=0,j=1;j<n;i++,j++)
{
first+=abs(a[j]-a[i]);
}
sum+=first+abs(now-a[0]);
cout<<endl;
cout<<"移动的总磁道数为： "<<sum<<endl;
}
3. 最短寻道时间优先（SSTF）算法部分主要代码
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}

if(a[n-1]<=now)//当前磁头位置大于最外围欲访问磁道
{
for(i=n-1;i>=0;i--)
cout<<a[i]<<" ";
sum=now-a[0];
}

if(l=-1)//磁头位置里侧的磁道已访问完
{
for(j=r;j<n;j++)//访问磁头位置外侧的磁道
{
cout<<a[j]<<" ";
}
sum+=a[n-1]-a[0];
}
if(r==n)//磁头位置外侧的磁道已访问完
{
for(j=k-1;j>-1;j--) //访问磁头位置里侧的磁道
{
cout<<a[j]<<" ";
}
sum+=a[n-1]-a[0];
}
}
cout<<endl;
cout<<"移动的总道数为:"<<sum<<endl;
}
4.扫描调度（SCAN）算法部分主要代码
void SCAN(int a[],int n)
{
int temp;
int k=1;
int now,l,r;
int i,j,sum=0;
for(i=0;i<n;i++)

if(a[n-1]<=now) //磁头位置大于最外围欲访问磁道
{
for(i=n-1;i>=0;i--)
cout<<a[i]<<" ";
sum=now-a[0];
}
5. 循环扫描（C-SCAN）算法部分主要代码
void CSCAN(int a[],int n)
{
int temp;
int now,l,r;
int i,j,sum=0;
int k=1;
for(i=0;i<n;i++)

if(a[n-1]<=now)//磁头位置大于最外围欲访问磁道
{
for(i=0;i<n;i++)
cout<<a[i]<<" ";
sum=now-2*a[0]+a[n-1];
}
七．课程设计结果显示
1.先来先服务（FCFS）算法测试结果

2. 最短寻道时间优先（SSTF）算法测试结果

3.扫描调度（SCAN）算法测试结果

4.循环扫描（C-SCAN）算法测试结果

八．课程设计总结
计算机磁盘是一种很重要也很常用的外部设备，其分配也有一定的分配策略。在操作系统中，作业对磁盘的请求常常要排队，由此需要一些高效率的磁盘分配策略算法。（1）先来先服务算法为一种最简单的磁盘调度算法，它直接根据作业请求磁盘的先后顺序对磁盘进行寻访，公平、简单，每个作业的磁盘请求都可以得到处理，不会出现某个作业的请求长期得不到满足的情况，但未对寻道方案进行优化；（2）最短寻道时间优先算法优先选择距离当前磁头位置最近的作业磁道请求，可以使得每次寻道时所用的时间都最短，但不能保证平均周转时间及带权周转时间最短；（3）电梯算法同时考虑下一个作业磁道请求与当前磁头位置的距离和当前磁头移动方向先选择当前磁头之外距离其最近的磁道进行访问，直到再无更外的磁道请求，再将磁臂换向，访问磁头内侧距离当前磁头位置最近的作业磁道请求，避免了饥饿现象的出现，每个作业的磁盘请求都可以得到处理，且使每次寻道时间相对较短；（4）N_SCAN算法同时考虑下一个作业磁道请求与当前磁头位置的距离和当前磁头移动方向，但每次磁臂调转方向时，将同时处理在磁头向一侧移动过程当中输入的作业请求，先选择当前磁头之外距离其最近的磁道进行访问，直到再无更外的磁道请求，接下来一并考虑在磁头向外侧移动过程当中输入的作业请求与磁头内侧未被处理的作业磁道请求，此算法对中间磁道请求比较有利。总之，各种算法都有其长处，也各有不足，需要在实际应用中权衡利弊，择优使用才能达到最好的效果。
九．心得体会
在这几天的课程设计中，由于之前做过相似的实验，所以在一开的实验设计流程图时还是很快就完成了，不过在接下来的编写代码的阶段里，出现很大的问题，花费了很多的时间。好在有老师的耐心细心的指导，一步一步的验证，一点一点的改正。每一次的运行看到错误都在慢慢的减少，正确的设计结果也在不断的靠近，最终取得了成功。由于自己的知识和能力还不到位，在课程设计时间里经历了很多困难和挑战，但我认为，在这过程中的每一次的错误和故障，都使我收获颇丰，使我成长了很多。
当然，这个磁盘调度系统的设计远非完美，还有很多地方可以改进，例如界面可以更加友好，资源可以更加节约，算法也还有优化的余地，但是时间有限，经历也有限，在课程设计时间允许的范围内只能做到这样，我会在课余时间自行完善该磁盘调度算法程序。
每一次的课程设计都是自己对所学知识的强化，是一次难得的动手机会。在课程设计的每一个步骤的执行中，都要认真的反复的去做，因为一个小小的错误都会导致课程设计结果发生巨大的偏差。完成一个成功的设计，会让自己学会很多很多的东西，并且能够很清楚的看到自己的不足，查补缺漏，继续学习。通过自己的动手动脑，既增加了知识，又给了我专业知识以及专业技能上的提升，对提高自己的思维能力和操作能力有很大的帮助。同时我也会更加努力，认真学习，争取在以后的课程中做得更好！
十．参考资料
《计算机操作系统》清华大学出版社
《计算机操作系统实验指导》清华大学出版社

附录：
#include<iostream>
#include<ctime>
using namespace std;
void FCFS(int a[],int n);
void SSTF(int a[],int n);
void SCAN(int a[],int n);
void CSCAN(int a[],int n);
int main()
{
int n; //磁道的个数
int s; //功能号
cout<<"请输入当前磁道的个数,按Enter键显示生成的随机磁道号："<<endl;
cin>>n;
int *a=new int[n];
cout<<"生成的随机磁道号为：";
srand((unsigned)time(NULL));
for(int i=0;i<n;i++)
{
a[i]=(rand()%100)+1;
cout<<a[i]<<" ";
}
cout<<endl;
while(1)
{ cout<<endl;
cout<<" ┏━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl;
cout<<" ┃　　　 　 　磁盘调度算法功能列表　　 　 ┃"<<endl;
cout<<" ┠───────────────────────┨"<<endl;
cout<<" ┃ 1、先来先服务算法（FCFS） ┃"<<endl;
cout<<" ┠───────────────────────┨"<<endl;
cout<<" ┃ 2、最短寻道时间算法（SSTF） ┃"<<endl;
cout<<" ┠───────────────────────┨"<<endl;
cout<<" ┃ 3、扫描算法（SCAN） ┃"<<endl;
cout<<" ┠───────────────────────┨"<<endl;
cout<<" ┃ 4、循环扫描算法（CSCAN） ┃"<<endl;
cout<<" ┠───────────────────────┨"<<endl;
cout<<" ┃ 0、退出 ┃"<<endl;
cout<<" ┗━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl;
cout<<endl;
cout<<"请选择所需功能的前置编号:";
cin>>s;
if(s>4)
{
cout<<"数据输入有误！请重新输入："<<endl;
}
else
{
switch(s)
{ case 0: exit(0);break ;
case 1:FCFS(a,n); break;
case 2:SSTF(a, n);break;
case 3:SCAN(a, n);break;
case 4:CSCAN(a,n);break;
}
}
}
return 0;
}
//先来先服务调度算法（FCFS）
void FCFS(int a[],int n)
{
int sum=0,j,i,first=0,now;
cout<<"请输入当前磁道号：";
cin>>now;//确定当前磁头所在位置
cout<<"磁盘调度顺序为："<<endl;
for( i=0;i<n;i++)//按访问顺序输出磁道号
{
cout<<a[i]<<" ";
}
//计算sum
for(i=0,j=1;j<n;i++,j++)
{
first+=abs(a[j]-a[i]);//外围磁道与最里面磁道的距离
}
sum+=first+abs(now-a[0]);
cout<<endl;
cout<<"移动的总磁道数为： "<<sum<<endl;
}
//最短寻道时间算法（SSTF）
void SSTF(int a[],int n)
{
int temp;
int k=1;
int now,l,r;
int i,j,sum=0;
//将磁道号按递增排序
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
cout<<"按递增顺序排好的磁道显示为："<<endl;
for( i=0;i<n;i++)
{
cout<<a[i]<<" ";//输出排好的磁道顺序
}
cout<<endl;
cout<<"请输入当前的磁道号：";
cin>>now;//确定当前磁头所在位置
cout<<"磁盘调度顺序为："<<endl;
if(a[n-1]<=now)//当前磁头位置大于最外围欲访问磁道
{
for(i=n-1;i>=0;i--)
cout<<a[i]<<" ";
sum=now-a[0];
}
else
if(a[0]>=now)//当前磁头位置小于最里欲访问磁道
{
for(i=0;i<n;i++)
cout<<a[i]<<" ";
sum=a[n-1]-now;
}
else
{
while(a[k]<now)//确定当前磁道在已排的序列中的位置
{
k++;
}
l=k-1;//在磁头位置的前一个欲访问磁道
r=k;//磁头欲访问磁道

while((l>=0)&&(r<n))
{
if((now-a[l])<=(a[r]-now))//选择离磁头近的磁道
{
cout<<a[l]<<" ";
sum+=now-a[l];
now=a[l];
l=l-1;
}
else
{
cout<<a[r]<<" ";
sum+=a[r]-now;
now=a[r];
r=r+1;
}
}
if(l=-1)//磁头位置里侧的磁道已访问完
{
for(j=r;j<n;j++)//访问磁头位置外侧的磁道
{
cout<<a[j]<<" ";
}
sum+=a[n-1]-a[0];
}
if(r==n)//磁头位置外侧的磁道已访问完
{
for(j=k-1;j>-1;j--) //访问磁头位置里侧的磁道
{
cout<<a[j]<<" ";
}
sum+=a[n-1]-a[0];
}
}
cout<<endl;
cout<<"移动的总道数为:"<<sum<<endl;
}
//扫描算法（SCAN）
void SCAN(int a[],int n)
{
int temp;
int k=1;
int now,l,r;
int i,j,sum=0;
for(i=0;i<n;i++)//对访问磁道按由小到大顺序排列输出
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
cout<<"按递增顺序排好的磁道为："<<endl;
for( i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"请输入当前的磁道号：";
cin>>now;
//以下算法确定磁道访问顺序
if(a[n-1]<=now) //磁头位置大于最外围欲访问磁道
{
for(i=n-1;i>=0;i--)
cout<<a[i]<<" ";
sum=now-a[0];
}
else
if(a[0]>=now) //磁头位置小于最里欲访问磁道
{
for(i=0;i<n;i++)
cout<<a[i]<<" ";
sum=a[n-1]-now;
}
else //磁头位置在最里侧磁道与最外侧磁道之间
{ int d;
while(a[k]<now)
{ //确定当前磁道在已排的序列中的位置
k++;
}
l=k-1;//在磁头位置的前一个欲访问磁道
r=k; //磁头欲访问磁道
cout<<"请输入当前磁头移动的方向 (0 表示向内 ，1表示向外) : ";
cin>>d; //确定磁头访问的方向
cout<<"磁盘调度顺序为：";
if(d==0||d==1)
{
if(d==0) //磁头向内
{
for(j=l;j>=0;j--)
{
cout<<a[j]<<" ";
}
for(j=r;j<n;j++)
{
cout<<a[j]<<" ";
}
sum=now-2*a[0]+a[n-1];
}
if(d==1) //磁头向外
{
for(j=r;j<n;j++)
{
cout<<a[j]<<" ";
}
for(j=l;j>=0;j--)
{
cout<<a[j]<<" ";
}
sum=2*a[n-1]-now-a[0];
}
}
else
cout<<"请输入0或1！"<<endl;
}
cout<<endl;
cout<<"移动的总道数为： "<<sum<<endl;
}
//循环扫描算法（CSCAN）
void CSCAN(int a[],int n)
{
int temp;
int now,l,r;
int i,j,sum=0;
int k=1;
for(i=0;i<n;i++)//对访问磁道按由小到大顺序排列输出
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
cout<<"按递增顺序排好的磁道为："<<endl;
for( i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"请输入当前的磁道号：";
cin>>now;//确定当前磁道号
if(a[n-1]<=now)//磁头位置大于最外围欲访问磁道
{
for(i=0;i<n;i++)
cout<<a[i]<<" ";
sum=now-2*a[0]+a[n-1];
}
else
if(a[0]>=now)//磁头位置小于最里欲访问磁道
{
for(i=0;i<n;i++)
cout<<a[i]<<" ";
sum=a[n-1]-now;
}
else //磁头位置在最里侧磁道与最外侧磁道之间
{ int d;
while(a[k]<now)
{
k++;
}
l=k-1;//在磁头位置的前一个欲访问磁道
r=k; //磁头欲访问磁道
cout<<"请输入当前磁头移动的方向 (0 表示向内 ，1表示向外) : ";
cin>>d; //确定磁头访问的方向
cout<<"磁盘调度顺序为：";
if(d==0||d==1)
{
if(d==1) //磁头向外侧访问
{
for(j=r;j<n;j++)//先访问外侧磁道再转向最里欲访问磁道
{
cout<<a[j]<<" ";
}
for(j=0;j<r;j++)
{
cout<<a[j]<<" ";
}
sum=2*a[n-1]-now-2*a[0]+a[l];
}
if(d==0) //磁头向内侧访问
{
for(j=r-1;j>=0;j--)
{
cout<<a[j]<<" ";
}
for(j=n-1;j>=r;j--)
{
cout<<a[j]<<" ";
}
sum=2*a[n-1]-2*a[0]+now-a[r];
}
}
else
cout<<"请输入0或1!";
}
cout<<endl;
cout<<"移动的总道数为： "<<sum<<endl;
}

34