1、编写并调试一个单道处理系统的作业等待模拟程序。
作业等待算法:分别采用先来先服务(FCFS),最短作业优先(SJF)、响应比高者优先(HRN)的调度算法。
对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间,以及这组作业的平均周转时间及带权平均周转时间,以比较各种算法的优缺点。
输入样例:
作业名 提交时间 运行时间
1 5 2
2 2 5
3 2 4
FCFS:
按照提交时间排序:2,3,1
作业2 开始时间 2
运行时间 5
完成时间 7
周转时间 7 - 2 = 5
带权周转时间 5 / 5 = 1
作业 3 开始时间 7
运行时间 4
完成时间 11
周转时间 11 - 2 = 9
带权周转时间 9 / 4 = 2.25
作业 1 开始时间 11
运行时间 2
完成时间 13
周转时间 13 - 5 = 8
带权周转时间 8 / 2 = 4
SJF:
按照运行时间从短到长排序:1,3,2
作业 1 开始时间 5
运行时间 2
完成时间 7
周转时间 7 - 5 = 2
带权周转时间 2 / 2 = 1
作业3 开始时间 7
运行时间 4
完成时间 11
周转时间 11 - 2 = 9
带权周转时间 9 / 4 = 2.25
作业 2 开始时间 11
运行时间 5
完成时间 16
周转时间 16 - 2 = 14
带权周转时间 14 / 5 = 2.8
HRN:
作业1 等待时间 5 - 5 = 0 优先权 0 / 2 + 1 = 1
作业2 等待时间 5 - 2 = 3 优先权 3 / 5 + 1 = 1.6
作业3 等待时间 5 - 2 = 3 优先权 3 / 4 + 1 = 1.75
按照优先权排序:3,2,1
作业 3 开始时间 2
运行时间 4
完成时间 6
周转时间 6 - 2 = 4
带权周转时间 4 / 4 = 1
作业 2 开始时间 6
运行时间 5
完成时间 11
周转时间 11 - 2 = 9
带权周转时间 11 / 5 = 1.8
作业1 开始时间 11
运行时间 2
完成时间 13
周转时间 13 - 5 = 8
带权周转时间 8 / 2 = 4
#include <iostream> #include <cmath> using namespace std; struct Box { string ID; //作业号 double begin_time; //提交时间 double turnaround_time; //周转时间 double service_time; //要求服务时间 double finish_time; //完成时间 double Wturnaround_time; //带权周转时间 double wait_time; //等待时间 double rate; //优先权 Box& operator = (const Box& p2) //重载 = 运算符,方便排序 { this->begin_time = p2.begin_time; this->finish_time = p2.finish_time; this->service_time = p2.service_time; this->ID = p2.ID; this->turnaround_time = p2.turnaround_time; this->Wturnaround_time = p2.Wturnaround_time; this->wait_time = p2.wait_time; this->rate = p2.rate; return *this; } }; typedef struct { Box data[100]; } JCB; JCB jcb; int n; void init() //初始化作业块 { cout<<"please input the number of the process:"; cin>>n; for(int i = 0; i<n; i++) { cout<<"process ID:"; cin>>jcb.data[i].ID; cout<<jcb.data[i].ID<<"'s begin time:"; cin>>jcb.data[i].begin_time; cout<<jcb.data[i].ID<<"'s service time:"; cin>>jcb.data[i].service_time; } for(int i = 0; i<n-1; i++) //按照提交时间从前到后排序,小的在前 { for(int j = i+1; j<n; j++) { if(jcb.data[i].begin_time > jcb.data[j].begin_time) swap(jcb.data[i],jcb.data[j]); } } for(int i = 0; i<n-1; i++) //提交时间一样,序号小的排前面 { for(int j = i+1; j<n; j++) { if(jcb.data[i].begin_time == jcb.data[j].begin_time && jcb.data[i].ID > jcb.data[j].ID) swap(jcb.data[i],jcb.data[j]); } } } void FCFS() //先来先服务 { double bt = jcb.data[0].begin_time; double gtt = 0; double gwtt = 0; double real_begin; cout<<"ID "<<"real begin time "<<"begin time "<<"turnaround time "<<"finish time "<<"wighted turnaround time"<<endl; for(int i = 0; i<n; i++) { real_begin = bt; //真实开始时间 jcb.data[i].finish_time = real_begin + jcb.data[i].service_time; //完成时间 = 开始时间 + 服务时间 jcb.data[i].turnaround_time = jcb.data[i].finish_time - jcb.data[i].begin_time; //周转时间 = 完成时间 - 提交时间 jcb.data[i].Wturnaround_time = jcb.data[i].turnaround_time/jcb.data[i].service_time; //带权周转时间 = 周转时间/服务时间 cout<<jcb.data[i].ID<<" "<<real_begin<<" "<<jcb.data[i].begin_time <<" "<<jcb.data[i].turnaround_time<<" "<<jcb.data[i].finish_time <<" "<<jcb.data[i].Wturnaround_time<<endl; bt = jcb.data[i].finish_time; //下一个作业的开始时间 gtt += jcb.data[i].turnaround_time; //总周转时间 gwtt += jcb.data[i].Wturnaround_time; //总带权周转时间 } cout<<"group's turnaround time :"<<gtt/n<<endl; cout<<"group's wighted turnaround time :"<<gwtt/n<<endl; } void SJF() //短作业优先 { double bt = 0; double gtt = 0; double gwtt = 0; double real_begin; cout<<"ID "<<"real begin time "<<"begin time "<<"turnaround time "<<"finish time "<<"wighted turnaround time"<<endl; for(int i = 0; i<n-1; i++) //按照服务时间从小到大排序 for(int j = i; j<n; j++) if(jcb.data[i].service_time > jcb.data[j].service_time) swap(jcb.data[i],jcb.data[j]); for(int i = 0; i<n-1; i++) { for(int j = i+1; j<n; j++) { if(jcb.data[i].service_time == jcb.data[j].service_time && jcb.data[i].ID > jcb.data[j].ID) swap(jcb.data[i],jcb.data[j]); } } bt = jcb.data[0].begin_time; for(int i = 0; i<n; i++) { real_begin = bt; jcb.data[i].finish_time = real_begin + jcb.data[i].service_time; jcb.data[i].turnaround_time = jcb.data[i].finish_time - jcb.data[i].begin_time; jcb.data[i].Wturnaround_time = jcb.data[i].turnaround_time/jcb.data[i].service_time; cout<<jcb.data[i].ID<<" "<<real_begin<<" "<<jcb.data[i].begin_time <<" "<<jcb.data[i].turnaround_time<<" "<<jcb.data[i].finish_time <<" "<<jcb.data[i].Wturnaround_time<<endl; bt = jcb.data[i].finish_time; gtt += jcb.data[i].turnaround_time; gwtt += jcb.data[i].Wturnaround_time; } cout<<"group's turnaround time :"<<gtt/n<<endl; cout<<"group's wighted turnaround time :"<<gwtt/n<<endl; } void HRN() //高响应比优先 { double bt = 0; double gtt = 0; double gwtt = 0; double real_begin; cout<<"ID "<<"real begin time "<<"begin time "<<"turnaround time "<<"finish time "<<"wighted turnaround time"<<endl; for(int i = 0; i<n; i++) { jcb.data[i].wait_time = jcb.data[n-1].begin_time - jcb.data[i].begin_time; //等待时间 = 作业最后提交时间 - 提交时间 jcb.data[i].rate = jcb.data[i].wait_time/jcb.data[i].service_time+1; //高响应比 = 等待时间 / 服务时间 + 1 } for(int i = 0; i<n-1; i++) for(int j = i; j<n; j++) if(jcb.data[i].rate < jcb.data[j].rate) swap(jcb.data[i],jcb.data[j]); bt = jcb.data[0].begin_time; for(int i = 0; i<n; i++) { real_begin = bt; jcb.data[i].finish_time = real_begin + jcb.data[i].service_time; jcb.data[i].turnaround_time = jcb.data[i].finish_time - jcb.data[i].begin_time; jcb.data[i].Wturnaround_time = jcb.data[i].turnaround_time/jcb.data[i].service_time; cout<<jcb.data[i].ID<<" "<<real_begin<<" "<<jcb.data[i].begin_time <<" "<<jcb.data[i].turnaround_time<<" "<<jcb.data[i].finish_time <<" "<<jcb.data[i].Wturnaround_time<<endl; bt = jcb.data[i].finish_time; gtt += jcb.data[i].turnaround_time; gwtt += jcb.data[i].Wturnaround_time; } cout<<"group's turnaround time :"<<gtt/n<<endl; cout<<"group's wighted turnaround time :"<<gwtt/n<<endl; } int main() { int k = 0; while(1) { cout<<"*****************************"<<endl; cout<<" 1.FCFS"<<endl<<" 2.SJF"<<endl<<" 3.HRN"<<endl; cout<<"*****************************"<<endl; cout<<"please choose:"; cin>>k; init(); switch(k) { case 1: FCFS(); break; case 2: SJF(); break; case 3: HRN(); break; default: break; } } return 0; }