调度与死锁-PPT课件.ppt

1、第4章 调度与死锁调度类型与准则调度类型与准则调度算法调度算法死锁的预防与避免死锁的预防与避免 死锁的基本概念死锁的基本概念死锁的检测与解除死锁的检测与解除4.1调度类型与准则调度类型与准则就绪阻塞执行退出创建进程调度超时I/O请求或等待某事件I/O完成或事件发生接纳完成阻塞挂起就绪挂起挂起挂起激活激活I/O完成或事件发生低级调度中级调度高级调度调度类型调度类型高级调度高级调度低级调度低级调度中级调度中级调度调度的层次调度的层次又称作业调度、宏观调度又称作业调度、宏观调度l任务：任务：决定将外存上后备队列中的哪些作业调入内存。l调度工作决定调度工作决定l接纳多少作业：取决于多道的程度，即内存允

2、许放多少个作业。l接纳哪些作业：有调度算法决定。l适用于批处理系统适用于批处理系统调度的层次调度的层次l又称进程调度、微观调度又称进程调度、微观调度l任务：任务：决定就绪队列中的哪些进程将获得处理机。l调度方式调度方式l非剥夺式l剥夺式l抢占原则抢占原则l时间片l优先权l进程长短l适用于分时、实时、批处理系统适用于分时、实时、批处理系统调度的层次调度的层次l又称对换程序又称对换程序l主要作用：主要作用：内存和外存对换区之间进行进程对换，以解决内存紧张问题。进程调度方式进程调度方式 非剥夺方式（非抢占方式）非剥夺方式（非抢占方式） 进程调度基本方式可分为非抢占和抢占方式： 进程被选中就一直运行下

3、去（不会因为时钟中断而被迫让进程被选中就一直运行下去（不会因为时钟中断而被迫让出出CPU），直至完成工作、自愿放弃），直至完成工作、自愿放弃CPU、或因某事件而、或因某事件而被阻塞才把被阻塞才把CPU让出给其它进程。让出给其它进程。剥夺方式（抢占方式剥夺方式（抢占方式 ）抢占方式发生的情况可为抢占方式发生的情况可为：新进程到达、出现中断且将阻新进程到达、出现中断且将阻塞进程转变为就绪进程、以及用完规定的时间片塞进程转变为就绪进程、以及用完规定的时间片等。等。好处为进程提供更好的服务，防止一个好处为进程提供更好的服务，防止一个进程长期占有进程长期占有CPU ，但开销大。，但开销大。 练习练习1.

4、1.作业是由用户提交的，进程是由系统自动生成，除此作业是由用户提交的，进程是由系统自动生成，除此之外，两者的区别是（之外，两者的区别是（ ）。）。 （A A）两者执行不同的程序段）两者执行不同的程序段 （B B）前者以用户任务为单位，后者是操作系统控）前者以用户任务为单位，后者是操作系统控制的单位制的单位 （C C）前者是批处理的，后者是分时的）前者是批处理的，后者是分时的 （D D）后者可并发执行，前者则不行）后者可并发执行，前者则不行练习练习2.2.当一进程运行时，系统可基于某种原因强行将其当一进程运行时，系统可基于某种原因强行将其撤下，把处理机分配给其他进程，这种调度方式撤下，把处理机分

5、配给其他进程，这种调度方式是（）。是（）。 ( () ) 非抢占式非抢占式 ( () ) 抢占式抢占式 ( () ) 中断方式中断方式 ( () ) 查找方式查找方式进程调度时机进程调度时机进程退出进程退出进程阻塞进程阻塞新进程创建新进程创建中断发生中断发生时钟中断时钟中断 调度的性能准则调度的性能准则面向用户的准则面向用户的准则响应时间快响应时间：从用户通过键盘提交请求到首次得到响应的时间周转时间短：周转时间：作业从提交到完成的时间间隔。优先权准则截止时间的保证面向系统的准则面向系统的准则系统吞吐量单位时间内完成的作业数。处理机利用率各类资源平衡利用公平周转时间定义周转时间定义ninTiT1

6、1实际服务时间实际服务时间等待时间实际服务时间周转时间TsiTiWininTsiTiW11周转时间周转时间Ti平均周转时间平均周转时间 带权周转时间带权周转时间 平均带权周转时间平均带权周转时间 siciittT响应时间定义响应时间定义n 响应时间；响应时间就是从任务就绪到处理开始（也有的称为等待时间）。 在交互式系统中，周转时间不可能是最好的评价准则。因为不断请求与不断输出在同时发生。 通常，响应时间一般用于分时系统性能评价，指用户通过键盘或终端提出一个请求开始到系统给出相应的响应结果的时间（与上面有所不同）。n 系统开销；系统开销就是系统调度任务的过程中所付出的时/空代价。 练习练习1.1

7、.从进程提交给系统开始到进程完成为止的时间间隔称从进程提交给系统开始到进程完成为止的时间间隔称为（为（ ）。）。 （A A）进程周转时间）进程周转时间 （B B）进程运行时间）进程运行时间 （C C）进程响应时间）进程响应时间 （D D）进程等待时间）进程等待时间练习练习2.2.设有设有4 4个作业同时到达，每个作业的执行时间为个作业同时到达，每个作业的执行时间为2 2小时，它们在单处理机上按单道方式运行，则平小时，它们在单处理机上按单道方式运行，则平均周转时间是（）小时。均周转时间是（）小时。 ( () 1) 1 ( () 5) 5 ( () 2.5) 2.5 ( () 8) 8练习练习3.

8、3.以下关于选择进程调度算法的准则错误的是以下关于选择进程调度算法的准则错误的是( (）。）。 ( () ) 尽量提高处理机利用率尽量提高处理机利用率 ( () ) 尽可能提高系统吞吐量尽可能提高系统吞吐量 ( () ) 适当增长进程在就绪队列中等待时间适当增长进程在就绪队列中等待时间 ( () ) 尽快响应交互式用户的请求尽快响应交互式用户的请求 作业调度算法与进程调度算法基本概念相通或相近的，只是空间位置空间位置有所不同。 系统中处于可运行状态进程的个数通常比处理机的个数要多，特别是在单处理机系统单处理机系统中尤为如此。这样就存在从就绪队列中选择哪一个进程，这就是调度算法问题。 先来先服务

9、调度算法短作业（进程）优先调度算法时间片轮转调度算法优先权调度算法多级反馈队列4.2 调度算法调度算法先来先服务先来先服务FCFSl算法思想算法思想 对于作业调度，从后备作业中选择最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。 对于进程调度，从就绪队列中选择最先进入该队列的进程，分配处理机，使之运行。 例1有四个作业（或进程），他们相应的时间见表： 作业作业到达时间到达时间 T Tinin服务服务时间时间T Tr r开始时间开始时间T TS S结束时间结束时间T Tc c周转时间周转时间T T带权周转时带权周转时间间W WA A0 01 1B B1 1100

10、100C C2 21 1D D3 3100100平均平均问题：问题：C的周转时间是所需要处理时间的100倍！ 作业D的周转时间近乎是C的两倍，但它的带权周转时间却低于2.0。 例2更一般的情况，设有五个作业，见表表 更一般作业类型的FCFS 的调度性能 TW作业作业到达时间到达时间T Tinin服务时服务时间间T Tr r开始时间开始时间T Ts s 结束时间结束时间T Tc c周转时间周转时间T T带权周转时带权周转时间间W WA A0 03 30 03 3T TA A=3=3W WA A=1=1B B2 26 63 39 9T TB B=7=7W WB B=1.17=1.17C C4 44

11、 49 91313T TC C=9=9W WC C=2.25=2.25D D6 65 513131818T TD D=12=12W WD D=2.40.=2.40.E E8 82 218182020T TE E=12=12W WE E=6=6平均平均 =8.60 =8.60 = 2.56 = 2.56同样，看到作业同样，看到作业E的不利情况。的不利情况。1. FCFS算法比较有利于长作业(进程)，而不利于短作业(进程)。2. FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业(进程)。u CPU繁忙型作业是指该类作业需要大量的CPU时间进行计算，而很少请求I/O。通常的科学计

12、算便属于CPU繁忙型作业。u I/O繁忙型作业是指CPU进行处理时需频繁地请求I/O。目前的大多数事务处理都属于I/O繁忙型作业。先来先服务先来先服务FCFS与短作业优先与短作业优先SJFl算法思想算法思想 短作业优先是从后备队列中选择估计运行时间最短的作业，将它们调入内存。 短进程优先是从就绪队列中选择估计运行时间最短的进程，将处理机分配给它，使之执行并一直到完成或因发生某事件而阻塞放弃处理机时，再重新调度。作业作业到达时间到达时间T Tinin服务时服务时间间T Tr r开始时间开始时间T Ts s 结束时间结束时间T Tc c 8 83 36 64 45 52 22 20 04 46 6

13、E EC CD DA AB B周转时间周转时间 T T平均平均带权周转时带权周转时 间间W W进程名 A B C D E 平 均 到达时间 0 1 2 3 4 作业 情况 调度 算法 服务时间 4 3 5 2 4 完成时间 4 7 12 14 18 周转时间 4 6 10 11 14 9 FCFS (a) 带权周转时间 1 2 2 5.5 3.5 2.8 完成时间 4 9 18 6 13 周转时间 4 8 16 3 9 8 SJF (b) 带权周转时间 1 2.67 3.1 1.5 2.25 2.1 SJF对短作业有利，并且整体性能也得到了提高；SJF的问题： n SJF需要事先知道或至少需要

14、估计每个作业所需估计每个作业所需的处理机时间的处理机时间。n 只要不断的有短作业进入系统，就有可能使长作业长期得不到运行而“饿死”。 n SJF 偏向短作业，不利于分时系统（由于不可抢占性）。 练习练习1.1.现有三个同时到达的作业现有三个同时到达的作业J1,J2,J3,J1,J2,J3,它们的执行时间它们的执行时间分别为分别为T1,T2,T3,T1,T2,T3,且且T1T2T3,T1T2T3,系统按单道方式运行且系统按单道方式运行且采用短作业优先算法，则平均周转时间是（采用短作业优先算法，则平均周转时间是（ ）。）。 （A A）T1+T2+T3 T1+T2+T3 （B B）（）（T1+T2+

15、T3T1+T2+T3）/3 /3 （C C）(3T1+2T2+T3)/3(3T1+2T2+T3)/3 （D D）（）（T1+2T2+3T3T1+2T2+3T3）/3 /3 时间片轮转调度算法时间片轮转调度算法(RR)算法思想算法思想进程按FCFS在就绪队列排队，调度程序把CPU分配给队首进程，令其执行一个时间片，一个时间片执行完毕将进程排在队尾。作业作业到达时间到达时间T Tinin服务时服务时间间T Tr r开始时间开始时间T Ts s 结束时结束时间间T Tc c 时间片轮转调度算法时间片轮转调度算法(RR)时间片大小的确定时间片大小的确定响应时间响应时间T=用户数目用户数目N*时间片时间

16、片q响应时间T当N一定，T与q成正比。T若要求快，则q也要小。就绪队列的进程数NT一定， q与N成反比。N越多， q要小。系统的处理能力保证用户键入的常用命令能在一个时间片内处理完毕。时间片大小时间片大小（a）时间片稍大于交互时间时间片q响应时间时间片q其它进程响应时间（b）时间片小于交互时间系统处理能力比较系统处理能力比较作业情况进程名ABCDE平均到达时间01234时间片服务时间43424完成时间151216917q=1周转时间15111461311.8带权周转时间3.753.673.533.333.46完成时间47111317q=4周转时间46910138.4带权周转时间122.2553

17、.332.5AAAABBBCCCCDDEEEEq=1ABCDEq=4算法思想算法思想 从后备队列中选择若干优先权最高的作业，将它们调入内存。 或从就绪队列中选择优先权最高的进程，将处理机分配给它。优先权类型优先权类型 静态优先权l确定因素：进程类型、进程对资源的需求、用户要求。 动态优先权l确定因素：等待时间、运行时间。特点：综合考虑各种情况特点：综合考虑各种情况优先权调度算法优先权调度算法高响应比优先调度算法高响应比优先调度算法 如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规

18、律可描述为： 要求服务时间要求服务时间等待时间优先权由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为： 要求服务时间响应时间要求服务时间要求服务时间等待时间PR由上式可以看出：(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。(2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。 (3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。作业作业到达时间到达时间T Tinin

19、服务时服务时间间T Tr r开始时间开始时间T Ts s 结束时间结束时间T Tc c 8 83 36 64 45 52 22 20 04 46 6E EC CD DA AB B周转时间周转时间 T T平均平均带权周转时带权周转时 间间W W最短剩余时间（SRT） SRT是针对 SJF 增加了强占机制的一种调度算法，它总是选择预期剩余时间最短的进程。只要新进程就绪，且有更短的剩余时间，调度程序就可能抢占当前正在运行的进程。作业作业到达时间到达时间T Tinin服务时服务时间间T Tr r开始时间开始时间T Ts s 结束时间结束时间T Tc c 3 36 64 45 52 2最短剩余时间（SR

20、T）SRT不象FCFS偏向长进程，也不象轮转法（下个算法）产生额外的中断，从而减少了开销。 必须记录过去的服务时间，从而增加了开销。 从周转时间来看，SRT 比SJF 有更好的性能。高响应比优先调度算法高响应比优先调度算法 如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为： 要求服务时间要求服务时间等待时间优先权由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为： 要求服务时间响应时间要求服务时间要求服务时间等待时间PR

21、由上式可以看出：(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。(2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。 (3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。作业作业到达时间到达时间T Tinin服务时服务时间间T Tr r开始时间开始时间T Ts s 结束时间结束时间T Tc c 8 83 36 64 45 52 22 20 04 46 6E EC CD DA AB B周转时间周转时间 T T平均平均带

22、权周转时带权周转时 间间W W不同调度算法对同一个 作业/进程的性能分析:W作业作业到达时间到达时间T Tinin服务时间服务时间T Tr r从平均周转时间及其平均带权周转时间来看，SRT 好于前面的任何一个算法。 A03 3B26 6C44 4D65 5E82 2FCFS8.602.56SJF7.601.84HRP8.002.14SRT7.201.59RR10.802.71T算法思想算法思想根据作业的性质和类型不同，将就绪队列再分为若干个子队列，每个进程分属于一个队列。在多级队列的基础上，不但设多个队列，且为每个队列赋予不同的优先权，第一个队列的优先权最高，第二个队列次之，其余队列的优先权逐

23、个降低。各个队列中的进程执行时间片大小逐渐增大。新进程投入第一个队列。调度从第一个队列进行，仅当第一个队列为空时，才调度第二个队列中的进程。多级反馈队列调度算法多级反馈队列调度算法多级反馈队列调度算法多级反馈队列调度算法CPU就绪队列1退出新进程就绪队列3就绪队列n就绪队列2S1CPU退出S2CPU退出S3CPU退出Sn时间片 S1 S2 S3 Sn各种常用调度算法的比较43/19 算法算法比较项比较项FCFSFCFSRRRRSJFSJFSRTSRTHRPHRPMFQMFQ调度方式调度方式非抢占式非抢占式抢占式抢占式( (按时间片按时间片) )非抢占式非抢占式抢占式抢占式( (进程到达进程到达

24、) )非抢占式非抢占式抢占式抢占式( (按时间片按时间片) )吞吐量吞吐量不突出不突出时间片太时间片太小小, ,可能变可能变低低高高高高高高不突出不突出响应时间响应时间可能很高，可能很高，对于短进对于短进程提供良程提供良好的响应好的响应时间时间对短作业对短作业/ /进程提供进程提供良好响应良好响应时间时间提供良好提供良好的响应时的响应时间间提供良好提供良好的响应时的响应时间间不突出不突出开销开销最小最小低低可能高可能高可能高可能高可能高可能高可能高可能高对进程对进程的作用的作用不利于短不利于短作业作业/ /进程进程和和I/OI/O忙型忙型公平对待公平对待不利于长不利于长作业作业/ /进程进程不

25、利于长不利于长进程进程良好的均良好的均衡衡（进程）（进程）可能偏向可能偏向I/OI/O繁忙的繁忙的作业作业/ /进程进程饥饿问题饥饿问题无无无无可能可能可能可能无无可能可能练习练习1.1.以下（以下（ ）是基于时间片的调度算法。）是基于时间片的调度算法。 （A A）时间片轮转法）时间片轮转法 （B B）高响应比优先调用算法）高响应比优先调用算法 （C C）抢占式调用算法）抢占式调用算法 （D D）先来先服务算法）先来先服务算法练习练习2.2.时间片轮转算法经常用于（时间片轮转算法经常用于（ ）。）。 （A A）单用户操作系统）单用户操作系统 （B B）实时系统）实时系统 （C C）分时系统）分

26、时系统 （D D）批处理系统）批处理系统练习练习3.3.以下（以下（ ）算法与作业的运行时间有关。）算法与作业的运行时间有关。 （A A）优先级调度）优先级调度 （B B）时间片轮转）时间片轮转 （C C）短作业优先）短作业优先 （D D）先来先服务）先来先服务练习练习4.4.（ ）优先级是在创建进程时确定的，确定之后在）优先级是在创建进程时确定的，确定之后在整个进程运行期间不再改变。整个进程运行期间不再改变。 （A A）先来先服务）先来先服务 （B B）静态）静态 （C C）动态）动态 （D D）短作业）短作业 练习练习5.5.对于处理机调度中高响应比调度算法，通常影响响应对于处理机调度中高

27、响应比调度算法，通常影响响应比的主要因素可以是（比的主要因素可以是（ ）。）。 （A A）程序长度）程序长度 （B B）静态优先数）静态优先数 （C C）运行时间）运行时间 （D D）等待时间）等待时间练习练习6 6. .设有三个作业，其运行时间分别是设有三个作业，其运行时间分别是2h,5h,3h,假定它们同时到假定它们同时到达，并在同一台处理器上以单道方式运行，则平均周转时间达，并在同一台处理器上以单道方式运行，则平均周转时间最小的执行顺序是（最小的执行顺序是（ ）A J1,J2,J3 B J3,J2,J1C J2,J1,J3 D J1,J3,J2练习练习7 7. .下列算法中，（ ）调度算

28、法是绝对可以抢占的。A 先来先服务B 时间片轮转C 优先级D 短进程优先练习练习8.关于优先权大小的论述中，正确的是（）计算型作业的优先权，应高于/O型作业的优先权用户进程的优先权，应高于系统进程的优先权在动态优先权中，随着作业等待时间的增加，其优先权将随之下降在动态优先权中，随着进程执行时间的增加，其优先权降低练习练习9.假设某操作系统采用时间片轮转调度策略,分配给A类进程的时间片为100ms,分配给B类进程的时间片为400ms,就绪进程队列的平均长度为5(包括正在运行的进程),其中A类进程有4个,B类进程有1个,所有进程的平均服务时间为2s,问A类进程和B类进程的平均周转时间各为少?(不考

29、虑I/O情况)(a)可能死锁(b)死锁4.3 死锁的基本概念死锁的基本概念产生死锁的原因产生死锁的原因资源数 要求该种资源的进程数进程的推进顺序非法进程进程Pget(A);get(B);release(A);release(B); 进程进程Qget(B);get(A);release(B);release(A);A、B分别代表某种资源进程的推进顺序不当进程的推进顺序不当(1)申请B申请A释放B释放A申请B释放B释放A申请Axy(2)(3)(4)(5)(6)P和Q都想要AP和Q都想要B死锁地带进程P进程Q(1)、(2) 、(4) 、(5)正常运行正常运行(3) 、(6)发生死锁发生死锁进程的推进

30、顺序合适进程的推进顺序合适(1)申请B申请A释放B释放A申请B释放B释放A申请Axy(2)(3)(4)(5)(6)P和Q都想要AP和Q都想要B进程P进程Q进程进程P对对资源的申资源的申请、释放请、释放次序改变次序改变后不死锁！后不死锁！交换交换P操作的位置操作的位置void producer() /生产者进程生产者进程 while (true) produce an item in data_p; P(empty); P(mutex); bufferi = data_p; i = (i + 1) % n; V(mutex); V(full); void consumer()/消费者进程消费者进

31、程while (true) P(mutex); P(full);data_c = bufferj; j = (j + 1) % n; V(mutex); V(empty); consume the item in data_c; 问题的提出：对于生产者问题的提出：对于生产者-消费者问题，如果消费者问题，如果将将P操作的位置交换，将产生什么样的后果？操作的位置交换，将产生什么样的后果？void producer() /生产者进程生产者进程 while (true) produce an item in data_p; P(mutex); P(empty); bufferi = data_p; i

32、 = (i + 1) % n; V(mutex); V(full); void consumer()/消费者进程消费者进程while (true) P(full); P(mutex);data_c = bufferj; j = (j + 1) % n; V(mutex); V(empty); consume the item in data_c; 交换交换P操作的位置操作的位置产生死锁的四个必要条件产生死锁的四个必要条件不剥夺条件不剥夺条件互斥条件互斥条件请求保持条件请求保持条件环路条件环路条件 (1)（资源独占）一个资源每次只能给一个进程使用(2)（部分分配，占有申请） 一个进程在申请新的资

33、源的同时保持对原有资源的占有 (3) （不可强占）资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放练习练习1.1.当出现（当出现（ ）情况下，系统出现死锁。）情况下，系统出现死锁。 （A A）计算机系统发生了重大故障）计算机系统发生了重大故障 （B B）资源个数远远小于进程数）资源个数远远小于进程数 （C C）若干进程因竞争资源而无休止地相互等待他）若干进程因竞争资源而无休止地相互等待他方释放已占有的资源方释放已占有的资源 （D D）进程同时申请的资源数超过资源总数）进程同时申请的资源数超过资源总数练习练习2.2.为多道程序提供的可共享资源不足时，可能出现死锁，为多道程序

34、提供的可共享资源不足时，可能出现死锁，但是，不适当的（但是，不适当的（ ）也可能产生死锁。）也可能产生死锁。 （A A）进程优先权）进程优先权 （B B）资源的线性分配）资源的线性分配 （C C）进程推进顺序）进程推进顺序 （D D）分配队列的优先权）分配队列的优先权练习练习3.3.以下（以下（ ）情况下，系统可能出现死锁。）情况下，系统可能出现死锁。 （A A）进程释放资源）进程释放资源 （B B）一个进程进入死循环）一个进程进入死循环 （C C）多个进程竞争资源出现了循环等待）多个进程竞争资源出现了循环等待 （D D）多个进程竞争）多个进程竞争CPUCPU练习练习4.4.一个进程在获得资源

35、后，只能在使用完资源后由自己一个进程在获得资源后，只能在使用完资源后由自己释放，这属于死锁必要条件的（释放，这属于死锁必要条件的（ ）。）。 （A A）互斥条件）互斥条件 （B B）请求与释放条件）请求与释放条件 （C C）不剥夺条件）不剥夺条件 （D D）环路等待条件）环路等待条件练习练习5.5.死锁产生的必要条件是互斥，（死锁产生的必要条件是互斥，（ ），不剥夺和环），不剥夺和环路等待。路等待。 （A A）请求与阻塞）请求与阻塞 （B B）请求与保持）请求与保持 （C C）请求与释放）请求与释放 （D D）释放与阻塞）释放与阻塞采用预先静态分配方法采用预先静态分配方法 系统要求所有进程一次

36、性地申请其所需的全部资源l优点：优点： 方法简单l缺点：缺点： 进程延迟运行 资源浪费 用户有时提不出他要使用的全部资源去掉去掉“请求保持条件请求保持条件”互斥条件不可禁止互斥条件不可禁止去掉去掉“不剥夺条件不剥夺条件”去掉去掉“环路环路“条件条件l方法方法占有某些资源的进程，当它有新的资源请求被拒绝时，该进程停止运行，并释放它所占有的资源。当它再次被执行时，重新申请资源。如果一个进程请求另一个进程占有的资源，操作系统可以剥夺后者占有的资源，要求它释放资源并将资源分配给前者使用 l缺点缺点 该策略实现起来比较复杂，而且要付出很大代价。 反复申请、释放，使进程执行无限延迟，不仅延迟了周转时间。还

37、增加了系统开销，降低了系统吞吐量。l采用资源的有序分配采用资源的有序分配 令所有资源排队，并赋予不同的序号。当进程请求资源时，必须严格按递增的次序提出，从而消除了环路。l缺点：缺点： 定好序号后，增加新设备类型受到限制。 尽管定序号时考虑大多数作业使用资源的顺序。但会发生使用顺序与规定顺序不一致的情况，造成资源浪费。限制用户简单、自主地编程 。死锁的预防死锁的预防4.4死锁的预防与避免死锁的预防与避免练习练习1发生死锁的必要条件有四个，要防止死锁产生，可以通过破坏这4个必要条件之一来实现，但破坏（ ）条件是不可行的。 A 互斥 B 不可剥夺 C 请求与保持 D 循环等待练习练习2一次分配所有资

38、源的方法可以预防死锁的发生，它破坏了死锁四个必要条件中的（ ）A 互斥B 请求并保持C 非剥夺D 循环等待练习练习3死锁预防是保证系统不进入死锁状态的静态策略，其解决办法是破坏产生死锁的四个必要条件之一，下列方法中破坏了“循环等待”条件的是（ ）A 银行家算法B 一次性分配策略C 剥夺资源法D 资源有序分配策略安全状态是指系统至少存在一个安全序列，按照这个序列为进程分配资源，直到满足最大需求，每个进程都可顺序完成。若系统不存在这样一个安全序列，则系统处于不安全状态。避免死锁是通过明智的选择，确保系统永远不会避免死锁是通过明智的选择，确保系统永远不会到达死锁点到达死锁点 。即动态地决定是否分配资

39、源给进程！即动态地决定是否分配资源给进程！安全状态安全状态与与不安全状态不安全状态死锁的避免死锁的避免 系统有三个进程P1、P2、P3，共有12台磁带机，进程P1要求10台，P2要求4台，P3要求9台。在T0时刻，进程P1、P2、P3已获得5、2、2台，尚有3台未分配，问：系统是否处于安全状态？进程 最大需求 已分配 可用P1 10 53P2 4 2 P3 9 2存在安全序列实例安全状态安全状态银行家算法银行家算法进行资源预分配进行资源预分配实施安全检测实施安全检测 安全：真正资源分配 不安全：回到预分配前状态银行家算法银行家算法1.1.银行家算法中的数据结构银行家算法中的数据结构 （1）可利

40、用资源向量可利用资源向量AvailableAvailable。它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目。如： ABC523银行家算法银行家算法1.1.银行家算法中的数据结构银行家算法中的数据结构 （2）最大需求矩阵）最大需求矩阵Max。n*m矩阵，表示矩阵，表示n个进程的每一个对个进程的每一个对m类资源的最大需求。类资源的最大需求。ABCP1562P2331P3425P4332银行家算法银行家算法1.1.银行家算法中的数据结构银行家算法中的数据结构 （3）分配矩阵）分配矩阵Allocation 。n*m矩阵，表矩阵，表示每个进程分配的资源数。示每个进程分配的资源数。AB

41、CP1212P2121P3222P4132银行家算法银行家算法1.1.银行家算法中的数据结构银行家算法中的数据结构 （4）需求矩阵）需求矩阵Need 。n*m矩阵，表示每矩阵，表示每个进程还需要各类资源数。个进程还需要各类资源数。ABCP1352P2211P3223P4232l2银行家算法 Pi请求资源请求资源Requesti Needi请求超量，错返请求超量，错返Requesti Available不满足，等待不满足，等待Available:=Available-RequestiAllocationi:=Allocationi+RequestiNeedi:=Needi-Requesti安全安

42、全确认，确认，pi继续继续Available:=Available+RequestiAllocationi:=Allocationi-RequestiNeedi:=Needi+Requestipi等待等待FTFTTF安全性检测算法FWork:=Available;Finish:=false; 有满足条件的有满足条件的j:Finishj=falseNeedj WorkFinishj=true;Work:=Work+AllocationjT j ,finishj=trueTF安全安全不安全不安全银行家算法银行家算法l设系统有五个进程和三类资源，每类资源分别设系统有五个进程和三类资源，每类资源分别有

43、有10、5、7。在。在T0时刻资源分配情况如图时刻资源分配情况如图: 资源情况资源情况进程进程MaxMaxA B CA B CAllocationAllocationA B CA B CNeedNeedA B CA B CAvailableAvailableA B CA B CP0P07 5 37 5 30 1 00 1 07 4 37 4 33 3 23 3 2P1P13 2 23 2 22 0 02 0 01 2 21 2 2P2P29 0 29 0 23 0 23 0 26 0 06 0 0P3P32 2 22 2 22 1 12 1 10 1 10 1 1P4P44 3 34 3 30

44、 0 20 0 24 3 14 3 1(1) T0时刻可以找到一个安全序列时刻可以找到一个安全序列p1,p3,p4,p2,p0, 系统是系统是安全的安全的银行家算法银行家算法l(2) P1发出请求发出请求Request(1,0,2)，执行银行家算法，执行银行家算法: 资源情况资源情况进程进程MaxMaxA B CA B CAllocationAllocationA B CA B CNeedNeedA B CA B CAvailableAvailableA B CA B CP0P07 5 37 5 30 1 00 1 07 4 37 4 33 3 23 3 22 3 02 3 0P1P13 2

45、23 2 22 0 02 0 03 0 23 0 21 2 21 2 20 02 02 0P2P29 0 29 0 23 0 23 0 26 0 06 0 0P3P32 2 22 2 22 1 12 1 10 1 10 1 1P4P44 3 34 3 30 0 20 0 24 3 14 3 1可以找到一个安全序列可以找到一个安全序列p1,p3,p4,p0,p2，系统是安全的，可以将可以将P1的请求分配给它。的请求分配给它。银行家算法银行家算法l() P4发出请求发出请求Request(3,3,0), 执行银行家算法执行银行家算法: 资源情况资源情况进程进程MaxMaxA B CA B CAll

46、ocationAllocationA B CA B CNeedNeedA B CA B CAvailableAvailableA B CA B CP0P07 5 37 5 30 1 00 1 07 4 37 4 32 3 02 3 0P1P13 2 23 2 23 0 23 0 20 02 02 0P2P29 0 29 0 23 0 23 0 26 0 06 0 0P3P32 2 22 2 22 1 12 1 10 1 10 1 1P4P44 3 34 3 30 0 20 0 24 3 14 3 1Available=（2, 3, 0），RequestiAvailable ，所以P4等待。银行

47、家算法银行家算法l(4) P0请求资源请求资源Request（0，2，0），执行银），执行银行家算法，行家算法，试试分配后分配后: 资源情况资源情况进程进程MaxMaxA B CA B CAllocationAllocationA B CA B CNeedNeedA B CA B CAvailableAvailableA B CA B CP0P07 5 37 5 30 3 00 3 07 2 37 2 32 1 02 1 0P1P13 2 23 2 23 0 23 0 20 02 02 0P2P29 0 29 0 23 0 23 0 26 0 06 0 0P3P32 2 22 2 22 1 1

48、2 1 10 1 10 1 1P4P44 3 34 3 30 0 20 0 24 3 14 3 1Available(2,1,0) 不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配的请求不能分配练习练习1.1.某个时刻进程的资源使用情况如表所示，此时安全序列是某个时刻进程的资源使用情况如表所示，此时安全序列是（ ）. . A P1P2P3P4 B P1P3P2P4 A P1P2P3P4 B P1P3P2P4 C P1P4P3P2 D C P1P4P3P2 D 不存在不存在进程已分配资源尚需资源可用资源R1R2R3R1R2R3R1R2R3P1200001021P2120132P3

49、011131P4001200练习练习 设系统中有设系统中有3种类型的资源（种类型的资源（A，B，C）和）和5个进程个进程P1，P2，P3，P4，P5，A资源数为资源数为17，B资源数为资源数为5， C资源数为资源数为20。假设系统在假设系统在t0时刻如下表所示，系统采用银行家算法避免死锁。时刻如下表所示，系统采用银行家算法避免死锁。进程最大资源需求已分配资源可用资源ABCABCABCP1559212233P2536402P34011405P4425204P5424314 1） t0t0时刻是不否为安全状态？若是，请给出安全序列。时刻是不否为安全状态？若是，请给出安全序列。2） 若在若在t0时刻

50、进程时刻进程P2申请资源（申请资源（0，3，4），是否能实施资源分配？），是否能实施资源分配？3） 在（在（2）基础上，若进程）基础上，若进程P4申请资源（申请资源（2，0，1），是否能实施资源分配？），是否能实施资源分配？4） 在（在（3）基础上，若进程）基础上，若进程P1申请资源（申请资源（0，2，0），是否能实施资源分配？），是否能实施资源分配？4.5死锁的检测与解除死锁的检测与解除 由二元组G=G=（V V，E E） V V：结点集，分为P(进程)，R(资源)两部分 P=p1,p2,pn, P=p1,p2,pn, R=r1,r2,rm R=r1,r2,rm E E：边的集合，其元素为有