《操作系统第五章死锁与饥饿.ppt

第五章 死锁与饥饿 死锁的概念 死锁的条件 死锁的处理 资源分配图 死锁的预防 死锁的避免 死锁的发现 死锁的恢复 饥饿与活锁 第五章 死锁与饥饿 一个进程需要使用独占型资源必须有一定的次序： 申请资源 使用资源 释放资源 1968年Havender在评论OS/360操作系统时说：“原先多任务的概念是让多个任务不加限制的竞争资源，……但是随着系统的发展，很多任务被锁在系统中了。” 1971年Lynch说：“1962年我们设计Exec2系统时并没有认识到死锁的问题，系统中也没有任何防范措施，结果现在一些程序中已被锁在系统中了。” 死锁产生的原因和必要条件 5.1 死锁产生的原因 5.1 死锁产生的原因 3、同类资源分配不当引起死锁 若系统中有m个资源被n个进程共享，当每个进程都要求k个资源。而mn*k时，即资源数小于进程所需要的总数时，如果分配不得当就可能引起死锁。 例3，m=5,n=5,k=2，采用的分配策略是为每个进程轮流分配。 5.1 死锁产生的原因 4、进程通讯引起死锁 在进程通讯时使用的信件可以看作是一种临时性资源，如果对信件的发送和接收不加限制的话，则可能引起死锁 例4：进程p1等待进程p3的信件s3来到后再向进程p2发送信件s1；p2又要等待p1信件来到后再向p3发送信件s2；而p3也要等待p2的信件s2来到后才能发出信件s3 5.2 死锁定义 一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁。 5.3 死锁的条件 Coffman条件（必要条件） 资源独占（mutual exclusion） 又称为互斥条件，一个资源在同一时刻只能分配给一个进程。任一时刻一个资源仅为一个进程独占，若另一个进程请求一个已被占用的资源时，它被置成等待状态，直到占用者释放资源。 不可剥夺（non preemption） 任一进程不能从另一进程那里抢夺资源，即已被占用的资源，只能由占用进程自己来释放。 保持申请（hold-while-applying） 又叫占有和等待条件，一个进程请求资源得不到满足而等待时，不释放已占有的资源。 循环等待（circular wait） 又叫环路等待条件，存在一个循环等待链，其中，每一个进程分别等待它前一个进程所持有的资源，造成永远等待。 破坏上述任意一个条件可以消除死锁。 5.4 死锁的处理 死锁预防（deadlock prevention）-静态 通过设置某些限制条件，去破坏产生死锁的4个必要条件中的一个或几个条件，来防止死锁发生。 死锁避免（deadlock avoidance）--动态 不需事先采取各种限制措施去破坏产生死锁的必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。 5.4 死锁的处理 死锁检测（deadlock detection） 这种方法预先并不采取任何限制措施，也不检查系统是否已经进入不安全区，此法允许系统在运行过程中发生死锁。但可通过系统设置的检测机构，及时地检测出死锁的发生，并精确的确定与死锁有关的进程和资源；然后采取适当的措施，从系统中将已发生的死锁清除掉。 死锁恢复（deadlock recovery） 这是与检测死锁相配套的一种措施，用于将进程从死锁状态下解脱出来，常用的实施方法是撤销或挂起一些进程，以便收回一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态以继续运行。 5.5 资源分配图 5.5 资源分配图 例子（无环路，无死锁） 例子（有环路，有死锁） 例子（有环路，无死锁） “死锁检测”程序 如果资源分配图中无环路，则此时系统没有发生死锁 如果资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程 如果资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件，未必系统一定就会发生死锁。看资源分配图能否化简。 5.5.2 资源分配图的约简 可以通过对资源分配图的约简，来判断系统是否处于死锁状态．资源分配图中的约简方法如下： (1)寻找一个非孤立且没有请求边的进程结点pi,若无算法结束； (2)去除所有pi的分配边使pi成为一个孤立结点； (3)寻找所有请求边均可满足的进程pj,将pj的请求边全部改为分配边； (4)转步骤(1)． 若算法结束时，所有结点均为孤点，则称资源分配图是可以完全约简的，否则称为不可完全约简的．文献已经证明，系统处于死锁状态的充分必要条件是资源分配图不可完全约简．这一结论称为死锁定理． 定理：S为死锁状态的充分必要条件是S的资源分配图不可完全约简。 判断下列资源分配图所标示的状态是否为死锁 化简下面的资源分配图，并利用死