磁盘调度管理算法
这是操作系统上机实验的最后一次实验,所以得好好收个尾,虽然就没精彩过。
"阔列娃" 题目
实验题
假定一磁盘有200个柱面,编号为0~199,当前移动臂的位置在143号柱面上,并刚刚完成125号柱面的服务请求,如果请求队列的先后顺序是86,147,91,177,94,150,102,175,130。请按下列算法分别计算为完成上述各次访问总共需要的磁头移动量,并写出磁头的移动顺序。要求通过编写模拟程序实现,开发工具任选。
- 电梯算法;
- 最短寻找时间优先算法(SSTF)。
"阔列娃" 分析
磁盘的盘面是有磁道的,那么磁道是什么呢?磁道就是一圈一圈的同心圆,一个盘面有200个同心圆。一个磁盘具有多个盘面,那么在立体3D结构上,每个盘面的同一个磁道就构成了一个柱面,就像一个圆柱体。
那么每一个盘面上都会有一个叫做磁头的东西,系统控制磁头去读写磁盘(磁头的旋转都是同时的),那么磁头总得有个位置,题目给出位置在143号柱面上,即在一个盘面上,她在143号磁道上。那么她刚刚完成125号柱面的服务请求是什么意思呢?就是说这个磁头将要往磁道号大的方向上移动了(即往圆心移动,最外磁道为0,最里面为200)。
那么现在请求队列的先后顺序是86,147,91,177,94,150,102,175,130
,那么对于我们的俩个调度算法怎么实现呢?我们先来学习俩个调度算法的core思想。
- 电梯算法(SCAN Pro)
电梯算法(SCAN Pro)不仅考虑到欲访问的磁道与当前磁道的距离,更优先考虑的是磁头的当前移动方向。当磁头正在由里向外移动时,SCAN算法所选择的下一个访问对象应是其欲访问的磁道,既在当前磁道之外,又是距离最近的。这样由里向外地访问,直至再无更外的磁道需要访问时,才将磁臂换向,由外向里移动。这时,同样也是每次选择在当前磁道之内,且距离最近的进程来调度。 -
最短寻找时间优先算法(SSTF)
SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道,以使每次的寻找时间最短。当然,总是选择最小寻找时间并不能保证平均寻找时间最小,但是能提供比FCFS(先来先服务)算法更好的性能。这种算法会产生“饥饿”现象。平均寻道 = \frac{moveDisk}{requestDisk}
"阔列娃" 调度管理效果
"阔列娃" 源码
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
vector<unsigned int> reqTrack = {55,58,39,18,90,160,150,38,184};//86,147,91,177,94,150,102,175,130; 55,58,39,18,90,160,150,38,184;
vector<unsigned int> seqTrack;
vector<unsigned int> countTrack;
unsigned int startPos;
unsigned int totalTrack;
bool direction = 0; // 0: to small, 1: to large
void disTrack()
{
cout<<" --------------------"<<endl;
for (int i = 0; i < seqTrack.size(); i++)
{
cout<<"||"<<setw(6)<<seqTrack[i]<<setw(4)<<"|"<<setw(5)<<countTrack[i]<<setw(5)<<"||"<<endl;
cout<<" --------------------"<<endl;
}
}
void initialVector()
{
seqTrack.clear();
countTrack.clear();
vector<unsigned int>().swap(seqTrack);
vector<unsigned int>().swap(countTrack);
totalTrack = 0;
}
void scanPro()
{
initialVector();
cout<<"Where the Track heading of ELEVATOR to: (For '0' to small, for '1' to large) ";
cin>>direction;
vector<unsigned int> small,large;
unsigned int dis=0;
int pos = startPos;
float averageTrack=0.0;
for (int i = 0; i < reqTrack.size(); i++)
{
if (reqTrack[i] == pos)
{
seqTrack.push_back(reqTrack[i]);
countTrack.push_back(0);
}
else if (reqTrack[i] < pos)
{
small.push_back(reqTrack[i]);
}
else if (reqTrack[i] > pos)
{
large.push_back(reqTrack[i]);
}
}
sort(large.begin(),large.end());
sort(small.rbegin(),small.rend());
// core
if (direction) // 1: first to large
{
for (int i = 0; i < large.size(); i++)
{
seqTrack.push_back(large[i]);
dis = large[i] - pos;
totalTrack+=dis;
countTrack.push_back(dis);
pos = large[i];
}
for (int i = 0; i < small.size(); i++)
{
seqTrack.push_back(small[i]);
dis = pos - small[i];
totalTrack+=dis;
countTrack.push_back(dis);
pos = small[i];
}
}
else // 0: first to small
{
for (int i = 0; i > small.size(); i++)
{
seqTrack.push_back(small[i]);
dis = pos - small[i];
totalTrack+=dis;
countTrack.push_back(dis);
pos = small[i];
}
seqTrack.push_back(0);
dis = pos - 0;
totalTrack+=dis;
countTrack.push_back(dis);
pos = 0;
for (int i = 0; i < large.size(); i++)
{
seqTrack.push_back(large[i]);
dis = large[i] - pos;
totalTrack+=dis;
countTrack.push_back(dis);
pos = large[i];
}
}
cout<<"#======Elevator======#"<<endl;
cout<<"#---Track--|--Dist---#"<<endl;
disTrack();
averageTrack = (float) totalTrack/ (float) reqTrack.size();
cout<<"The Total Track is: "<<totalTrack<<endl;
cout<<"The Average Track is: "<<averageTrack<<endl;
}
void SSTF()
{
initialVector();
vector<unsigned int> small,large;
unsigned int dis=0;
int pos = startPos;
float averageTrack=0.0;
for (int i = 0; i < reqTrack.size(); i++)
{
if (reqTrack[i] == pos)
{
seqTrack.push_back(reqTrack[i]);
countTrack.push_back(0);
}
else if (reqTrack[i] < pos)
{
small.push_back(reqTrack[i]);
}
else if (reqTrack[i] > pos)
{
large.push_back(reqTrack[i]);
}
}
sort(large.begin(),large.end());
sort(small.rbegin(),small.rend());
// core
int i=0,j=0;
while (i < small.size() && j < large.size())
{
if (pos - small[i] >= large[j] - pos) // close to the large
{
seqTrack.push_back(large[j]);
dis = large[j] - pos;
totalTrack+=dis;
countTrack.push_back(dis);
pos = large[j];
j++;
}
else // close to the small
{
seqTrack.push_back(small[i]);
dis = pos - small[i];
totalTrack+=dis;
countTrack.push_back(dis);
pos = small[i];
i++;
}
}
while (i < small.size())
{
seqTrack.push_back(small[i]);
dis = pos - small[i];
totalTrack+=dis;
countTrack.push_back(dis);
pos = small[i];
i++;
}
while (j < large.size())
{
seqTrack.push_back(large[j]);
dis = large[j] - pos;
totalTrack+=dis;
countTrack.push_back(dis);
pos = large[j];
j++;
}
cout<<"#========SSTF========#"<<endl;
cout<<"#---Track--|--Dist---#"<<endl;
disTrack();
averageTrack = (float) totalTrack/ (float) reqTrack.size();
cout<<"The Total Track is: "<<totalTrack<<endl;
cout<<"The Average Track is: "<<averageTrack<<endl;
}
int main()
{
cout<<"The Request Track is: ";
for (int i = 0; i < reqTrack.size(); i++)
{
cout<<reqTrack[i]<<" ";
}
cout<<endl;
cout<<"The Start Track is: ";
cin>>startPos;
scanPro();
cout<<endl;
SSTF();
return 0;
}
叨叨几句... 2 条评论
太详细了,有文字还有代码,赞一个
@天津网站建设

还行还行,谢谢夸奖