作业调度
一、实验目的
1、 对作业调度的相关内容作进一步的理解。
2、 明白作业调度的主要任务。
3、 通过编程掌握作业调度的主要算法。
二、实验内容及要求
1、对于给定的一组作业, 给出其到达时间和运行时间，例如下表所示：
2、分别用先来先服务算法、短作业优先和响应比高者优先三种算法给出作业的调度顺序。
3、计算每一种算法的平均周转时间及平均带权周转时间并比较不同算法的优劣。
三、实验过程
1、程序中使用的数据结构及符号说明
进程结构体
{‘作业名’:’A’,’到达时间’:0,’服务时间’:6,’结束时间’:0,’周转时间’:0,’带权周转时间’:0}
2、实验程序：
#include<iostream>
using namespace std;
struct works
{
char name;//作业名
double ctime;//到达时间
double stime;//服务时间
double ftime;//完成时间
double ztime;//周转时间
double dtime;//带权周转时间
double wtime;//等待时间
double rratio;//响应比
};
double sumztime,sumdtime;
double avgztime,avgdtime;
void input(works *p,int n);//输入
void output(works *p,int n);//输出
void datap(works *p,int n);//数据处理
void sort(works *p,int n);//按到达时间排序
void fcfs(works *p,int n);//先来先服务
void sjf(works *p,int n);//短作业优先
void hrf(works *p,int n);//高响应比优先
int main()
{
int n;
cout<<"输入作业数目: ";
cin>>n;
works *a=new works[n];
input(a,n);
fcfs(a,n);
cout<<"\n";
sjf(a,n);
cout<<"\n";
hrf(a,n);
delete a;
return 0;
}
void input(works *p,int n)
{
cout<<"请输入作业信息: "<<endl<<endl;
for(int i=0;i<n;i++)
{
cout<<"作业名: ";
cin>>p[i].name ;
cout<<"到达时间: ";
cin>>p[i].ctime ;
cout<<"服务时间: ";
cin>>p[i].stime ;
cout<<"\n";
}
}
void datap(works *p,int n)
{
sumztime=sumdtime=0;
p[0].ftime =p[0].ctime +p[0].stime ;
for(int i=1;i<n;i++)
{
p[i].ftime=p[i-1].ftime+p[i].stime;
}
for(int j=0;j<n;j++)
{
p[j].ztime =p[j].ftime -p[j].ctime ;
p[j].dtime =p[j].ztime /p[j].stime ;
sumztime+=p[j].ztime;
sumdtime+=p[j].dtime;
}
avgztime=sumztime/n;
avgdtime=sumdtime/n;
}
void output(works *p,int n)
{
cout<<"作业调度顺序: ";
for(int k=0;k<n;k++)
{
cout<<p[k].name <<" ";
}
cout<<"\n";
cout<<"平均周转时间="<<avgztime<<endl;
cout<<"平均带权周转时间="<<avgdtime<<endl;
}
void sort(works *p,int n)
{
for(int i=n-1;i>=1;i--)
for(int j=0;j<i;j++)
if(p[j].ctime >p[j+1].ctime )
{
works temp;
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
}
void fcfs(works *p,int n)
{
sort(p,n);
datap(p,n);
cout<<"先来先服务算法"<<endl;
output(p,n);
}
void sjf(works *p,int n)
{
sort(p,n);
for(int i=0;i<n-1;i++)
{
int k=0;
if(i==0)
p[i].ftime =p[i].ctime +p[i].stime ;
else
p[i].ftime =p[i].stime +p[i-1].ftime ;
for(int j=i+1;j<n;j++)
{
if(p[j].ctime<=p[i].ftime )
k++;
}
double minstime=p[i+1].stime ;
int ps=i+1;
for(int m=i+1;m<i+k;m++)
{
if(p[m+1].stime <minstime)
{
minstime=p[m+1].stime ;
ps=m+1;
}
}
works temp;
temp=p[i+1];
p[i+1]=p[ps];
p[ps]=temp;
}
datap(p,n);
cout<<"短作业优先算法: "<<endl;
output(p,n);
}
void hrf(works *p,int n)
{
sort(p,n);
for(int i=0;i<n-1;i++)
{
int k=0;
if(i==0)
p[i].ftime =p[i].ctime +p[i].stime ;
else
p[i].ftime =p[i].stime +p[i-1].ftime ;
for(int j=i+1;j<n;j++)
{
if(p[j].ctime <=p[i].ftime )
k++;
}
double maxrratio=(p[i].ftime -p[i+1].ctime )/p[i+1].stime ;
int ps=i+1;
for(int m=i+1;m<i+k;m++)
{
if((p[i].ftime -p[m+1].ctime)/p[m+1].stime >=maxrratio)
{
maxrratio=(p[i].ftime -p[m+1].ctime)/p[m+1].stime;
ps=m+1;
}
}
works temp;
temp=p[i+1];
p[i+1]=p[ps];
p[ps]=temp;
}
datap(p,n);
cout<<"高响应比优先算法: "<<endl;
output(p,n);
}
3、给出测试数据和运行结果
workA={'作业名':'A','到达时间':0,'服务时间':6}
workB={'作业名':'B','到达时间':2,'服务时间':50}
workC={'作业名':'C','到达时间':5,'服务时间':20}
workD={'作业名':'D','到达时间':5,'服务时间':10}
workE={'作业名':'E','到达时间':12,'服务时间':40}
workF={'作业名':'F','到达时间':15,'服务时间':8}
先来先服务算法
调度顺序:['A', 'B', 'C', 'D', 'E', 'F'] 周转时间:74.1667 带权周转时间:5.2425
短作业优先算法
调度顺序:['A', 'D', 'F', 'C', 'E', 'B'] 周转时间:44.8333 带权周转时间:1.16025
高响应比优先算法
