处理机调度实验报告1

1、深圳大学实验报告课程名称：操作系统实验工程名称:处理机调度学院：计算机与软件学院专业：软件工程指导教师:报告人一学号;班级：实验时间：2021年5月7日实验报告提交时间：2021年5月22日教务处制一、实验目的与要求：实验目的：模拟在单处理器多进程操作系统的CPU调度.帮助学生掌握多种CPU调度算法的知识原理和运作机制.本实验为模拟实验,不要求实现真正的进程创立与进程调度.主要实现各种调度算法.实验要求：1、阅读理解例程,掌握例程的运作流程.运行例程,理解先来先效劳算法的调度原理和运行结果.2、参考先来先效劳算法,尝试实现其他四种调度算法：短作业优先、高响应比、时间片轮转、多级反应队列.要求至

2、少实现一种算法.a除了多级反应队列,其他算法采用非抢占调度b短作业优先算法使用例题一数据或程序内置数据,要求运行结果给出调度顺序、完成时间、周转时间、带权周转时间c高响应比算法使用例题二的数据,要求运行结果给出调度顺序、完成时间、周转时间、带权周转时间d时间片轮转算法可以使用程序内置数据,要求运行结果给出每个时间片是被哪个进程使用,每个进程完成时,要修改状态并输出提示.e多级反应队列算法使用例题三的数据,要求运行结果给出正确的进程调度顺序和过程描述二、方法、步骤：说明程序相关的算法原理或知识内容,程序设计的思路和方法,可以用流程图表述,程序主要数据结构的设计、主要函数之间的调用关系等先来先效劳

3、算法：接到达时间先后,选择最先来的作业最先执行实现思想：对作业的到达时间按大小进行排序,然后按顺序执行短作业优先算法：在后备队列中,选择效劳时间最短的作业最先执行实现思想：对作业按到达时间排序,接着对到达的作业,即后备队列中的作业按效劳时间排序,取效劳时间最小的作业最先执行高响应比算法：对作业的优先权响应时间/要求效劳时间进行计算,对优先权最高的最先执行实现实现：计算后备队列中作业的优先权,并排序,优先权最高的最先执行时间片轮转算法：将所有就绪进程按先来先效劳排成队列,把CPU分配给队首进程,进程只执行一个时间片,时间片用完后,将已使用时间片的进程送往就绪队列的末尾,分配处理机给就绪队列中下一

4、进程实现思想:将作业按到达时间排序,在后备队列中选择第一个作业,把CPU分配给它,执行一个时间片,时间片用完后,将作业送往后备队列的末尾,把CPU分配给下一个作业,直到所有作业完成多级反应队列调度算法：设置多个就绪队列,各个队列优先级逐个降低,各个队列时间片逐个增加,优先级越高的队列执行时间片就越短,一般时间片按倍增规那么,每个新进程首先进入第一个队列,遵循FCFS,在当前队列的时间片内,进程假设能完成,退出,进程假设未完成,降级到第二个队列,同样遵循FCFS依次类推,假设在第二个队列的时间片内仍未完成,再降级到第三个队列实现思想：设置多个就绪队列,各个队列优先级逐个降低,各个队列时间片逐个增

5、加,优先级越高的队列执行时间片就越短,一般时间片按倍增规那么,例如,第二队列的时间片要比第一个队列的时间片长一倍,第i+1个队列的时间片要比第i个队列的时间片长一倍,整合了时间片、FCFS、优先级三种机制.三.实验过程及内容：对程序代码进行说明和分析,越详细越好,代码排版要整洁,可读性要高#include"stdio.h"#include<stdlib.h>/#include<conio.h>#include<time.h>#include<math.h>/#defineNULL0#definegetpch(type)(typ

6、e*)malloc(sizeof(type)系统函数typedefstructpcbPCB;structpcbintid;charname10;inttime_start;inttime_need;inttime_left;inttime_used;charstate;/*void_sleep(intn)clock_tgoal;/定义进程限制块PCB/标不符/名称/到达时间/效劳时间/剩余运行时间/已使用时间/进程状态goal=(clock_t)n*CLOCKS_PER_SEC+clock();while(goal>clock();char_keygo()(charc;printf(&q

7、uot;按任意键继续n");c=getchar();returnc;)*用户函数inttime_unit=2;intnum=5;/实际进程数量PCBpcbdata10=/例程内置数据1000,"A",0,4,4,0,'R',1001,"B",1,3,3,0,'R',1002,"C",2,5,5,0,R,1003,"D",3,2,2,0,'R',1004,'E',4,4,4,0,'R',;intnum1=4;PCBpcbdata

8、110=/例题一数据1000,"Job1,1,9,9,0,'R',1001,"Job2",1,16,16,0,R,1002,"Job3,1,3,3,0,'R',1003,"Job4",1,11,11,0,'R',；intnum2=4;PCBpcbdata210=/例题二数据1000,"P1,10,8,8,0,'R',1001,"P2,12,12,12,0,'R',1002,"P3,14,4,4,0,'R',10

9、03,"P4,16,6,6,0,'R',;intnum3=4;PCBpcbdata310=/例程三数据1000,"A",0,7,7,0,'R',1001,"B",5,4,4,0,'R',1002,"C",7,13,13,0,'R',1003,"D",12,9,9,0,'R',;intready10;就绪队列,存放进程在pcbdata中的位置intorder10;/记录排序使用哪个数值作为排序对象voidintput()(int

10、i;printf("进程总数为：");scanf("%d",&num);for(i=0;i<num;i+)(pcbdatai.id=1000+i;printf("输入第d个进程名：",i+1);scanf("%s",&);printf("输入第d个进程到达时间：",i+1);scanf("%d",&pcbdatai.time_start);printf("输入第d个进程效劳时间：,i+1);scanf(&quo

11、t;%d",&pcbdatai.time_need);pcbdatai.time_left=pcbdatai.time_need;printf("n");pcbdatai.time_used=0;pcbdatai.state='R'*调度函数voidFCFS()(inti,j,temp;doublek;for(i=0;i<num;i+)orderi=pcbdatai.time_start;readyi=i;for(i=0;i<num;i+)/按到达时间排序for(j=i+1;j<num;j+)if(orderi>or

12、derj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf"-先来先效劳算法调度：非抢占,无时间片-n"temp=pcbdataready0.time_start;for(i=0;i<num;i+)(printf("第个进程-%s,",i+1,);printf("本进程正在运行");_sleep(1);printf("运行完毕n");temp+=pcbdata

13、readyi.time_need;j=temp-pcbdatareadyi.time_start;k=(float)j/pcbdatareadyi.time_need;printf("完成时间-%d,周转时间-%d,带权周转时间-%.1fn",temp,j,k);printf("所有进程调度完毕n");voidSJF()(inti,j,temp,l,temp_num;doublek;inttime=0;orderi=pcbdata1i.time_start;readyi=i;)for(i=0;i<num1;i+)/按到达时间排序for(j=i+1;

14、j<num1;j+)(if(orderi>orderj)(temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;)printf("-短作业算法调度：非抢占,无时间片-n");intt_ready10;就绪队列,存放进程在pcbdata中的位置intt_order10;/记录排序使用哪个数值作为排序对象t_orderi=pcbdata1readyi.time_need;/效劳时间作为排序对象t_readyi=readyi;)time=order0;for(l=0;l&

15、lt;num1;l+)/判断到达的进程数,用temp_num存放for(i=0;i<num&&pcbdata1readyi.time_start<=time;i+)temp_num=i+1;/把到达的进程按效劳时间大小进行排序for(i=0;i<temp_num;i+)for(j=i+1;j<temp_num;j+)if(t_orderi>t_orderj&&t_orderj!=0|t_orderi=0)temp=t_orderi;t_orderi=t_orderj;t_orderj=temp;temp=t_readyi;t_rea

16、dyi=t_readyj;t_readyj=temp;printf("第个进程-%s,",l+1,pcbdata1t_);printf("正在运行");_sleep(1);printf("运行完毕n");time+=pcbdata1t_ready0.time_need;j=time-pcbdata1t_ready0.time_start;k=(float)j/pcbdata1t_ready0.time_need;t_order0=0;printf("完成时间-%d,周转时间-%d,带权周转时间-%.1f

17、n",time,j,k);)printf("所有进程调度完毕n");)voidHRF()inti,j,temp,l,temp_num;doublek;inttime=0;orderi=pcbdata2i.time_start;readyi=i;)for(i=0;i<num2;i+)/按到达时间排序for(j=i+1;j<num2;j+)(if(orderi>orderj)(temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;)printf(&quo

18、t;-高响应比算法调度：非抢占,无时间片-n");intt_ready10;intt_order10;for(i=0;i<num2;i+)t_orderi=1;t_readyi=readyi;)time=order0;for(l=0;l<num2;l+)/判断到达进程数for(i=0;i<num&&pcbdata2readyi.time_start<=time;i+)temp_num=i+1;for(i=0;i<temp_num;i+)/计算已到达进程的优先权if(t_orderi)t_orderi=(time-pcbdata2t_rea

19、dyi.time_start+pcbdata2t_readyi.time_need)/pcbdata2t_readyi.time_need;)for(i=0;i<temp_num;i+)/按优先权排序for(j=i+1;j<temp_num;j+)if(t_orderi<t_orderj)temp=t_orderi;t_orderi=t_orderj;t_orderj=temp;temp=t_readyi;t_readyi=t_readyj;t_readyj=temp;)printf("第个进程-%s,",l+1,pcbdata2t_

20、);printf("正在运行");_sleep(1);printf("运行完毕n");time+=pcbdata2t_ready0.time_need;j=time-pcbdata2t_ready0.time_start;k=(float)j/pcbdata2t_ready0.time_need;t_order0=0;printf("完成时间-%d,周转时间-%d,带权周转时间-%.1fn",time,j,k);)printf("所有进程调度完毕n");)voidTimeslice()doublek;inttime

21、=0;intdone=0;for(i=0;i<num;i+)(orderi=pcbdatai.time_start;readyi=i;for(i=0;i<num;i+)/按到达时间排序for(j=i+1;j<num;j+)(if(orderi>orderj)(temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf"-时间片轮转算法调度：非抢占,时间片大小为2-n"intt_ready10;for(i=0;i<num;i+)t_ready

22、i=readyi;time=order0;for(l=0;done<num;l+)/判断到达的进程数for(i=0;i<num&&pcbdatareadyi.time_start<=time;i+)temp_num=i+1;if(time!=order0)/将已使用时间片的进程,即第一个移到队列末尾for(i=1;i<temp_num;i+)temp=t_readyi;t_readyi=t_readyi-1;t_readyi-1=temp;if(pcbdatat_ready0.state!='F')printf("第d个时间片被

23、进程s使用,",l+1,pcbdatat_;printf"正在运行n"_sleep1;printf"时间片使用完,所需时问d,",pcbdatat_ready0.time_left;time+=2;pcbdatat_ready0.time_used+=2;pcbdatat_ready0.time_left-=2;printf"使用时间%d,还需时问d,",2,pcbdatat_ready0.time_left;/判断进程是否结束ifpcbdatat_ready0.time_left<=0print

24、f"进程s结束n",pcbdatat_;done+;pcbdatat_ready0.state='F'elseprintf"进程s就绪n",pcbdatat_;printf"所有进程调度完毕An"voidMRLA()(inti,j,temp,l,temp_num,temp_num2;doublek;inttime=0;/系统时间intdone=0;/已完成的进程intt_ready10;intqueue10;/进程对应的队列intqtime10;/进程对应的时间片for(i=

25、0;i<num3;i+)(orderi=pcbdata3i.time_start;readyi=i;queuei=1;qtimei=0;for(i=0;i<num3;i+)/按到达时间排序for(j=i+1;j<num3;j+)(if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;)printf("-多级反应算法调度：抢占式,时间片大小为2-n");for(i=0;i<num3;i+)t_readyi=ready

26、i;)time=order0;for(l=0;done<num3;l+)/判断到达的进程数for(i=0;i<num3&&pcbdata3readyi.time_start<=time;i+)temp_num=i+1;if(time!=order0)for(i=0;i<temp_num;i+)/按队列优先级排序for(j=1;j<temp_num-i;j+)if(pcbdata3t_readyj-1.state='F'|(queuej-1>queuej&&pcbdata3t_readyj.state!='

27、;F')temp=queuej-1;queuej-1=queuej;queuej=temp;temp=t_readyj-1;t_readyj-1=t_readyj;t_readyj=temp;temp=qtimej-1;qtimej-1=qtimej;qtimej=temp;if(pcbdata3t_ready0.state!='F')printf("队列d中的进程%s占用CPU,",queue0,pcbdata3t_);printf("正在运行n");_sleep(1);if(!qtime0)/判断是否有未

28、用完的时间片qtime0=pow(2,queue0);elseprintf("继续使用时间片,")；for(i=1;i<qtime0;i+)(time+;for(j=0;j<num3&&pcbdata3readyj.time_start<=time;j+)temp_num2=j+1;/判断是否有进程进入比本进程更高优先级的队列if(temp_num!=temp_num2&&queue0>queuetemp_num2-1&&pcbdata3t_ready0.time_left-i>0)qtime0-

29、=i;break;if(temp_num!=temp_num2&&queue0>queuetemp_num2-1&&pcbdata3t_ready0.time_left-i>0)printf("发生抢占,使用时间片d,剩余时间片d,返回队列尾部n",i,qtime0);)elseprintf("时间片使用完,所需时间%d,",pcbdata3t_ready0.time_left);time+;pcbdata3t_ready0.time_used+=pow(2,queue0);pcbdata3t_ready0.t

30、ime_left-=pow(2,queue0);if(pcbdata3t_ready0.time_left<=0)printf("使用时间%d,还需时间%d,进程s结束n",qtime0,pcbdata3t_ready0.time_left,pcbdata3t_);done+;pcbdata3t_ready0.state='F')elseprintf("使用时间%d,还需时间%d,进程s进入队列%d就绪n",qtime0,pcbdata3t_ready0.time_left,pcbdata3t_ready0.n

31、ame,十+queue0);qtime0=0;)for(j=1;j<temp_num2;j+)/将执行的程序返回队尾排队temp=queuej;queuej=queuej-1;queuej-1=temp;temp=qtimej;qtimej=qtimej-1;qtimej-1=temp;temp=t_readyj;t_readyj=t_readyj-1;t_readyj-1=temp;)printf("所有进程调度完毕n");)intmain()inti=0,sch=99;while(sch!=0)printf("n请选择其中一种调度算法：n");

32、printf("(1)先来先效劳FCFSn");printf("(2)短作业优先SJF'n");printf("(3)高响应比HRF'n");printf("(4)时间片轮转Timeslicen");printf("(5)多级反应队列MRLAn");printf("(0)退出n");printf("请输入上述一个数字：");scanf("%d,&sch);switch(sch)case1:FCFS();break;case

33、2:SJF();break;case3:HRF();break;case4:Timeslice();break;case5:MRLA();break;case0:printf("退出程序n");break;_keygo();return0;voiddis_pcb(PCB*pr)printf("%s的PCB:n",pr->name);printf("标识符-%d,状态-%c,至U达时间-%dn",pr->id,pr->state,pr->time_start);printf("效劳时间-%d,剩余运行时

34、间-%d,已用时间-%dn",pr->time_need,pr->time_left,pr->time_used);printf("n");voiddis_pcb_all()inti;printf("*当前所有进程状态*n");for(i=0;i<num;i+)dis_pcb(&pcbdatai);voiddis_ready()inti;printf("当前就绪队列为：");for(i=0;i<num-1;i+)printf("%s-",pcbdataorderi.n

35、ame);printf("%sn",);四、实验结论：提供运行结果,对结果进行探讨、分析、评价,并提出结论性意见和改良想法先来先效劳算法FCFS:LhJ一毕毕.毕5毕匚-/2O11LW3685一堂兀间宦古汗多退谕JrJ/VI/VJJ-J/JyUc2c3gi59请zhouji.an<5an®Ehouji.ancan-PC/20211.B0368$./a度£调丁JFJffilFsq*11A-SLIeRn)砧Ti列转队抻先业应届3T行T行无仃胆运a-运明运推运推运推;.11ao.nU无可勺转一转一转：转一周：周一周：周

36、)根权：站.£K厂带一厂带一厂带非旬乐闻声石10运11运14.在T在Y在一在一在歪间正间正间非时程时w昇本期本琳本周本周本周翻一号AJB,62048井-FT-4-711-达月-一呈一呈一口王优点：实现简单,算法开销小,有利于长时间作业进程缺点：不利于短时间作业进程,所有进程调度完毕间一3%带权周转时间一2有进程调度完毕修业算法调度：非抢占,无时间片一妈-4,周转朝J二索带权周转腼工才闻一13周转时面一1二市权周转时间-/201L1503B优点：有利于短作业或短进程缺点：导致长作业或进程长时间不被调度,不能保证实时性,执行时间一般基于用户估算,准确性缺乏高响应比算法HRF:高响应比优先

37、调度算法的优点：对于等待时间相同的时候,效劳时间愈短那么优先权愈高,算法有利于短作业；对于效劳时间相同的时候,等待时间愈长其优先权愈高,算法实现的是先来先效劳；对于长作业,作业的优先级可以随等待时间的增加而提升,当其等待时间足够长时,其优先级便可升到很高保证能获得处理机.缺点：每次调度前都要计算优先权,增加系统开销.时间片轮转算法Timeslice:EW20L1150双35调CFJHARL中F£尸T歹T务先回转队L需比管-时一间一间寸:-B-Tff,行用行理行行用行用行用熬用占运使运使运使运使运使应使运使运使隹便珏便抢在2在及在d在&在以tL4在L在,中工臼h非正正正正间由普

38、正司>JJdi、+1-14-、TIPI-P一号-一二'm二-a二、m-nn一二七n二-二三nE"l!-i4矗需用壬辕金ffe需饕第需前需雪R使壬窿毒计,程,程,程,程,程,程,程庶般施W晟士再三翌士建士翌士底.屈士辞一豳一趣元邹一T-7丹；-i哨j_"JT"-;.一LrFy_1-.-,-Ii:个41>-Fgrrp4rn1-pbgrrF-FrrrrnrrTr-ptrrpT三*弓三翼.一心已-116XIPX1EXirxlEXLCXr44kMh便M桂春古肾多田时个时小时个时个时个时小时个时4班小B+la濡一/.JrJ-YT»11t-CJS1

39、111-清IC1K2BIC4IC5K0请-第需第第常第第翳第翳-先业应贫箸UH砰黑.砰母目砰词用nrS在时间片轮转算法中,时间片大小对系统性能有很大的影响,如选择很小的时间片将有利于短作业,由于它能较快的完成,但会频繁的发生中断、进程上下文的切换,从而增加系统的开销；反之,如选择较长的时间片,使得每个进程都能在一个时间片内完成,时间片轮转算法便退化为FCFS算法,无法满足交互式用户的需求.多级反应队列算法MRLA:C$011150368zhoujiarcan®Lhoujiancan-PC丁叩1115136苫$./a请选择其电二种调度算法；FCFS理作业优先SJF高响庠比HRF时同庆辂转J多级皮储队列MRLA退节请福注