如果当前停留在第122号磁道上,接下来8个磁道按顺序分别是 120,98,4,51,180,195,140,23。请写出最短寻道时间优先和扫描算 法的访问顺序以及各自的平均寻道长度。
最短寻道时间优先算法:
SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道,以使每次的寻找时间最短。当然,总是选择最小寻找时间并不能保证平均寻找时间最小,但是能提供比FCFS算法更好的性能。这种算法会产生“饥饿”现象。
最短寻道时间优先:122, 120, 140, 180, 195, 98, 51, 23, 4
先找离122最近的120,接着找离120最近的,140,以此类推
平均寻道长度:(2+20+40+15+97+47+28+19)/8 = 33.5
扫描算法:
该算法不仅考虑到欲访问的磁道与当前磁道间的距离,更优先考虑的是磁头当前的移动方向。例如,当磁头正在自里向外移动时,SCAN算法所考虑的下一个访问对象,应是其欲访问的磁道既在当前磁道之外,又是距离最近的。这种自里向外地访问,直至再无更外的磁道需要访问时,才将磁臂换向为自外向里移动。这是,同样也是每次选择这样的进程来调度,即要访问的磁道在当前位置内距离最近者,这样,磁头又逐步地从外向里移动,直至再无更里面的磁道要访问,从而避免了出现“饥饿”现象。由于在这种算法中磁盘移动的规律颇似电梯的运行,因而又常称之为电梯调度算法。
扫描算法:122, 140, 180, 195, 120, 98, 51, 23, 4
按顺序先从小到大,122 140 180 195 到了最大值开始从大到小
平均寻道长度:(18+40+15+75+22+47+28+19)/8 = 33
最短寻道时间算法(C语言)文章来源:https://www.toymoban.com/news/detail-518228.html
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 51
struct TCB //track control block磁道控制块
{
int tn; //track number磁道号
int flag; //完成标志 flag=-1没完成 flag=1完成
}track[N];
int a[N]; //记录磁道访问的先后顺序
int randomnumber(int n,int max,int min) //各磁道互不相同
{
srand((int)time(NULL));
int t; //用来判断这个随机数是否重复
int x,y;
for(x=1;x<=n;)
{
t=rand()%(max-min+1)+min;
for(y=1;y<x;y++)
{if(track[y].tn==t) break;}
if(y==x) //不重复
{track[x++].tn=t;track[--x].flag=-1;x++;}//有进程的为-1,没有的为0 (系统初始化)
}
}
int SSTF(int n,int present,int max,int min)
{
/*这个最短寻道时间优先要分两部分考虑,
第一,访问第一个磁道:
比如说磁头开始处在第六道,然后等待服务的磁道先后顺序为8,2,5,3,7,9
那么问题来了,这个最短访问磁道距离为1(分别是磁道5和7),
那么我就以这两个磁道先到达的处理,那就是处理5;
当然,除了第一个访问的会出现这种问题,之后不会出现了(因为顺序)
第二,访问之后的磁道就以当前磁头所在地找最短的访问
*/
int z=1; //记录顺序访问数组a的下标
int s=0; // 记录对于第一个访问中最短距离有几个
int sum=0; //移动的磁道总数
int add=0; //记录已经访问的磁道个数
int md=max-min; //min distance用来存当前最短距离 (初值最大)
int mdp; //min distance position用来存放当前最短距离磁道下标
int i,j;
//访问第一个磁道
for(i=1;i<=n;i++) //找最小距离
{
if(abs(present-track[i].tn)<md)
md=abs(present-track[i].tn);
}
for(i=1;i<=n;i++) //找最小距离的个数 ,mdp记录的是最后一个磁道其md等于最小距离的下标
{
if(md==abs(present-track[i].tn)) {s++;mdp=i;}
}
if(s==1) //如果只有一个,那就直接访问
{
a[z++]=track[mdp].tn;
track[mdp].flag=1;
sum+=abs(present-track[mdp].tn);
present=track[mdp].tn;
add+=1;
}
else if(s>1) //如果有两个
{
for(i=1;i<=n;i++) //先找到最先到达的一个 ,再访问
if(md==abs(present-track[i].tn)) {mdp=i;break;}
a[z++]=track[mdp].tn;
track[mdp].flag=1;
sum+=abs(present-track[mdp].tn);
present=track[mdp].tn;
add+=1;
}
//访问其他的磁道
while(add<n)
{
md=max-min;
for(i=1;i<=n;i++)
{ //找到接下来访问的位置
if(track[i].flag==-1)
if(abs(present-track[i].tn)<md)
{md=abs(present-track[i].tn);mdp=i;}
}
sum+=md;
present=track[mdp].tn;
track[mdp].flag=1;
add++;
a[z++]=track[mdp].tn;
}
printf("\n\n\n磁道访问顺序:");
for(j=1;j<=n;j++)
printf("%d ",a[j]);
printf("\n\n磁道移动总数sum=%d\n",sum);
printf("平均寻道总数=%lf\n",sum/(float)n);
}
int main()
{
int n;
int max,min,current;
printf("\t\t最短寻道时间优先\n\n");
printf("请输入请求进程的个数(1-50):");
scanf("%d",&n);
printf("请输入最小磁道号:");
scanf("%d",&min);
printf("请输入最大磁道号:");
scanf("%d",&max);
printf("请输入当前磁头所在的位置:");
scanf("%d",¤t);
randomnumber(n,max,min);
//for(int i=1;i<=N;i++) //检验产生的数是否符合要求
//printf("%d %d\n",track[i].tn,track[i].flag);
printf("\n磁道请求调度先后顺序为:\n");
for(int j=1;j<=n;j++)
printf("%d\t",track[j].tn);
SSTF(n,current,max,min);
return 0;
}
扫描算法(C语言)文章来源地址https://www.toymoban.com/news/detail-518228.html
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 51
struct TCB //track control block
{
int tn; //track number磁道号
int flag; //完成标志 flag=-1没完成 flag=1完成
}track[N];
int randomnumber(int n,int max,int min) //各磁道互不相同
{
srand((int)time(NULL));
int t; //用来判断这个随机数是否重复
int x,y;
for(x=1;x<=n;)
{
t=rand()%(max-min+1)+min;
for(y=1;y<x;y++)
{if(track[y].tn==t) break;}
if(y==x) //不重复
{track[x++].tn=t;track[--x].flag=-1;x++;}//有进程的为-1,没有的为0 (系统初始化)
}
}
int SCAN(int n,int present,int max,int min,int option)
{
int i,j;
int z=1;
int start; //存放磁头访问开始位置
int sum=0; //磁头移动总数
for(i=1;i<n;i++) //对磁道从小到大排序
for(j=i+1;j<=n;j++)
if(track[i].tn>track[j].tn)
{
track[0].tn=track[i].tn;
track[i].tn=track[j].tn;
track[j].tn=track[0].tn;
}
if(present<=track[1].tn) start=1; //找分断点和访问开始位置
else if(present>=track[n].tn) start=n;
else
{
for(i=2;i<n;i++)
if(track[i-1].tn<present&&track[i+1].tn>present)
{start=i;break;}
if(track[start].tn==present) start=i;
else if(track[start].tn<=present)
{
if(option==1) start=i+1;
else if(option==0) start=i;
}
else if(track[start].tn>=present)
{
if(option==1) start=i;
else if(option==0) start=i-1;
}
}
//找到磁头访问开始位置后,就是扫描访问各磁道
printf("\n\n\n磁道访问顺序:");
if(start==1||start==n)
{
if(start==1)
for(j=1;j<=n;j++)
{printf("%d ",track[j].tn); sum+=abs(present-track[j].tn); present=track[j].tn;}
else if(start==n)
for(j=n;j>=1;j--)
{printf("%d ",track[j].tn);sum+=abs(present-track[j].tn);present=track[j].tn;}
}
else
{
if(option==1) //自低向高走
{
for(j=start;j<=n;j++) {printf("%d ",track[j].tn);sum+=abs(present-track[j].tn);present=track[j].tn;}
for(j=start-1;j>=1;j--) {printf("%d ",track[j].tn);sum+=abs(present-track[j].tn);present=track[j].tn;}
}
else if(option==2) //自高向低走
{
for(j=start;j>=1;j--){printf("%d ",track[j].tn);sum+=abs(present-track[j].tn);present=track[j].tn;}
for(j=start+1;j<=n;j++){printf("%d ",track[j].tn);sum+=abs(present-track[j].tn);present=track[j].tn;}
}
printf("\n\n磁道移动总数sum=%d\n",sum);
printf("平均寻道总数=%lf\n",sum/(float)n);
}
}
int main()
{
int n;
int max,min,current;
int option; //用于磁头移动方向选择
printf("\t\t最短寻道时间优先\n\n");
printf("请输入请求进程的个数(1-50):");
scanf("%d",&n);
printf("请输入最小磁道号:");
scanf("%d",&min);
printf("请输入最大磁道号:");
scanf("%d",&max);
printf("请输入当前磁头所在的位置:");
scanf("%d",¤t);
printf("\n请选择磁头的移动方向: 1.自低向高; 2.自高向低。\n");
scanf("%d",&option);
randomnumber(n,max,min);
//for(int i=1;i<=N;i++) //检验产生的数是否符合要求
//printf("%d %d\n",track[i].tn,track[i].flag);
printf("\n磁道请求调度先后顺序为:\n");
for(int j=1;j<=n;j++)
printf("%d\t",track[j].tn);
SCAN(n,current,max,min,option);
return 0;
}
到了这里,关于磁盘调度算法例题解析以及C语言实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!