学习操作系统ch7deadlock os

1、第7章 死锁（Deadlock）主讲教师: 庞俊彪 邮件：junbiao_办公室:信息楼 南 412内容回顾：并发进程带来临界区问题进入区退出区临界区剩余区1.临界区(critical section)：一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构进行操作。2.进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应正在访问临界区标志3.退出区(exit section)：用于将正在访问临界区标志清除。4.剩余区(remainder section)：代码中的其余部分。内容回顾：临界区问题带来信号量技术/

2、表示申请一个资源表示申请一个资源/表示没有空闲资源表示没有空闲资源 / /调用进程进入等待队列调用进程进入等待队列s.queues.queue; ; / / 阻塞调用进程阻塞调用进程; ;；/表示释放一个资源表示释放一个资源；/表示有进程处于阻塞状态；表示有进程处于阻塞状态； /从等待队列从等待队列s.queues.queue中取出一个进程中取出一个进程P;P; / /进程进程P P进入就绪队列进入就绪队列; ;是否信号量技术就能解决所有的进程的 所有问题？本章教学目标 死锁的概念 死锁的特征 死锁的预防 死锁的避免 死锁的检测 死锁的恢复死锁1.1 死锁的产生死锁的产生原因原因1.2 死锁的

3、死锁的特征特征1.3 死锁的死锁的预防预防1.4 死锁的死锁的避免避免1.5 死锁的死锁的检测检测1.6 死锁的死锁的恢复恢复死锁死锁1.1 死锁的产生死锁的产生原因原因1.2 死锁的特征1.3 死锁的预防1.4 死锁的避免1.5 死锁的检测1.6 死锁的恢复生产者 消费者的信号量解法n不合理的信号量使用会导致Consumer() P(mutex); P(fullBuffers); item = Dequeue();V(mutex);V(emptyBuffers);Producer(item) P(mutex); P(emptyBuffers);Enqueue(item);V(mutex);V

4、(fullBuffers); 当mutex= 1, emptyBuffers = 0时， 生产者占有mutex信号量后又阻塞在emptyBuffers信号量上。而消费者阻塞在mutex上，不能唤醒生产者最后谁也没法执行没有先查看资源在进行互斥操作！死锁现象n看一个实际的例子n现在分析这个例子争用了资源: 道路A占有道路1，又要请求道路2，B占有DABC12341A占有2B等待3D4C形成了无限等待形成死锁死锁概念(Deadlock)n死锁: 多个进程因循环等待资源而造成无法执行的现象。资源2资源1进程B进程A等待等待占有占有死锁会造成进程无法执行死锁会造成系统资源的极大浪费(资源没法释放)消除

5、死锁之首应先分析死锁!死锁死锁1.1 死锁的产生原因1.2 死锁的死锁的特征特征1.3 死锁的预防1.4 死锁的避免1.5 死锁的检测1.6 死锁的恢复从资源的角度分析多个进程因等待资源才造成死锁n资源: 进程在完成其任务过程所需要的所有对象CPU，内存，磁盘块，外设，文件，信号量等n显然有些资源不会造成死锁，而有些会只读文件是不会造成进程等待的，也就不会死锁打印机一次只能让一个进程使用，就会造成死锁称为互斥访问资源显然，资源互斥访问是死锁的必要条件可重用资源与可消费资源 可重用资源一次只能供一个进程安全地使用, 且不会由于使用而耗尽例子: CPU、 I/O通道、主存和辅存、 设备、文件、数据

6、库、信号量等数据结构 可消费资源可以创建并且可以销毁的资源数目没有限制, 当一个进程得到一个可消费资源时, 这个资源就不再存在了例子: 中断、信号、 消息、 I/O缓冲区中的信息例: 两个进程竞争可重用资源导致死锁 两个进程：一个访问磁盘文件D，一个访问磁带设备T 如果执行序列为:P0、P1、q0、q1、P2、q2，则发生死锁过桥的例子 每次只有一个方向通行 桥的每一头都可以看成资源 如果死锁发生，它可以由一辆车返回而解决，（抢占资源并回退） 如果死锁发生，可能很多车都不得不返回 有可能产生饥饿 （注意饥饿与死锁的区别 饥饿一般不占有资源，死锁进程一定占有资源）死锁并不总是发生死锁并不总是发生

7、n一简单实例一简单实例进程进程 Ax.P(); y.P(); y.V(); x.V();进程进程 By.P(); x.P(); x.V(); y.V();考虑序列：考虑序列：A:x.P()，B:y.P()，B:x.P()，A:y.P()形成循环等待，出现死锁形成循环等待，出现死锁考虑序列：考虑序列：A:x.P()，A:y.P()，B:y.P()，B:x.P()并不形成死锁并不形成死锁如何描述这种等待关系如何描述这种等待关系?资源请求需要形成环路等待才死锁资源请求需要形成环路等待才死锁资源分配图n资源分配图模型一个进程集合P1,P2,Pn记号R1R2P1P2一资源类型集合R1,R2,Rm资源类型

8、Ri有Wi个实例资源请求边：有向边PiRj资源分配边：有向边RiPkR2P1P2资源分配图实例1A占有2B等待3D4C1ABCD234存在环路: 1-A-2-B-3-C-4-D-1P1P2P3R2R1P4存在环路: P1-R1-P3-R2-P1但并不一定死锁。如P4释放资源R2后，仍可继续执行资源进程请求/分配总结：死锁的4个必要条件n互斥使用(Mutual exclusion)资源的固有特性，如道口n不可抢占(No preemption)资源只能自愿放弃，如车开走以后n请求和保持(Hold and wait)进程必须占有资源，再去申请n循环等待(Circular wait)在资源分配图中存在

9、一个环路1ABCD234死锁死锁1.1 死锁的产生原因1.2 死锁的特征1.3 死锁的死锁的预防预防1.4 死锁的避免1.5 死锁的检测1.6 死锁的恢复死锁处理方法概述n死锁预防破坏死锁的必要条件“no smoking”，预防火灾n死锁避免检测每个资源请求，如果造成死锁就拒绝检测到煤气超标时，自动切断电源n死锁检测+恢复检测到死锁出现时，剥夺一些进程的资源发现火灾时，立刻拿起灭火器n死锁忽略就好像没有出现死锁一样在太阳上可以对火灾全然不顾死锁预防: 破除死锁的必要条件n破坏互斥使用资源的固有特性，通常无法破除，如信号量n破除不可抢占如果一个进程占有资源并申请另一个不能立即分配的资源，那么已分

10、配资源就被抢占如果申请的资源得到满足，则被抢占的所有资源需一次性分配给该进程只对状态能保存和恢复的资源(如CPU，内存空间)有效，对打印机等外设不适用死锁预防: 破除死锁的必要条件n破除请求和保持在进程执行前，一次性申请所有需要的资源缺点1: 需要预知未来，编程困难缺点2: 许多资源分配后很长时间后才使用，资源利用率低死锁预防: 破除死锁的必要条件n破除循环等待对资源类型进行排序，资源申请必须按序进行缺点: 如果编程时就需考虑，用户会觉得很别扭；否则需要释放某些资源(申请序号小的资源)，进程可能会无法执行所有的进程必须先申请磁盘驱动，再申请打印机，再.如日常交通中的单行道总之，破除死锁的必要条

11、件会引入不合理因素，实际中很少使用。死锁死锁1.1 死锁的产生原因1.2 死锁的特征1.3 死锁的预防1.4 死锁的死锁的避免避免1.5 死锁的检测1.6 死锁的恢复死锁避免思想: 判断此次请求是否造成死锁不死锁的安全状态就成了问题的核心!安全状态定义:系统能按某种顺序, 如, 为每个进程分配所需资源, 直到最大需求, 使每个进程都可顺序完成, 称系统处于安全状态。（安全状态一定是没有死锁发生的，)都能执行完成当然就不死锁关系：u只要系统处于安全状态, 必定不会进入死锁状态；死锁状态是不安全状态u不安全状态不一定是死锁状态（不安全状态可能导致死锁）；不安全状态: 系统中不存在安全序列。不安全状

12、态不一定导致死锁。死锁避免（Deadlock Avoidance） 不需象死锁预防那样，事先采取限制措施破坏产生死锁的必要条件; 在资源的动态分配过程中, 采用某种策略防止系统进入不安全状态, 从而避免发生死锁 定义：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配如果一个新的进程的资源请求会导致死锁, 则拒绝启动这个进程如果满足一个进程新提出的一项资源请求会导致死锁, 则拒绝分配资源给这个进程系统的安全状态 安全序列: 一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它

13、以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和，系统处于安全状态。 安全序列可以不唯一!如何找到不安全序列问题：如何找到安全序列？死锁避免（安全序列）之银行家算法n安全序列P1，Pn应该满足的性质Pi(1in)需要资源剩余资源+分配给Pj(1ji)资源Banker()int n,m; /系统中进程总数和资源类总数int Available1.m; /每种资源剩余数量int Allocation1.n,1.m; /当前给分配给每个进程的各种资源数量int Need1.n,1.m; /当前每个进程还需分配的各种资源数量int Work1.m; /当前可分配

14、的资源bool Finish 1.n; /进程是否结束Int MaxI,j; /定义每个进程最大需求死锁避免（安全序列）之银行家算法Pi(1in)需要资源剩余资源+分配给Pj(1ji)资源（进程Pj在进程Pi之前运行）Work = Available; Finish1.n = false;/初始化 while(true) for(i=1;i=n;i+) if(Finishi=false & Needi,jWorkj)/还有资源可分配 Workj = Workj + Allocationi,j;/workj已分配的资源 Finishi = true; break; else goto N

15、OSOURCE; / for (i=1,)NOSOURCE: for(i=1;i=n;i+) if(Finishi=false)return “deadlock”;T(n)=O(mn2)剩余资源+分配给Pj(1ji)资源=资源数死锁避免之银行家算法实例 Allocation Max Need AvailableA B C A B C A B C A B C P00 1 0 7 4 3 7 3 3 3 3 2 P12 0 0 3 2 2 1 2 2 P23 0 2 9 0 2 6 0 0 P32 1 1 2 2 2 0 1 1 P40 0 2 4 3 3 4 3 1n当前状态当前状态:Work=

16、3 3 2安全序列是安全序列是Work=5 3 2P1Work=7 4 3P3Work=7 4 5P4Work=10 4 7P2Work=10 5 7P0初始条件初始条件 A B C : 10 5 7 死锁避免之死锁避免之资源请求算法资源请求算法extern Banker();int Request1.m; /进程进程Pi的资源申请的资源申请if(RequestNeedi) return “error”;if(RequestAvailable) sleep();/挂起进程挂起进程PiAvailable=Available-Request;Allocationi=Allocationi+Requ

17、est;Needi=Needi-Request;if(Banker() = “deadlock”) 拒绝拒绝Request;死锁避免小结 优点比死锁预防限制少无死锁检测方法中的资源剥夺, 进程重启 缺点 必须事先声明每个进程请求的最大资源考虑的进程必须是无关的, 也就是说, 它们执行的顺序没有任何同步要求的限制进程的数量保持固定不变，且分配的资源数目必须是固定的在占有资源时, 进程不能退出死锁死锁1.1 死锁的产生原因1.2 死锁的特征1.3 死锁的预防1.4 死锁的避免1.5 死锁的死锁的检测检测1.6 死锁的恢复死锁检测+恢复: 死锁检测如果一个系统既不采用死锁预防算法也不采用死锁避免算法

18、，那么可能会出现死锁。因此，系统应该提供：1. 一个用来检查系统状态从而确定是否出现了死锁的死锁检测算法；2. 一个用来从死锁状态中恢复的算法；死锁检测+恢复: 死锁检测 死锁检测没有任何预先限制措施资源分配时不检查系统是否会进入不安全状态,被请求的资源都被授予给进程系统可能出现死锁周期性检测是否出现死锁（执行检测算法） 检测时机在每个资源请求时都进行：尽早地检测，其缺点是系统的开销大（CPU） 定时检测 系统资源利用率下降时检测死锁死锁检测+恢复: 死锁检测n基本原因: 每次申请都执行O(mn2)，效率低。发现问题再处理，不要做“杞人忧天”的事情定时检测或者是发现资源利用率低时检测 Fini

19、sh1.n = false; if(Allocationi = 0) Finishi=true; ./和Banker算法完全一样 for(i=1;i=n;i+) if(Finishi=false) deadlock = deadlock + i;死锁死锁1.1 死锁的产生原因1.2 死锁的特征1.3 死锁的预防1.4 死锁的避免1.5 死锁的检测1.6 死锁的死锁的恢复恢复死锁检测+恢复: 死锁恢复n终止进程 选谁终止?优先级? 占用资源多的? n剥夺资源 进程需要滚回(rollback)滚回点的选取? 如何滚回? 死锁的恢复（Deadlock Recovery）一旦检测到死锁，就需要某种策略以恢复死锁方法1：进程