动态优先权算法模拟-操作系统课程设计

东北大学秦皇岛分校计算机与通信工程学院操作系统课程设计设计题目动态优先权算法模拟专业名称计算机科学与技术班级学号学生姓名指导教师设计时间课程设计任务书专业：计算机科学与技术学号：学生姓名（签名）：设计题目：动态优先权算法模拟一、设计实验条件综合楼808二、设计任务及要求模拟单处理机环境下的进程调度模型，调度采用基于动态优先权的调度算法。三、设计报告的内容1.设计题目与设计任务设计题目：动态优先权算法模拟设计任务：模拟单处理机环境下的进程调度模型，调度采用基于动态优先权的调度算法。2.前言（绪论）在操作系统中调度算法的实质是一种资源的分配，因而调度算法是指“根据系统资源分配策略所规定的资源分配算法”。对于不同的操作系统和系统目标，通常采用不同的调度算法。为了照顾紧迫作业，使之在进入系统后便获得优先处理，引入了最高优先权先调度算法。在作为进程调度算法时，该算法是把处理机分配给就绪队列优先权最高的进程。这可以分为抢占式优先权算法和非抢占式优先权算法。对于最高优先权优先调度算法，其关键在于：它是使用静态优先权还是动态优先权，以及如何确定进程的优先权。本次课程设计所实现的算法就是动态优先权算法的抢占式优先权调度算法和非抢占式动态优先权算法。动态优先权拥有其特有的灵活优点，同时，若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程，将因其动态优先权变得高而优先获得处理机，此即FCFS算法。若所有的就绪进程具有各不相同优先权初值，那么，对于优先权初值低的进程，在等待了足够长的时间后，其优先权便可能升为最高，从而获得处理机。当采用抢占式优先权调度算法时，如果规定当前进程的优先权以一定速率下降，则可防止一个长作业长期垄断处理机。这里，我们采用高响应比来决定每个进程的优先权。3.设计主体（各部分设计内容、分析、结论等）【设计内容】动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。非抢占式优先权调度算法。在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。抢占式优先权算法。系统同样把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个优先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将进程分配给优先权最高的进程。在批处理系统中，段作业优先算法是一种比较好的算法，其主要不足之处，是长作业的运行得不到保证。如果我们为每个作业引入动态优先权，并使作业优先级随着等待时间的增加而以一定速率提高，则可以解决这个问题。优先权的变化规律可描述为：优先权=（等待时间+要求服务时间）/要求服务时间对优先权计算完毕之后，要能够通过正确的调度函数，完成相应进程的每个变量的更新，其中等待时间加一，运行进程的CPU时间减一，如果这时候运行的进程结束，则改变其状态并记录完成时间。【算法分析】模拟动态优先权算法，在主函数中选择采用抢占式进程调度算法还是非抢占式进程调度算法，进而调用对应的函数完成模拟。设置进程结构体，structPROCESS{intid;//进程iddoubleresponse_rate;//优先权intcputime;//要求服务时间intwaittime;//等待时间intendtime;//进程完成时间，未完成时标记-1intSTATE;//进程当前状态};记录完成的进程id，使用数组pro_list[10]功能函数display()打印各进程当前状态init()初始化进程状态change()抢占式调度算法进程状态更新no_change()非抢占式调度算法进程状态更新函数调用顺序如图1：图1函数调用顺序图main()init()display()change()no_change()endbegin采用高响应比作为进程调度的优先权，其特点如下：（1）如果作业的等待时间相同，则要求服务时间愈短，其优先权愈高，因而该算法有利于短作业；（2）当服务时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。（3）对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可以升到很高，从而也可以获得处理机。【代码实现】#includeiostream#includecstring#includestdio.h#includecstdlibusingnamespacestd;#definenum6#defineRUN1#defineREADY0#defineRUNOUT-1inttime=0;structPROCESS{intid;doubleresponse_rate;intcputime;intwaittime;intendtime;intSTATE;}pro[10];intpro_list[10],q=0;voiddisplay(){coutTime:timeendl;cout===========================================endl;coutID\t\t0\t1\t2\t3\t4\t5endl;coutrespone_rate\t;for(inti=0;inum;i++){coutpro[i].response_rate'\t';}coutendl;coutcputime\t\t;for(inti=0;inum;i++){coutpro[i].cputime'\t';}coutendl;coutwaittime\t;for(inti=0;inum;i++){coutpro[i].waittime'\t';}coutendl;coutendtime\t\t;for(inti=0;inum;i++){coutpro[i].endtime'\t';}coutendl;coutSTATE\t\t;for(inti=0;inum;i++){if(pro[i].STATE==RUN)coutRUN\t;elseif(pro[i].STATE==READY)coutREADY\t;elsecoutRUNOUT\t;}coutendl;couttheendprocessendtime:;for(inti=0;iq;i++){cout-pro_list[i]''pro[pro_list[i]].endtime'';}coutendl;cout===========================================endl;}voidinit(){for(inti=0;inum;i++){pro[i].id=i;pro[i].response_rate=1;pro[i].waittime=0;pro[i].endtime=-1;pro[i].STATE=0;}pro[0].cputime=5;pro[1].cputime=3;pro[2].cputime=1;pro[3].cputime=2;pro[4].cputime=4;pro[5].cputime=6;}voidchange(){doublerunflag=0;intrunprocess=0;for(inti=0;inum;i++){if(pro[i].STATE!=RUNOUT){pro[i].response_rate=1.0*(pro[i].waittime+pro[i].cputime)/pro[i].cputime;if(pro[i].response_raterunflag){runflag=pro[i].response_rate;runprocess=i;}}}for(inti=0;inum;i++){if(pro[i].STATE==RUN){pro[i].STATE=READY;pro[i].waittime=-1;}}pro[runprocess].cputime--;pro[runprocess].waittime=-1;pro[runprocess].STATE=RUN;for(inti=0;inum;i++){if(pro[i].STATE==RUNOUT){continue;}pro[i].waittime++;if(pro[i].cputime==0){pro[i].endtime=time;pro[i].STATE=RUNOUT;pro[i].response_rate=0;pro_list[q++]=i;}}}voidno_change(){intrunprocess=0,flag=0;doublerunflag=0;for(inti=0;inum;i++){if(pro[i].STATE==RUNOUT){continue;}pro[i].response_rate=1.0*(pro[i].waittime+pro[i].cputime)/pro[i].cputime;if(pro[i].response_raterunflag){runflag=pro[i].response_rate;runprocess=i;}}for(inti=0;inum;i++){if(pro[i].STATE==RUNOUT){continue;}if(pro[i].STATE==RUN){flag=1;pro[i].cputime--;pro[i].waittime=-1;for(intj=0;jnum;j++){if(pro[j].STATE==RUNOUT){continue;}pro[j].waittime++;}if(pro[i].cputime==0){pro[i].STATE=RUNOUT;pro[i].endtime=time;pro[i].response_rate=0;pro_list[q++]=i;}break;}}if(!flag){pro[runprocess].cputime--;pro[runprocess].waittime=-1;pro[runprocess].STATE=RUN;for(intj=0;jnum;j++){if(pro[j].STATE==RUNOUT){continue;}pro[j].waittime++;}if(pro[runprocess].cputime==0){pro[runprocess].STATE=RUNOUT;pro[runprocess].endtime=time;pro[runprocess].response_rate=0;pro_list[q++]=runprocess;}}}intmain(){intflag=0,type;coutselecettype£¨1.preemptivescheduling2.non-preemptivescheduling£©£º;cintype;init();while(1){flag=0;display();for(inti=0;inum;i++){if(pro[i].STATE!=RUNOUT){flag=1;break;}}if(!flag)break;time++;if(type==1){change();}elseno_change();coutendl;getchar();}coutendlendl;coutAllprocesseshaverunedout!!endl;}【结果截图】抢占式优先权调度算法非抢占式优先调度算法4.结束语本次课程设计是由小组合作完成，大家一同讨论算法的可行性、实现流程、结构安排等，一起讨论交流使得大家对这个算法了解得更加深刻，从各个不同的角度对它有了不同的认