实现作业调度的三种典型算法：先来先服务；短作业优先；高响应比优先，程序会给出算法的平均周转时间和平均带权周转时间。
实现算法的大致过程如下：
主要算法流程图
代码如下：
#include<iostream>
using namespace std;
struct jobs {
char name;
double inTime;
double runTime;
double finishTime;
double turnTime;
double weight;
double rratio;
};
double avgturnTime,avgweight;
void input(jobs *p,int n);
void output(jobs *p,int n);
void datap(jobs *p,int n);
void sort(jobs *p,int n);
void fcfs(jobs *p,int n);
void sjf(jobs *p,int n);
void hrf(jobs *p,int n);
int main() {
int n;
cout<<"输入作业数目：";
cin>>n;
jobs *a=new jobs[n];
input(a,n);
fcfs(a,n);
cout<<"\n";
sjf(a,n);
cout<<"\n";
hrf(a,n);
delete a;
return 0;
}
void input(jobs *p,int n) {
for(int i=0; i<n; i++) {
cout<<"请输入第"<<i+1<<"作业信息(作业名、到达时间、服务时间)："<<endl;
cin>>p[i].name>>p[i].inTime>>p[i].runTime ;
}
}
void datap(jobs *p,int n) {
avgturnTime=avgweight=0;
p[0].finishTime =p[0].inTime +p[0].runTime ;
for(int i=1; i<n; i++) {
p[i].finishTime=p[i-1].finishTime+p[i].runTime;
}
for(int j=0; j<n; j++) {
p[j].turnTime =p[j].finishTime -p[j].inTime ;
p[j].weight =p[j].turnTime /p[j].runTime ;
avgturnTime+=p[j].turnTime/n;
avgweight+=p[j].weight/n;
}
}
void output(jobs *p,int n) {
cout<<endl<<"作业名\t到达时间\t开始时间\t服务时间\t结束时间\t周转时间\t带权周转时间\n";
double stime;
for(int k=0; k<n; k++) {
if (k==0) stime=0;
else stime=p[k-1].finishTime;
cout<<""<<p[k].name<<"\t"<<p[k].inTime<<"\t\t"<<stime<<"\t\t"<<p[k].runTime<<"\t\t"<<p[k].finishTime<<"\t\t"<<p[k].turnTime<<"\t\t"<<p[k].weight<<"\n";
}
cout<<"平均周转时间="<<avgturnTime<<endl;
cout<<"平均带权周转时间="<<avgweight<<endl;
}
void sort(jobs *p,int n) {
for(int i=n-1; i>=1; i--)
for(int j=0; j<i; j++)
if(p[j].inTime >p[j+1].inTime ) {
jobs temp;
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
}
void fcfs(jobs *p,int n) {
sort(p,n);
datap(p,n);
cout<<"--先来先服务算法--";
output(p,n);
}
void sjf(jobs *p,int n) {
sort(p,n);
for(int i=0; i<n-1; i++) {
int k=0;
if(i==0)
p[i].finishTime =p[i].inTime +p[i].runTime ;
else
p[i].finishTime =p[i].runTime +p[i-1].finishTime ;
for(int j=i+1; j<n; j++) {
if(p[j].inTime<=p[i].finishTime )
k++;
}
double minrunTime=p[i+1].runTime ;
int mark=i+1;
for(int m=i+1; m<i+k; m++) {
if(p[m+1].runTime <minrunTime) {
minrunTime=p[m+1].runTime ;
mark=m+1;
}
}
jobs temp;
temp=p[i+1];
p[i+1]=p[mark];
p[mark]=temp;
}
datap(p,n);
cout<<"--短作业优先算法--";
output(p,n);
}
void hrf(jobs *p,int n) {
sort(p,n);
for(int i=0; i<n-1; i++) {
int k=0;
if(i==0)
p[i].finishTime =p[i].inTime +p[i].runTime ;
else
p[i].finishTime =p[i].runTime +p[i-1].finishTime ;
for(int j=i+1; j<n; j++) {
if(p[j].inTime <=p[i].finishTime )
k++;
}
double maxrratio=(p[i].finishTime -p[i+1].inTime )/p[i+1].runTime ;
int mark=i+1;
for(int m=i+1; m<i+k; m++) {
if((p[i].finishTime -p[m+1].inTime)/p[m+1].runTime >=maxrratio) {
maxrratio=(p[i].finishTime -p[m+1].inTime)/p[m+1].runTime;
mark=m+1;
}
}
jobs temp;
temp=p[i+1];
p[i+1]=p[mark];
p[mark]=temp;
}
datap(p,n);
cout<<"--高响应比优先算法--";
output(p,n);
}
运行的结果：
输入作业数目：6
请输入第1作业信息(作业名、到达时间、服务时间)：
A 0 6
请输入第2作业信息(作业名、到达时间、服务时间)：
B 2 50
请输入第3作业信息(作业名、到达时间、服务时间)：
C 5 20
请输入第4作业信息(作业名、到达时间、服务时间)：
D 5 10
请输入第5作业信息(作业名、到达时间、服务时间)：
E 12 40
请输入第6作业信息(作业名、到达时间、服务时间)：
F 15 8
--先来先服务算法--
作业名 到达时间 开始时间 服务时间 结束时间 周转时间 带权周转时间
A 0 0 6 6 6 1
B 2 6 50 56 54 1.08
C 5 56 20 76 71 3.55
D 5 76 10 86 81 8.1
E 12 86 40 126 114 2.85
F 15 126 8 134 119 14.875
平均周转时间=74.1667
平均带权周转时间=5.2425
--短作业优先算法--
作业名 到达时间 开始时间 服务时间 结束时间 周转时间 带权周转时间
A 0 0 6 6 6 1
D 5 6 10 16 11 1.1
F 15 16 8 24 9 1.125
C 5 24 20 44 39 1.95
E 12 44 40 84 72 1.8
B 2 84 50 134 132 2.64
平均周转时间=44.8333
平均带权周转时间=1.6025
--高响应比优先算法--
作业名 到达时间 开始时间 服务时间 结束时间 周转时间 带权周转时间
A 0 0 6 6 6 1
D 5 6 10 16 11 1.1
C 5 16 20 36 31 1.55
F 15 36 8 44 29 3.625
B 2 44 50 94 92 1.84
E 12 94 40 134 122 3.05
平均周转时间=48.5
平均带权周转时间=2.0275
网友评论