第四章调度与死锁

1、2022-6-61第四章第四章 调度与死锁调度与死锁n4.1 处理机调度概述处理机调度概述n4.2 死锁的概念死锁的概念n4.3 死锁的预防、避免、检测和解除死锁的预防、避免、检测和解除2022-6-624.1 处理机调度处理机调度n处理机管理需要解决三个主要问题：n（1）按什么原则分配处理机，即需要确定处）按什么原则分配处理机，即需要确定处理机调度算法；理机调度算法；n（2）什么时候分配处理机，即需要确定处）什么时候分配处理机，即需要确定处理机调度时机；理机调度时机；n（3）如何分配处理机，即需要给出处理机）如何分配处理机，即需要给出处理机调度过程。调度过程。 2022-6-63一、 调度算

2、法 v引入多道程序系统的直接目的就是想让处理机“忙”，一直以来处理机都是计算机系统中的瓶颈资源之一，特别是在单处理机系统中，处于就绪状态的多个进程竞争使用一台处理机，所以当处理机空闲时，系统需要从多个就绪进程中挑选一个使其投入运行。选择哪一个呢？这需要按某一种算法。调度算法的实质就是一种资源分配调度算法的实质就是一种资源分配。 v从资源的角度来看，该算法确定了处理机的分配策略，故称其为处理机调度算法；v而从资源使用者的角度看，该算法确定了进程运行的次序，故也称进程调度算法。 2022-6-64要设计一个理想的调度算法是一件十分困难的事要设计一个理想的调度算法是一件十分困难的事在实际系统中，调度

3、算法往往折衷考虑在实际系统中，调度算法往往折衷考虑设计设计调度算法时应考虑的因素：调度算法时应考虑的因素：n调度算法应与系统设计目标保持一致调度算法应与系统设计目标保持一致n注意系统资源均衡使用注意系统资源均衡使用n保证提交的作业在截止时间内完成保证提交的作业在截止时间内完成n设法缩短作业平均周转时间设法缩短作业平均周转时间大多数操作系统都采用比较简单的调度算法大多数操作系统都采用比较简单的调度算法调度算法性能的衡量调度算法性能的衡量2022-6-65平均带权周转时间平均带权周转时间 W W（ ） ri ri 为某作业为某作业i i的实际执行（服务）时间的实际执行（服务）时间niriTi1n1

4、Ti 为某作业周转时间（提交到完成的时间）为某作业周转时间（提交到完成的时间）Ti/ri为为带权周转时间带权周转时间2022-6-66处理机的使用方式有两种：处理机的使用方式有两种： n不可抢占方式与与可抢占方式 基本的处理机调度算法有先来先服务法、优先级法基本的处理机调度算法有先来先服务法、优先级法和时间片轮转法等，现在也有些操作系统使用综合性的调和时间片轮转法等，现在也有些操作系统使用综合性的调度算法，比如多级反馈队列调度算法等。度算法，比如多级反馈队列调度算法等。 2022-6-671先来先服务调度算法FCFS n该算法按照进程进入就绪队列的先后顺序选择最先进入该队列的进程，把处理机分配

5、给它，使之投入运行。DCBACPU完成2022-6-68在单道环境下，某批处理显然有四道作业，已知他们的在单道环境下，某批处理显然有四道作业，已知他们的进入系统的时刻、估计运算时间如下：进入系统的时刻、估计运算时间如下：进程进程到达时刻到达时刻服务时间服务时间开始时刻开始时刻完成时刻完成时刻 周转时间周转时间 带权周转带权周转ABCD0123110011000110110211011022021100100199111001.99短作业短作业C的带权周转时间高达的带权周转时间高达100。长作业长作业D的带权周转时间仅为的带权周转时间仅为1.99 2022-6-69FCFS算法有利于CPU繁忙型

6、的作业，不利于I/O繁忙型的作业。 n 这是一种不可抢占方式的调度算法，优点是实现简单，缺点是后来的进程等待CPU的时间较长。即有利于长作业（进程），不利于短作业（进程）。 在当今系统中，先进先出很少作为调度模式，而是常常嵌套在其它的调度模式中。 例如，许多调度模式根据优先级将处理机分配给进程，但具有相同优先级的进程却按先进先出进行分配。2022-6-6102优先级调度算法 n总是选择具有最高优先级的进程首先使用处理机。在这种算法中，首先考虑的问题是如何确定进程的优先数。 分为： 静态优先权：在创建进程的时候便确定的，且在进程的运行期间保持不变。（简单易行，系统开销小，但不够精确，很可能出现优

7、先权低的作业（进程）长期不被调度的情况。所以，只在要求不太高的系统中，才使用静态优先数（权）n动态优先权：在创建进程时所赋予的优先权，可以随进程的推进而改变，以便获得更好的调度性能 2022-6-611这是一种可抢占方式的调度算法，可防止一个长作业长期的垄断处理机。 n若所有的进程具有相同的优先权初值，则按照FCFS算法，最先进入就绪队列的进程最先获得处理机。若所有的就绪进程具有各不相同的优先权初值，对于优先权初值低的进程，在等待足够的时间后，其优先权可能升为最高，从而获得处理机执行。 2022-6-612例2. 有5个进程P1、P2、P3、P4、P5，它们同时依次进入就绪队列，它们的优先数和

8、需要的处理机时间如下： n进程 处理机时间 优先数nP1 10 3nP2 1 1nP3 2 3nP4 1 4nP5 5 2 2022-6-613忽略进程调度所花的时间，要求： n（1）分别写出采用先来先服务调度算法和静态优先级调度算法中进程的执行次序；n（2）分别计算各进程在就绪队列中的等待时间和平均等待时间。n解：（1）采用先来先服务调度算法时各进程的执行次序为：P1P2P3P4P5。n采用静态优先级调度算法时各进程的执行次序为： P4P1P3P5P2。 2022-6-614（2）FCFS中，平均等待时间（0+10+11+13+14）/59.6；静态优先级法中，平均等待时间（1+18+11+

9、0+13）/58.6n进程 处理机时间 FCFS等待时间 静态优先级法等待时间nP1 10 0 1nP2 1 10 18nP3 2 11 11nP4 1 13 0nP5 5 14 13 2022-6-6153.3.最短作业最短作业/ /进程优先法进程优先法（SJF/SPFSJF/SPF）SJF:从后备队列中选择估计运行时间最短的作业，先调入内存运行。SPF:从就绪队列中选择估计运行时间最短的进程，先将处理机分配给它，使它立即执行。非抢占式。缺点：没有考虑到某些作业/进程的紧迫程度。 用户作出的估计时间并不准确，带有很大的主观性。2022-6-6164.4.最高响应比作业优先算法（最高响应比作业

10、优先算法（HRNHRN）n是对FCFS方式和SJF方式的一种综合平衡响应比。nR(作业等待时间需运行时间)/ 需运行时间 1已等待时间 / 需运行时间 1W/Tn由于R与要求运行时间成反比，故对短作业是有利的，另一方面，因R与等待时间成正比，故长作业随着其等待时间的增长，也可获的较高的相应比。这就克服了短作业优先数法的缺点，既照顾了先来者，又优待了短作业，是上述两种算法的一种较好的折中。2022-6-6175时间片轮转调度算法(RR) n基本思想：系统把所有的就绪进程按FCFS原则排成一个队列，且规定一个时间片作为进程每次使用处理机的最长时间单位，按时间片把处理机轮流分配给当前位于就绪队列队首

11、的进程使用，当该进程的时间片用完以后，系统产生时钟中断，剥夺该进程的执行，将它送到就绪队列队尾，等待下一轮次的调度。同时处理机调度程序又去调度当前就绪队列的队首进程，也让它运行给定的时间片，如此循环往复。2022-6-618FCB A .CPU完成 A B C时间片轮转算法图示时间片轮转算法图示 2022-6-619 最佳时间片的确定 这个最佳的时间片值是多少呢？显然，它将随系统而异。随负载而异，同时也随进程而异。 时间片的选取是实现各种调度算法的关键之处，而时间片的选定通常应考虑终端数目，处理机能力、各终端任务的急迫程度、外存传输速度等方面的因素。时间片轮转法亦可应用于批处理系统的处理机调度

12、。 当时间片很大时，大到一个进程足以完成其全部运行工作所需的时间，此时轮转调度模式退化为FCFS模式。 当时间片非常小时，调度程序剥夺处理机的次数增多，这将加重了系统开销，系统性能降低，大多数时间都消耗在处理机的转换上。2022-6-6206多级反馈队列调度算法 n以上介绍的算法，都存在一定的局限性。n现在主流的操作系统，如UNIX、Windows NT、Linux等，都使用一种综合性的调度算法多级反馈队列调度算法。该算法综合了上述三种算法以及多队列调度算法的思想和优点，总体调度性能优越，适于各种类型的作业，但其实现也比较复杂。 2022-6-621算法的基本思想（实施过程）是： n首先：系统

13、按进程优先级设置了多级（比如n级，n2）就绪进程队列，从第一级队列到最后一级队列，优先级越来越低。n其次：每一级就绪队列对应一个不同的时间片。优先权越高的队列，进程的时间片越小。n再次：当一个新进程进入内存后，首先被放到第一级队列的队尾。按照FCFS原则排队等待调度。当轮到该进程执行时，如能在时间片内完成，便可准备撤离系统；如果在时间片内未完成，调度程序便将该进程转入第二队列的末尾，再依次按照FCFS原则等待调度。2022-6-622n最后：仅当第一级队列为空时，才调度第二级队列中的进程；如此下去，仅当前面的n-1级队列全部为空时，才去调度最后第n级队列中的进程。如果处理机正在第I队列中为某进

14、程服务时，又有新的进程进入优先权高的队列（第1I-1中任何一队列），则系统抢占正在运行的进程的处理机，由调度程序把正在运行的进程放回到刚才所在第i队列的队尾，重新进行处理机调度。 2022-6-623二、 调度时机 n当发生以下几种情况时，现行进程都要放弃处理机的使用，即将引起系统对进程的重新调度：n1在分时系统中，现行进程的时间片用完了；n2发生了外部中断；n3进程因等待某事件或资源而阻塞；n4现行进程运行结束或出现异常情况。 2022-6-624三、 调度过程 n1保存“下降”进程现场n2选择将要运行的进程“上升”进程n3恢复“上升”进程的现场 2022-6-625作业调度算法应用例子作业

15、调度算法应用例子2022-6-626先来先服务调度算法计算结果先来先服务调度算法计算结果作作业业进进入入时时间间估估计计运运行行时时间间（分分钟钟）开开始始时时间间结结束束时时间间周周转转时时间间（分分钟钟）带带权权周周转转时时间间JOB18：001208：0010：001201JOB28：505010：0010：501202.4JOB39：001010：5011：0012012JOB49：502011：0011：20904.5作作业业平平均均周周转转时时间间 T = 112.5作作业业带带权权平平均均周周转转时时间间 W = 4.97545019.92022-6-627最短作业优先作业算法计

16、算结果最短作业优先作业算法计算结果作作业业进进入入时时间间估估计计运运行行时时间间（分分钟钟）开开始始时时间间结结束束时时间间周周转转时时间间（分分钟钟）带带权权周周转转时时间间JOB18：001208：0010：001201JOB28：505010：3011：201503JOB39：001010：0010：10707JOB49：502010：1010：30402作作业业平平均均周周转转时时间间 T = 95作作业业带带权权平平均均周周转转时时间间 W = 3.25380132022-6-628最高响应比优先作业算法计算结果最高响应比优先作业算法计算结果2022-6-6294。3 死锁的概念死

17、锁的概念n死锁举例死锁举例n产生死锁的原因产生死锁的原因 n产生死锁的必要条件产生死锁的必要条件 n处理死锁的基本方法处理死锁的基本方法 2022-6-630死锁举例死锁举例n例例1：两个小孩在一起玩耍，一个在玩皮球，另一个玩两个小孩在一起玩耍，一个在玩皮球，另一个玩自动步枪，如果这两个小孩都要对方手中的玩自动步枪，如果这两个小孩都要对方手中的玩具，而又不肯先放掉自己拿着的玩具，这时就具，而又不肯先放掉自己拿着的玩具，这时就发生了僵持局面。发生了僵持局面。2022-6-631n例例2：设系统有一台打印机和一台扫描仪，进程设系统有一台打印机和一台扫描仪，进程P1、P2并发执行，在某时刻并发执行，

18、在某时刻T，进程进程P1和和P2分别占用分别占用了打印机和扫描仪。在时刻了打印机和扫描仪。在时刻T1（T1T），），P1又又要申请扫描仪，但由于扫描仪被要申请扫描仪，但由于扫描仪被P2占用，占用，P1只只有等待。在时刻有等待。在时刻T2（T2T），），P2又申请打印机，又申请打印机，但由于打印机被但由于打印机被P1占用，占用，P2只有等待。如此两只有等待。如此两进程均不能执行完成。称这种现象为进程均不能执行完成。称这种现象为死锁。2022-6-632 n例例3：在生产者在生产者-消费者问题中将生产者进程的消费者问题中将生产者进程的两个两个P操作颠倒时会发生死锁。操作颠倒时会发生死锁。 将消费者

19、进程的两个将消费者进程的两个P操作颠倒时也会发操作颠倒时也会发生死锁。生死锁。 2022-6-633死锁的定义死锁的定义 一组进程中，每个进程都无限等待被该一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而组进程中另一进程所占有的资源，因而永远无法得到该资源，这种现象称为永远无法得到该资源，这种现象称为进进程死锁程死锁，这一组进程就称为，这一组进程就称为死锁进程死锁进程2022-6-634判断判断 1 1 参与死锁的所有进程都占有资源参与死锁的所有进程都占有资源 2 2 参与死锁的所有进程均正在等待资源参与死锁的所有进程均正在等待资源 3 3 参与死锁的所有进程中至少有两个进

20、程占有资源参与死锁的所有进程中至少有两个进程占有资源 4 4 参与死锁的进程至少有两个参与死锁的进程至少有两个2022-6-635参与死锁的进程最少是两个参与死锁的进程最少是两个 （两个以上进程才会出现死锁）（两个以上进程才会出现死锁）参与死锁的进程至少有两个已经占有资源参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃甚至导致系统崩溃关于死锁的一些结论关于死锁的一些结论2022

21、-6-636产生死锁的必要条件产生死锁的必要条件四个必要条件：四个必要条件：n互斥条件：涉及的资源是非共享的。互斥条件：涉及的资源是非共享的。n不剥夺条件：不能强行剥夺进程拥有的资源。不剥夺条件：不能强行剥夺进程拥有的资源。n部分分配条件：进程在等待一新资源时继续部分分配条件：进程在等待一新资源时继续占有已分配的资源。占有已分配的资源。n环路条件：存在一种进程的循环链，链中的环路条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一每一个进程已获得的资源同时被链中的下一个进程所请求。个进程所请求。 2022-6-637处理死锁的基本方法处理死锁的基本方法1、预防死锁：、预防死

22、锁：通过设置某些限制条件，去破坏死锁四个必要通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。条件中的一个或多个，来防止死锁。较易实现，广泛使用，但由于所施加的限制往较易实现，广泛使用，但由于所施加的限制往往太严格，可能导致系统资源利用率和系统往太严格，可能导致系统资源利用率和系统吞吐量的降低。吞吐量的降低。2022-6-6382 2、避免死锁：、避免死锁：不事先采取限制去破坏产生死锁的条件，而是不事先采取限制去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发止系统进入不安全状态，从

23、而避免死锁的发生。生。实现较难，只需要较弱的限制条件，可获得较实现较难，只需要较弱的限制条件，可获得较高的资源利用率和系统吞吐量。高的资源利用率和系统吞吐量。2022-6-6393、检测死锁：、检测死锁：事先并不采取任何限制，也不检查系统是否进事先并不采取任何限制，也不检查系统是否进入不安全区，允许死锁发生，但可通过检测入不安全区，允许死锁发生，但可通过检测机构及时检测出死锁的发生，并精确确定与机构及时检测出死锁的发生，并精确确定与死锁有关的进程和资源，然后采取适当措施，死锁有关的进程和资源，然后采取适当措施，将系统中已发生的死锁清除掉将系统中已发生的死锁清除掉2022-6-6404、解除死锁

24、：、解除死锁：与检测死锁相配套，用于将进程从死锁状态解与检测死锁相配套，用于将进程从死锁状态解脱出来。脱出来。常用的方法是撤消或挂起一些进程。以回收一常用的方法是撤消或挂起一些进程。以回收一些资源，再将它们分配给处于阻塞状态的进些资源，再将它们分配给处于阻塞状态的进程，使之转为就绪状态。程，使之转为就绪状态。实现难度大，但可获得较好的资源利用率和系实现难度大，但可获得较好的资源利用率和系统吞吐量。统吞吐量。 2022-6-6414.3 死锁的预防、避免、检测和解除死锁的预防、避免、检测和解除n4.3.1 死锁的预防死锁的预防 n4.3.2 系统的安全状态系统的安全状态 n4.3.3 利用银行家

25、算法避免死锁利用银行家算法避免死锁n4.3.4 死锁的检测和解除死锁的检测和解除2022-6-6424.3.1 死锁的预防死锁的预防在系统设计时确定资源分配算法，保证不发生在系统设计时确定资源分配算法，保证不发生死锁死锁 具体的做法是破坏产生死锁的四个必要条件具体的做法是破坏产生死锁的四个必要条件之一之一2022-6-643破坏部分分配条件破坏部分分配条件系统要求所有进程要一次性地申请在整个系统要求所有进程要一次性地申请在整个运行过程中所需的全部资源。若系统有运行过程中所需的全部资源。若系统有足够资源则完全分配。足够资源则完全分配。2022-6-644 优点：简单、易于实现且安全。优点：简单、

26、易于实现且安全。缺点：缺点：n一个用户在作业运行之前可能提不出他的作业将要一个用户在作业运行之前可能提不出他的作业将要使用的全部设备。使用的全部设备。n用户作业必须等待，直到所有资源满足才能运行。用户作业必须等待，直到所有资源满足才能运行。实际上某些资源可能要到运行后期才会用到。实际上某些资源可能要到运行后期才会用到。n一个作业运行期间，对某些设备的使用时间很短，一个作业运行期间，对某些设备的使用时间很短，甚至不会用到。如：当用户作业出错时才需要打印甚至不会用到。如：当用户作业出错时才需要打印机输出错误信息，但采用静态分配法必须把打印机机输出错误信息，但采用静态分配法必须把打印机分配给该作业，

27、并长期占用。采用该方法对系统来分配给该作业，并长期占用。采用该方法对系统来说是非常浪费的。说是非常浪费的。 2022-6-645破坏不可剥夺条件破坏不可剥夺条件一个已拥有资源的进程，若它再提出新资源要一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，它必须释放已经求而不能立即得到满足时，它必须释放已经拥有的所有资源。以后需要时再重新申请。拥有的所有资源。以后需要时再重新申请。实现复杂、要付出很大的代价。实现复杂、要付出很大的代价。 2022-6-646破坏环路条件破坏环路条件系统中的所有资源都有一个确定的唯一号码，系统中的所有资源都有一个确定的唯一号码，所有分配请求必须以序号上升

28、的次序进行。所有分配请求必须以序号上升的次序进行。例如：系统中有下列设备：输入机（例如：系统中有下列设备：输入机（1），打），打印机（印机（2），穿孔机（），穿孔机（3），磁带机（），磁带机（4），磁），磁盘（盘（5）。有一进程要先后使用输入机、磁盘、）。有一进程要先后使用输入机、磁盘、打印机，则它申请设备时要按输入机、打印打印机，则它申请设备时要按输入机、打印机、磁盘的顺序申请。机、磁盘的顺序申请。2022-6-647优点：同前两法相比，其资源利用率和系统吞优点：同前两法相比，其资源利用率和系统吞吐量有较明显的改善。吐量有较明显的改善。 缺点：缺点：进程实际需要资源的顺序不一定与资源进程实际

29、需要资源的顺序不一定与资源的编号一致，因此仍会造成资源浪费。的编号一致，因此仍会造成资源浪费。2022-6-6484.3.2 系统的安全状态系统的安全状态死锁避免定义死锁避免定义 在系统运行过程中，对进程发出的在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配锁，则不予分配，否则予以分配2022-6-649安全状态安全状态如 果 系 统 能 按 某 种 顺 序 （如 果 系 统 能 按 某 种 顺

30、 序 （ 如如 P 4 ，P1，,Pn, 称为安全序列称为安全序列）为每个进程分配）为每个进程分配其所需的资源，直至所有进程都能运行完成，其所需的资源，直至所有进程都能运行完成，称系统处于安全状态。若不存在这样一个安称系统处于安全状态。若不存在这样一个安全序列称系统处于不安全状态。全序列称系统处于不安全状态。2022-6-650安全状态举例安全状态举例有三个进程有三个进程p1,p2,p3，有有12台磁带机。台磁带机。P1共要求共要求10台，台，P2共要求共要求4台，台，P3共要求共要求9台。在台。在T0时刻，时刻，p1,p2,p3分别获得分别获得5、2、2台，尚有台，尚有3台空闲。台空闲。20

31、22-6-651图图进程进程最大需求最大需求已分配已分配还需还需可用可用p110553p2422p3927经分析，在经分析，在T0时刻，系统是安全的。时刻，系统是安全的。因为存在一个安全序列因为存在一个安全序列p2、p1、p3。见下图。见下图。2022-6-652由安全状态向不安全状态的转换由安全状态向不安全状态的转换如果不按安全序列分配资源，则系统可能如果不按安全序列分配资源，则系统可能会由安全状态进入不安全状态。如在会由安全状态进入不安全状态。如在T0以后，以后，P3要求要求1台磁带机，若系统分给它一台，则台磁带机，若系统分给它一台，则系统进入不安全状态。因为其余系统进入不安全状态。因为其

32、余2台分给台分给P2，P2完成后，只能释放完成后，只能释放4台，这既不能满足台，这既不能满足P1（5台），也不能满足台），也不能满足P3（6台）。将导致死台）。将导致死锁。可见当锁。可见当P3申请资源时，尽管系统中有资申请资源时，尽管系统中有资源也不能分给它。源也不能分给它。 2022-6-653系统进入不安全状态系统进入不安全状态进程进程最大需求最大需求已分配已分配还需还需可用可用p110552p2422p39362022-6-6544.3.3 利用银行家算法避免死锁利用银行家算法避免死锁最有代表性的避免死锁算法，由最有代表性的避免死锁算法，由Dijkstra提出。提出。1、银行家算法中的数

33、据结构、银行家算法中的数据结构n可利用资源向量可利用资源向量Available。它是一个含有它是一个含有m个元素的数组，其中每个元素代表一类可利个元素的数组，其中每个元素代表一类可利用资源的数目。用资源的数目。n如：如： ABC5232022-6-655n最大需求矩阵最大需求矩阵Max。n*m矩阵，表示矩阵，表示n个进程个进程的每一个对的每一个对m类资源的最大需求。类资源的最大需求。ABCP1562P2331P3425P43322022-6-656n分配矩阵分配矩阵Allocation 。n*m矩阵，表示每个矩阵，表示每个进程分配的资源数。进程分配的资源数。ABCP1212P2121P3222

34、P41322022-6-657n需求矩阵需求矩阵Need 。n*m矩阵，表示每个进程还矩阵，表示每个进程还需要各类资源数。需要各类资源数。ABCP1352P2211P3223P42322022-6-658例例设系统有五个进程和三类资源，每类资源分别有设系统有五个进程和三类资源，每类资源分别有10、5、7。在。在T0时刻资源分配情况如图时刻资源分配情况如图2022-6-659银行家算法描述银行家算法描述当进程当进程pipi提出资源申请时，系统执行下列步提出资源申请时，系统执行下列步骤：骤：（1 1）若）若RequestiRequestiNeedi,Needi,转（转（2 2）；）； 否则错误返回

35、否则错误返回（2 2）若若RequestiRequestiAvailable,Available, 转（转（3 3）；）；否则进程等待否则进程等待2022-6-660(3(3）假设系统分配了资源，则有：）假设系统分配了资源，则有：Available:=Available-Requesti;Available:=Available-Requesti;Allocationi:=Allocationi+Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi-RequestiNeedi:=Needi-Requesti（4 4）执行）执行安全性算法

36、安全性算法，若系统新状态是安，若系统新状态是安全的，则分配完成，若系统新状态是不全的，则分配完成，若系统新状态是不安全的，则恢复原状态，进程等待安全的，则恢复原状态，进程等待2022-6-661安全性算法安全性算法为进行安全性检查，定义数据结构：为进行安全性检查，定义数据结构：Work:ARRAY0.m-1 of integer;Work:ARRAY0.m-1 of integer;Finish:ARRAY0.n-1 of Boolean;Finish:ARRAY0.n-1 of Boolean;m m代表资源的数量，代表资源的数量，n n代表进程的数量代表进程的数量2022-6-662安全性

37、算法安全性算法步骤步骤(1) (1) Work:=Available;Work:=Available; Finish:=false; Finish:=false;(2) (2) 寻找满足下列条件的寻找满足下列条件的i i： a). Finishi=false; a). Finishi=false; b). Needi b). NeediWorkWork; ;如果不存在，则转如果不存在，则转(4)(4)2022-6-663( (3) 3) Work:=Work+Allocationi;Work:=Work+Allocationi; Finishi:=true; Finishi:=true; 转转

38、(2)(2)(4) (4) 若对所有若对所有i,Finishi=true,i,Finishi=true,则则系统处于安全状态，否则处于不安系统处于安全状态，否则处于不安全状态全状态2022-6-664T0时刻的安全性检查时刻的安全性检查nT0时刻可以找到一个安全序列时刻可以找到一个安全序列p1,p3,p4,p2,p0. 系统是安系统是安全的。全的。2022-6-665例例1：T0时刻时刻P1请求资源请求资源nP1发出请求发出请求Request(1,0,2)，执行银行家算法执行银行家算法2022-6-666执行安全性算法执行安全性算法n可以找到一个安全序列可以找到一个安全序列p1,p3,p4,p

39、0,p2. 系统是安全的，系统是安全的，可可以将以将P1的请求分配给它。的请求分配给它。2022-6-667例例2：P4请求资源请求资源nP4发出请求发出请求Request(3,3,0), 执行银行家算法执行银行家算法nAvailable=2 3 0Available=2 3 0n不能通过算法第不能通过算法第2步步（ RequestiAvailableRequestiAvailable ），所以），所以P4等待。等待。2022-6-668例例3：P0请求资源请求资源nRequest（0，2，0），），执行银行家算法执行银行家算法2022-6-669进行安全性检查进行安全性检查nAvailabl

40、e2,1,0已不能满足任何进程需要，已不能满足任何进程需要，所以系统进入不安全状态，所以系统进入不安全状态，P0的请求不能分的请求不能分配配2022-6-670n练习：有三类资源练习：有三类资源A(17)、B(5)、C(20)。有有5个进程个进程P1P5。T0时刻系统状态如下：时刻系统状态如下：问问(1)、T0时刻是否为安全状态，给出安全系列。时刻是否为安全状态，给出安全系列。(2)、T0时刻，时刻，P2: Request(0,3,4)，能否分配，为什么？能否分配，为什么？(3)、在、在(2)的基础上的基础上P4：Request(2,0,1)，能否分配，为什么？能否分配，为什么？(4)、 在在

41、(3)的基础上的基础上P1：Request(0,2,0)，能否分配，为什么？能否分配，为什么？ 最大需求最大需求已分配已分配P15 5 92 1 2P25 3 64 0 2P34 0 114 0 5P44 2 52 0 4P54 2 43 1 42022-6-671解：解：(1) T0时刻的出安全系列时刻的出安全系列最大需求最大需求已分配已分配NeedP15 5 92 1 23 4 7P25 3 64 0 21 3 4P34 0 114 0 50 0 6P44 2 52 0 42 2 1P54 2 43 1 41 1 0A(17)、B(5)、C(20)Work=2 3 3先求出先求出Need和

42、和Work2022-6-672WorkAllocationNeedW+AFinishP52 3 33 1 41 1 05 4 7TP45 4 72 0 42 2 17 4 11TP37 4 114 0 50 0 611 4 16TP211 4 164 0 21 3 415 4 18TP115 4 182 1 23 4 717 5 20TWork=2 3 32022-6-673(2) P2: Request(0,3,4)n因因（ Available =2 3 3） Request(0,3,4) 所以不能分所以不能分配配2022-6-674(3) P4：Request(2,0,1)WorkAllo

43、cationNeedW+AFinishP40 3 24 0 50 2 04 3 7TP54 3 73 1 41 1 07 4 11TP37 4 114 0 50 0 611 4 16TP211 4 164 0 21 3 415 4 18TP115 4 182 1 23 4 717 5 20TAvailable =2 3 3AllocationNeedAvailableP12 1 23 4 70 3 2P24 0 21 3 4P34 0 50 0 6P44 0 50 2 0P53 1 41 1 0有安全序有安全序列列P4 P5 P3 P2 P1 可以分配可以分配2022-6-675(4) P1：

44、Request(0,2,0)AllocationNeedAvailableP12 3 23 2 70 1 2P24 0 21 3 4P34 0 50 0 6P44 0 50 2 0P53 1 41 1 00 1 2 已不能满足任何进程的需要，不能分配已不能满足任何进程的需要，不能分配2022-6-676死锁检测：死锁检测： 允许死锁发生，操作系统不断监视系统进允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生展情况，判断死锁是否发生 一旦死锁发生则采取专门的措施，一旦死锁发生则采取专门的措施，解除死解除死锁锁并以最小的代价恢复操作系统运行并以最小的代价恢复操作系统运行4.3.4 死锁

45、的检测和解除死锁的检测和解除2022-6-677检测时机：检测时机： 当进程等待时检测死锁当进程等待时检测死锁 （其缺点是系统的开销大）（其缺点是系统的开销大） 定时检测定时检测 系统资源利用率下降时检测死锁系统资源利用率下降时检测死锁2022-6-678死锁的解除死锁的解除 重要的是以最小的代价恢复系统的运行。方重要的是以最小的代价恢复系统的运行。方法如下：法如下： 1 1）重新启动）重新启动 2 2）撤消进程）撤消进程 3 3）剥夺资源）剥夺资源 4 4）进程回退）进程回退2022-6-679资源分配图资源分配图 用有向图描述进程的死锁用有向图描述进程的死锁 准确、形象准确、形象 系统由若

46、干类资源构成，一类资源称为一系统由若干类资源构成，一类资源称为一个个资源类资源类；每个资源类中包含若干个同种；每个资源类中包含若干个同种资源，称为资源，称为资源实例资源实例2022-6-680 二元组二元组G=G=（V V，E E） V V：结点集，分为结点集，分为P P，R R两部分两部分 P=p1,p2,pnP=p1,p2,pn R=r1,r2,rm R=r1,r2,rm E E：边的集合，其元素为有序二元组边的集合，其元素为有序二元组 ( (pi,rj)pi,rj)或或( (rj,pi)rj,pi) 2022-6-681表示法表示法资源类（资源的不同类型）资源类（资源的不同类型） 用方框

47、表示用方框表示资源实例（存在于每个资源中）资源实例（存在于每个资源中） 用方框中的黑圆点（圈）表示用方框中的黑圆点（圈）表示进程进程 用圆圈中加进程名表示用圆圈中加进程名表示2022-6-682分配边：分配边： 资源实例资源实例进程的一条有向边进程的一条有向边申请边：申请边： 进程进程资源类的一条有向边资源类的一条有向边2022-6-683例例2022-6-684死锁定理死锁定理 如果资源分配图中没有环路，则系统如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中没有死锁，如果图中存在环路则系统中中可能可能存在死锁存在死锁 如果每个资源类中只包含一个资源实例，如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件则环路是死锁存在的充分必要条件2022-6-685资源分配图化简资源分配图化简1 1）找一