第六章并发、死锁和饥饿浙江工业大学

1、1并发性并发性: 死锁和饥饿死锁和饥饿第第 6 章章2死锁死锁 多道程序系统中，多个进程并发执行可改善多道程序系统中，多个进程并发执行可改善系统的资源利用率和提高系统的处理能力，但也系统的资源利用率和提高系统的处理能力，但也带来一种危险，即死锁现象发生。所谓带来一种危险，即死锁现象发生。所谓死锁死锁是指是指计算机计算机系统和进程所处的一种状态系统和进程所处的一种状态。在系统中，在系统中，两个或多个进程无限期地等待永远不会发生的条两个或多个进程无限期地等待永远不会发生的条件件，此时称系统处于死锁状态。，此时称系统处于死锁状态。 n一组进程因竞争系统资源或相互通信所造成的永一组进程因竞争系统资源或

2、相互通信所造成的永久性阻塞久性阻塞n没有有效的通用解决办法没有有效的通用解决办法n涉及到两个或更多的进程之间因对资源的需求所涉及到两个或更多的进程之间因对资源的需求所引起的冲突引起的冲突3汽车以汽车以7070码的速度码的速度行驶，如行驶，如果没有任果没有任何的措施，何的措施，接下来会接下来会发生什么？发生什么？4怎么办？怎么办？5进程进程A A进程进程B B 申请输入设备申请输入设备申请输出设备申请输出设备 申请输出设备申请输出设备申请输入设备申请输入设备 释放输入设备释放输入设备释放输出设备释放输出设备 释放输出设备释放输出设备释放输入设备释放输入设备 如果执行次序为：进程如果执行次序为：进

3、程A A进程进程B B.， 则发生死锁。则发生死锁。输入设备输入设备输出设备输出设备BA输入设备输入设备输出设备输出设备占有占有占有占有等待等待等待等待 A在干什么？在干什么？ B在干什么？在干什么？竞竞争争外外设设死死锁锁示示例例6ABCDELMNOPQFGHIJKAABBCCDDFGHILLMMNNOOFGHISPOOLing系统死锁示例输出井进程B进程C 满啦！ 不够！ 不够！ 不够！进程A7系统资源系统资源n可重用资源可重用资源 (Reusable Resources) 一次只能供一个进程安全地使用一次只能供一个进程安全地使用 使用资源顺序：请求资源；使用资源；释放资源使用资源顺序：请

4、求资源；使用资源；释放资源 进程用完资源后可以释放该资源，供其他进程再次进程用完资源后可以释放该资源，供其他进程再次使用使用 如处理器、如处理器、I/O通道、主存和辅存、设备等通道、主存和辅存、设备等n可消费资源可消费资源(Consumable Resources)（临时资源）临时资源） 可以创建并且可以消费的资源可以创建并且可以消费的资源 进程消费完资源后，该资源就不存在了进程消费完资源后，该资源就不存在了 如中断、信号、消息等如中断、信号、消息等8系统资源系统资源n可抢占性资源可抢占性资源 进程在获得这类资源后，该资源可被其它进进程在获得这类资源后，该资源可被其它进程或系统抢占。程或系统抢

5、占。 这类资源不会引起死锁这类资源不会引起死锁 如处理器、主存等如处理器、主存等n不可抢占性资源不可抢占性资源 一旦系统把某资源分配给该进程后，就不能一旦系统把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放将它强行收回，只能在进程用完后自行释放 如磁带机、打印机等如磁带机、打印机等9资源分配图资源分配图n用资源分配图来表示系统状态。用资源分配图来表示系统状态。n资源分配图由结点和边组成，资源分配图由结点和边组成，是由一组结是由一组结点点N和一组边和一组边E所组成的一个对偶所组成的一个对偶G=（N，E）。）。（1） P是一组进程结点是一组进程结点P= P1,P2, Pn，R是

6、是资源结点资源结点R= r1,r2, rn ，N=PUR，且，且PR= 。（2） 任意一边任意一边eE，都连接着，都连接着P中的一个结点中的一个结点和和R中的一个结点，我们用圆圈表示进程，方中的一个结点，我们用圆圈表示进程，方框表示一类相同的资源，方框中的小圆表示一框表示一类相同的资源，方框中的小圆表示一类资源中的一个资源。类资源中的一个资源。10表示法表示法资源类（资源的不同类型）资源类（资源的不同类型）: :用方框表示用方框表示 资源实例（存在于每个资源中）：用方框资源实例（存在于每个资源中）：用方框中的黑圆点表示中的黑圆点表示 进程：用圆圈中加进程名表示进程：用圆圈中加进程名表示 P分配

7、边：分配边： 资源实例资源实例进程的一条有向边进程的一条有向边申请边：申请边： 进程进程资源类的一条有向边资源类的一条有向边PiRjPiRj11系统资源分配图示例系统资源分配图示例 R1R2 P1P212产生死锁的原因产生死锁的原因1.竞争资源引起死锁竞争资源引起死锁 竞争不可抢占性资源：资源不足竞争不可抢占性资源：资源不足 竞争可消耗性资源竞争可消耗性资源2.进程推进顺序不合理进程推进顺序不合理 请求和释放资源的顺序不当请求和释放资源的顺序不当 13产生死锁的原因产生死锁的原因1.1.竞争资源引起死锁竞争资源引起死锁 在多道程序系统，多个进程共享系在多道程序系统，多个进程共享系统的资源。对于

8、可重用的资源，当系统统的资源。对于可重用的资源，当系统把这类资源分配给某进程后，不能强行把这类资源分配给某进程后，不能强行收回，只能在进程用完后自动释放。当收回，只能在进程用完后自动释放。当多个进程竞争这类资源时就可能引起死多个进程竞争这类资源时就可能引起死锁。锁。14竞争资源竞争资源申请申请P2 R1 R2 P1分配分配分配分配申请申请例如系统只有一台打印机例如系统只有一台打印机R1和一台磁带和一台磁带机机R2，可供进程，可供进程P1和和P2共享。共享。两个进程都在等两个进程都在等待对方释放出自待对方释放出自己所需要的资源，己所需要的资源，但它们又都因不但它们又都因不能获得所需的资能获得所需

9、的资源而不能继续推源而不能继续推进，从而也不能进，从而也不能释放出自己占有释放出自己占有的资源，以致进的资源，以致进入死锁状态。入死锁状态。152.2.进程推进顺序不当引起死锁进程推进顺序不当引起死锁 在多道程序系统中，并发执行的进程推在多道程序系统中，并发执行的进程推进序列不可预测，有些推进顺序，进程可进序列不可预测，有些推进顺序，进程可以顺利完成，这些推进顺序是合法的；而以顺利完成，这些推进顺序是合法的；而有的推进顺序会引起进程无限期地等待永有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进，造成远不会发生的条件而不能向前推进，造成了死锁。了死锁。产生死锁的原因产生死锁的原

10、因16例例1进程推进顺序不当引起死锁进程推进顺序不当引起死锁 进程进程P和和Q并发执行，竞争两个资源并发执行，竞争两个资源A和和B。每个进程需要独占使用这两个资源。每个进程需要独占使用这两个资源。进程进程P和和Q程序如下：程序如下：Process P Process Q .Get A Get B .Get B Get A Release A Release B .Release B Release A17进程进程P和和Q按路径按路径1、2、5、6推进顺序推进顺序合法，按合法，按3、4推进推进顺序非法顺序非法18Process P Process Q .Get A Get B .Release

11、A Get A Get B Release B .Release B Release A修改修改P程序，可避免死锁程序，可避免死锁1920例例2竞争可重用性资源引起死锁竞争可重用性资源引起死锁进程进程P、Q并发执行，竞争访问磁盘并发执行，竞争访问磁盘D和磁带和磁带T。假设按以下执行序列执行：假设按以下执行序列执行：p0p1q0q1p2q2解决办法：定义资源请求的先后次序解决办法：定义资源请求的先后次序 21n解决办法：使用虚拟存储机制解决办法：使用虚拟存储机制P1. . . . .Request 80 Kbytes;Request 60 Kbytes;P2. . . . .Request 70

12、 Kbytes;Request 80 Kbytes;例例3竞争可重用性资源引起死锁竞争可重用性资源引起死锁 进程进程P1、P2并发执行，请求主存空间。并发执行，请求主存空间。假设可用的主存空间初始为假设可用的主存空间初始为200KB，P1、P2按以下顺序请求：按以下顺序请求：22P1. . . . .Receive(P2);Send(P2, M1);P2. . . . .Receive(P1);Send(P1, M2);例例4竞争可消耗资源引起死锁竞争可消耗资源引起死锁 进程进程P1、P2并发执行，通过信号量机并发执行，通过信号量机制进行同步。假设采用的是制进行同步。假设采用的是Receive

13、阻塞机阻塞机制（即未收到信息则该进程被阻塞）制（即未收到信息则该进程被阻塞）23死锁的条件死锁的条件死锁的三个必要条件死锁的三个必要条件n互斥互斥 (Mutual exclusion) 一次只有一个进程可以使用一个资源一次只有一个进程可以使用一个资源n占有且等待占有且等待 (Hold-and-wait) 当一个进程在等待分配得到其他资源时，将当一个进程在等待分配得到其他资源时，将继续占有已分配到的资源继续占有已分配到的资源n非剥夺非剥夺 (No preemption )（不可抢占）（不可抢占） 不能强行抢占进程已占有的资源不能强行抢占进程已占有的资源Q: 上述三个条件是不是一定会导致死锁的上述

14、三个条件是不是一定会导致死锁的发生发生 ?24死锁的条件死锁的条件n循环等待循环等待 (Circular wait)存在一个封闭的进程存在一个封闭的进程-资源链，每个进资源链，每个进程至少占有一个该链中下一个进程所程至少占有一个该链中下一个进程所需要的资源需要的资源25死锁的三种处理办法死锁的三种处理办法n死锁的预防（死锁的预防（Prevention）静态方法：在进程执行前采取的措施，通过设置某静态方法：在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个必要条件之一，些限制条件，去破坏产生死锁的四个必要条件之一，防止发生死锁。防止发生死锁。 n死锁的避免死锁的避免（Avoida

15、nce）动态的方法：在进动态的方法：在进程程执行过程中采取的措施，不需执行过程中采取的措施，不需事先采取限制措施破坏产生死锁的必要条件，而是事先采取限制措施破坏产生死锁的必要条件，而是在进程申请资源时用某种方法去防止系统进入不安在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁。全状态，从而避免发生死锁。n死锁的检测死锁的检测（Detection）和解除和解除这种方法预先并不采用任何限制措施，允许系统在这种方法预先并不采用任何限制措施，允许系统在运行过程中发生死锁，但可通过系统设置的检测机运行过程中发生死锁，但可通过系统设置的检测机构及时检测死锁的发生构及时检测死锁的发生（定

16、期执行死锁检测算法）（定期执行死锁检测算法），如检测到死锁，则采用撤消进程等死锁解除方法使如检测到死锁，则采用撤消进程等死锁解除方法使系统系统恢复恢复正常工作。正常工作。2627死锁的预防死锁的预防 (Deadlock Prevention) 预防死锁的方法是破坏四个产生死锁的必要预防死锁的方法是破坏四个产生死锁的必要条件之一条件之一。n破坏互斥条件破坏互斥条件 互斥使用是资源本身特征所决定的。使用互斥使用是资源本身特征所决定的。使用硬软件结合可改变资源本身特性，例如采硬软件结合可改变资源本身特性，例如采用用SPOOLing技术可将技术可将“独享独享” 打印机改打印机改变为变为“共享共享”的打

17、印机。的打印机。n破坏不可抢占条件破坏不可抢占条件 可采用抢占式调度，但抢占式调度法主要可采用抢占式调度，但抢占式调度法主要用于处理机和存储器资源调度，它们的状用于处理机和存储器资源调度，它们的状态容易保存和恢复。此法对外部设备和私态容易保存和恢复。此法对外部设备和私有数据不宜使用。有数据不宜使用。28n破坏请求和保持条件破坏请求和保持条件系统可系统可采用资源静态预先全分配方式来破坏采用资源静态预先全分配方式来破坏请求保持条件请求保持条件。系统要求所有进程一次性地。系统要求所有进程一次性地申请在整个运行过程中全部资源，若系统有申请在整个运行过程中全部资源，若系统有足够资源满足给进程，则在运行前

18、，一次性足够资源满足给进程，则在运行前，一次性将其所需要的所有资源分配给该进程。这样将其所需要的所有资源分配给该进程。这样该进程在整个运行期间，便不再提出资源要该进程在整个运行期间，便不再提出资源要求，从而摒弃了请求条件。求，从而摒弃了请求条件。优点是简单、易于实现且很安全，但其资源优点是简单、易于实现且很安全，但其资源利用率很低，进程也延迟运行。利用率很低，进程也延迟运行。死锁的预防死锁的预防29n破坏循环等待条件破坏循环等待条件有序资源使用法有序资源使用法 该方法将所有的资源按类型进行线性排队，并赋该方法将所有的资源按类型进行线性排队，并赋予不同的序号。例如令输入机的序号为予不同的序号。例

19、如令输入机的序号为1 1，打印机，打印机序号为序号为2 2，磁盘机序号为，磁盘机序号为3 3等。等。 所有进程对资源的请求必须严格按资源序号递所有进程对资源的请求必须严格按资源序号递增的次序提出。这样在所形成的资源分配图中不可增的次序提出。这样在所形成的资源分配图中不可能再出现环路，因而摒弃了能再出现环路，因而摒弃了“循环等待循环等待”条件，在条件，在采用这种策略时总有一个进程占据了较高序号的资采用这种策略时总有一个进程占据了较高序号的资源，它继续请求的资源必然是空闲的，因而进程可源，它继续请求的资源必然是空闲的，因而进程可以一直向前推进。以一直向前推进。可提高资源利用率，但在进程使用各类资源

20、可提高资源利用率，但在进程使用各类资源的顺序与系统规定的顺序不同时会造成资源的顺序与系统规定的顺序不同时会造成资源浪费的情况。浪费的情况。死锁的预防死锁的预防30反证：若出现循环等待，则必会有小序号资反证：若出现循环等待，则必会有小序号资源序号大于大序号资源序号。源序号大于大序号资源序号。 令令R=r1,r2,rm表示一组资源类型。我们定表示一组资源类型。我们定义一个一对一的函数义一个一对一的函数F(R)=N,N是一组自然数。是一组自然数。 例：一组资源包括磁盘机、磁带机、读卡机和例：一组资源包括磁盘机、磁带机、读卡机和打印机。打印机。 函数函数F可定义如下：可定义如下： F(读卡机读卡机)=

21、1,F(磁盘机磁盘机)=5, F(磁带机磁带机)=7,F(打印机打印机)= 12 若存在环路等待，则必然有若存在环路等待，则必然有F(r1)F(r2)F(ri)F(r1) 由传递性得到：由传递性得到：F(r1)F(r1) 矛盾矛盾31有序资源使用法有序资源使用法 R1 R2 R3 R4 R5 R6 R7A * * *B * * *C * * * *A、B、C三个进程对于资源的请求只能按照三个进程对于资源的请求只能按照资源排列的先后次序请求资源排列的先后次序请求32XX如果红绿如果红绿灯坏了，灯坏了，或者没装或者没装红绿灯，红绿灯，怎么办？怎么办？33驾驶员在行驶过程中实时地判断安不安全。如驾驶

22、员在行驶过程中实时地判断安不安全。如果不安全就减速或停车等待，安全后再通过。果不安全就减速或停车等待，安全后再通过。小心！注意安全！小心！注意安全！34死锁的避免死锁的避免 (Deadlock Avoidance)n允许三个条件的存在，但通过动态的选允许三个条件的存在，但通过动态的选择，确保永远不会到达死锁点。择，确保永远不会到达死锁点。n允许进程动态地申请资源，系统在进行允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统从安全状性。若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配态向不安全状态转换，

23、便可将资源分配给进程；否则不分配资源，进程必须阻给进程；否则不分配资源，进程必须阻塞等待。从而避免发生死锁。塞等待。从而避免发生死锁。n需要知道将来的进程资源请求情况需要知道将来的进程资源请求情况35资源分配拒绝资源分配拒绝n系统的系统的安全状态安全状态是指系统的一种状态，是指系统的一种状态，在此状态下系统能按某种顺序（例如在此状态下系统能按某种顺序（例如P P1 1、P P2 2PPn n）来为各个进程分配其所需资源，）来为各个进程分配其所需资源，直至最大需求，使每个进程都可顺序地直至最大需求，使每个进程都可顺序地一个个地完成。这个序列（一个个地完成。这个序列（P P1 1、P P2 2.P

24、.Pn n）称为安全序列。）称为安全序列。n若系统在某个状态下不存在一个安全序若系统在某个状态下不存在一个安全序列，使所有进程能运行结束，则称系统列，使所有进程能运行结束，则称系统处于处于不安全状态不安全状态。不安全状态并不是死。不安全状态并不是死锁状态，而是存在死锁的可能性。锁状态，而是存在死锁的可能性。n系统只有在安全状态下才满足进程对于系统只有在安全状态下才满足进程对于资源的请求，否则拒绝。资源的请求，否则拒绝。36 设银行家有设银行家有1010万贷款，万贷款，P, Q, RP, Q, R分别需要分别需要8,3,98,3,9万元搞项目，万元搞项目，如果如果P P已申请到了已申请到了4 4

25、万，万，Q Q要申请要申请2 2万，显然，如果满足万，显然，如果满足Q Q的申请，的申请，有安全序列有安全序列/。 客户客户最大需求量最大需求量已分配已分配还需要还需要可用可用P8444Q321R909还需要还需要可用可用客户客户910R18Q44P37客户客户最大需求量最大需求量已分配已分配还需要还需要可用可用P8442Q303R945还需要还需要可用可用客户客户2若满足若满足R的申请，显然不存在安全序列。的申请，显然不存在安全序列。如果如果R要申请要申请4万万38注意注意n安全状态不是死锁状态；死锁状态是不安安全状态不是死锁状态；死锁状态是不安全状态。全状态。n不安全状态不安全状态:不存在

26、一个安全序列不存在一个安全序列n不安全状态可能导致死锁，但不安全状态不安全状态可能导致死锁，但不安全状态不一定是死锁状态。不一定是死锁状态。39银行家算法银行家算法n最具代表的避免死锁算法是最具代表的避免死锁算法是Dijkstra的银行家的银行家算法，这是由于该算法用于银行系统现金贷款算法，这是由于该算法用于银行系统现金贷款的发放而得名。的发放而得名。n某银行共有资金某银行共有资金100万元和三个借贷客户甲、万元和三个借贷客户甲、乙、丙乙、丙, 他们的最大借款额分别为他们的最大借款额分别为100, 80, 70(万元万元). 他们已借得的金额分别为他们已借得的金额分别为10, 20, 50(万

27、元万元). 银行还有资金多少银行还有资金多少? 各客户还需多少各客户还需多少资金资金? 按目前状况按目前状况, 银行可能收回全部贷款吗银行可能收回全部贷款吗? 如果乙提出借如果乙提出借10万万, 可以满足吗可以满足吗? 如果丙提出如果丙提出借借10万万, 可以满足吗可以满足吗?(假设客户获得最大借款额后就返还银行所有借款假设客户获得最大借款额后就返还银行所有借款)40算法的数据结构算法的数据结构考虑一个具有考虑一个具有n个进程个进程和和 m 种不同类型资种不同类型资源源系统。系统。nResource=R=(R1,R2,Rm)：向量，表示系：向量，表示系统中每种资源的总量统中每种资源的总量nAv

28、ailable=V=(V1,V2,Vm)：向量，未分配：向量，未分配给进程的每种资源的总量，即可用的资源数给进程的每种资源的总量，即可用的资源数nClaim=C：矩阵，：矩阵，Cij表示进程表示进程i对资源对资源 j的最大的最大需求需求nAllocation=A：矩阵，：矩阵，Aij表示当前进程表示当前进程i已分已分配到的资源配到的资源j的数量的数量nNeed=N：矩阵，表示每个进程尚需的各类资：矩阵，表示每个进程尚需的各类资源数，源数， Needi,j=k 表示进程表示进程i还需要还需要j类资源类资源k个。个。Needi,j=Claimi,j-Allocationi,j41安全状态检测（安全

29、状态检测（1）是否为安全状态是否为安全状态?42P2 运行结束，并释放所占用的资源运行结束，并释放所占用的资源43P1 运行结束，并释放所占用的资源运行结束，并释放所占用的资源44P3 运行结束，并释放所占用的资源运行结束，并释放所占用的资源45安全状态检测（安全状态检测（2）是否为安全状态是否为安全状态?46算法思想算法思想n假设在进程并发执行时，进程假设在进程并发执行时，进程i i提出请求提出请求j j类资源类资源k k个个后，表示为后，表示为RequestRequest i,j=ki,j=k。系统按下述步骤进行安。系统按下述步骤进行安全检查：全检查：1.1.如果如果alloci,j+Re

30、quest i,jclaimi,jalloci,j+Request i,jclaimi,ji i则继续则继续以下检查，否则显示需求申请超出最大需求值的错误。以下检查，否则显示需求申请超出最大需求值的错误。2.2.如果如果Request iAvailableRequest iAvailable则继续以下检查，否则则继续以下检查，否则显示系统无足够资源，显示系统无足够资源，P Pi i阻塞等待。阻塞等待。3.3.系统假设同意进程系统假设同意进程i i的请求，将系统状态修改为满足的请求，将系统状态修改为满足请求之后的状态，然后对此状态执行安全性算法检测，请求之后的状态，然后对此状态执行安全性算法检测

31、，判断在此次资源分配后，系统是否处于安全状态，若判断在此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给进程安全，才正式将资源分配给进程i i，以完成本次分配；，以完成本次分配；否则将恢复原来的资源分配状态，让进程否则将恢复原来的资源分配状态，让进程P Pi i等待，即等待，即进程进程P Pi i置为阻塞状态。置为阻塞状态。n因此，在图因此，在图6.8b,中，中，P1的请求将被拒绝，的请求将被拒绝，P1将从运将从运行状态转变为阻塞状态。行状态转变为阻塞状态。47安全性算法思想安全性算法思想执行步骤如下：执行步骤如下：A.A.初始化设置工作向量初始化设置工作向量currentava

32、ilmcurrentavailm表示系统可提供表示系统可提供的各类资源数目，用以保护原数据结构有关值。的各类资源数目，用以保护原数据结构有关值。currentavail = Availablecurrentavail = Available。设置完成标志向量。设置完成标志向量 FinishnFinishn，Finishi = false Finishi = false 表示表示i i进程尚末完成，进程尚末完成，如值为如值为truetrue则表示进程则表示进程i i已完成。已完成。B.B.从进程集合从进程集合n n中找到一个能满足下述二个条件中找到一个能满足下述二个条件: : Finishi =

33、 falseFinishi = false和和NeedicurrentavailNeedicurrentavail，如找到，如找到则执行步骤则执行步骤C C，如找不到同时满足以上二条件的进程则，如找不到同时满足以上二条件的进程则执行步骤执行步骤D D。C.C.当进程当进程i i获得资源后可顺利执行直到完成，并释放出分获得资源后可顺利执行直到完成，并释放出分配给它的资源，表示如下：配给它的资源，表示如下： currentavail=currentavail+allocationicurrentavail=currentavail+allocationi ； Finishi=true Finish

34、i=true ；转执行步骤；转执行步骤 B B。D.D.如果所有的如果所有的FinishiFinishitruetrue，则表示系统处于安全状，则表示系统处于安全状态，否则系统处于不安全状态。态，否则系统处于不安全状态。48死锁避免算法死锁避免算法4950例例1假定系统中有五个进程假定系统中有五个进程P0、P1、P2、P3、P4和三种类型资源和三种类型资源A、B、C，每一种资源的数量分，每一种资源的数量分别为别为10、5、7。各进程的最大需求、。各进程的最大需求、T0时刻资源分时刻资源分配情况如下配情况如下 所示。所示。 Claim Allocation Need Available A B

35、C A B C A B C A B C P0 7 5 3 0 1 0 P1 3 2 2 2 0 0 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2 4 32 20 00 1 14 3 13 3 251n1.T1.T0 0时刻是否安全？时刻是否安全？解：解：1).已知：已知： Allocation和和ClaimClaim要先求要先求Need = Claim-Claim-Allocation2).已知：总资源数和已知：总资源数和Allocation要先求要先求Available =总资源数总资源数 - 3).求是不是安全状态的关键求是不是安全状态的关键就在

36、于能否找到一个就在于能否找到一个进程的执行序列，使所有的进程都能执行结束。进程的执行序列，使所有的进程都能执行结束。该序列称为安全序列。该序列称为安全序列。1niTi52 1 T0时刻的安全序列时刻的安全序列存在安全性序列存在安全性序列P1，P3，P4，P2，P0或或P1，P3，P4，P0，P2。 3 3 2P11 2 22 0 0 5 3 2True 5 3 2P30 1 12 1 1 7 4 3true 7 4 3P44 3 10 0 2 7 4 5trueP0 7 4 57 4 30 1 0 7 5 5true 7 4 5P26 0 03 0 2 10 4 7trueP2 7 5 56

37、0 03 0 2 10 5 7true10 4 7P07 4 30 1 0 10 5 7true 资源情况资源情况进程进程Work A B CNeedA B CAllocationA B CWork+Allocation A B CFinish从表中可找出一个序列从表中可找出一个序列(P1 、 P3、 P4 、 P2 、 P0）使各进使各进程程顺序地一个个地执行顺序地一个个地执行完成。完成。claimclaimAllocatiAllocationon NeedNeedWorkWork(Availabl(Available)e)Work + Work + AllocatioAllocation

38、n i i次次序序 A B CA B C A B CA B C A B CA B CA B CA B C3 3 23 3 2 A B CA B CP P0 0 7 5 3 7 5 3 0 1 00 1 0 7 4 37 4 3 10 5 710 5 75 5P P1 1 3 2 23 2 2 2 0 02 0 0 1 2 21 2 2 5 3 25 3 21 1P P2 2 9 0 29 0 2 3 0 23 0 2 6 0 06 0 0 10 4 710 4 74 4P P3 3 2 2 22 2 2 2 1 12 1 1 0 1 10 1 1 7 4 37 4 32 2P P4 4 4 3

39、 34 3 3 0 0 20 0 2 4 3 14 3 1 7 4 57 4 53 354nT0时刻系统是安全的。时刻系统是安全的。n可能有几个安全序列，只要找出一个安全序可能有几个安全序列，只要找出一个安全序列就可以。列就可以。n注意：注意： Needi = Available 要求数组每个元要求数组每个元素都成立素都成立 例：例： 1 2 3 = 3 3 2 不成立不成立n2. P2. P1 1请求资源请求资源RequestRequest1 1(1,0,2)(1,0,2)可否允许？可否允许？RequestRequest1 1(1,0,2)Need(1,0,2)Need1 1(1,2,2)(

40、1,2,2)，P1请求在最大需求请求在最大需求范围内。范围内。RequestRequest1 1(1,0,2) Available(3,3,2)(1,0,2) Available(3,3,2)，可用资源可，可用资源可满足满足P1请求需要。请求需要。试探把要求的资源分配给进程试探把要求的资源分配给进程P1并修改有关数据结构并修改有关数据结构的数值：的数值：Available = Available(3Available = Available(3，3 3，2)2)RequestRequest1 1(1,0,2)=Available(2,3,0)(1,0,2)=Available(2,3,0)；N

41、eed1 = Need1(1,2,2)1,2,2)Request1(1,0,2)= (1,0,2)= NeedNeed1 1(0,2,0)(0,2,0)；Allocation1 =Allocation1(2,0,0),0,0)+Request1(1,0,2) (1,0,2) =Allocation=Allocation1 1(3,0,2)(3,0,2)；利用安全性算法检查试探将资源分配后状态的安全性利用安全性算法检查试探将资源分配后状态的安全性如下：如下：56 WorkA B CNeedA B CAllocationA B CWork+AllocationA B CFinishP12 3 00

42、 2 03 0 25 3 2trueP35 3 20 1 12 1 17 4 3trueP47 4 34 3 10 0 27 4 5trueP07 4 57 4 30 1 07 5 5trueP27 5 56 0 03 0 210 5 7true 存在安全序列存在安全序列 P1，P3，P4，P0，P2，可以将，可以将P1所申请的资源分配给它。所申请的资源分配给它。 claim Allocation Need Available Available (分配资源前分配资源前) (释放释放资源资源后）后） A B C A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4

43、 3 = 10 4 7 10 5 7P1 3 2 2 3 0 2 0 2 0 = 2 3 0 5 3 2P2 9 0 2 3 0 2 6 0 0 = 7 4 5 10 4 7P3 2 2 2 2 1 1 0 1 1 = 5 3 2 7 4 3P4 4 3 3 0 0 2 4 3 1 = 7 4 3 7 4 5 因为先分配资源给因为先分配资源给P P1 1进程符合按安全序列进程符合按安全序列PP1 1、P P3 3、P P4 4、P P2 2、P P0 0 分配资源，所以试探将资源分配给进程分配资源，所以试探将资源分配给进程P P1 1后的状后的状态是安全的，可将资源分配给进程态是安全的，可将资

44、源分配给进程P P1 1。58n3.P3.P4 4请求资源请求资源RequestRequest4 4(3,3,0)(3,3,0)是否允许？是否允许？RequestRequest4 4(3,3,0)Need(3,3,0)Need4 4(4,3,1)(4,3,1)，P P4 4请求在最请求在最大需求范围内。大需求范围内。RequestRequest4 4(3,3,0)Available(2,3,0)(3,3,0)Available(2,3,0)不成立，不成立，即可用资源暂不能满足即可用资源暂不能满足P P4 4请求资源需要，请求资源需要，P P4 4阻阻塞等待。塞等待。 59例例2 进程进程 P1

45、、P2和和P3共享共享12个相同资源，它个相同资源，它们对于资源的最大需求分别是：们对于资源的最大需求分别是：8，6，9。如。如果它们按以下步骤请求资源：果它们按以下步骤请求资源：Steps Process Resources Request 1 P1 4 2 P2 4 3 P3 2 4 P1 1 5 P3 2 6 P2 2使用银行家算法解决：使用银行家算法解决：（1）哪一步将导致不安全状态？）哪一步将导致不安全状态？（2）在第六步之后，）在第六步之后，P1、P2和和P3的状态分别的状态分别是什么？它们所占用的资源数为多少？是什么？它们所占用的资源数为多少？60nstep1, P1请求请求4个

46、资源，个资源，4=8&4=12，可以满足；，可以满足； Claim Allocation Need Available P1 8 4 4 8 P2 6 0 6 P3 9 0 9 n假设分配给假设分配给P1，则系统可用资源数为，则系统可用资源数为8，P1还需的资源数为还需的资源数为4，显然是安全状态；，显然是安全状态；61nstep2, P2请求请求4个资源，个资源，4=6&4=8，可以满足；，可以满足；n假设分配给假设分配给P2，则系统可用资源数为，则系统可用资源数为4，P2还需的资还需的资源数为源数为2，显然是安全状态；，显然是安全状态； Claim Allocation N

47、eed Available P1 8 4 4 8 P2 6 0 6 P3 9 0 9 Claim Allocation Need Available P1 8 4 4 4 P2 6 4 2 P3 9 0 9 62nstep3, P3请求请求2个资源，个资源，2=9&2=2，可，可以满足；以满足；n假设分配给假设分配给P3，则系统可用资源数为，则系统可用资源数为2，P3还需的资源数为还需的资源数为7。分配之后，此时系统仍然。分配之后，此时系统仍然可以沿着可以沿着P2、P1、P3的序列执行，因此仍然的序列执行，因此仍然是安全状态；是安全状态； Claim Allocation Need A

48、vailable P1 8 4 4 4 P2 6 4 2 P3 9 0 9 Claim Allocation Need Available P1 8 4 4 2 P2 6 4 2 P3 9 2 763nstep4, P1请求请求1个资源，个资源，1=4&1=2，可，可以满足；以满足；n假设分配给假设分配给P1，则系统可用资源数为，则系统可用资源数为1，P1还需的资源数为还需的资源数为3。分配之后，此时系统所剩分配之后，此时系统所剩的资源数不能满足任何一个进程执行所需，的资源数不能满足任何一个进程执行所需，故不存在一条安全序列，即如果进行分配，故不存在一条安全序列，即如果进行分配，则系统

49、将进入不安全状态，因此，则系统将进入不安全状态，因此，第第4步将导步将导致系统变成不安全状态。致系统变成不安全状态。采用银行家算法将采用银行家算法将避免这种分配，即将避免这种分配，即将P1置为阻塞状态。置为阻塞状态。 Claim Allocation Need Available P1 8 4 4 2 P2 6 4 2 P3 9 2 764nStep5, P3请求请求2个资源，个资源，2=7&2=2，可以满，可以满足；足；n假设分配给假设分配给P3，则系统可用资源数为，则系统可用资源数为0，P3还需还需的资源数为的资源数为5。分配之后，此时系统所剩的资源。分配之后，此时系统所剩的资源数

50、不能满足任何一个进程执行所需，故不存在一数不能满足任何一个进程执行所需，故不存在一条安全序列，即如果进行分配，则系统将进入不条安全序列，即如果进行分配，则系统将进入不安全状态，安全状态，采用银行家算法将避免这种分配，即采用银行家算法将避免这种分配，即将将P3置为阻塞状态。置为阻塞状态。 Claim Allocation Need Available P1 8 4 4 2 P2 6 4 2 P3 9 2 765nStep6, P2请求请求2个资源，个资源，2=2&2=2，可以满足；，可以满足；n假设分配给假设分配给P2，则系统可用资源数为，则系统可用资源数为0，P2还需的还需的资源数为资

51、源数为0。这种分配符合我们先前所说的安全序列。这种分配符合我们先前所说的安全序列执行顺序，因此可以满足。执行顺序，因此可以满足。P2处于运行状态，占用处于运行状态，占用的资源数为的资源数为6。n因此，在第六步之后，因此，在第六步之后，P1的状态为阻塞，占用资源的状态为阻塞，占用资源数为数为4；P2状态为运行，占用资源数为状态为运行，占用资源数为6；P3的状态的状态为阻塞，占用资源数为为阻塞，占用资源数为2 Claim Allocation Need Available P1 8 4 4 2 P2 6 4 2 P3 9 2 7 Claim Allocation Need Available P1

52、 8 4 4 0 P2 6 6 0 P3 9 2 766死锁避免方法的限制死锁避免方法的限制n必须事先声明每个进程请求的最大资源必须事先声明每个进程请求的最大资源数数n考虑的进程必须是无关的，即进程之间考虑的进程必须是无关的，即进程之间不存在同步关系不存在同步关系n分配的资源数目必须是固定的分配的资源数目必须是固定的n在占有资源时，进程不能退出在占有资源时，进程不能退出67堵车是不可避免的？怎么办？堵车是不可避免的？怎么办？交警来疏通交警来疏通68死锁检测死锁检测 (Deadlock Detection)n不限制资源访问或约束进程的行为不限制资源访问或约束进程的行为n只要系统资源能满足进程的请

53、求就立即只要系统资源能满足进程的请求就立即满足满足n操作系统定期执行一个算法（死锁检测操作系统定期执行一个算法（死锁检测算法），检测当前系统是否满足了循环算法），检测当前系统是否满足了循环等待的条件，即当前系统是不是出现死等待的条件，即当前系统是不是出现死锁锁n若出现死锁，则进行相应的恢复若出现死锁，则进行相应的恢复69死锁检测算法死锁检测算法算法主要思想：标记没有发生死锁的进程。算法主要思想：标记没有发生死锁的进程。Allocation矩阵表示当前状态下，进程分配资源的情况矩阵表示当前状态下，进程分配资源的情况 ；Available向量表示系统可用资源数。向量表示系统可用资源数。请求矩阵请求

54、矩阵Qij表示进程表示进程i请求的请求的j资源的数量。资源的数量。算法步骤如下：算法步骤如下：n标记在标记在Allocation矩阵中全为矩阵中全为0的进程。因为这些进的进程。因为这些进程没有占用任何的资源，肯定不会造成死锁程没有占用任何的资源，肯定不会造成死锁 。n初始化一个临时向量初始化一个临时向量W，W= Available。n查找下标查找下标 i，使得，使得QikWk。如果找不到，终止算法。如果找不到，终止算法。1.如果找到，则标记进程如果找到，则标记进程 i，并设置，并设置Wk= Wk+Aik. 返回返回步骤步骤3。当算法结束后存在未标记的进程，则每个未标当算法结束后存在未标记的进程，则每个未标记的进程都是死锁进程，系统处于死锁状态。记的进程都是死锁进程，系统处于死锁状态。70死锁检测算法示例死锁检测算法示例P1、P2进程未标