实验-进程描述与控制
一、实验描述
磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列，常用的磁盘调度算法有以下四种：先来先服务算法（FCFS ），最短寻道时间优先算法（SSTF），扫描算法（SCAN ），循环扫描算法（CSCAN ）。
通过编程，预先设定一个磁道个数及磁盘访问序列。分别采用先来先服务算法（FCFS ），最短寻道时间优先算法（SSTF），扫描算法（SCAN ），循环扫描算法（CSCAN ），通过结果，计算出四种算法的平均寻道的长度，比较四种算法之间的差异和优势。
二、实验代码
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
typedef vector<int> vInt; //向量，动态数组
struct OrderItem
{
int Data;
bool IsVisited;
};
typedef vector<OrderItem> Order;
Order InitOrder;
vInt TrackOrder;
vInt MoveDistance;
double AverageDistance;
void InitDate(int &num);
inline void Init(int disk); //内联函数（内联函数的代码会在任何调用它的地方展开）
void FCFS(int disk);
void SSTF(int disk);
void SCAN(int disk);
void CSCAN(int disk);
void Show(int disk);
int main()
{
int num;
InitDate(num);
char cmd;
do
{
cout<<"选择算法:\n"<<"1-FCFS,2-SSTF,3-SCAN,4-CSCAN:\t";
int type;cin>>type;
switch(type)
{
case 1:FCFS(num);break;
case 2:SSTF(num);break;
case 3:SCAN(num);break;
case 4:CSCAN(num);break;
}
Show(num);
cout<<"Continue? y or n?\t";
cin>>cmd;
}while(cmd!='n');
return 0;
}
inline void Init(int disk)
{
TrackOrder.clear();
MoveDistance.clear();
for(int i = 0; i < disk; i++)
{
InitOrder[i].IsVisited = false;
}
}
void InitDate(int &num)
{
//ifstream cin("data.txt");
cout<<"输入磁道个数";
cin>>num;
cout<<"磁盘访问序列";
for(int i=0; i<num; i++)
{
OrderItem oi;
cin>>oi.Data;
oi.IsVisited = false;
InitOrder.push_back(oi);
}
}
void FCFS(int disk)
{
cout<<"输入开始磁盘号";
int start;cin>>start;
cout<<"FCFS:"<<endl;
int p = start;
Init(disk);
for(int i = 0 ; i < disk; i++ )
{
TrackOrder.push_back(InitOrder[i].Data);
int t = InitOrder[i].Data-p;
MoveDistance.push_back(t>0?t:-t);
InitOrder[i].IsVisited = true;
p = InitOrder[i].Data;
}
}
void SSTF(int disk)
{
cout<<"输入开始磁盘号";
int start;cin>>start;
cout<<"SSTF:"<<endl;
Init(disk);
int curp=0,dif=0;
int p = start;
for(int i = 0; i < disk; i++)
{
int temp = 0;
for(int j = 0 ; j < disk; j++)
{
if(InitOrder[j].IsVisited == false)
{
temp = p-InitOrder[j].Data>0?
p-InitOrder[j].Data:-(p-InitOrder[j].Data);
if(dif==0||temp<dif)
{
dif = temp;
curp = j;
}
}
}
InitOrder[curp].IsVisited = true;
TrackOrder.push_back(InitOrder[curp].Data);
MoveDistance.push_back(dif);
p = InitOrder[curp].Data;
dif = 0;
}
}
void SCAN(int disk)
{
cout<<"输入开始磁盘号";
int start;cin>>start;
cout<<"选择访问方向:0-磁道号递增1-磁道号递减\t";
int dir; cin>>dir;
cout<<"SSTF:"<<endl;
Init(disk);
int curp=0,dif=0,cdir=dir,max=InitOrder[0].Data,min=max;
for(int i =1; i<disk;i++)
{
if(max<InitOrder[i].Data)
max = InitOrder[i].Data;
if(min>InitOrder[i].Data)
min = InitOrder[i].Data;
}
int p = start;
for(int k = 0; k< disk; k++)
{
int temp = 0;
for(int j = 0 ; j < disk; j++)
{
if(cdir==0&&p>InitOrder[j].Data||cdir==1&&p<InitOrder[j].Data)
continue;
if(InitOrder[j].IsVisited == false)
{
temp = p-InitOrder[j].Data>0?
p-InitOrder[j].Data:-(p-InitOrder[j].Data);
if(dif==0||temp<dif)
{
dif = temp;
curp = j;
}
}
}
if(dir==0&&InitOrder[curp].Data==max)cdir = 1;
if(dir==1&&InitOrder[curp].Data==min)cdir = 0;
InitOrder[curp].IsVisited = true;
TrackOrder.push_back(InitOrder[curp].Data);
MoveDistance.push_back(dif);
p = InitOrder[curp].Data;
dif = 0;
}
}
void CSCAN(int disk)
{
cout<<"输入开始磁盘号";
int start;cin>>start;
cout<<"选择访问方向:0-磁道号递增1-磁道号递减\t";
int dir; cin>>dir;
cout<<"CSSTF:"<<endl;
Init(disk);
int curp=0,dif=-1,max=InitOrder[0].Data,min=max,mmin=0,mmax=0;
for(int i =1; i<disk;i++)//找到磁道序列中最小和最大的磁道号及下标
{
if(max<InitOrder[i].Data)
{
max = InitOrder[i].Data;
mmax = i;
}
if(min>InitOrder[i].Data)
{
min = InitOrder[i].Data;
mmin=i;
}
}
int p = start;//p表示上一个访问的磁道号
for(int k = 0; k < disk; k++)
{
int temp = 0;
for(int j = 0 ; j < disk; j++)//查找下一个要访问的磁道
{
if(dir==0&&p>InitOrder[j].Data||dir==1&&p<InitOrder[j].Data)
continue;
if(InitOrder[j].IsVisited == false)//dir方向且未被访问的项
{
temp = p-InitOrder[j].Data>0?
(p-InitOrder[j].Data):(InitOrder[j].Data-p);
if(dif==-1||temp<dif)
{
dif = temp;
curp = j;//找到下一个被访问的磁道
}
}
}
InitOrder[curp].IsVisited = true;//访问
TrackOrder.push_back(InitOrder[curp].Data);
MoveDistance.push_back(dif);
p = InitOrder[curp].Data;
//达到极限点
if(dir==0&&InitOrder[curp].Data==max&&InitOrder[mmin].IsVisited==false)
{
//从最小项开始
TrackOrder.push_back(min);
InitOrder[mmin].IsVisited = true;
MoveDistance.push_back(p-TrackOrder[mmin]>=0?
p-TrackOrder[mmin]:TrackOrder[mmin]-p);
curp = mmin;
}
if(dir==1&&InitOrder[curp].Data==min&&InitOrder[mmax].IsVisited==false)
{
TrackOrder.push_back(max);
InitOrder[mmax].IsVisited = true;
MoveDistance.push_back(p-TrackOrder[mmin]>=0?
p-TrackOrder[mmin]:TrackOrder[mmin]-p);
curp = mmax;
}
p = InitOrder[curp].Data;
dif = -1;
}
}
void Show(int disk)
{
cout<<"被访问的下一个磁道号\t"<<"移动距离"<<endl;
int sum=0;
for(int i = 0 ; i <disk; i++)
{
sum+=MoveDistance[i];
cout<<"\t"<<TrackOrder[i]<<"\t\t "<<MoveDistance[i]<<endl;
}
AverageDistance = (double)sum/disk;
cout<<"平均寻道长度:"<<AverageDistance<<endl;
}