第三章计算机操作系统处理机调度与死锁

1、2021-10-142021-10-141 12021-10-142021-10-142 2内容概述内容概述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 死锁的检测与解除死锁的检测与解除 2021-10-142021-10-143 33.1.1 3.1.1 高级调度高级调度3.1.2 3.1.2 低级调度低级调度3.1.3 3.1.3

2、中级调度中级调度2021-10-142021-10-144 43.1.1 3.1.1 高级调度高级调度1.1.高级调度的含义高级调度的含义又称为又称为作业调度作业调度或或长程调度：长程调度：将外存上处于将外存上处于后备队列后备队列上上的作业调入内存，并创建进程、分配资源，安排在的作业调入内存，并创建进程、分配资源，安排在就绪就绪队列队列上。上。2.2.作业作业程序、数据和作业说明书。以作业为单位从外存调入内程序、数据和作业说明书。以作业为单位从外存调入内存。存。2021-10-142021-10-145 53.3.作业控制块作业控制块JCBJCBv 是作业在系统中存在的标志。是作业在系统中存在

3、的标志。v JCBJCB包含的内容：包含的内容：作业标识作业标识用户名称、用户账户用户名称、用户账户作业类型（作业类型（CPUCPU繁忙型、繁忙型、I/OI/O繁忙型等）、作业状态繁忙型等）、作业状态调度信息（优先级、已运行时间）调度信息（优先级、已运行时间）资源需求（预计运行时间、内存大小、资源需求（预计运行时间、内存大小、I/OI/O设备类型等）设备类型等）进入系统时间、开始处理时间、作业完成时间、作业推进入系统时间、开始处理时间、作业完成时间、作业推出时间出时间资源使用情况资源使用情况2021-10-142021-10-146 64.4.作业调度作业调度在每次执行作业调度时，都须做出以下

4、两个在每次执行作业调度时，都须做出以下两个决定决定：(1)(1)接纳多少个作业接纳多少个作业 取决于取决于多道程序度，多道程序度，即允许多少个作业同时在内存即允许多少个作业同时在内存中运行。中运行。作业太少作业太少 资源利用率低资源利用率低作业太多作业太多 服务质量下降服务质量下降(2)(2)接纳哪些作业：作业调度算法接纳哪些作业：作业调度算法先来先服务先来先服务短作业优先短作业优先优先权高优先优先权高优先2021-10-142021-10-147 73.1.1 3.1.1 高级调度高级调度3.1.2 3.1.2 低级调度低级调度3.1.3 3.1.3 中级调度中级调度2021-10-1420

5、21-10-148 81.1.低级调度的含义低级调度的含义也称为也称为进程调度进程调度或或短程调度短程调度，决定就绪队列中的，决定就绪队列中的哪个进程应获得处理机。哪个进程应获得处理机。2.2.低级调度的功能低级调度的功能保存处理机的现场信息保存处理机的现场信息按照某种算法选取进程按照某种算法选取进程把处理机分配给进程（恢复处理机现场）把处理机分配给进程（恢复处理机现场）2021-10-142021-10-149 93.3.进程调度方式进程调度方式 (1)(1)非抢占方式非抢占方式( (非剥夺方式非剥夺方式) ) (2) (2)抢占方式（剥夺方式抢占方式（剥夺方式)抢占原则抢占原则优先权原则优

6、先权原则短作业短作业( (进程进程) )优先原则优先原则时间片原则时间片原则2021-10-142021-10-1410103.1.1 3.1.1 高级调度高级调度3.1.2 3.1.2 低级调度低级调度3.1.3 3.1.3 中级调度中级调度2021-10-142021-10-141111中级调度又称中级调度又称中程调度中程调度为了提高为了提高内存利用率内存利用率和和系统吞吐量系统吞吐量暂时不能运行的进程，而将它们调至外存上去等待，把此暂时不能运行的进程，而将它们调至外存上去等待，把此时的进程状态称为时的进程状态称为就绪驻外存就绪驻外存状态或状态或挂起挂起状态。当这些进程状态。当这些进程重又

7、具备运行条件、且内存又稍有空闲时重又具备运行条件、且内存又稍有空闲时, ,由中级调度来决由中级调度来决定把外存上的哪些又具备运行条件的就绪进程定把外存上的哪些又具备运行条件的就绪进程, ,重新调入内重新调入内存存, ,并修改其状态为并修改其状态为就绪就绪状态状态, ,挂在就绪队列上等待进程调度挂在就绪队列上等待进程调度对换功能对换功能2021-10-142021-10-141212内容概述内容概述3.1 3.1 处理机调度的层次处理机调度的层次 3.2 3.2 调度队列模型和调度准则调度队列模型和调度准则 3.3 3.3 调度算法调度算法 3.4 3.4 实时调度实时调度 3.5 3.5 产生

8、死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 2021-10-142021-10-1413133.2.1 3.2.1 调度队列模型调度队列模型3.2.2 3.2.2 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则2021-10-142021-10-1414143.2.1 3.2.1 调度队列模型调度队列模型1.1.仅有进程调度的调度队列模型仅有进程调度的调度队列模型图图3-1 3-1 仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型 2021-10-142021-10-14

9、15152.2.具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型图图3-2 3-2 具有高、低两级调度的调度队列模型具有高、低两级调度的调度队列模型 2021-10-142021-10-1416163.3.同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 图图3-3 3-3 具有三级调度时的调度队列模型具有三级调度时的调度队列模型 2021-10-142021-10-1417173.2.1 3.2.1 调度队列模型调度队列模型3.2.2 3.2.2 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则2021-10-142021-10-1418181.

10、1. 面向用户的准则面向用户的准则(1)(1)周转时间短周转时间短(2)(2)响应时间快响应时间快(3)(3)截止时间保证截止时间保证(4)(4)优先权准则优先权准则 作业周转时间作业周转时间： 作业在外存后备队列上等待作作业在外存后备队列上等待作业业 调度的时间调度的时间 进程在就绪队列上等待进程调进程在就绪队列上等待进程调度度 的时间的时间 进程在进程在CPU上执行的时间上执行的时间 进程等待进程等待I/O操作完成的时间操作完成的时间n11iiTnTniSiiTTnW11平均周转时间平均周转时间：平均带权周转时间平均带权周转时间：2021-10-142021-10-1419192. 2.

11、面向系统的准则面向系统的准则 (1)(1)系统吞吐量高系统吞吐量高 吞吐量吞吐量指单位时间内系统所完成的作业数指单位时间内系统所完成的作业数 作业调度的方式和算法对吞吐量的大小有较大影响作业调度的方式和算法对吞吐量的大小有较大影响(2)(2)处理机利用率高处理机利用率高(3)(3)各类资源的平衡利用各类资源的平衡利用 使内存、外存和使内存、外存和I/OI/O设备的利用率高设备的利用率高2021-10-142021-10-142020内容概述内容概述3.1 3.1 处理机调度的层次处理机调度的层次 3.2 3.2 调度队列模型和调度准则调度队列模型和调度准则 3.3 3.3 调度算法调度算法 3

12、.4 3.4 实时调度实时调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 2021-10-142021-10-1421213.2.1 3.2.1 先来先服务和短作业优先算法先来先服务和短作业优先算法3.2.2 3.2.2 高优先权优先调度算法高优先权优先调度算法3.2.3 3.2.3 基于时间片的轮转调度算法基于时间片的轮转调度算法2021-10-142021-10-1422223.2.1 3.2.1 先来先服务和短作业先来先服务和短作业( (进程进程) )优先调度算法优先调

13、度算法 1.1.先来先服务调度算法先来先服务调度算法(FCFS)(FCFS) 按照作业进入系统的按照作业进入系统的先后次序先后次序进行调度，先进入系统进行调度，先进入系统者先调度；即启动等待时间最长的作业。者先调度；即启动等待时间最长的作业。 是一种最简单的调度算法，即可用于是一种最简单的调度算法，即可用于作业调度作业调度，也可，也可用于用于进程调度。进程调度。 FCFSFCFS算法比较有利于算法比较有利于长作业长作业( (进程进程) ), ,而不利于而不利于短作业短作业( (进程进程) )。2021-10-142021-10-142323内存内存无限大无限大，作业调度和进程调度都采用，作业调

14、度和进程调度都采用FCFSFCFS。作业名作业名 进入磁盘进入磁盘 需要服务需要服务 装入主存装入主存 开始执行开始执行 结束执行结束执行 周转周转 带权周转带权周转时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 A A 0 1 0 1 B B 1 1 100 100 C C 2 2 1 1 D D 3 3 100 100执行顺序执行顺序: :A-B-C-DA-B-C-D周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间0 00 01 11 11 11 13 31 1101101

15、1001001 12 21021022022021991991.991.99101101102102100100100100平均值平均值:100:10025.997525.99752021-10-142021-10-1424242.2.短作业短作业( (进程进程) )优先调度算法优先调度算法SJ(P)FSJ(P)F对短作业或短进程优先调度的算法对短作业或短进程优先调度的算法。可以分别用于可以分别用于作业调度作业调度和和进程调度。进程调度。调度过程调度过程SJFSJF：从后备队列中选择：从后备队列中选择一个或若干个一个或若干个估计运行时间估计运行时间最短最短的作业，将它们调入内存运行。的作业，将

16、它们调入内存运行。SPFSPF：从就绪队列中选出：从就绪队列中选出一个一个估计运行时间最短估计运行时间最短的进的进程，将处理机分配给它，使它立即执行并一直执行程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。重新调度。2021-10-142021-10-1425251 1）内存）内存无限大无限大, ,作业调度和进程调度都采用作业调度和进程调度都采用FCFSFCFS作业名作业名 进入磁盘进入磁盘 需要服务需要服务 装入主存装入主存 开始执行开始执行 结束执行结束执行 周转周转 带权周转带权周转时间时间 时

17、间时间 时间时间 时间时间 时间时间 时间时间 时间时间 A A 0 4 0 4 B B 1 1 3 3 C C 2 2 5 5 D D 3 3 2 2 E E 4 4 4 4执行顺序执行顺序: :A-B-C-D-EA-B-C-D-E2 2）作业调度和进程调度都采用）作业调度和进程调度都采用SJFSJF A A 0 4 0 4 B B 1 1 3 3 C C 2 2 5 5 D D 3 3 2 2 E E 4 4 4 4周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间0 00 04 44 41 11

18、 13 34 47 76 62 22 21212141411115.55.57 7121210102 24 41414181814143.53.50 00 04 44 41 11 13 36 69 98 88/38/32 24 46 63 31.51.513131818161616/516/54 49 913139 99/49/4平均值平均值: 9 92.82.8平均值平均值: 8 82.12.1执行顺序执行顺序: :A-D-B-E-CA-D-B-E-C2021-10-142021-10-142626SJ(P)FSJ(P)F调度算法也存在不容忽视的调度算法也存在不容忽视的缺点缺点: : (1)

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

20、而用户又可能会有意或无意地缩短其作业的估计运行时间的估计运行时间, ,致使该算法不一定能真正做到短作业优先致使该算法不一定能真正做到短作业优先调度。调度。2021-10-142021-10-1427273.2.1 3.2.1 先来先服务和短作业优先算法先来先服务和短作业优先算法3.2.2 3.2.2 高优先权优先调度算法高优先权优先调度算法3.2.3 3.2.3 基于时间片的轮转调度算法基于时间片的轮转调度算法2021-10-142021-10-1428281.1.优先权调度算法的类型优先权调度算法的类型 (1)(1)非抢占式非抢占式优先权算法优先权算法主要用于主要用于批处理系统批处理系统中，

21、也可用于某些对中，也可用于某些对实时性要实时性要求求不严不严的实时系统中。的实时系统中。(2)(2)抢占式抢占式优先权调度算法优先权调度算法能更好地满足能更好地满足紧迫紧迫作业的要求作业的要求, ,故而常用于故而常用于要求比要求比较较严格严格的实时系统中的实时系统中, , 以及对性能要求较高的批处以及对性能要求较高的批处理和分时系统中。理和分时系统中。2021-10-142021-10-1429292.2.优先权的类型优先权的类型(1)(1)静态优先权静态优先权在在创建进程创建进程时时确定确定的，且在进程的整个运行期间保持不变。的，且在进程的整个运行期间保持不变。一般地。一般地。(2)(2)动

22、态优先权动态优先权在创建进程时所赋予的优先权在创建进程时所赋予的优先权, ,是可以随是可以随进程的推进进程的推进或随或随其其等待时间的增加等待时间的增加而改变的而改变的, ,以便获得更好的调度性能。以便获得更好的调度性能。2021-10-142021-10-1430303.3.高响应比优先调度算法高响应比优先调度算法(HRF)(HRF)该算法是该算法是FCFSFCFS和和SJFSJF的结合，克服了两种算法的缺点。的结合，克服了两种算法的缺点。响应比响应比最高的作业优先启动最高的作业优先启动由于由于等待时间等待时间与与服务时间服务时间之和之和, ,就是系统对该作业的就是系统对该作业的响响应时间应

23、时间，故该优先权又相当于，故该优先权又相当于响应比响应比R RP P。据此，又可。据此，又可表示为表示为要求服务时间要求服务时间等待时间优先权要求服务时间响应时间要求服务时间要求服务时间等待时间pR2021-10-142021-10-143131对高响应比优先调度算法对高响应比优先调度算法(HRF)(HRF)的的解释解释 (1)(1)如果作业的如果作业的等待时间等待时间相同相同, ,则要求则要求服务的时间服务的时间愈愈短短, ,其优先权愈高其优先权愈高, ,因而该算法有利于短作业。因而该算法有利于短作业。 (2)(2)当当要求服务的时间要求服务的时间相同相同时时, ,作业的优先权决定于作业的优

24、先权决定于其等待时间其等待时间, ,等待时间愈等待时间愈长长, ,其优先权愈其优先权愈高高, ,因而它实现的因而它实现的是是先来先服务先来先服务。 (3)(3)对于长作业对于长作业, ,作业的优先级可以随作业的优先级可以随等待时间等待时间的的增增加加而提高而提高, ,当其等待时间足够长时当其等待时间足够长时, ,其优先级便可升到很其优先级便可升到很高高, ,从而也可获得处理机。从而也可获得处理机。2021-10-142021-10-1432323.2.1 3.2.1 先来先服务和短作业优先算法先来先服务和短作业优先算法3.2.2 3.2.2 高优先权优先调度算法高优先权优先调度算法3.2.3

25、3.2.3 基于时间片的轮转调度算法基于时间片的轮转调度算法2021-10-142021-10-1433333.2.3 3.2.3 基于时间片的轮转调度算法基于时间片的轮转调度算法 1.1.时间片轮转法时间片轮转法 就绪进程按先来先服务的原则排成一个队列，每次调度就绪进程按先来先服务的原则排成一个队列，每次调度时，把时，把CPUCPU分配给队首进程，并令其执行一个时间片。分配给队首进程，并令其执行一个时间片。 当执行的时间片用完时，停止该进程的执行，并将它送当执行的时间片用完时，停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列往就绪队列的末尾；然后，再把处理机分配给就

26、绪队列中新的队首进程，同时也让它执行一个时间片。中新的队首进程，同时也让它执行一个时间片。 可以保证就绪队列中的所有进程可以保证就绪队列中的所有进程, ,在一给定的时间内在一给定的时间内, ,均均能获得一时间片的处理机执行时间。能获得一时间片的处理机执行时间。2021-10-142021-10-143434图图3-5 3-5 多级反馈队列调度算法多级反馈队列调度算法 2.2.多级反馈队列调度算法多级反馈队列调度算法优先级高优先级高2021-10-142021-10-143535设置设置多个就绪队列多个就绪队列, ,并为各个队列赋予不同的优先级，各并为各个队列赋予不同的优先级，各队列的优先权逐个

27、队列的优先权逐个降低降低。各个队列中进程执行各个队列中进程执行时间片时间片的的大小大小也各也各不相同不相同，在优先权，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。愈高的队列中，为每个进程所规定的执行时间片就愈小。调度方式调度方式当一个新进程进入内存后当一个新进程进入内存后, ,首先将它放入第一队列的末首先将它放入第一队列的末尾，按尾，按FCFSFCFS原则排队等待调度。原则排队等待调度。当轮到该进程执行时当轮到该进程执行时, ,如它能在该时间片内完成如它能在该时间片内完成, ,便可便可准备撤离系统准备撤离系统; ;如果它在一个时间片结束时尚未完成如果它在一个时间片结束时尚未完成,

28、 ,调度程序便将该进程转入第二队列的末尾，再同样地调度程序便将该进程转入第二队列的末尾，再同样地按按FCFSFCFS原则等待调度执行；如果它在第二队列中运行原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队一个时间片后仍未完成，再依次将它放入第三队列列,如此下去，当一个长作业如此下去，当一个长作业( (进程进程) )从第一队列从第一队列依次降到第依次降到第n n队列后，在第队列后，在第n n队列中便采取按时间片轮队列中便采取按时间片轮转的方式运行。转的方式运行。2021-10-142021-10-143636仅当仅当第一队列空闲第一队列空闲时时, ,调度程序才调

29、度第二队列中的调度程序才调度第二队列中的进程运行进程运行; ;仅当第仅当第1(i-1) 1(i-1) 队列均空时队列均空时, ,才会调度第才会调度第i i队列中的进程运行。队列中的进程运行。如果处理机正在第如果处理机正在第i i队列中为某进程服务时队列中为某进程服务时, ,又有新进又有新进程进入优先权较高的队列程进入优先权较高的队列( (第第1(i-1)1(i-1)中的任何一个队中的任何一个队列列),),则此时新进程将则此时新进程将抢占抢占正在运行进程的处理机正在运行进程的处理机, ,即即由调度程序把正在运行的进程放回到第由调度程序把正在运行的进程放回到第i i队列的末尾队列的末尾, ,把把处

30、理机分配给新到的高优先权进程。处理机分配给新到的高优先权进程。2021-10-142021-10-143737 3. 3.多级反馈队列调度算法的性能多级反馈队列调度算法的性能 (1)(1)终端型作业用户终端型作业用户终端型作业用户所提交的作业多属于终端型作业用户所提交的作业多属于交互型作业交互型作业，通，通常较常较小小，系统只要能使这些作业在第一队列所规定的，系统只要能使这些作业在第一队列所规定的时间片内完成即可。时间片内完成即可。(2)(2)短批处理作业用户短批处理作业用户若若在第在第1 1队列中执行队列中执行一个时间片一个时间片即可完成，便可获得即可完成，便可获得与终端型作业一样的响应时间

31、。与终端型作业一样的响应时间。如在第一个队列中如在第一个队列中不能完成不能完成，只需在第，只需在第2 2、3 3队列中各队列中各执行一个时间片。执行一个时间片。(3)(3)长批处理作业用户长批处理作业用户长作业将依次在第长作业将依次在第1,2,3,n1,2,3,n队列中执行，最终按轮队列中执行，最终按轮转方式运行。转方式运行。2021-10-142021-10-143838内容概述内容概述3.1 3.1 处理机调度的层次处理机调度的层次 3.2 3.2 调度队列模型和调度准则调度队列模型和调度准则 3.3 3.3 调度算法调度算法 3.4 3.4 实时调度实时调度3.5 3.5 产生死锁的原因

32、和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 2021-10-142021-10-1439393.5.1 3.5.1 产生死锁的原因产生死锁的原因3.5.2 3.5.2 产生死锁的必要条件产生死锁的必要条件3.5.3 3.5.3 处理死锁的基本方法处理死锁的基本方法2021-10-142021-10-1440403.5.1 3.5.1 产生死锁的原因产生死锁的原因1.1.竞争资源引起进程死锁竞争资源引起进程死锁 可剥夺和非剥夺性资源可剥夺和非剥夺性资源 可剥夺性资源可剥夺性资源是指进程在获得这类资源后，该资是

33、指进程在获得这类资源后，该资源可以再被其他进程或系统剥夺，如源可以再被其他进程或系统剥夺，如处理机处理机、内内存存等。等。 不可剥夺性资源不可剥夺性资源是指当系统把这类资源分配给某是指当系统把这类资源分配给某个进程后，再不能强行收回，只能在进程用完后个进程后，再不能强行收回，只能在进程用完后自行释放，如自行释放，如磁带机磁带机、打印机打印机等。等。 竞争非剥夺性资源竞争非剥夺性资源 系统中的系统中的非剥夺性资源非剥夺性资源由于数量有限而不能满足由于数量有限而不能满足进程运行的需要，进程在运行过程中因争夺这些进程运行的需要，进程在运行过程中因争夺这些资源而限入僵局。资源而限入僵局。2021-10

34、-142021-10-144141图图3-12 I/O3-12 I/O设备共享时的死锁情况设备共享时的死锁情况 请请 求求请请 求求R1R2P1P2配配 分分已已 配配 分分 已已2021-10-142021-10-144242图图3-13 3-13 进程之间通信时的死锁进程之间通信时的死锁 S2P1S3P3S1P2 竞争临时性资源竞争临时性资源 临时性资源临时性资源区别于区别于永久性资源永久性资源，指由一个进程产生，指由一个进程产生，被另一进程使用后就再也无用的资源，也称为被另一进程使用后就再也无用的资源，也称为消耗性消耗性资源。资源。申请申请释放释放申请申请释放释放申请申请释放释放2021

35、-10-142021-10-1443432.2.进程推进顺序不当引起死锁进程推进顺序不当引起死锁 图图3-14 3-14 进程推进顺序对死锁的影响进程推进顺序对死锁的影响 P P1 1进程进度进程进度P P2 2进程进度进程进度2021-10-142021-10-144444 若并发进程若并发进程P1和和P2按曲线按曲线所示的顺序推进，它们将进入所示的顺序推进，它们将进入不安全区不安全区D内。此时内。此时P1保持了资源保持了资源R1，P2保持了资源保持了资源R2，系统处于不安全状态。因为，这时两进程再向前推进，便系统处于不安全状态。因为，这时两进程再向前推进，便可能发生死锁。可能发生死锁。 例

36、如，当例如，当P1运行到运行到P1;Request(R2)时，将因时，将因R2已被已被P2占用占用而阻塞；当而阻塞；当P2运行到运行到P2; Request(R1)时，也时，也将因将因R1已被已被P1占用而阻塞，于是发生了进程死锁。占用而阻塞，于是发生了进程死锁。2021-10-142021-10-1445453.5.1 3.5.1 产生死锁的原因产生死锁的原因3.5.2 3.5.2 产生死锁的必要条件产生死锁的必要条件3.5.3 3.5.3 处理死锁的基本方法处理死锁的基本方法2021-10-142021-10-1446463.5.2 3.5.2 产生死锁的必要条件产生死锁的必要条件 1.1

37、.互斥条件互斥条件进程对所分配到的资源进行进程对所分配到的资源进行排它性排它性的使用。临界的使用。临界( (独占独占) )资源资源, ,即一次只有一个进程可以使用资源。即一次只有一个进程可以使用资源。2.2.请求和保持条件请求和保持条件进程已经至少进程已经至少保持了保持了一个资源一个资源, ,但又提出了但又提出了新新的资源的资源请求请求, ,而而该资源又已被其他进程占有。该资源又已被其他进程占有。3.3.不剥夺条件不剥夺条件进程已获得的资源在进程已获得的资源在未未使用完之前使用完之前不能不能被剥夺。被剥夺。4.4.环路等待条件环路等待条件在发生死锁时在发生死锁时, ,必然存在一个必然存在一个进

38、程进程-资源资源的的环形链环形链。2021-10-142021-10-1447473.5.1 3.5.1 产生死锁的原因产生死锁的原因3.5.2 3.5.2 产生死锁的必要条件产生死锁的必要条件3.5.3 3.5.3 处理死锁的基本方法处理死锁的基本方法2021-10-142021-10-1448483.5.3 3.5.3 处理死锁的基本方法处理死锁的基本方法(1)(1)预防死锁。预防死锁。 通过设置通过设置限制条件限制条件, ,破坏产生死锁的必要条件的一个或几个。破坏产生死锁的必要条件的一个或几个。 (2)(2)避免死锁。避免死锁。 在分配资源时在分配资源时, ,用某种方法用某种方法防止防止

39、系统进入系统进入不安全不安全的状态。的状态。(3)(3)检测死锁。检测死锁。 确定与死锁有关的进程和资源确定与死锁有关的进程和资源, ,采取措施采取措施, ,清除死锁。清除死锁。(4)(4)解除死锁。解除死锁。 与检测死锁配套的一种措施。与检测死锁配套的一种措施。2021-10-142021-10-144949内容概述内容概述3.1 3.1 处理机调度的基本概念处理机调度的基本概念 3.2 3.2 调度算法调度算法 3.3 3.3 实时调度实时调度 3.4 3.4 多处理机系统中的调度多处理机系统中的调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死

40、锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 2021-10-142021-10-1450503.6.1 3.6.1 预防死锁预防死锁3.6.2 3.6.2 系统安全状态系统安全状态3.6.3 3.6.3 利用银行家算法避免死锁利用银行家算法避免死锁2021-10-142021-10-1451513.6.1 3.6.1 预防死锁预防死锁 摒弃摒弃“请求和保持请求和保持”条件条件 摒弃摒弃“不剥夺不剥夺”条件条件 摒弃摒弃“环路等待环路等待”条件条件 原理：原理： 该方法是通过对资源分配的原则进行限制，从而使产该方法是通过对资源分配的原则进行限制，从而使产生死锁的四个

41、必要条件中的第生死锁的四个必要条件中的第2 2、3 3、4 4个条件之一个条件之一不不能能成立，来预防产生死锁。成立，来预防产生死锁。 互斥：这个条件不可能被禁止。互斥：这个条件不可能被禁止。2021-10-142021-10-1452521.1.摒弃摒弃“请求和保持请求和保持”条件条件 所有进程在开始运行之前必须所有进程在开始运行之前必须一次性一次性的申请整个运的申请整个运行过程所需的全部资源。行过程所需的全部资源。 优点优点: :简单、易于实现、安全。简单、易于实现、安全。 缺点缺点:(1):(1)资源浪费严重资源浪费严重 (2)(2)进程延迟运行进程延迟运行2021-10-142021-

42、10-1453532.2.摒弃摒弃“不剥夺不剥夺”条件条件 系统规定系统规定: :进程逐个地申请所需资源进程逐个地申请所需资源 当一个已经当一个已经保持保持了某些资源的进程申请新资源而了某些资源的进程申请新资源而不不能能得到满足时得到满足时, ,必须必须放弃放弃所有已保持的资源所有已保持的资源 实现复杂、代价高昴实现复杂、代价高昴( (例如例如: :打印机打印机) )2021-10-142021-10-1454543.3.摒弃摒弃“环路等待环路等待”条件条件 系统将所有资源按类型分配序号并排队系统将所有资源按类型分配序号并排队( (例如打印机例如打印机为为1 1、磁带机为、磁带机为2 2、磁盘

43、为、磁盘为3 3、等等、等等) )。 所有进程申请资源必须按序号所有进程申请资源必须按序号递增递增的顺序的顺序 对比前两种方法对比前两种方法: :资源利用率和系统吞吐量较高资源利用率和系统吞吐量较高 缺点缺点:(1):(1)序号固定序号固定, ,限制了新设备类型的增加限制了新设备类型的增加 (2)(2)资源浪费资源浪费( (不像前边那么严重不像前边那么严重, ,考虑进程使用考虑进程使用资源顺序了资源顺序了) ) (3) (3)限制用户自由编程限制用户自由编程( (因限制了序号因限制了序号) )2021-10-142021-10-145555例如例如:进程进程PA,使用资源的顺序是使用资源的顺序

44、是R1,R2; 进程进程PB,PB,使用资源的顺序是使用资源的顺序是R2,R1;R2,R1;若采用若采用无限制条件无限制条件, ,有可能形成环路条件有可能形成环路条件, ,造成造成死锁死锁。采用有序资源分配法采用有序资源分配法:R1:R1的编号为的编号为1,R21,R2的编号为的编号为2;2; PA: PA:申请次序应是申请次序应是:R1,R2:R1,R2 PB:PB:申请次序应是申请次序应是:R1,R2:R1,R2 这样就破坏了环路条件这样就破坏了环路条件, ,避免了死锁的发生。避免了死锁的发生。2021-10-142021-10-1456563.6.1 3.6.1 预防死锁预防死锁3.6.

45、2 3.6.2 系统安全状态系统安全状态3.6.3 3.6.3 利用银行家算法避免死锁利用银行家算法避免死锁2021-10-142021-10-1457571.1.安全状态安全状态避免死锁：允许进程避免死锁：允许进程动态地动态地申请资源申请资源, ,但系统在进行资源分配但系统在进行资源分配之前之前, ,应先应先计算计算此次资源分配的此次资源分配的安全性安全性。若此次分配不会导致。若此次分配不会导致系统进入不安全状态系统进入不安全状态, ,则将资源分配给进程则将资源分配给进程; ; 否则否则, ,令进程等令进程等待。待。安全状态安全状态：指系统能按某种进程顺序：指系统能按某种进程顺序(P(P1

46、1, P, P2 2, ,P, ,Pn n)()(称称P P1 1, , P P2 2, , P, , Pn n序列为序列为安全序列安全序列),),来为每个进程来为每个进程P Pi i分配其所需资分配其所需资源源, ,直至满足每个进程对资源的最大需求直至满足每个进程对资源的最大需求, ,使每个进程都可顺使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列利地完成。如果系统无法找到这样一个安全序列, ,则称系统处则称系统处于不安全状态。于不安全状态。 3.6.2 3.6.2 系统安全状态系统安全状态 2021-10-142021-10-145858 2. 2.安全状态之例安全状态之例 假定

47、系统中有三个进程假定系统中有三个进程P1P1、P2P2和和P3,P3,共有共有1212台台磁带机。进程磁带机。进程P1P1总共要求总共要求1010台磁带机台磁带机,P2,P2和和P3P3分别要求分别要求4 4台和台和9 9台。假设在台。假设在T0T0时刻时刻, ,进程进程P1P1、P2P2和和P3P3已分别获得已分别获得5 5台、台、2 2台和台和2 2台磁带机台磁带机, ,尚有尚有3 3台空闲未分配台空闲未分配, ,如下表所示如下表所示: : 进进 程程 最最 大大 需需 求求 已已 分分 配配 可可 用用 P P1 1P P2 2P P3 310104 49 95 52 22 23 3安全

48、序列安全序列2021-10-142021-10-1459593.3.由安全状态向不安全状态的转换由安全状态向不安全状态的转换如果不按照安全序列分配资源如果不按照安全序列分配资源, ,则系统可能会由安全则系统可能会由安全状态进入不安全状态。状态进入不安全状态。例如例如, ,在在T0T0时刻以后时刻以后,P3,P3又请求又请求1 1台磁带机台磁带机, ,若此时系统若此时系统把剩余把剩余3 3台中的台中的1 1台分配给台分配给P3,P3,则系统便进入不安全状则系统便进入不安全状态。态。 因为因为, ,此时也无法再找到一个安全序列此时也无法再找到一个安全序列, ,例如例如, ,把把其余的其余的2 2台

49、分配给台分配给P2,P2,这样这样, ,在在P2P2完成后只能释放出完成后只能释放出4 4台台, ,既不能满足既不能满足P1P1尚需尚需5 5台的要求台的要求, ,也不能满足也不能满足P3P3尚需尚需6 6台台的要求的要求, ,致使它们都无法推进到完成致使它们都无法推进到完成, ,彼此都在等待对彼此都在等待对方释放资源方释放资源, ,即陷入僵局即陷入僵局, ,结果导致死锁。结果导致死锁。2021-10-142021-10-1460603.6.1 3.6.1 预防死锁预防死锁3.6.2 3.6.2 系统安全状态系统安全状态3.6.3 3.6.3 利用银行家算法避免死锁利用银行家算法避免死锁202

50、1-10-142021-10-1461613.6.3 3.6.3 利用银行家算法避免死锁利用银行家算法避免死锁 1.1.银行家算法中的数据结构银行家算法中的数据结构 (1)(1)可利用资源向量可利用资源向量AvailableAvailable 这是一个含有这是一个含有m m个元素的数组个元素的数组, ,其中的每一个元素代表一其中的每一个元素代表一类可利用的资源数目类可利用的资源数目, ,其初始值是系统中所配置的该类全其初始值是系统中所配置的该类全部可用资源的数目部可用资源的数目, ,其数值随该类资源的分配和回收而动其数值随该类资源的分配和回收而动态地改变。如果态地改变。如果Availablej

51、=KAvailablej=K, ,则表示系统中现有则表示系统中现有RjRj类类资源资源K K个。个。(2)(2)最大需求矩阵最大需求矩阵MaxMax 这是一个这是一个n nm m的矩阵的矩阵, ,它定义了系统中它定义了系统中n n个进程中的每一个进程中的每一个进程对个进程对m m类资源的最大需求。如果类资源的最大需求。如果Maxi,j=KMaxi,j=K, ,则表示则表示进程进程i i需要需要RjRj类资源的最大数目为类资源的最大数目为K K。2021-10-142021-10-146262(3)(3)分配矩阵分配矩阵AllocationAllocation 这也是一个这也是一个n nm m的

52、矩阵的矩阵, ,它定义了系统中每一类资源当它定义了系统中每一类资源当前已分配给每一进程的资源数。如果前已分配给每一进程的资源数。如果Allocationi,j=KAllocationi,j=K, ,则表示进程则表示进程i i当前已分得当前已分得RjRj类资源类资源的数目为的数目为K K(4)(4)需求矩阵需求矩阵NeedNeed 这也是一个这也是一个n nm m的矩阵的矩阵, ,用以表示每一个进程尚需的各用以表示每一个进程尚需的各类资源数。如果类资源数。如果Needi,j=KNeedi,j=K, ,则表示进程则表示进程i i还需要还需要RjRj类类资源资源K K个个, ,方能完成其任务方能完成

53、其任务Needi,j=Maxi,j-Allocationi,jNeedi,j=Maxi,j-Allocationi,j2021-10-142021-10-146363 2. 2.银行家算法银行家算法 设设RequestRequesti i是进程是进程P Pi i的请求向量的请求向量, ,如果如果RequestRequesti i(1,0,2),(1,0,2),表表示进程示进程P Pi i需要需要1 1个个R R1 1类型的资源类型的资源, ,需要需要0 0个个R R2 2类型的资源类型的资源, ,需要需要2 2个个R R3 3类型的资源。当类型的资源。当P Pi i发出资源请求后发出资源请求后

54、, ,系统按下述步骤进系统按下述步骤进行检查行检查: :(1)(1)如果如果RequestRequesti iNeedNeedi i, ,便转向步骤便转向步骤2;2;否则认为否则认为出错出错, ,因因为它所需要的资源数已超过它所宣布的最大值。为它所需要的资源数已超过它所宣布的最大值。(2)(2)如果如果RequestRequesti iAvailable,Available,便转向步骤便转向步骤(3);(3);否则否则, ,表示表示尚尚无足够无足够资源资源, ,P Pi i须等待。须等待。2021-10-142021-10-146464(3)(3)系统系统试探试探着把资源分配给进程着把资源分配

55、给进程P Pi i, ,并修改下面数据结构并修改下面数据结构中的数值中的数值; ;Available:=Available-RequestAvailable:=Available-Requesti i; ;AllocationAllocationi i:=Allocation:=Allocationi i+Request+Requesti i; ;NeedNeedi i:=Need:=Needi i-Request-Requesti i; ;(4)(4)系统执行系统执行安全性算法安全性算法, ,检查此次资源分配后检查此次资源分配后, ,系统是否处系统是否处于安全状态。若安全于安全状态。若安全,

56、 ,才正式将资源分配给进程才正式将资源分配给进程P Pi i, ,以完以完成本次分配成本次分配; ;否则否则, ,将本次的试探分配作废将本次的试探分配作废, ,恢复原来的恢复原来的资源分配状态资源分配状态, ,让进程让进程P Pi i等待。等待。2021-10-142021-10-1465653.3.安全性算法安全性算法(1)(1)设置两个向量设置两个向量初值初值; ;工作向量工作向量WorkWork; ;它表示系统可提供给进程继续运行所它表示系统可提供给进程继续运行所需的各类资源数目需的各类资源数目, ,它含有它含有m m个元素个元素, ,在执行安全算法在执行安全算法开始时开始时, ,Wor

57、k:=Available;Work:=Available;FinishFinish; ;它表示系统是否有足够的资源分配给进程它表示系统是否有足够的资源分配给进程, ,使之使之运行完成运行完成。开始时先做。开始时先做Finishi:=falseFinishi:=false; ;当有当有足够资源分配给进程时足够资源分配给进程时, ,再令再令Finishi:=trueFinishi:=true2021-10-142021-10-146666(2)(2)从进程集合中找到一个能满足下述条件的进程从进程集合中找到一个能满足下述条件的进程; ;Finishi=false;Finishi=false;Need

58、Needi iWork;Work;若找到若找到, ,执行步骤执行步骤(3),(3),否则否则, ,执行步骤执行步骤(4)(4)(3)(3)当进程当进程P Pi i获得资源后获得资源后, ,可顺利执行可顺利执行, ,直至完成直至完成, ,并释放出分并释放出分配给它的资源配给它的资源, ,故应执行故应执行; ; Work:=Work+Allocation;Work:=Work+Allocation; Finishi:=true;Finishi:=true; go to step 2; go to step 2;(4)(4)如果所有进程的如果所有进程的Finishi=trueFinishi=true

59、都满足都满足, ,则表示系统处于则表示系统处于安全状态安全状态; ;否则否则, ,系统处于不安全状态系统处于不安全状态2021-10-142021-10-146767 最大需求最大需求 已分配已分配 可用资源可用资源 (Max) (Allocation) (Max) (Allocation) (Available) (Available) P0 7 5 3 0 1 0 P0 7 5 3 0 1 0 3 3 2 3 3 2 P1 3 2 2 2 0 0 P1 3 2 2 2 0 0 P2 9 0 2 3 0 2 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P3 2 2 2 2 1

60、 1 P4 4 3 3 0 0 2 P4 4 3 3 0 0 27 4 3还需要还需要(Need)1 2 26 0 00 1 14 3 14.4.银行家算法之例银行家算法之例 五个进程五个进程P0, P1, P2, P3, P4P0, P1, P2, P3, P4和三类资源和三类资源A, B, CA, B, C各种资源的数量分别为各种资源的数量分别为1010、5 5、7 7。 (1)(1)在在T0T0时刻的安全性：时刻的安全性：Work=Available=(3,3,2) Finish分配给分配给P1,完成后完成后Work=(5,3,2) ture分配给分配给P3,完成后完成后Work=(7,