处理机调度与死锁par.ppt

《处理机调度与死锁par.ppt》由会员分享，可在线阅读，更多相关《处理机调度与死锁par.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 处理机调度与死锁 第三章第三章 处理机调度与死锁处理机调度与死锁 3.1 3.1 处理机调度的层次处理机调度的层次 3.2 3.2 调度队列模型和调度准则调度队列模型和调度准则 3.3 3.3 调度算法调度算法 3.4 3.4 实时调度实时调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 1第三章 处理机调度与死锁 3.3 调调 度度 算算 法法 3.3.1 先来先服务和短作业先来先服务和短作业(进程进程)优先调度算法优先调度算法 1.先来先服务调度算法先来先服务调度算

2、法 貌似公平的算法，对短作业不利。貌似公平的算法，对短作业不利。2.短作业短作业(进程进程)优先调度算法优先调度算法 短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。2第三章 处理机调度与死锁 SJ(P)F调度算法也存在不容忽视的缺点：调度算法也存在不容忽视的缺点：(1)该该算算法法对对长长作作业业不不利利。更更严严重重的的是是，如如果果有有一一长长作作业业(进进程程)

3、进进入入系系统统的的后后备备队队列列(就就绪绪队队列列)，由由于于调调度度程程序序总总是是优优先先调调度度那那些些(即即使使是是后后进进来来的的)短短作作业业(进进程程)，将将导导致长作业致长作业(进程进程)长期不被调度。长期不被调度。(2)该该算算法法完完全全未未考考虑虑作作业业的的紧紧迫迫程程度度，因因而而不不能能保保证证紧迫性作业紧迫性作业(进程进程)会被及时处理。会被及时处理。(3)由由于于作作业业(进进程程)的的长长短短只只是是根根据据用用户户所所提提供供的的估估计计执执行行时时间间而而定定的的，而而用用户户又又可可能能会会有有意意或或无无意意地地缩缩短短其其作作业业的的估估计计运运

4、行行时时间间，致致使使该该算算法法不不一一定定能能真真正正做做到到短短作作业业优先调度。优先调度。3第三章 处理机调度与死锁 3.3.2 高优先权优先调度算法高优先权优先调度算法 1.优先权调度算法的类型优先权调度算法的类型 1)非抢占式优先权算法 在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批批处处理理系系统统中；也可用于某些对实时性要要求不严的实时系统求不严的实时系统中。4第三章 处理机调度与死锁 2)抢占式优先权调度算法抢占式优先

5、权调度算法 在在这这种种方方式式下下，系系统统同同样样是是把把处处理理机机分分配配给给优优先先权权最最高高的的进进程程，使使之之执执行行。但但在在其其执执行行期期间间，只只要要又又出出现现了了另另一一个个其其优优先先权权更更高高的的进进程程，进进程程调调度度程程序序就就立立即即停停止止当当前前进进程程(原原优优先先权权最最高高的的进进程程)的的执执行行，重重新新将将处处理理机机分分配配给给新新到到的的优先权最高的进程。优先权最高的进程。因因此此，在在采采用用这这种种调调度度算算法法时时，是是每每当当系系统统中中出出现现一一个个新新的的就就绪绪进进程程i时时，就就将将其其优优先先权权Pi与与正正

6、在在执执行行的的进进程程j的的优优先先权权Pj进进行行比比较较。如如果果PiPj，原原进进程程Pj便便继继续续执执行行；但但如如果果是是PiPj,则则立立即即停停止止Pj的的执执行行，做做进程切换，使进程切换，使i进程投入执行进程投入执行。显显然然，这这种种抢抢占占式式的的优优先先权权调调度度算算法法，能能更更好好地地满满足足紧紧迫迫作作业业的的要要求求，故故而而常常用用于于要要求求比比较较严严格格的的实实时时系系统统中中，以以及及对性能要求较高的批处理和分时系统对性能要求较高的批处理和分时系统中。中。5第三章 处理机调度与死锁 2.优先权的类型优先权的类型 1)静态优先权静态优先权 静静态态

7、优优先先权权是是在在创创建建进进程程时时确确定定的的，且且在在进进程程的的整整个个运行期间保持不变。运行期间保持不变。一一般般地地，优优先先权权是是利利用用某某一一范范围围内内的的一一个个整整数数来来表表示示的的，例例如如，07或或0255中中的的某某一一整整数数，又又把把该该整整数数称称为为优优先先数数。只只是是具具体体用用法法各各异异：有有的的系系统统用用“0”表表示示最最高高优优先先权权，当当数数值值愈愈大大时时，其其优优先先权权愈愈低低；而而有有的的系系统统恰恰恰恰相反。相反。6第三章 处理机调度与死锁 确定进程优先权的依据有如下三个方面：确定进程优先权的依据有如下三个方面：(1)进程

8、类型。进程类型。(2)(2)进程对资源的需求。进程对资源的需求。(3)(3)用户要求。用户要求。7第三章 处理机调度与死锁 2)动态优先权动态优先权 动动态态优优先先权权是是指指，在在创创建建进进程程时时所所赋赋予予的的优优先先权权，是是可可以以随随进进程程的的推推进进或或随随其其等等待待时时间间的的增增加加而而改改变变的的，以以便便获获得更好的调度性能。得更好的调度性能。例例如如，我我们们可可以以规规定定，在在就就绪绪队队列列中中的的进进程程，随随其其等等待待时间的增长，其优先权以速率时间的增长，其优先权以速率a a提高。提高。若若所所有有的的进进程程都都具具有有相相同同的的优优先先权权初初

9、值值，则则显显然然是是最最先先进进入入就就绪绪队队列列的的进进程程，将将因因其其动动态态优优先先权权变变得得最最高高而而优优先先获获得得处处理理机机，此此即即FCFS算法。算法。若若所所有有的的就就绪绪进进程程具具有有各各不不相相同同的的优优先先权权初初值值，那那么么，对对于于优优先先权权初初值值低低的的进进程程，在在等等待待了了足足够够的的时时间间后后，其其优优先先权权便便可可能能升升为为最最高高，从从而而可可以以获获得得处处理理机机。当当采采用用抢抢占占式式优优先先权权调调度度算算法法时时，如如果果再再规规定定当当前前进进程程的的优优先先权权以以速速率率b下下降降，则则可可防防止止一一个个

10、长长作作业业长期地垄断处理机。长期地垄断处理机。8第三章 处理机调度与死锁 3.高响应比优先调度算法高响应比优先调度算法 优先权的变化规律可描述为：优先权的变化规律可描述为：由由于于等等待待时时间间与与服服务务时时间间之之和和，就就是是系系统统对对该该作作业业的的响响应应时间，故该优先权又相当于响应比时间，故该优先权又相当于响应比RP。据此，又可表示为：。据此，又可表示为：9第三章 处理机调度与死锁 (1)如如果果作作业业的的等等待待时时间间相相同同，则则要要求求服服务务的的时时间间愈愈短，其优先权愈高，因而该算法有利于短作业。短，其优先权愈高，因而该算法有利于短作业。(2)当当要要求求服服务

11、务的的时时间间相相同同时时，作作业业的的优优先先权权决决定定于于其其等等待待时时间间，等等待待时时间间愈愈长长，其其优优先先权权愈愈高高，因因而而它它实实现的是先来先服务。现的是先来先服务。(3)对对于于长长作作业业，作作业业的的优优先先级级可可以以随随等等待待时时间间的的增增加加而而提提高高，当当其其等等待待时时间间足足够够长长时时，其其优优先先级级便便可可升升到到很高，很高，从而也可获得处理机。从而也可获得处理机。10第三章 处理机调度与死锁【例】【例】假设有四个作业，它们的提交、运行时间如下假设有四个作业，它们的提交、运行时间如下表所示。若采用响应比高者优先调度算法，试问平均表所示。若采

12、用响应比高者优先调度算法，试问平均周转时间和平均带权周转时间为多少？（时间单位：周转时间和平均带权周转时间为多少？（时间单位：小时，以十进制进行计算。）小时，以十进制进行计算。）作业号 到达时间 运行时间1 8.0 2.02 8.3 0.53 8.5 0.14 9.0 0.4解：解：响应比作业响应时间响应比作业响应时间/运行时间的估计值运行时间的估计值 1 1作业等待时间作业等待时间/运行时间的估计值运行时间的估计值 11第三章 处理机调度与死锁 作作业业号号到达到达时间时间运行运行时间时间开始开始时间时间完成完成时间时间周周转时间转时间带权带权周周转时间转时间1（1）8.02.08.010.

13、02（3）8.30.510.110.63（2）8.50.110.010.14（4）9.00.410.611.0四个作业的调度次序为：作业四个作业的调度次序为：作业1，作业，作业3，作业，作业2，作业，作业4。平均周转时间平均周转时间平均带权周转时间平均带权周转时间12第三章 处理机调度与死锁 3.3.3 基于时间片的轮转调度算法基于时间片的轮转调度算法 1.时间片轮转法时间片轮转法 在在早早期期的的时时间间片片轮轮转转法法中中，系系统统将将所所有有的的就就绪绪进进程程按按先先来来先先服服务务的的原原则则，排排成成一一个个队队列列，每每次次调调度度时时，把把CPU分分配配给给队队首首进进程程，并

14、并令令其其执执行行一一个个时时间间片片。时时间间片片的的大大小小从从几几ms到几百到几百ms。当当执执行行的的时时间间片片用用完完时时，由由一一个个计计时时器器发发出出时时钟钟中中断断请请求求，调调度度程程序序便便据据此此信信号号来来停停止止该该进进程程的的执执行行，并并将将它它送送往往就就绪绪队队列列的的末末尾尾；然然后后，再再把把处处理理机机分分配配给给就就绪绪队队列列中中新新的的队首进程，同时也让它执行一个时间片。队首进程，同时也让它执行一个时间片。这这样样就就可可以以保保证证就就绪绪队队列列中中的的所所有有进进程程，在在一一给给定定的的时时间内，均能获得一时间片的处理机执行时间。间内，

15、均能获得一时间片的处理机执行时间。例题例题13第三章 处理机调度与死锁 2.多级反馈队列调度算法多级反馈队列调度算法 (1)应应设设置置多多个个就就绪绪队队列列，并并为为各各个个队队列列赋赋予予不不同同的的优先级。优先级。第第一一个个队队列列的的优优先先级级最最高高，第第二二个个队队列列次次之之，其其余余各队列的优先权逐个降低。各队列的优先权逐个降低。该该算算法法赋赋予予各各个个队队列列中中进进程程执执行行时时间间片片的的大大小小也也各各不不相相同同，在在优优先先权权愈愈高高的的队队列列中中，为为每每个个进进程程所所规规定定的的执执行行时时间间片片就就愈愈小小。例例如如，第第二二个个队队列列的

16、的时时间间片片要要比比第第一一个个队队列列的的时时间间片片长长一一倍倍，第第i+1个个队队列列的的时时间间片片要要比比第第i个个队列的时间片长一倍。队列的时间片长一倍。图图 3-5 是多级反馈队列算法的示意是多级反馈队列算法的示意。14第三章 处理机调度与死锁 图 3-5 多级反馈队列调度算法 15第三章 处理机调度与死锁 (2)当一个新进程进入内存后，当一个新进程进入内存后，l首首先先将将它它放放入入第第一一队队列列的的末末尾尾，按按FCFS原原则则排排队队等等待待调调度度。当当轮轮到到该该进进程程执执行行时时，如如它它能能在在该该时时间间片片内内完完成，便可准备撤离系统；成，便可准备撤离系

17、统；l如如果果它它在在一一个个时时间间片片结结束束时时尚尚未未完完成成，调调度度程程序序便便将将该该进进程程转转入入第第二二队队列列的的末末尾尾，再再同同样样地地按按FCFS原原则则等等待调度执行；待调度执行；l如如果果它它在在第第二二队队列列中中运运行行一一个个时时间间片片后后仍仍未未完完成成，再再依次将它放入第三队列，依次将它放入第三队列，l如如此此下下去去，当当一一个个长长作作业业(进进程程)从从第第一一队队列列依依次次降降到到第第n队队列列后后，在在第第n队队列列中中便便采采取取按按时时间间片片轮轮转转的的方方式式运运行。行。16第三章 处理机调度与死锁 (3)仅仅当当第第一一队队列列

18、空空闲闲时时，调调度度程程序序才才调调度度第第二二队队列列中中的的进进程程运运行行；仅仅当当第第1(i-1)队队列列均均空空时时，才才会会调调度度第第i队列中的进程运行。队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。17第三章 处理机调度与死锁 3.多级反馈队列调度算法的性能多级反馈队列调度算法的性能(1)终端型作业用户。(2)(2)短批处理作业用户。(3)(3)长批处理作业用户。18第三章 处

19、理机调度与死锁 3.4 实实 时时 调调 度度 3.4.1 实现实时调度的基本条件实现实时调度的基本条件 1.提供必要的信息提供必要的信息(1)就绪时间。(2)(2)开始截止时间和完成截止时间。(3)(3)处理时间。(4)(4)资源要求。(5)(5)优先级。19第三章 处理机调度与死锁 2.系统处理能力强系统处理能力强 在在实实时时系系统统中中，通通常常都都有有着着多多个个实实时时任任务务。若若处处理理机机的的处处理理能能力力不不够够强强，则则有有可可能能因因处处理理机机忙忙不不过过来来而而使使某某些些实实时时任任务务不不能能得得到到及及时时处处理理，从从而而导导致致发发生生难难以以预预料料的

20、的后后果果。假假定定系系统统中中有有m个个周周期期性性的的硬硬实实时时任任务务，它它们们的的处处理理时时间间可可表表示示为为Ci，周周期期时时间间表表示示为为Pi，则则在在单单处处理理机机情情况况下下，必必须须满足下面的限制条件：满足下面的限制条件：系统才是可调度的。系统才是可调度的。20第三章 处理机调度与死锁 假假如如系系统统中中有有6个个硬硬实实时时任任务务，它它们们的的周周期期时时间间都都是是 50 ms，而每次的处理时间为，而每次的处理时间为 10 ms。系统可调度吗？系统可调度吗？不不难难算算出出，此此时时是是不不能能满满足足上上式式的的，因因而而系系统统是是不不可可调度的。调度的

21、。解决的方法是提高系统的处理能力，其途径有二：解决的方法是提高系统的处理能力，其途径有二：其一仍是其一仍是采用单处理机系统，采用单处理机系统，但须增强其处理能力，但须增强其处理能力，以显著地减少对每一个任务的处理时间；以显著地减少对每一个任务的处理时间；其二是其二是采用多处理机系统采用多处理机系统。假定系统中的处理机数为。假定系统中的处理机数为N，则应将上述的限制条件改为：，则应将上述的限制条件改为：21第三章 处理机调度与死锁 3.采用抢占式调度机制采用抢占式调度机制 当当一一个个优优先先权权更更高高的的任任务务到到达达时时，允允许许将将当当前前任任务务暂暂时时挂挂起起，而而令令高高优优先先

22、权权任任务务立立即即投投入入运运行行，这这样样便便可可满满足足该该硬硬实实时时任务对截止时间的要求。但这种调度机制比较复杂。任务对截止时间的要求。但这种调度机制比较复杂。对对于于一一些些小小的的实实时时系系统统，如如果果能能预预知知任任务务的的开开始始截截止止时时间间，则则对对实实时时任任务务的的调调度度可可采采用用非非抢抢占占调调度度机机制制，以以简简化化调调度度程程序序和和对对任任务务调调度度时时所所花花费费的的系系统统开开销销。但但在在设设计计这这种种调调度度机机制制时时，应应使使所所有有的的实实时时任任务务都都比比较较小小，并并在在执执行行完完关关键键性性程程序序和和临临界界区区后后，

23、能能及及时时地地将将自自己己阻阻塞塞起起来来，以以便便释释放放出出处处理理机机，供供调调度程序去调度那种开始截止时间即将到达的任务。度程序去调度那种开始截止时间即将到达的任务。22第三章 处理机调度与死锁 4.具有快速切换机制具有快速切换机制 该机制应具有如下两方面的能力：(1)对对外外部部中中断断的的快快速速响响应应能能力力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)。(2)快快速速的的任任务务分分派派能能力力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度，应使系统中的每

24、个运行功能单位适当的小，以减少任务切换的时间开销。23第三章 处理机调度与死锁 3.4.2 实时调度算法的分类实时调度算法的分类 1.非抢占式调度算法非抢占式调度算法(1)非抢占式轮转调度算法。(2)(2)非抢占式优先调度算法。24第三章 处理机调度与死锁 2.抢占式调度算法抢占式调度算法(1)基于时钟中断的抢占式优先权调度算法。(2)(2)立即抢占(Immediate Preemption)的优先权调度算法。图 3-6 实时进程调度 25第三章 处理机调度与死锁 3.4.3 常用的几种实时调度算法常用的几种实时调度算法 1.最早截止时间优先即最早截止时间优先即EDF(Earliest Dea

25、dline First)算法算法 图 3-7 EDF算法用于非抢占调度方式【例题】【例题】26第三章 处理机调度与死锁 2.最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)算法算法 该该算算法法是是根根据据任任务务紧紧急急(或或松松弛弛)的的程程度度，来来确确定定任任务务的的优优先先级级。任任务务的紧急程度愈高，为该任务所赋予的优先级就愈高，的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。以使之优先执行。例例如如，一一个个任任务务在在200ms时时必必须须完完成成，而而它它本本身身所所需需的的运运行行时时间间就就有有100ms，因因此此，调调度度程程

26、序序必必须须在在100 ms之之前前调调度度执执行行，该该任任务务的的紧紧急急程程度度(松松弛弛程程度度)为为100 ms。又又如如，另另一一任任务务在在400 ms时时必必须须完完成成，它它本本身身需需要要运行运行 150 ms，则其松弛程度为，则其松弛程度为 250 ms。在在实实现现该该算算法法时时要要求求系系统统中中有有一一个个按按松松弛弛度度排排序序的的实实时时任任务务就就绪绪队队列列，松松弛弛度度最最低低的的任任务务排排在在队队列列最最前前面面，调调度度程程序序总总是是选选择择就就绪绪队队列列中中的的队队首首任任务务执执行行。该该算算法法主主要要用用于于可可抢抢占占调调度度方方式式

27、中中。假假如如在在一一个个实实时时系系统统中中，有有两两个个周周期期性性实实时时任任务务A和和B，任任务务A要要求求每每 20 ms执执行行一一次次，执执行行时时间间为为 10 ms；任务；任务B只要求每只要求每50 ms执行一次，执行时间为执行一次，执行时间为 25 ms。27第三章 处理机调度与死锁 图 3-8 A和B任务每次必须完成的时间 在在刚刚开开始始时时(t1=0)，A1必必须须在在20ms时时完完成成，而而它它本本身身运运行行又又需需 10 ms，可可算算出出A1的的松松弛弛度度为为10ms；B1必必须须在在50ms时时完完成成，而而它它本本身身运运行行就需就需25 ms，可算出

28、，可算出B1的松弛度为的松弛度为25 ms，故调度程序应先调度，故调度程序应先调度A1执行。执行。在在t2=10 ms时，时，A2的松弛度可按下式算出：的松弛度可按下式算出：A2的松弛度的松弛度=必须完成时间必须完成时间-其本身的运行时间其本身的运行时间-当前时间当前时间 =40 ms-10 ms-10 ms=20 ms 类似地，可算出类似地，可算出B1的松弛度为的松弛度为15ms，故调度程序应选择，故调度程序应选择B1运行。运行。28第三章 处理机调度与死锁 在在t3=30 ms时时，A2的的松松弛弛度度已已减减为为0(即即40-10-30)，而而B1的的松松弛弛度度为为15 ms(即即50

29、-5-30)，于是调度程序应抢占，于是调度程序应抢占B1的处理机而调度的处理机而调度A2运行。运行。在在t4=40 ms时时，A3的的松松弛弛度度为为10 ms(即即60-10-40)，而而B1的的松松弛弛度度仅仅为为5 ms(即即50-5-40)，故又应重新调度，故又应重新调度B1执行。执行。在在t5=45 ms时时，B1执执行行完完成成，而而此此时时A3的的松松弛弛度度已已减减为为5 ms(即即60-10-45)，而，而B2的松弛度为的松弛度为30 ms(即即100-25-45)，于是又应调度，于是又应调度A3执行。执行。在在t6=55ms时时，任任务务A尚尚未未进进入入第第4周周期期，而

30、而任任务务B已已进进入入第第2周周期期，故故再再调度调度B2执行。执行。在在t7=70 ms时时，A4的的松松弛弛度度已已减减至至0 ms(即即80-10-70)，而而B2的的松松弛弛度度为为20 ms(即即100-10-70)，故此时调度又应抢占，故此时调度又应抢占B2的处理机而调的处理机而调度度A4执行。执行。图图 3-9 利用利用ELLF算法进行调度的情况算法进行调度的情况 29第三章 处理机调度与死锁 先来先服先来先服务务短作短作业优业优先先高响高响应应比比优优先先时间时间片片轮转轮转多多级级反反馈队馈队列列能否是可能否是可抢抢占占否否能能能能能能队队列内不一定列内不一定能否是不可能否

31、是不可抢抢占占能能能能能能否否队队列内不一定列内不一定优优点点公平，公平，实实现简单现简单，利于利于CPU繁忙型繁忙型平均等待平均等待时时间间最少，效最少，效率最高率最高兼兼顾长顾长短作短作业业兼兼顾长顾长短作短作业业兼兼顾长顾长短作短作业业，有有较较好的响好的响应时应时间间，利于，利于终终端型端型作作业业和短批和短批处处理理作作业业缺点缺点不利于短作不利于短作业业，不利用，不利用I/O繁忙型繁忙型长长作作业业会会饥饿饥饿，估估计时间计时间不易不易确定，未考确定，未考虑虑紧紧迫程度迫程度计计算响算响应应比比的开的开销销大大平均等待平均等待时间时间较长较长，上下文，上下文切切换换浪浪费时间费时间

32、尤其适用于尤其适用于作作业调业调度，度，批批处处理系理系统统分分时时系系统统相当通用相当通用能否用于作能否用于作业调业调度度能能能能能能否否否否能否用于能否用于进进程程调调度度能能能能能能能能能能 调度算法比较调度算法比较30第三章 处理机调度与死锁 关于调度算法的几点说明：关于调度算法的几点说明：（1）批处理系统、分时系统和实时系统中的主要调度算法：）批处理系统、分时系统和实时系统中的主要调度算法：l批处理系统批处理系统中即设有作业调度，又设有进程调度。批处理系中即设有作业调度，又设有进程调度。批处理系统中的作业调度算法有先来先服务（统中的作业调度算法有先来先服务（FCFS）、短作业优先）、

33、短作业优先（SJF）、优先级调度（）、优先级调度（HPF）和高响应比优先（）和高响应比优先（RF）。批处）。批处理系统的进程调度算法有：先进先出（理系统的进程调度算法有：先进先出（FIFO）、短进程优先）、短进程优先（SPF）、优先级调度（）、优先级调度（PRI）和高响应比优先（）和高响应比优先（RF）。）。l分时系统中分时系统中只设有进程调度，不设作业调度。其进程调度算只设有进程调度，不设作业调度。其进程调度算法只有轮转法（法只有轮转法（RR）一种。）一种。31第三章 处理机调度与死锁 关于调度算法的几点说明：关于调度算法的几点说明：实时系统实时系统中只设有进程调度，不设作业调度。其进程调度

34、中只设有进程调度，不设作业调度。其进程调度算法有：轮转法（算法有：轮转法（RR）、优先级调度算法（）、优先级调度算法（HPF）。后者）。后者又可细分为：非抢占式优先级调度、抢占式优先级调度又可细分为：非抢占式优先级调度、抢占式优先级调度（基于时钟中断的抢占式优先级调度和立即抢占的优先级（基于时钟中断的抢占式优先级调度和立即抢占的优先级调度）。调度）。说明：实时系统中不可以使用先进先出（说明：实时系统中不可以使用先进先出（FIFO）和短进）和短进程优先算法（程优先算法（SPF）。）。（2）时间片轮转法：分时系统中，多个进程以轮流方式）时间片轮转法：分时系统中，多个进程以轮流方式分享分享CPU，一

35、般与进程的优先级、进程进入就绪队列的时，一般与进程的优先级、进程进入就绪队列的时间、进程的长短等无关。间、进程的长短等无关。32第三章 处理机调度与死锁【例】下列选项中，降低进程优先级的合理时机是【例】下列选项中，降低进程优先级的合理时机是（）。）。（全国联考全国联考 2010）A.进程的时间片用完进程的时间片用完B.进程刚完成进程刚完成I/O，进入就绪队列，进入就绪队列C.进程长期处于就绪队列中进程长期处于就绪队列中D.进程从就绪状态转为运行态进程从就绪状态转为运行态答案：答案：A。33第三章 处理机调度与死锁 现有现有3个同时到达的作业个同时到达的作业J1、J2和和J3，它们的执行时，它们

36、的执行时间分别是间分别是T1、T2和和T3，且，且T1T2T3。系统按单道方。系统按单道方式运行且采用短作业优先算法，则平均周转时间是式运行且采用短作业优先算法，则平均周转时间是()。（西电（西电 2002）A.T1+T2+T3 B.（T1+T2+T3）/3C.（3T1+2T2+T3）/3 D.（T1+2T2+3T3）/334第三章 处理机调度与死锁【例】有【例】有5个任务个任务A，B，C，D，E，它们几乎同时到达，预，它们几乎同时到达，预计它们的运行时间为计它们的运行时间为10，6，2，4，8min。其优先级分别为。其优先级分别为3，5，2，1和和4，这里，这里5为最高优先级。对于下列每一种

37、调度算法，为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间（进程切换开销可不考虑）。计算其平均进程周转时间（进程切换开销可不考虑）。（1）先来先服务（按）先来先服务（按A，B，C，D，E）算法。）算法。（2）优先级调度算法。）优先级调度算法。（3）时间片轮转算法。）时间片轮转算法。35第三章 处理机调度与死锁 解：解：（1）采用先来先服务（）采用先来先服务（FCFS）调度算法时，）调度算法时，5个任务在系个任务在系统中的执行顺序、完成时间及周转时间如表统中的执行顺序、完成时间及周转时间如表3-2所示：所示：表表3-2 采用先来先服务（采用先来先服务（FCFS）调度算法）调度算法执行

38、次序执行次序到达时间到达时间服务时间服务时间开始执行时间开始执行时间完成时间完成时间周转时间周转时间A01001010B06101616C02161818D04182222E082230305个进程的平均周转时间个进程的平均周转时间T为：为：T=（10+16+18+22+30）36第三章 处理机调度与死锁（2）采用最高优先级调度（）采用最高优先级调度（HPF）算法时，）算法时，其优先级分其优先级分别为别为3，5，2，1和和4，这里，这里5为最高优先级。为最高优先级。5个任务在个任务在系统中的执行顺序、完成时间及周转时间如表系统中的执行顺序、完成时间及周转时间如表3-3所示：所示：表表3-3 采

39、用最高优先级调度算法采用最高优先级调度算法执行次序到达时间服务时间开始执行时间完成时间周转时间B06066E0861414A010142424C02242626D01262727它们的平均周转时间为：它们的平均周转时间为：T=（6+14+24+26+27）37第三章 处理机调度与死锁（3）如果系统采用时间片轮转（）如果系统采用时间片轮转（RR）算法，令时间片为）算法，令时间片为2分钟，分钟，5个任务轮流执行的情况为：个任务轮流执行的情况为：第第1轮：（轮：（A，B，C，D，E）第第2轮：（轮：（A，B，D，E）第第3轮：（轮：（A，B，E）第第4轮：（轮：（A，E）第第5轮：（轮：（A）由于由

40、于5个任务同时到达，所有任务到达时间都可以理解个任务同时到达，所有任务到达时间都可以理解为为0，因此，每个任务的周转时间为其最后一次获得的时间片，因此，每个任务的周转时间为其最后一次获得的时间片及之前系统所有时间片之和。显然，及之前系统所有时间片之和。显然，5个进程的周转时间为：个进程的周转时间为：T1=30min、T2=22min、T3=6min、T4=16min、T5=28min。它们的平均周转时间它们的平均周转时间T为：为：T=（30+22+6+16+28）38第三章 处理机调度与死锁 在一单道批处理系统中，一组作业的提交时间和运行时间在一单道批处理系统中，一组作业的提交时间和运行时间如

41、表所示。试计算以下如表所示。试计算以下3种作业调度算法的平均周转时间种作业调度算法的平均周转时间T和平均带权周转时间和平均带权周转时间W。（西北大学西北大学 1998）（1）先来先服务；）先来先服务；（2）短作业优先；）短作业优先；（3）响应比高者优先。）响应比高者优先。表表3-4 作业提交时间和运行时间表作业提交时间和运行时间表作业作业提交时间提交时间运行时间运行时间18.01.028.50.539.00.249.10.1【分析】本题目中，多个任务先后在不同时刻到达且不【分析】本题目中，多个任务先后在不同时刻到达且不要求等所有任务全部到达后才开始调度，也就是说，某个要求等所有任务全部到达后才开始调度，也就是说，某个作业到达时，如果后备队列是空，则立即得到调度。作业到达时，如果后备队列是空，则立即得到调度。【作业】【作业】39