一、实验名称
作业调度算法实验。 二、实验目标
已知n个作业的进入时间和估计运行时间（以分钟计） （1）单道环境下，分别用先来先服务调度算法、短作业优先调度算法、响应比高者优先调度算法，求出批作业的平均周转时间和带权平均周转时间； 在多道环境（如2道）下，求出这些作业的平均周转时间和带权平均周转时间
（2）就同一批次作业，分别讨论这些算法的优劣； （3）衡量同一调度算法对不同作业流的性能。 三、实验环境要求 1.PC机。
2.Windows环境。 3.CodeBlocks 四、实验基本原理
（1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。
（2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。
（ 3）响应比高者优先算法：是在每次调度前都要计算所有被选作
!-
业（在后备队列中）的响应比，然后选择响应比最高的作业执行。 （4）两道批处理系统中最短作业优先调度算法：内存中可以进入两个作业，这两个作业按照最短作业优先调度算法调整作业执行的次序。
五、数据结构设计
使用一维数组来保存多个作业Job job[20];，采用的是顺序存储。 使用queue int hour;//时间的小时 int minute;//时间的分钟 }; struct Jcb//作业结构体，用来描述作业 { int no;//作业编号 Date enter;//进入时间 int operation;//估计运行时间 Date start;//开始时间 Date over;//结束时间 int turnover;//周转时间 double weighted;//带权周转时间 int state=0;//标记改作业是否进入运行状态 !- }; 六、流程图 单道环境下算法流程图 开始先来先服务调度最高响应比优先服务最短作业优先服务将JCB按作业提交的时刻的先后顺序排队将作业一入调度队列，不断从就绪队列中选择state=0，且处理时间最短的作业放入调度队列中，直到所有作业都进入调度队列不断从就绪队列中选择state=0，且响应比最高的作业放入到调度队列中，直到所有作业都进入调度队列。调用runing函数处理调度队列作业调度队首的作业投入运行No调度队列为空？Yes调用display函数，计算这组作业的平均周转时间及带权周转时间，并作业处理输出结果结束 !- 多道环境下的两道批处理系统中最短作业优先作业调度算法的流程图。 !- 开始初始化作业在内存中停留时间数组op[], 是每个作业的停留时间设为将要运行的时间，即op[i]=J[i].operation. 将最先进入的2个作业调入到内存，work1=0,work2=1;并改变标记状态state=1，作业处理个数记为 t=2作业总数n>=t?No处理work1YesWork1的预计运行时间 !- #include 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 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\ fscanf(p, \"%d\ //批次一作业 for(int i=0;i \"%d%d%d\ &job[i].enter.hour, &job[i].enter.minute, &job[i].operation); } //批次二作业 fscanf(p, \"%d\ for(int i=0;i \"%d%d%d\ &job1[i].enter.hour, &job1[i].enter.minute, &job1[i].operation); } //批次三作业 fscanf(p, \"%d\ for(int i=0;i !- fscanf(p, \"%d%d%d\&job2[i].enter.hour, &job2[i].enter.minute, &job2[i].operation); } fclose(p); printf(\"\\n--------------------单道环境,同一批次作业,不同算法----------------------\\n\"); cout<<\"先来先服务作业调度：\"< printf(\"------------------------单道环境，不同批次作业，同一算 法--------------------\\n\"); cout<<\".............................先来先服务作业调 度................................\"< cout<<\".............................最短优先服务作业调 度..............................\"< !- cout<<\".............................最高响应比优先服务作业调 度:.......................\"< 道 环 境 text(hrfc, job,n,job1,n1,job2,n2); ----------------------------------------\\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<<\"批次一作业:\"< dispatch(J1,n1); cout<<\"批次三作业:\"< double T=0,W=0; printf(\" 作业 进入时间 估计运行时间(分钟) 开始时间 结束时间 周转时间(分钟) 带权周转时间\\n\"); for(int i=0;i 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\ %2d:%02d\ %-14d\ %2d:%02d\ %2d:%02d\ %-6d\%-5.2f\\\n\ J[i].no,J[i].enter.hour, J[i].start.hour, + J[i].enter.minute,J[i].operation, !- J[i].start.minute,J[i].over.hour, J[i].turnover,J[i].weighted ); } T/=n; W/=n; J[i].over.minute, printf(\"作业平均周转时间 T=%.2lf 分钟\\n\ printf(\"作业带权平均周转时间 W=%.3lf\\n\\n\\n\} //根据算法将就绪队列排好队后的单道作业的运行主体 void runing( queue 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)/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); } //最高响应比优先作业调度算法 void hrfc(Jcb J[],int n)//最高响应比优先作业调度算法 { + !- queue int flag[20]; for(int j=0;j qjob.push(&J[0]); double wait=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 { if( (J[j].enter.hour*60+J[j].enter.minute)>wait) break;//如果这个作业还没来到，则停止继续比较,只考虑已经进入就绪队列的作业 if(flag[j]==0 ) { double waiti=wait-J[i].enter.hour*60-J[i].enter.minute;//作业J[i]的等待时间 double waitj=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 runing(qjob,n); display(J,n); } //最短作业优先作业调度算法 void sfc(Jcb J[],int n)//最短作业优先作业调度算法 { queue !- time=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 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); } //两道环境，内存中可以用两个作业，内存中的这两个作业按照作业 void mulfc(Jcb J[],int n)//两道环境，内存中可以用两个作业，内存中的这两个作业按照作业长短调整作业执行的次序。 {//至少有两个作业。 cout<<\"两道批处理系统中最短作业优先作业调度算法\"< !- for(i=0;i work1=0; J[0].state=1; J[0].start.hour=J[0].enter.hour; J[0].start.minute=J[0].enter.minute; work2=1; int h=J[0].enter.hour; int m=J[0].enter.minute; int work=work1; int time; int t=2; while(t<=n) { !- if(J[work1].operation>J[work2].operation) {//第二个work2进入内存的作业的执行时间短于work1，就暂停执行work1,转而执行work2. op[work1]+=J[work2].operation; if(t==2) {//第二个进入内存的，且运行时间较已在内存中的短，则作业开始时间为进入的时间 J[work2].start.hour=J[work2].enter.hour; J[work2].start.minute=J[work2].enter.minute; } else {//从第三个进入内存的作业，且执行时间比当前在内存中的执行时间短，则开始时间为上一个作业的结束时间 J[work2].start.hour=h; J[work2].start.minute=m; } J[work2].over.hour=J[work2].start.hour+(J[work2].start.minute+op[work2])/60; J[work2].over.minute=(J[work2].start.minute+op[work2])%6 !- 0; h=J[work2].over.hour; m=J[work2].over.minute; time=h*60+m; work2=-1;//改作业执行完毕 } else {//第二个work2进入内存的作业的执行时间较长，所以仍然执行开始就在内存的作业work1,知道work1执行完毕 J[work1].over.hour=J[work1].start.hour+(J[work1].start.minute+op[work1])/60; J[work1].over.minute=(J[work1].start.minute+op[work1])%60; h=J[work2].over.hour; m=J[work2].over.minute; !- time=h*60+m; J[work2].start.hour=h; J[work2].start.minute=m; work1=work2; work2=-1; } int w; int i=1; while(J[i].state==1) { i++; } w=i; for(int j=w; j break;//如果这个作业还没来到，则停止继续比较,只考虑已经进入就绪队列的作业 } if(J[j].state==0 && (J[w].operation > J[j].operation)) w=j; !- work2=w;//第二个进入内存的作业 t++; J[work2].state=1; } //最后剩下work1作业 J[work1].over.hour=J[work1].start.hour+(J[work1].start.minute+op[work1])/60; J[work1].over.minute=(J[work1].start.minute+op[work1])%60; display(J,n); } 八、实验结果 （1）在单道环境下，已知n个作业的进入时间和估计运行时间（以分钟计），得到的每一个作业的开始时间、结束时间、周转时间、带权周转时间，以及这些作业的平均周转时间和带权平均周转时间； !- （2）同一调度算法对不同作业流的性能，每个算法有三个测试作业流 先来先服务作业调度 !- 最短优先服务作业调度 !- 最高响应比优先服务作业调度 !- （3）在2道环境下，已知n个作业的进入时间和估计运行时间（以分钟计），得到的每一个作业的开始时间、结束时间、周转时间、带权周转时间，以及这些作业的平均周转时间和带权平均周转时间。 !- 九、结果分析 （1）单道环境下，对于批次一作业流。 先来先服务的作业调度的作业平均周转时间T=112.5分钟 最短作业优先服务作业调度的作业平均周转时间T=90分钟 最高相应比优先服务作业调度的作业平均周转时间T=102.5 分钟. 可见对于批次一作业，最短作业优先作业调度算法效率最高。 （2）单道环境下。 2.1对于3个不同批次作业，先来先服务的作业调度 批次一，作业带权平均周转时间 W=4.975 批次二，作业带权平均周转时间 W=4.188 批次三，作业带权平均周转时间 W=2.433 可见，先来先服务的作业调度，对于批次三作业的效率最高。 2.2对于3个不同批次作业，最短优先服务的作业调度 批次一，作业带权平均周转时间 W=4.975 批次二，作业带权平均周转时间 W=2.875 批次三，作业带权平均周转时间 W=2.317 !- 可见，最短优先服务的作业调度，对于批次三作业的效率最高。 2.3对于3个不同批次作业，最高响应比优先服务的作业调度 批次一，作业带权平均周转时间 W=3.775 批次二，作业带权平均周转时间 W=3.250 批次三，作业带权平均周转时间 W=2.317 可见，最高响应比优先服务的作业调度，对于批次二作业的效率最高 十、本次实验体会 1. 先来先服务的作业调度，实现最简单。 2. 对于同批次作业，最短作业的效率最高。 3. 最高响应比优先作业调度，既照顾了短作业，又照顾了作业到 来的顺序，不会使长作业长期得不到运行，但是每次调度下一个作业前要计算剩余到来作业的响应比，增加了系统的开销。 4. 两道批处理系统中最短作业优先作业调度算法，在实现时，我 默认为作业之间没有时间空余，默认在处理一个作业流时处理器一直处于运行状态。所以代码有漏洞，考虑的也不是很全面。 5. 开始时对作业调度不是很那么地清晰，通过做这个实验，现在 对操作系统的作业调度有了清晰的理解，感觉在这个过程中自己就是充当了调度员的角色。开始写好的代码比较繁杂，于是写了display 和running函数来简化代码。 6. 最初忽略了作业的进入时间问题，和同学讨论了一下，意见不太一致，但我觉得这个问题是应该考虑的。 !- 7. 实验代码修改了好多次，一些细小的问题，如输入、输出和如何简化代码等比较耗费时间。通过这个实验，发现自己的C\\C++功底太差了，做实验时可谓是边做边翻书。通过这个实验，也回顾了一下C\\C++的一些基础知识。 十一、参考资料 (1) 郭浩志 社 (2) 庞丽萍 西安电子科技大学出版华中科技大学出版社 《计算机软件实践教程》 《计算机操作系统》 因篇幅问题不能全部显示，请点此查看更多更全内容