操作系统原理方敏死锁课件

1、 第四章 死 锁操作系统课程组 第四章 死 锁操作系统课程组内容回顾UNIX进程模型进程结构：proc结构，数据段，正文段。进程状态调度算法：动态优先级调度算法。进程创建与终止：fork(), exit()。进程通信：pipe; sleep, wakeup; wait, exit。死锁2内容回顾UNIX进程模型2一、什么是死锁？死锁(deadlock)定义：在多道程序中，由于多个并发进程共享系统的资源，如果使用不当可能会造成一种僵局，即当某个进程提出资源的使用请求后，使得系统中一些进程处于无休止的阻塞状态，在无外力的作用下，这些进程将无法继续进行下去，这就是死锁。3一、什么是死锁？死锁(dea

2、dlock)定义：在多道程序中，二、为什么会产生死锁？产生死锁的环境多道程序设计技术多个并发进程资源共享(独占)没有外力可以借助使用不当造成的死锁示例P、V操作不当进程T1:while(true) 启动读卡机; 送卡片到缓冲区; P(S2); V(S1);进程T2:while(true) P(S1); 从缓冲区取卡片; V(S2);semaphore s1,s2;s1=0; s2 = 0;4二、为什么会产生死锁？产生死锁的环境进程T1:进程T2:se二、为什么会产生死锁？进程申请顺序不当同类资源分配不当123456进程1进程2进程312345675二、为什么会产生死锁？进程申请顺序不当1234

3、56进程1进程二、为什么会产生死锁？进程通信不当资源的类型独占资源 VS 非独占资源永久性资源 VS 临时性资源独占资源分类可剥夺式资源不可剥夺式资源T1T3T2S3S1S26二、为什么会产生死锁？进程通信不当T1T3T2S3S1S26二、为什么会产生死锁？必要条件(Coffman 1971年指出)资源互斥使用(资源独占)非剥夺控制(不可强占)零散请求循环等待破坏其中任何一个条件，就可一防止死锁的发生。7二、为什么会产生死锁？必要条件(Coffman 1971年指三、如何解决死锁问题？死锁的危害轻则系统资源利用率严重下降，重则系统崩溃。解决死锁的策略置之不理法鸵鸟政策优点：简单，简化系统设计，

4、节约成本。缺点：安全性欠佳。8三、如何解决死锁问题？死锁的危害优点：简单，简化系统设计，节三、如何解决死锁问题？积极防御法不让死锁发生思想：以积极的遏制为出发点。手段：破坏产生死锁的必要条件。分类：静态策略：进程创建时就由系统分配了所有需要的资源，然后才执行，并且以后没有资源申请要求。缺点：系统效率低，并发性下降，资源浪费严重。动态策略：执行时动态改变资源分配策略。缺点：实现复杂。优点：灵活，资源利用率高。9三、如何解决死锁问题？积极防御法不让死锁发生9三、如何解决死锁问题？事后处理法让死锁发生，事后处理提出原因：预防策略虽然可以杜绝死锁发生，但是它提出的策略可能会或多或少影响到系统效率。思想

5、：可以容忍死锁的发生，事后处理。优点：灵活，效率高。10三、如何解决死锁问题？事后处理法让死锁发生，事后处理10四、死锁的预防破坏死锁产生的必要条件破坏互斥条件SPOOLingP1P2P3执行上无先后顺序剩余票数n=3P1P2P3执行上有先后顺序局限：破坏“互斥”比较困难，而且对很多资源行不通。11四、死锁的预防破坏死锁产生的必要条件SPOOLingP1P2四、死锁的预防破坏不可剥夺条件思想：允许进程还未执行完成时释放已经占有的资源。方法:已经占有部分资源，还需要资源，如果得不到满足，则释放自己所占有的所有资源，以后再申请。正在使用资源，有高优先级的进程请求相同资源，则低优先级进程放弃资源。局

6、限：实现困难，为了恢复现场需要耗费很多时间和空间。因此只适合类似CPU、存储器这样的资源。12四、死锁的预防破坏不可剥夺条件12四、死锁的预防破坏零散请求条件常常采用静态策略：进程创建时就由系统分配了所有需要的资源，然后才执行，并且以后没有资源申请要求，进程执行完后，释放资源。缺点：系统效率低，并发性下降，资源浪费严重。破坏循环等待条件方法：给资源编号，进程必须按序申请资源。P1P5124712345673334567P1P5P2P3P413四、死锁的预防破坏零散请求条件P1P512471234567四、死锁的预防局限：资源编号困难：尽管资源的按序分配方法消除了死锁的问题，但给资源编号很困难，

7、很难满足每一个进程的要求。资源的编号很难和进程申请资源的顺序一致：资源顺序分配法是按资源编号申请资源，可能与实际使用资源的顺序不一致，使得一些先申请的资源因暂时不用，而长时间闲置，降低了系统资源利用率。结论死锁的预防是以破坏死锁产生的必要条件为基本方法，从而防止死锁发生的。其中由于对资源的申请加上了诸多的限制，因此这种策略虽有一定的效果，但其资源的利用率和效率比较低，很难令人满意。14四、死锁的预防局限：14五、死锁的避免思想允许死锁产生的条件存在，但通过动态的、明智的选择在分配资源之前，系统判断假若满足进程的要求是否会发生死锁，如果会，资源就不予分配，从而确保永远不会到达死锁点，避免死锁的发

8、生。优点：比预防策略更为灵活实用，允许更多的并发，其资源利用率和效率也更高。15五、死锁的避免思想15五、死锁的避免系统的状态安全状态不安全状态死锁安全状态：指在某个时刻，当多个进程动态的申请资源时，如果存在一种顺序，使得系统按照这种顺序逐次地为每个进程分配所需资源后每个进程都可以在最终得到最大需求量后，依次顺利地完成。避免死锁的关键就是：让系统在动态分配资源的过程中，不要进入不安全状态。16五、死锁的避免系统的状态安全状态不安全状态死锁安全状态：指在五、死锁的避免单银行家算法（Bankers Algorithm）1965年由Dijkstra为T.H.E系统设计基本思想：借用了银行借贷系统的分

9、配策略。基于这样一些规则：客户银行1、第一次申请需要声明最大资金需求量2、满足最大需求后要及时归还资金3、客户申请的贷款数量不超过它自己拥有的 最大值时，银行要尽量满足客户需求进程资源操作系统17五、死锁的避免单银行家算法（Bankers Algorit客户abcd举例：假设一个银行拥有资金数量为10（单位省略），现在有4个客户a, b, c, d要来贷款，所需最大资金需求量为8，5，6，7，为方便期间我们用图形表示如下。已用资金最大需求仍需资金五、死锁的避免088055066077银行剩余资金10初始状态客户已用资金最大需求仍需资金abcd187253165275银行剩余资金4状态1Q：如何

10、分配才能保证银行资金能够顺利周转？18客户abcd举例：假设一个银行拥有资金数量为10（单位省略）五、死锁的避免客户已用资金最大需求仍需资金abcd187550165275银行剩余资金1状态2客户已用资金最大需求仍需资金abcd187165275银行剩余资金6状态3客户已用资金最大需求仍需资金abcd187660275银行剩余资金1状态4客户已用资金最大需求仍需资金abcd187275银行剩余资金7状态519五、死锁的避免客户已用资金最大需求仍需资金abcd18755五、死锁的避免客户已用资金最大需求仍需资金abcd880275银行剩余资金0状态6客户已用资金最大需求仍需资金abcd275银行

11、剩余资金8状态7客户已用资金最大需求仍需资金abcd770银行剩余资金3状态8分配策略：bcad20五、死锁的避免客户已用资金最大需求仍需资金abcd880五、死锁的避免算法流程21五、死锁的避免算法流程21五、死锁的避免以上讨论的是单银行家算法只涉及到了一种资源，实际中资源的种类是多样的，一个进程往往需要申请多个资源才能完成工作。解决这一问题需要使用多银行家算法。22五、死锁的避免以上讨论的是单银行家算法只涉及到了一种资源五、死锁的避免多项资源银行家算法举例：系统中有以下资源：5台打印机，7个手写板，8台扫描仪，9个读卡器，共有5个进程T1、T2、T3、T4、T5共享这些资源。各进程所需最大

12、资源量和当前各进程请求资源情况如下：各进程所需最大资源量当前各进程请求资源23五、死锁的避免多项资源银行家算法各进程所需最大资源量当前各进1、sum向量：表示系统资源总量sum = （5，7，8，9）2、allocation向量：表示当前系统已分配资源allocation =（3，5，7，7） 3、available向量：表示系统剩余资源available = sum allocation =（2，2，1，2） 4、claim(i)向量：表示第i个进程还需申请资源数claim(i) = sum(i) allocation(i)五、死锁的避免为方面讨论，我们用向量来表示资源分配及占用情况：sum

13、allocationclaim(i)241、sum向量：表示系统资源总量五、死锁的避免为方面讨论，我五、死锁的避免步骤：比较claim(i)和available向量，寻找满足下列关系的进程claim(i) availableavailable = （2，2，1，2）allocationavailable = （2，5，5，2）25五、死锁的避免步骤：available = （2，2，1，2五、死锁的避免available = （2，6，7，3）allocationavailable = （3，7，7，5）allocation26五、死锁的避免available = （2，6，7，3）al五、死

14、锁的避免available = （5，7，7，6）allocationallocationavailable = （5，7，8，9）27五、死锁的避免available = （5，7，7，6）al五、死锁的避免28五、死锁的避免28六、死锁的检测和解除死锁的检测检测工具资源分配图定义：是描述进程申请资源和资源分配情况的关系模型图。表示系统中某个时刻进程对资源的申请和占有情况。示例：规则：（1）圆表示一个进程；（2）方块表示一个资源类，其中的圆点表示该类型资源中的单个资源；（3）从资源指向进程的箭头表示资源被分配给了这个进程；（4）从进程指向资源的箭头表示进程申请一个这类资源；29六、死锁的检测

15、和解除死锁的检测规则：29六、死锁的检测和解除一张合理的资源分配图应当满足如下条件设资源类Rj有资源Wj个，用|(Rj, Pi)|表示Rj分配给进程Pi的资源个数；用|(Pi, Rj)|表示进程Pi申请Rj资源的资源个数。1、资源Rj分配给各进程的资源数目不能大于Wj，即：2、任何一个进程Pi对某类资源Rj的申请量和已分配数量之和，不应大于该类资源的总数Wj，即：30六、死锁的检测和解除一张合理的资源分配图应当满足如下条件1、六、死锁的检测和解除检测方法化简算法资源分配图中的所有进程如果都能化简成孤立结点，则这个资源图就是可完全化简的（completely reducible）；反之，就是不可

16、完全化简的（irrreducible）。死锁定理：如果一个系统状态为死锁状态，当且仅当资源分配图是不可完全化简的。也即，如果资源图中所有的进程都成为孤立结点，则系统不会死锁；否则系统状态为死锁状态。31六、死锁的检测和解除检测方法化简算法资源分配图中的所有进六、死锁的检测和解除举例结论：系统不会发生死锁。32六、死锁的检测和解除举例结论：系统不会发生死锁。32六、死锁的检测和解除临时资源的死锁检测临时性资源：即可消耗的资源。如信号、消息、邮件等。特点：没有固定数目；不需要释放。一般的资源分配图无法清楚的描述33六、死锁的检测和解除临时资源的死锁检测一般的资源分配图33六、死锁的检测和解除临时性

17、资源分配的表述方式重定义的资源分配图定义：圆表示一个进程；方块表示一个资源类，其中的圆点表示该类型资源中的单个资源；由资源类指向进程的箭头表示该进程产生这种资源，一个箭头可表示产生一到多个资源，每个资源类至少有一个生产者进程；由进程指向资源的箭头表示该进程申请这种资源，一个箭头只表示申请一个资源。34六、死锁的检测和解除临时性资源分配的表述方式重定义的资源六、死锁的检测和解除死锁判断标准分析：一个进程死锁意味着永久被阻塞。对于临时性资源来讲，它有生产者，生产者会源源不断的生产资源，因此只要生产者进程不被阻塞，可以认为资源最终一定是充分的，可以满足各消费进程的需要。需要的资源可以满足则进程一定不

18、会死锁。结论：判断系统是否死锁的关键在于判断生产者进程的状态，若生产者进程不被阻塞，则可以认为它总会生产出该类资源，也就是说，某类资源的生产者进程只要不被阻塞，申请这类资源的所有申请者进程都可以得到满足。35六、死锁的检测和解除死锁判断标准35六、死锁的检测和解除检测方法化简方法：从那些没有阻塞的进程入手，删除那些没有阻塞的进程的请求边，并使资源类中资源数（图中黑点的数目）减1。重复以上步骤直至：a. 图中所有的请求边都已经删除，则不会死锁 b. 图中仍然存在请求边但无法再化简，系统死锁。36六、死锁的检测和解除检测方法化简36六、死锁的检测和解除死锁的解除重新启动：这是一种常用但比较粗暴的方

19、法，虽然实现简单，但会使之前的工作全部白费，造成很大的损失和浪费。撤消进程：死锁发生时，系统撤消造成死锁的进程，解除死锁。一次性撤消所有的死锁进程。损失较大。逐个撤消，分别收回资源。具体做法：系统可以先撤消那些优先级低的、已占有资源少或已运行时间短的、还需运行时间较长的进程，尽量减少系统的损失。 37六、死锁的检测和解除死锁的解除37六、死锁的检测和解除剥夺资源：死锁时，系统保留死锁进程，只剥夺死锁进程占有的资源，直到解除死锁。选择被剥夺资源进程的方法和选择被撤消进程相同。进程回退：死锁时，系统可以根据保留的历史信息，让死锁的进程从当前状态向后退回到某种状态，直到死锁解除。实现方法：可以通过结

20、合检查点或回退（checkpoint/Rollback）机制实现。进程某一时刻的瞬间状态叫做检查点，可以定期设置检查点。系统保存所有的检查点。一旦系统检查到有某个进程卷入了死锁，该进程就会被终止，剥夺它占有的所有资源。然后，系统查看保存的检查点信息，重新建立该进程的状态，从上次检查点的位置重新执行。目前发展已比较成熟，广泛用于DBMS中。38六、死锁的检测和解除剥夺资源：死锁时，系统保留死锁进程，只剥六、死锁的检测和解除死锁检测举例例1：以下有两个资源分配图，图a表示的是永久性资源，图b表示临时性资源，请分别化简并说明是否会发生死锁。(a)(b)39六、死锁的检测和解除死锁检测举例(a)(b)39六、死锁的检测和解除(a)Step1.检测有无环路Setp2.检测环路中每个资源类中是否只有一个资源Step3.在环路中查找非阻塞也非独立的进程结论：此资源分配图无法化简，因此必定死锁。40六、死锁的检测和解除(a)Step1.检测有无环路Setp2六、死锁的检测和解除(b)查找非阻塞进程结论：会发生死锁41六、死锁的检测和解除(b)查找非阻塞进程结论：会发生死锁41六、死锁的检测和解除例2：某