作业调度实验报告

一、实验名称作业调度算法实验。

二、实验目标已知n个作业的进入时间和估计运行时间（以分钟计）（1）单道环境下，分别用先来先服务调度算法、短作业优先调度算法、响应比高者优先调度算法，求出批作业的平均周转时间和带权平均周转时间；在多道环境（如2道）下，求出这些作业的平均周转时间和带权平均周转时间（2）就同一批次作业，分别讨论这些算法的优劣；（3）衡量同一调度算法对不同作业流的性能。

三、实验环境要求1.PC机。

2.Windows环境。

3.CodeBlocks四、实验基本原理（1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。

（2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。

（3）响应比高者优先算法：是在每次调度前都要计算所有被选作业（在后备队列中）的响应比，然后选择响应比最高的作业执行。

（4）两道批处理系统中最短作业优先调度算法：内存中可以进入两个作业，这两个作业按照最短作业优先调度算法调整作业执行的次序。

五、数据结构设计使用一维数组来保存多个作业Job job[20];，采用的是顺序存储。

使用queue<Jcb *> q保存调度队列里的作业指针。

struct Date//时间结构体{int hour;//时间的小时int minute;//时间的分钟};struct Jcb//作业结构体，用来描述作业{int no;//作业编号Date enter;//进入时间int operation;//估计运行时间Date start;//开始时间Date over;//结束时间int turnover;//周转时间double weighted;//带权周转时间int state=0;//标记改作业是否进入运行状态};六、流程图单道环境下算法流程图多道环境下的两道批处理系统中最短作业优先作业调度算法的流程图。

七、源代码#include<iostream> #include<stdio.h>#include<cstring>#include<algorithm>#include<queue>using namespace std;struct Date//时间结构体{int hour;//时间的小时int minute;//时间的分钟};struct Jcb//作业结构体，用来描述作业{int no;//作业编号Date enter;//进入时间int operation;//估计运行时间Date start;//开始时间Date over;//结束时间int turnover;//周转时间double weighted;//带权周转时间int state=0;//标记改作业是否进入运行状态};//函数声明void display(Jcb J[],int n);//输出void runing( queue<Jcb *> q,int n);//根据算法将就绪队列排好队后的单道作业的运行主体void fcfs( Jcb J[],int n);//先来先服务作业调度void sfc(Jcb J[],int n);//最短作业优先作业调度void hrfc(Jcb J[],int n);//最高响应比作业调度void text(void (*dispatch)(Jcb J[], int n),Jcb J[],int n,Jcb J1[],int n1, Jcb J2[],int n2);//测试单道环境，不同批次作业，相同算法void mulfc(Jcb J[],int n);//两道环境，内存中可以用两个作业，内存中的这两个作业按照作业长短调整作业执行的次序。

//主函数，（1）同一批次作业，分别用先来先服务调度算法、短作业优先调度算法、响应比高者优先调度算法，得到批作业的平均周转时间和带权平均周转时间；（2）同一调度算法对不同作业流的调度。

int main(){int n,n1,n2;Jcb job[20],job1[20],job2[20];FILE*p=fopen("example1.txt", "r");fscanf(p, "%d", &n);//批次一作业for(int i=0;i<n;i++){job[i].no=i+1;fscanf(p, "%d%d%d", &job[i].enter.hour, &job[i].enter.minute, &job[i].operation);}//批次二作业fscanf(p, "%d", &n1);for(int i=0;i<n1;i++){job1[i].no=i+1;fscanf(p, "%d%d%d", &job1[i].enter.hour, &job1[i].enter.minute, &job1[i].operation);}//批次三作业fscanf(p, "%d", &n2);for(int i=0;i<n2;i++){job2[i].no=i+1;fscanf(p, "%d%d%d", &job2[i].enter.hour, &job2[i].enter.minute, &job2[i].operation);}fclose(p);printf("\n--------------------单道环境,同一批次作业,不同算法----------------------\n");cout<<"先来先服务作业调度："<<endl;fcfs(job,n);cout<<"最短时间优先服务作业调度："<<endl;sfc(job,n);cout<<"最高响应比优先作业调度算法"<<endl;hrfc(job,n);printf("\n\n");printf("------------------------单道环境，不同批次作业，同一算法--------------------\n");cout<<".............................先来先服务作业调度................................"<<endl;text(fcfs, job,n,job1,n1,job2,n2);cout<<".............................最短优先服务作业调度.............................."<<endl;text(sfc, job,n,job1,n1,job2,n2);cout<<".............................最高响应比优先服务作业调度:......................."<<endl;text(hrfc, job,n,job1,n1,job2,n2);printf("-------------------------------两道环境----------------------------------------\n");mulfc(job1,n);printf("-------------------------------------------------------------------------------\n");return 0;}//单道环境，不同批次作业，同一算法void text(void (*dispatch)(Jcb J[], int n),Jcb J[],int n,Jcb J1[],int n1, Jcb J2[],int n2){//单道环境，不同批次作业，同一算法cout<<"批次一作业:"<<endl;dispatch(J,n);cout<<"批次二作业:"<<endl;dispatch(J1,n1);cout<<"批次三作业:"<<endl;dispatch(J2,n2);}//输出void display(Jcb J[],int n){double T=0,W=0;printf(" 作业进入时间估计运行时间(分钟) 开始时间结束时间周转时间(分钟) 带权周转时间\n");for(int i=0;i<n;i++){J[i].turnover=(J[i].over.hour*60 + J[i].over.minute)-(J[i].enter.hour*60+J[i].enter.minute);T+=J[i].turnover;J[i].weighted=J[i].turnover/(double)J[i].operation;W+=J[i].weighted;printf("Job%2d\t %2d:%02d\t %-14d\t %2d:%02d\t %2d :%02d\t %-6d\t%-5.2f\t\n", J[i].no,J[i].enter.hour, J[i].enter.minute,J[i].operation, J[i].start.hour,J[i].start.minute,J[i].over.hour, J[i].over.minute, J[i].turnover,J[i].weighted );}T/=n;W/=n;printf("作业平均周转时间T=%.2lf 分钟\n", T);printf("作业带权平均周转时间W=%.3lf\n\n\n",W);}//根据算法将就绪队列排好队后的单道作业的运行主体void runing( queue<Jcb *> q,int n){Jcb *j;int h,m;j=q.front();h=j->enter.hour;m=j->enter.minute;while (!q.empty()){j=q.front();q.pop();j->start.hour=h;j->start.minute=m;j->over.hour=j->start.hour+(j->start.minute+j->operation)/6 0;j->over.minute=(j->start.minute+j->operation)%60;j->turnover=(j->over.hour*60 + j->over.minute)-(j->enter.hour*60+j->enter.minute);j->weighted=j->turnover/(double)j->operation;h=j->over.hour;m=j->over.minute;}// display(J,t);}//最高响应比优先作业调度算法void hrfc(Jcb J[],int n)//最高响应比优先作业调度算法{queue<Jcb *> qjob;int flag[20];for(int j=0;j<n;j++){flag[j]=0;}qjob.push(&J[0]);doublewait=J[0].operation+J[0].enter.hour*60+J[0].enter.minute;//记录作业流已经执行的时间int t=n-1;flag[0]=1;while(t){int i=1;while(flag[i]){i++;}for(int j=i; j<n ;j++){if( (J[j].enter.hour*60+J[j].enter.minute)>wait)break;//如果这个作业还没来到，则停止继续比较,只考虑已经进入就绪队列的作业if(flag[j]==0 ){doublewaiti=wait-J[i].enter.hour*60-J[i].enter.minute;//作业J[i]的等待时间doublewaitj=wait-J[j].enter.hour*60-J[j].enter.minute;if((waiti/J[i].operation)<(waitj/J[j].operation))i=j;}}qjob.push(&J[i]);flag[i]=1;wait+=J[i].operation;t--;}runing(qjob,n);display(J,n);}void fcfs( Jcb J[],int n)//先来先服务作业调度算法{queue<Jcb *> qjob;for(int i=0;i<n;i++){qjob.push(&J[i]);}runing(qjob,n);display(J,n);}//最短作业优先作业调度算法void sfc(Jcb J[],int n)//最短作业优先作业调度算法{queue<Jcb *> qjob;qjob.push(&J[0]);inttime=J[0].enter.hour*60+J[0].enter.minute+J[0].operation;/ /上一个作业的结束时间J[0].state=1;int t=n-1;while(t){int i=1;while(J[i].state){i++;}for(int j=i;j<n;j++){if( (J[j].enter.hour*60+J[j].enter.minute)>time)break;//如果这个作业还没来到，则停止继续比较,只考虑已经进入就绪队列的作业if(J[j].state==0 && (J[i].operation>J[j].operation)){i=j;}}qjob.push(&J[i]);J[i].state=1;time+=J[i].operation;t--;}runing(qjob,n);display(J,n);}//两道环境，内存中可以用两个作业，内存中的这两个作业按照作业void mulfc(Jcb J[],int n)//两道环境，内存中可以用两个作业，内存中的这两个作业按照作业长短调整作业执行的次序。