作业调度实验报告

一、实验名称作业调度算法实验。二、实验目标已知n个作业的进入时间和估计运行时间（以分钟计）（1）单道环境下，分别用先来先服务调度算法、短作业优先调度算法、响应比高者优先调度算法，求出批作业的平均周转时间和带权平均周转时间；在多道环境（如2道）下，求出这些作业的平均周转时间和带权平均周转时间（2）就同一批次作业，分别讨论这些算法的优劣；（3）衡量同一调度算法对不同作业流的性能。三、实验环境要求1.PC机。2.Windows环境。3.CodeBlocks四、实验基本原理（1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。（2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。（3）响应比高者优先算法：是在每次调度前都要计算所有被选作业（在后备队列中）的响应比，然后选择响应比最高的作业执行。（4）两道批处理系统中最短作业优先调度算法：内存中可以进入两个作业，这两个作业按照最短作业优先调度算法调整作业执行的次序。五、数据结构设计使用一维数组来保存多个作业Jobjob[20];，采用的是顺序存储。使用queueJcb*q保存调度队列里的作业指针。structDate//时间结构体{inthour;//时间的小时intminute;//时间的分钟};structJcb//作业结构体，用来描述作业{intno;//作业编号Dateenter;//进入时间intoperation;//估计运行时间Datestart;//开始时间Dateover;//结束时间intturnover;//周转时间doubleweighted;//带权周转时间intstate=0;//标记改作业是否进入运行状态};六、流程图单道环境下算法流程图开始将JCB按作业提交的时刻的先后顺序排队调用runing函数处理调度队列作业调度队列为空？调用display函数，计算这组作业的平均周转时间及带权周转时间，并作业处理输出结果调度队首的作业投入运行结束先来先服务调度YesNo将作业一入调度队列，不断从就绪队列中选择state=0，且处理时间最短的作业放入调度队列中，直到所有作业都进入调度队列不断从就绪队列中选择state=0，且响应比最高的作业放入到调度队列中，直到所有作业都进入调度队列。最短作业优先服务最高响应比优先服务多道环境下的两道批处理系统中最短作业优先作业调度算法的流程图。开始初始化作业在内存中停留时间数组op[],是每个作业的停留时间设为将要运行的时间，即op[i]=J[i].operation.将最先进入的2个作业调入到内存，work1=0,work2=1;并改变标记状态state=1，作业处理个数记为t=2作业总数n=t?YesNo处理work1计算平均周转时间和平均带权周转时间，输出作业处理后的结果。结束Work1的预计运行时间work2的预计运行时间？处理work1，work1=work2,Work2=-1,处理work2，Op[work1]+=op[work2].Work2=-1,YesNo从剩余到达的作业中选出预计处理时间最短的作业i,t++,work2=i七、源代码#includeiostream#includestdio.h#includecstring#includealgorithm#includequeueusingnamespacestd;structDate//时间结构体{inthour;//时间的小时intminute;//时间的分钟};structJcb//作业结构体，用来描述作业{intno;//作业编号Dateenter;//进入时间intoperation;//估计运行时间Datestart;//开始时间Dateover;//结束时间intturnover;//周转时间doubleweighted;//带权周转时间intstate=0;//标记改作业是否进入运行状态};//函数声明voiddisplay(JcbJ[],intn);//输出voidruning(queueJcb*q,intn);//根据算法将就绪队列排好队后的单道作业的运行主体voidfcfs(JcbJ[],intn);//先来先服务作业调度voidsfc(JcbJ[],intn);//最短作业优先作业调度voidhrfc(JcbJ[],intn);//最高响应比作业调度voidtext(void(*dispatch)(JcbJ[],intn),JcbJ[],intn,JcbJ1[],intn1,JcbJ2[],intn2);//测试单道环境，不同批次作业，相同算法voidmulfc(JcbJ[],intn);//两道环境，内存中可以用两个作业，内存中的这两个作业按照作业长短调整作业执行的次序。//主函数，（1）同一批次作业，分别用先来先服务调度算法、短作业优先调度算法、响应比高者优先调度算法，得到批作业的平均周转时间和带权平均周转时间；（2）同一调度算法对不同作业流的调度。intmain(){intn,n1,n2;Jcbjob[20],job1[20],job2[20];FILE*p=fopen(example1.txt,r);fscanf(p,%d,&n);//批次一作业for(inti=0;in;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(inti=0;in1;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(inti=0;in2;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);return0;}//单道环境，不同批次作业，同一算法voidtext(void(*dispatch)(JcbJ[],intn),JcbJ[],intn,JcbJ1[],intn1,JcbJ2[],intn2){//单道环境，不同批次作业，同一算法cout批次一作业:endl;dispatch(J,n);cout批次二作业:endl;dispatch(J1,n1);cout批次三作业:endl;dispatch(J2,n2);}//输出voiddisplay(JcbJ[],intn){doubleT=0,W=0;printf(作业进入时间估计运行时间(分钟)开始时间结束时间周转时间(分钟)带权周转时间\n);for(inti=0;in;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);}//根据算法将就绪队列排好队后的单道作业的运行主体voidruning(queueJcb*q,intn){Jcb*j;inth,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)/60;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);}//最高响应比优先作业调度算法voidhrfc(JcbJ[],intn)//最高响应比优先作业调度算法{queueJcb*qjob;intflag[20];for(intj=0;jn;j++){flag[j]=0;}qjob.push(&J[0]);doublewait=J[0].operation+J[0].enter.hour*60+J[0].enter.minute;//记录作业流已经执行的时间intt=n-1;flag[0]=1;while(t){inti=1;while(flag[i]){i++;}for(intj=i;jn;j++){if((J[j].enter.hour*60+J[j].en