处理机调度算法的实现.docx

《处理机调度算法的实现.docx》由会员分享，可在线阅读，更多相关《处理机调度算法的实现.docx（23页珍藏版）》请在第一文库网上搜索。

1、处理机调度算法的实现一、核心算法思想1 .先来先服务调度算法先来先服务调度算法是一种最简单的调度算法，该算法既可以用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。2 .短作业（进程）优先调度算法短作业（进程）优先调度算法SJ（P）F

2、,是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。SJ（P）F调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。该算法对长作业不利，完全未考虑作业的紧迫程度。3 .高响应比优先调度算法在批处理系统中，短作业优先算法是一种比较好的算法，其主要不足之处是长作业的运行得不到保证。如果我们能为每个作业

3、引人动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：优先权=（等待时间+要求服务时间）/要求服务时间即优先权=响应时间/要求服务时间如果作业的等待时间相同，则要求服务的时间越短，其优先权越高，因而该算法有利于短作业。当要球服务的时间相同时，作业的优先权决定于其等待时间，等待时间越长，优先权越高，因而它实现的是先来先服务对于长作业，作业的优先级可以随着等待时间的增加而提高，当其等待时间足够长时,其优先级便可以升到很高，从而也可获得处理机。4 .时间片轮转算法在时间片轮转算法中，系统将所有的就绪进程按先来

4、先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计数器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。二、核心算法流程图1.先来先服务算法流程图2.短进程优先算法下面给出的是用C实现程序的源代码：#inc1ude#inc1ude#inc1udetypedefstructpcb(intname;in

5、tneedtime;intarrivetime;intpri;intstate;intcputime;)p1ist;voidaction(p1ist*nowpro);voidaction(p1ist*nowpro)(de1ay(1000);printf(,nowisprocess%d,nowpro-name);nowpro-needtime;if(nowpro-needtime=0)(printf(theprocess%disendn,nowpro-name);*nowpro-state=1;*/printf(n);)e1se(printf(process%dneedtimeis%dn,now

6、pro-name,nowpro-needtime);printf(n);)voidcreatpro(intn,p1ist*process)intj；Sr(J=O；jn；j+)(processj.name=j;processj.needtime=rand()%10+1;processj.arrivedme=rand()%10;processj.pri=rand()%4;processj.state=O;processj.cputime=0;)voidshow(intn,p1ist*process)(intj;for(j=0;jn;j+)(printf(,nameofprocess%dt,proc

7、ess(jj.name);printf(needtime%dt,processj.needtime);printf(,arrivetime%dt,processj.aivetime);printf(,pri%dn,processj.p);printf(rstate%dt,processj.state);printf(,cputime%dn,processj.cputime);1)voidmain()(voidcreatpro(intn,p1ist*process);voidshow(intn,p1ist*process);voidfcfs(intn,p1ist*process);voidsjf

8、(intn,p1ist*process);voidrr(intn,p1ist*pro1);voidhrrn(intn,p1ist*pro1);intn;*thenumberofprocess*/intk;p1istprocess10;printf(p1easeinputthenumberofprocessfrom0to10n,t);scanf(%dn);creatpro(n,process);show(n,process);printf(p1easechoosethewhatyouwanttousen);printf(1FCFSt2SJFt3HRRNt4RRn);scanf(,%dk);swi

9、tch(k)case1:fcfs(n,process);break;case 2: sjf(n,process);break;case 3: hrm(n,process);break;case 4: rr(n,process);break;defau1t:break;1getch();)voidfcfs(intn,p1ist*pro1)(voidshow(intn,p1ist*process);inti,j,k;intm=0;inttime;p1isttemp;p1istpro2110J;fbr(i=O;in;i+)(k=0;whi1e(pro1k.state=1)(k+;1temp=pro1

10、k;for(j=k+1;jpro1j.arrivetime&pro1j.state!=1)(temp=proHj;k=j；)pro21m+=temp;pro1k.state=1;)show(n,pro2);fbr(i=O;i0)action(fcpro21i);voidsjf(intn,p1ist*pro!)voidshow(intn,p1ist*process);inti,j,k;intm=0;p1isttemp;p1istpro2IOJ;for(i=0;in;i+)(k=0;whi1e(pro1k.state=1)(k+;)temp=prok;for(j=k+1;jpro1|jj.need

11、time&pro1j.state!=1)(temp=pro1j;k=j;11pro2m+=temp;pro1k.state=1;)show(n,pro2);for(i=0;i0)(action(fcpro2i);voidrr(intn,p1ist*pro1)(voidshow(intn,p1ist*process);inti,j,k;intm=0;inttime;p1isttemp;p1istpro210;fbr(i=O;in;i+)(k=0;whi1e(pro1k.state=1)(k+;1temp=prok;for(j=k+1;jpro1|j.arrivetime&pro1IjJstate

12、!=!)(temp=proHj;k=j；)pro21m+=temp;pro1k.state=1;)show(n,pro2);time=pro20.needtime;for(i=0;in;i+)(if(timeO)(for(i=0;i0)(action(fepro2i);)Itime-;)voidhrrn(intn,p1ist*pro1)intca1(inta,p1ist*pro2);inti,k,j,m;intcurtime=O;p1isttemp;for(i=0;in;i+)(k=0;whi1e(proIk.state=1)k+;)temp=pro1k;m=ca1(curtime,&temp

13、);fbr(j=0ypro11j.pri)(temp=pro1j;m=pro1j1pri;k=j;whi1e(pro1k.needtimeO)(action(fcpro1k);curtime+;)pro1k.state=1;intca1(inta,p1ist*pro2)(intpr;if(a-pro2-arrivetime)arrivetime+pro2-needtime)pro2-needtime;returnpr;)五、运行结果1.先来先服务算法运行结果01333331-C*c*c*process0needtimeis5process0needtimeis4process0needtimeis3process0needtimeis2process0needtimeis1theprocess0isend