磁盘调度算法的实现讲课稿.doc

磁盘调度算法的实现

精品资料

一、 实验目的:
通过模拟设计磁盘驱动调度程序，观察驱动调度程序的动态运行过程，理解和掌握磁盘驱动调度的职能，并比较各种算法的调度结果。
二、实验内容:
要求设计主界面能灵活选择某算法，且以下算法都要实现。
（1）先来先服务算法（FCFS）
（2）最短寻道时间优先算法（SSTF）
（3）扫描算法（SCAN）
（4）循环扫描算法（CSCAN）
三、实验步骤
（1） 需求分析：
本设计中可在运行时随机产生一个请求序列，先把序列排序，以方便找 到下一个要寻找的磁道。要求用户选择磁头移动方向，向里和向外移动用1和0表示，若输入值不为0或1，则报错。选择某种调度算法后，要求显示调度顺序和移动的总磁道数。
（2）详细设计：
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<<"请输入磁道的个数："<<endl;
cin>>n;
int *a=new int[n];
cout<<"生成随机磁道号..."<<endl;
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<<"1、先来先服务算法（FCFS）"<<endl;
cout<<"2、最短寻道时间算法（SSTF）"<<endl;
cout<<"3、扫描算法（SCAN）"<<endl;
cout<<"4、循环扫描算法（CSCAN）"<<endl;
cout<<"0、退出"<<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;
}
实验源代码
#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<<"请输入磁道的个数："<<endl;
cin>>n;
int *a=new int[n];
cout<<"生成随机磁道号..."<<endl;
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<<"1、先来先服务算法（FCFS）"<<endl;
cout<<"2、最短寻道时间算法（SSTF）"<<endl;
cout<<"3、扫描算法（SCAN）"<<endl;
cout<<"4、循环扫描算法（CSCAN）"<<endl;
cout<<"0、退出"<<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;
}

（3）测试结果：
1.先来先服务算法（FCFS）测试结果

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

3.循环扫描算法（SCAN）测试结果

4.循环扫描算法（CSCAN）测试结果

四、设计总结:
此次设计基本完成了本实验所规定的功能，但是还不够完善，很多东西 做的不够好，程序不够完善和严谨。由于我的编程基础不是很好，其中不免会 有些纰 漏，出错处理不够完善等多方面问题，这些都有进一步改善。
在编程设计过程中，由于不知道怎产生不相等的随机数，以及后来的扫描算法和循环扫描算法计算移动总的磁道数都遇到了一点问题，通过上网查询，最后在老师以及同学的指导下很快完成了设计。
此次课程设计中我学到了很多东西，无论在理论上还是实践中，都得到不少的提高，这对于我以后的工作和学习都是一种巨大的帮助！

仅供学习与交流，如有侵权请联系网站删除 谢谢13