多级反馈队列调度.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,多级反馈队列调度,最复杂的算法,多级反馈队列算法,（,Multilevel Feedback QueueMFQ,）,多级反馈队列调度算法是一种,CPU,处理机调度算法，它不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。,UNIX,操作系统采取的便是这种调度算法。,设置多个就绪队列，并为各个队列赋予不同的优先级和不同长度的时间片；第一个队列的优先级最高，进程所执行时间片最小。新创建的进程挂到第一优先级的队列后，然后按,FCFS,原则排队等待调度。当轮到其执行时，如它能在时间片内完成，便撤离系统；如果不能完成，便被挂入第二级队列后，,；仅当第一级队列空闲时，调度程序才调度第二级队列中的进程运行，依次类推,；新进程可抢占低级进程的处理机。,1,多级反馈队列调度算法的思想,2,多级反馈队列调度算法的示意图,3,多级反馈队列调度算法的原理,1,、设有,N,个队列（,Q1,Q2.QN,），其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业,(,进程,),的优先级也是不一样的。一般来说，优先级,Priority(Q1)Priority(Q2).Priority(QN),。怎么讲，位于,Q1,中的任何一个作业,(,进程,),都要比,Q2,中的任何一个作业,(,进程,),相对于,CPU,的优先级要高（也就是说，,Q1,中的作业一定要比,Q2,中的作业先被处理机调度），依次类推其它的队列。,2,、对于某个特定的队列来说，里面是遵循时间片轮转法。也就是说，位于队列,Q2,中有,N,个作业，它们的运行时间是通过,Q2,这个队列所设定的时间片来确定的（为了便于理解，我们也可以认为特定队列中的作业的优先级是按照,FCFS,来调度的）。,3,多级反馈队列调度算法的原理,不一样，这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。同时，为了便于那些超大作业的完成，最后一个队列,QN(,优先级最低的队列,),的时间片一般很大。,3,、各个队列的时间片是一样的吗？,4,多级反馈队列调度算法的,描述,1,、,进程在进入待调度的队列等待时，首先进入优先级最高的Q1,等待。,2,、,首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：,Q1,Q2,Q3,三个队列，只有在,Q1,中没有进程等待时才去调度,Q2,，同理，只有,Q1,Q2,都为空时才会去调度,Q3,。,3,、,对于同一个队列中的各个进程，按照时间片轮转法调度。比如,Q1,队列的时间片为,N,，那么,Q1,中的作业在经历了,N,个时间片后若还没有完成，则进入,Q2,队列等待，若,Q2,的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。,4,、,在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，,CPU,马上分配给新到达的作业（抢占式）。,5,多级反馈队列调度算法,如何运作,假设系统中有,3,个反馈队列,Q1,Q2,Q3,，时间片分别为,2,，,4,，,8,。,现在有,3,个作业,J1,J2,J3,分别在时间,0,，,1,，,3,时刻到达。而它们所需要的,CPU,时间分别是,3,，,2,，,1,个时间片。,1,、,时刻,0 J1,到达。于是进入到队列,1,，运行,1,个时间片，时间片还未到，此时,J2,到达。,2,、,时刻,1 J2,到达。由于时间片仍然由,J1,掌控，于是等待。,J1,在运行了,1,个时间片后，已经完成了在,Q1,中的,2,个时间片的限制，于是,J1,置于,Q2,等待被调度。现在处理机分配给,J2,。,3,、,时刻,2 J1,进入,Q2,等待调度，,J2,获得,CPU,开始运行。,5,多级反馈队列调度算法,如何运作,4,、,时刻,3 J3,到达，由于,J2,的时间片未到，故,J3,在,Q1,等待调度，,J1,也在,Q2,等待调度。,5,、,时刻,4 J2,处理完成，由于,J3,，,J1,都在等待调度，但是,J3,所在的队列比,J1,所在的队列的优先级要高，于是,J3,被调度，,J1,继续在,Q2,等待。,6,、,时刻,5 J3,经过,1,个时间片，完成。,7,、,时刻,6,由于,Q1,已经空闲，于是开始调度,Q2,中的作业，则,J1,得到处理器开始运行。,J1,再经过一个时间片，完成了任务。于是整个调度过程结束。,6,多级反馈队列调度算法,C,语言实现,谢谢观看！,