操作系统实验九

1安徽大学计算机实验教学中心学号E11614051专业计算机科学与技术姓名施飞宇实验日期2018/12/20教师签字成绩实验报告【实验名称】最低松弛度优先调度算法【实验目的】1.学习最低松弛度算法思想。2.用代码实现改算法，解决最低松弛度优先调度问题。【实验原理】最低松弛度优先（LLF）算法是根据任务紧急（或松弛）的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，使之优先执行。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，被优先调度。松弛度的计算方法如下：任务的松弛度=必须完成的时间-其本身的运行时间-当前时间其中其本身运行的时间指任务运行结束还需多少时间，如果任务已经运行了一部分，则：任务松弛度=任务的处理时间-任务已经运行的时间–当前时间【实验内容】数据结构：本实验进程采用结构体来存储线信息，采用结构体数组来存储进程序列。2安徽大学计算机实验教学中心进程结构定义如下：typedefstruct{intstart;//进程申请服务开始时间intover;//进程截止时间intsurvey1;//需要服务总时间intsurvey2;//已经服务时间intsongchi;//松弛度intlabel;//等于0未被处理，等于1已经被处理完毕}pcb;程序流程图：程序开始输入测试A，B进程个数初始化A,B进程并打印A.SONGCHI=0||A.SONGCHIB.SONGCHI是否计算A,B松弛度服务B进程服务A进程时间片加A,B服务时间最小公倍数进程服务完毕程序结束是否3安徽大学计算机实验教学中心程序代码：%2018/12/20笃行南楼A202E11614051施飞宇#includeiostream#includestdio.husingnamespacestd;typedefstruct{intstart;//进程申请服务开始时间intover;//进程截止时间intsurvey1;//需要服务总时间intsurvey2;//已经服务时间intsongchi;//松弛度intlabel;//等于0未被处理，等于1已经被处理完毕}pcb;voidpcb_A(pcb*A,intn)//A进程创建函数{inti;for(i=0;in+1;i++){A[i].start=i*20;A[i].survey2=0;A[i].label=0;A[i].songchi=10;A[i].survey1=10;A[i].over=A[i].start+20;if(i!=n)coutAi+1到达时间A[i].start截止时间A[i].overendl;}}voidpcb_B(pcb*B,intn)//B进程创建函数{inti;for(i=0;in+1;i++){B[i].start=i*50;B[i].survey2=0;B[i].label=0;B[i].songchi=25;B[i].survey1=25;B[i].over=B[i].start+50;if(i!=n)coutBi+1到达时间B[i].start截止时间4安徽大学计算机实验教学中心B[i].overendl;}}inttest(pcb*X,intn,inttime){inti,j;for(i=0;in;i++){if(X[i].label==0&&X[i].start=time){X[i].songchi=X[i].over-(X[i].survey1-X[i].survey2)-time;returni;}}return-1;}voidrun_AB(pcb*A,intn1,pcb*B,intn2){inttime;intai,bi,ka,kb;intmax_time;intAB=1;intlabel=0;if(n1*20=n2*50){max_time=n1*20;}else{max_time=n2*50;}cout时间A截止时间服务时间松弛度B截止时间服务时间松弛度endl;cout0A1A[0].overA[0].survey2A[0].songchiB1B[0].overB[0].survey2B[0].songchiendl;for(time=0;time=max_time;time=time+1){ka=test(A,n1,time);if(ka==-1){ai=ai+1;}5安徽大学计算机实验教学中心else{ai=ka;}//coutAai+1A[ai].songchiendl;kb=test(B,n2,time);if(kb==-1){bi=bi+1;}else{bi=kb;}//coutBbi+1B[bi].songchiendl;if(B[bi].songchi==0||ka==-1||label==1){AB=0;label=0;}if(A[ai].songchi==0||kb==-1||label==2){AB=1;label=0;}if(AB==1&&ain1){if(A[ai].survey1==(++A[ai].survey2)){couttime+1Aai+1A[ai].overA[ai].survey2A[ai].songchi/5*5Bbi+1B[bi].overB[bi].survey2B[bi].songchi/5*5endl;couttime+1Aai+1进程结束endl;A[ai].label=1;label=1;}else{if((time+1)%5==0)couttime+1Aai+1A[ai].overA[ai].survey2A[ai].songchi/5*5Bbi+1B[bi].overB[bi].survey2B[bi].songchi/5*5endl;}}6安徽大学计算机实验教学中心if(AB==0&&bin2){if(B[bi].survey1==(++B[bi].survey2)){couttime+1Aai+1A[ai].overA[ai].survey2A[ai].songchi/5*5Bbi+1B[bi].overB[bi].survey2B[bi].songchi/5*5endl;couttime+1Bbi+1进程结束endl;B[bi].label=1;label=2;}else{if((time+1)%5==0)couttime+1Aai+1A[ai].overA[ai].survey2A[ai].songchi/5*5Bbi+1B[bi].overB[bi].survey2B[bi].songchi/5*5endl;}}if(kb==-1){bi=bi-1;}if(ka==-1){ai=ai-1;}}}intmain(){intn1,n2;pcbA[10],B[10];cout输入A进程个数endl;cinn1;pcb_A(A,n1);cout输入B进程个数endl;cinn2;pcb_B(B,n2);run_AB(A,n1,B,n2);return0;}7安徽大学计算机实验教学中心运行截图：【小结或讨论】在实现该算法的时候刚开始，未考虑进程的到达时间，所以调试的过程中一直出错。其次该算法涉及进程抢占，只有当该进程松弛度为0时才会进行抢占。这也是最低松弛度优先调度算法的难点。