《OS10死锁1讲义教材》由会员分享，可在线阅读，更多相关《OS10死锁1讲义教材（38页珍藏版）》请在金锄头文库上搜索。
1、3.4 死锁问题(DEADLOCK) P103,3.4.1 概述 3.4.2 死锁的预防 3.4.3 死锁的避免 3.4.4 死锁的检测 3.4.5 死锁的解除,3.4.1 概述,死锁指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。,1. 死锁发生原因,（1）竞争资源 （2）进程推进顺序非法,(1) 竞争资源引起死锁,死锁发生：双方都等待对方去生成资源， 如次序：P1 P2,B.竞争临时性资源引起死锁,详见书 P104 图3-13,图3-14,从资源出发的箭头表示该资源已分配,如R1已分配给P1,从进程出发的箭头表示进程正在申请资源,如P1正申请R2,S1P
2、1:表示由P1产生的消息S1,即:S1隶属于P1,P1S2 表示由P1要求接收消息S2,S2是另一个进程产生的。,(2)进程推进顺序不当引起死锁,Process Q,Release A,Release B,Get A,Get B,Get A,Get B,Release A,Release B,Process P,deadlock inevitable,1,2,3,4,5,6,P105 图3-15,2. 死锁发生条件,死锁的发生必须具备下列4个必要条件： 互斥：任一时刻只允许一个进程使用资源 请求和保持：进程在请求其余资源时，不主动释放已经占用的资源 非剥夺：进程已经占用的资源，不会被强制剥夺
3、环路等待：环路中的每一条边是进程在请求另一进程已经占有的资源。,3. 处理死锁的基本方法,预防死锁：破坏四个必要条件中的一个或几个条件； 易于实现，但会导致资源利用率和系统吞吐量降低 避免死锁：用某种方法在资源动态分配过程中，防止系统进入不安全状态。实现有难度，但可获得较高的资源利用率和系统吞吐量。 检测死锁：允许死锁发生。通过检测机构检测，然后采取措施，清除死锁。 解除死锁：与检测配套完成。常通过撤销或挂起一些进程实现。,3.4.2 死锁的预防,预防是采用某种策略，限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。,预防死锁的3种策略： 摒弃“请求和保持”条件：要求所有进程一
4、次性申请所需全部资源，保证不等待资源； 简单、易于实现，但： 降低了对资源的利用率，降低进程的并发程度； 进程延迟运行； 有可能无法预先知道所需资源；,对于已经保持了某些资源的进程，当他再提出新的资源要求而不能立即满足时，必须释放已保持的所有资源，待以后需要时重新申请。 摒弃“环路等待”条件： 把资源分类按顺序排列，所有进程对资源的请求必须严格按照资源序号递增的次序提出，保证不形成环路； 改善了资源利用率和系统吞吐量，但： 1. 限制了新设备类型的增加 2. 进程申请资源的顺序很难与系统为资源分配的序号总保持一致。 3. 限制了用户简单、自主的编程,-摒弃“不剥夺”条件：,3.4.3 死锁的避
5、免,用预防死锁的方法解决死锁问题，是通过增加了较强的限制条件来完成的，实现简单，但严重损害了系统的性能。 避免死锁来解决死锁问题，可施加较弱的条件，获得令人满意的系统性能。 避免死锁在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。,1.系统的安全状态（见书107）,如果系统能够按照某种顺序为每个进程分配其所需资源，直至最大需求，则当前状态为安全状态。否则 进程推进的顺序称为安全序列.,可为资源分配提供借鉴： 当有进程提出资源请求时，若分配后能够安全，则执行资源分配。否则不予分配，将进程阻
6、塞,安全状态举例,假定系统有三个进程P1,P2,P3, 12台磁带机。,1、当前是否为安全状态?,2、若进程2提出2个资源需求是否可以分配？,3、若进程3提出1个资源需求是否可以分配？,是， P2，P1，P3,2.利用银行家算法避免死锁,银行家算法（Dijkstra, 1965）问题,一个银行家把他的固定资金（capital）贷给若干顾客。只要不出现一个顾客借走所有资金后还不够，银行家的资金应是安全的。银行家需一个算法保证借出去的资金在有限时间内可收回。,具体步骤如下： 假定顾客分成若干次进行；并在第一次借款时，能说明他的最大借款额。 顾客的借款操作依次顺序进行，直到全部操作完成； 银行家对当
7、前顾客的借款操作进行判断，以确定其安全性（能否支持顾客借款，直到全部归还）； 安全时，贷款；否则，暂不贷款。,银行家算法的实现：,可利用资源向量Available: m个元素的数组； 最大需求矩阵Max：n m矩阵； 分配矩阵Allocation: nm矩阵； 需求矩阵Need:n m矩阵；,设系统中有n个进程， m种资源：,三个矩阵间的关系：Needi,j=Maxi,j-Allocationi,j,算法中用到的数据结构：,银行家算法 P109,假设用Requestij=k表示并发执行时进程i提出请求j类资源k个。系统按下述步骤进行检查： (1)如果RequestiNeedi则继续以下检查，否
8、则显示需求申请超出最大需求值的错误。 (2)如果RequestiAvailable则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。 (3)系统试探性的把要求的资源分配给进程i并修改有关数据结构的值： Available=Available-Requesti； Allocationi=Allocationi+Requesti； Needi=Needi-Requesti； (4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给进程i，以完成本次分配；否则将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,安全性算法:,安全性算法执行步骤如下： A
9、.初始化设置工作向量Workm表示系统可提供的各类资源数目，用以保护原数据结构有关值。Work = Available； 设置完成标志向量 Finishn。Finishi = false 表示进程i尚末完成，如值为true则表示进程i已完成(可以顺利推进)。 B.从进程集合n中找到一个能满足下述二个条件: Finishi = false和NecdiWork，如找到则执行步骤C，如找不到同时满足以上二条件的进程则执行步骤D。 C.当进程i获得资源后可顺利执行直到完成，并释放出分配给它的资源，表示如下： work = work+Allocationi ； Finishi=true ；转执行步骤B。
10、 D.如果所有的Finishitrue，则表示系统处于安全状态，否则系统处于不安全状态。,银行家算法例：P110,假定系统中有五个进程P0、P1、P2、P3、P4和三种类型资源A、B、C，每一种资源的数量分别为10、5、7。各进程的最大需求、T0时刻资源分配情况如下所示。,试问： 1.T0时刻是否安全？ 2.P1请求资源Request1(1,0,2)是否允许？ 3.P4请求资源Request4(3,3,0)是否允许？ 4.P0请求资源Request(0,2,0)是否允许？,T0时刻的资源分配表,1、T0时刻的安全性,1,3 3 2,5 3 2,2,5 3 2,7 4 3,3,7 4 3,7 5
11、 3,true,true,true,4,7 5 3,10 5 5,true,5,10 5 5,10 5 7,true,P1 P3 P0 P2 P4,T0时刻的资源分配表,1、T0时刻的安全性（2）,P1发出请求向量Request(1,0,2),系统按银行家算法进行检查：,2、 P1请求资源,发现可以找到一个安全序列P1，P3，P4，P0，P2，因此系统是安全的，可以立即将P1所申请的资源分配给它。,（1）Request1(1,0,2)Need(1,2,2) （2）Request1(1,0,2) Available(3,3,2) （3）系统假定可为P1分配资源，并修改Available,Allo
12、cation1和Need向量。 （4）检查此时系统是否安全。,P4发出请求向量Request4(3,3,0),系统按银行家算法进行检查： （1）Request4(3,3,0)Need4(4,3,1) （2）Request4(3,3,0)Available(2,3,0),让P4等待。,3、P4请求资源,P0发出请求向量Request0(0,2,0),系统按银行家算法进行检查：,4、P0请求资源,（1）Request0(0,2,0)Need0(7,4,3) （2）Request0(0,2,0) Available(2,3,0) （3）系统暂时假定可为P0分配资源，并修改有关数据，下表所示。,（4）
13、进行安全性检查，发现可用资源Available(2,1,0)已不能满足任何进程的需要，故进程进入不安全状态，此时系统不分配资源给该进程。,练 习,如果将P0的请求(0,2,0)改为(0,1,0),系统能否讲资源分配给它？,3.4.4 死锁的检测,进行死锁检测：必须 1.保存资源的请求和分配信息; 2.利用某种算法对这些信息加以检查，以判断是否存在死锁。,资源分配图(resource allocation graph)用于描述系统的死锁,是一个有向图G； 结点:为资源或进程， 边: 从资源R到进程P的边表示R已分配给P， 从进程P到资源R的边表示P正因请求R而处于等待状态。 有向图的循环是死锁存
14、在的必要条件,有环有死锁,有环无死锁,2.死锁定理,当且仅当S状态的资源分配图是不可完全简化的，称S为死锁状态.该充分条件称为死锁定理。 其中的有边进程就是死锁进程。,死锁检测的计算机实现 P113,1、教材P113方法； 2、通常的方法是程序员的经验，如UNIX系统中，可考察进程的运行时间。在UNIX系统中有命令PS可显示进程占用CPU的时间，若发现有一组进程在一段时间内没有占用CPU，就认为这类进程出现了死锁。,3.4.5 死锁的解除,重新启动 进程回退 回滚每个死锁进程到前一个检查点，重新执行每个进程。 撤销死锁进程 全部撤销； 按照某种原则逐个选择死锁进程进行撤消，直到解除系统死锁 选
15、择原则：一般选择系统付出代价最小的进程，即： 花费处理机的时间最少、输出最少、估计未执行部分最多、已分配的资源量最少、优先级最低 剥夺资源 按照某种原则逐个剥夺进程资源，直到解除死锁。,课后练习,系统可供用户使用的内存共150MB，目前分配给3个进程的数量如下表所示。这时，第个4进程产生，它最终需要内存60MB，目前的申请数为25MB。应用关于死锁问题的银行家算法，回答是否可以分配给第4个进程25MB内存，为什么？,-,T0时刻的资源分配表,资源分配图的简化,找一个既不阻塞又非独立的进程节点（说明可以顺利执行直至释放出资源），消去请求边和分配边。 再把相应的资源分配给一个等待该资源的进程，继续消去，以此类推 在进行一系列化简后，若能消去图中所有的边，即所有进程都成为孤立的点，称该图是可以完全简化的；否则是不可完全简化的。 对于不可完全简化的资源图，不同的简化顺序，将得到相同的不可简化图。,资源分配图的简化例：,资源分配图的简化例：不可完全简化,
