武汉理工大学操作系统处理机调度实验报告

1学生学号Xxx实验课成绩学生实验报告书实验课程名称操作系统C开课学院计算机科学与技术学院指导教师姓名xxx学生姓名xxx学生专业班级xxxx2016--2017学年第1学期1实验课程名称：操作系统C实验项目名称处理机调度报告成绩实验者陈硕专业班级计算机zy1401组别同组者完成日期2016年11月25日第一部分：实验分析与设计（可加页）一、实验目的和要求1.目的掌握处理机调度的相关内容对进程调度算法有深入的理解2.要求模拟实现进程调度功能任选一种计算机高级语言编程实现选择1-2种进程调度算法，例如：先来先服务、短进程优先、最高响应比优先、时间片轮转、优先级法等能够输入进程的基本信息，例如进程名、到达时间和预估运行时间等根据选择的调度算法显示进程的调度顺序显示完成调度后每个进程的开始时间、完成时间和周转时间、带权周转时间计算平均周转时间和平均带权周转时间二、分析与设计1.实验原理分析(1)先来先服务调度算法的基本原理按照作业提交/进程变为就绪状态放的先后次序，调入系统或分派CPU，(即调度程序每次选择的作业或进程是等待时间最久的，而不管其运行时间的长短。)(2)短进程优先调度算法的基本原理对预计执行时间短的作业（进程）优先处理。通常后来的短作业不抢先正在执行的作业。(3)优先级调度算法的基本原理对优先级高的作业（进程）优先处理。可分为抢占式和非抢占式。本实验采用非抢占式。(4)最高响应比优先调度算法的基本原理响应比优先算法是介于FCFS算法和SJF算法之间的一种折中算法，同时考虑每个作业的等待时间和估计需要运行的时间，从中选出响应比最高的作业投入运行。依据上述的实验目的与要求，可导出实现处理机调度的流程为：①将作业信息保存到结构体数组中②设计不同的进程调度算法2③用while进行循环控制选择不同的算法2.数据结构的设计记录不同作业信息的结构体数组。structnodejob[100];记录作业/进程详细信息的结构体typedefstructnode{stringname;doublesubmit;//提交时间doublestart;//开始时间doublerun;//运行时间doubleend;//完成时间doubleTi;//周转时间doubleWi;//带权周转时间doubleH;//响应比intpriority;//优先级}*work;3.核心算法设计(1)按提交时间进行排序的算法Input：workp//指向作业的指针intN//作业的个数Process：voidsort(workp,intN){for(inti=0;iN;i++){3for(intj=0;ji;j++){if(p[i].submitp[j].submit){nodetemp;temp=p[i];p[i]=p[j];p[j]=temp;}}}}（2）先来先服务算法Input：workp//指向作业的指针intN//作业的个数Process：voidFCFS(workp,intN){sort(p,N);//调用排序算法for(k=0;kN;k++){if(k==0){p[k].start=p[k].submit;p[k].end=p[k].start+p[k].run;p[k].Ti=p[k].end-p[k].submit;p[k].Wi=p[k].Ti/p[k].run;}else{if(p[k].submitp[k-1].end)//选择在作业完成之前已将提交了的作业的计算方法{p[k].start=p[k-1].end;p[k].end=p[k].start+p[k].run;p[k].Ti=p[k].end-p[k].submit;p[k].Wi=p[k].Ti/p[k].run;}else{p[k].start=p[k].submit;//作业完成时还没有提交的作业计算方法p[k].end=p[k].start+p[k].run;p[k].Ti=p[k].end-p[k].submit;p[k].Wi=p[k].Ti/p[k].run;4}}sumTi=sumTi+p[k].Ti;sumWi=sumWi+p[k].Wi;}T=sumTi/N;//计算平均周转时间W=sumWi/N;//计算平均带权周转时间output(p,N);//调用输出函数}(3)短进程优先算法Input：workp//指向作业的指针intN//作业的个数Process：voidSJF(workp,intN){sort(p,N);//按提交时间排序for(k=0;kN;k++){if(k==0){p[k].start=p[k].submit;p[k].end=p[k].start+p[k].run;p[k].Ti=p[k].end-p[k].submit;p[k].Wi=p[k].Ti/p[k].run;for(n=k+1;nN;n++){if(p[n].submitp[k].end){break;}}for(m=k+1;mn;m++){for(intl=k+1;lm;l++){if(p[m].runp[l].run){nodetemp;temp=p[m];p[m]=p[l];p[l]=temp;}}}5}else{if(p[k].submitp[k-1].end){p[k].start=p[k-1].end;p[k].end=p[k].start+p[k].run;p[k].Ti=p[k].end-p[k].submit;p[k].Wi=p[k].Ti/p[k].run;}else{p[k].start=p[k].submit;p[k].end=p[k].start+p[k].run;p[k].Ti=p[k].end-p[k].submit;p[k].Wi=p[k].Ti/p[k].run;}for(n=k+1;nN;n++){if(p[n].submitp[k].end){break;}}for(m=k+1;mn;m++){for(intl=k+1;lm;l++){if(p[m].runp[l].run){nodetemp;temp=p[m];p[m]=p[l];p[l]=temp;}}}}sumTi=sumTi+p[k].Ti;sumWi=sumWi+p[k].Wi;}T=sumTi/N;W=sumWi/N;output(p,N);6}(4)最高响应比优先算法Input：workp//指向作业的指针intN//作业的个数Process：voidHRN(workp,intN){sort(p,N);//按提交时间排序for(k=0;kN;k++){if(k==0){p[k].start=p[k].submit;p[k].end=p[k].start+p[k].run;p[k].Ti=p[k].end-p[k].submit;p[k].Wi=p[k].Ti/p[k].run;for(n=k+1;nN;n++){if(p[n].submitp[k].end){break;}}inty=k+1;for(intx=k+1;xn;x++){p[x].H=1.00+((p[y-1].end-p[x].submit)/p[x].run);//注意在计算响应比时不能用变量X进行循环计算。}for(m=k+1;mn;m++){for(intl=k+1;lm;l++){if(p[m].Hp[l].H){nodetemp;temp=p[m];p[m]=p[l];p[l]=temp;}}}}else{7if(p[k].submitp[k-1].end){p[k].start=p[k-1].end;p[k].end=p[k].start+p[k].run;p[k].Ti=p[k].end-p[k].submit;p[k].Wi=p[k].Ti/p[k].run;}else{p[k].start=p[k].submit;p[k].end=p[k].start+p[k].run;p[k].Ti=p[k].end-p[k].submit;p[k].Wi=p[k].Ti/p[k].run;}for(n=k+1;nN;n++){if(p[n].submitp[k].end){break;}}inty=k+1;for(intx=k+1;xn;x++){p[x].H=1.00+((p[y-1].end-p[x].submit)/p[x].run);}for(m=k+1;mn;m++){for(intl=k+1;lm;l++){if(p[m].Hp[l].H){nodetemp;temp=p[m];p[m]=p[l];p[l]=temp;}}}}sumTi=sumTi+p[k].Ti;sumWi=sumWi+p[k].Wi;}T=sumTi/N;W=sumWi/N;8output(p,N);}(5)优先级响应算法Input：workp//指向作业的指针intN//作业的个数Process：voidPS(workp,intN)//优先级调度算法{sort(p,N);//按提交时间排序for(k=0;kN;k++){if(k==0)//第一个提交的作业单独计算相关调度信息{p[k].start=p[k].submit;p[k].end=p[k].start+p[k].run;p[k].Ti=p[k].end-p[k].submit;p[k].Wi=p[k].Ti/p[k].run;/*按优先级进行排序*/for(n=k+1;nN;n++）{if(p[n].submitp[k].end){break;}}for(m=k+1;mn;m++){for(intl=k+1;lm;l++){if(p[m].priorityp[l].priority){nodetemp;temp=p[m];p[m]=p[l];p[l]=temp;}}}}else{if(p[k].submitp[k-1].end){p[k].start=p[k-1].end;p[k].end=p[k].start+p[k].run;p[k].Ti=p[k].end-p[k].submit;9p[k].Wi=p[k].Ti/p[k].run;}else{p[k].start=p[k].submit;p[k].end=p[k].start+p[k].run;p[k].Ti=p[k].end-p[k].submit;p[k].Wi=p[k].Ti/p[k].run;}//进行作业相关调度信息的计算/*按优先级进行排序*/for(n=k+1;nN;n++){if(p[n].submitp[k].end){break;}}for(m=k+1;mn;m++){for(intl=k+1;lm;l++){if(p[m].priorityp[l].priority){nodetemp;temp=p[m];p[m]=p[l];p[l]=temp;}}}}sumTi=sumTi+p[k].Ti;sumWi=sumWi+p[k].Wi;}T=sumTi/N;W=sumWi/N;output(p,N);}3.测试用例设计（1）10（2）三、主要仪器设备及耗材1．安装了WindowsXP或Windows7或其它版本的Windows操作系统的PC机1台2．PC机系统上安装了MicrosoftVisualStudio2010开发环境第二部分：实验过程和结果（可加页）一、实现说明在VS2010中创建一个算法调度项目，对于不同的调度算法分别进行算法设计，对于算法的设计要特别注意作业的提交情况，实验中存储作业信息的结构体是相同的，采用结构体数组保存全部的作业，每次通过对结构体数组进行遍历计算不同算法需要的信息，最后在主函数中用while循环和switch语句进行各个调度算法的选择，最后经过不断的调试和运行，实现四个调度算法分别是先来先服务、短进程优先、优先级