*3.5死锁资源死锁的定义产生死锁的原因产生死锁的必要条件处理死锁的基本方法*二、死锁的定义计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象（僵局），如无外力作用，这些进程将永远不能再向前推进。死锁Deadlock：系统中存在一组进程(两个或多个进程),它们中的每一个进程都占用了某种资源而又都在等待其中另一进程所占用的资源,这种等待永远不能结束,则说系统出现了“死锁”,或说这组进程处于死锁状态。陷入死锁状态的进程称为死锁进程，所占用的资源或者需要它们进行某种合作的其它进程就会相继陷入死锁，最终可能导致整个系统处于瘫痪状态。死锁和饥饿的主要差别是什么？1）死锁：是一种相互或循环等待的局面，且它们等待的事件是决不会发生的；被死锁的进程应该是两个或两个以上，一个进程不可能自己把自己锁上，除非出现程序
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
错误。2）饥饿：不是循环等待的局面，而是一种单向等待；它们等待的事件不是没有发生，而是总被别的进程抢先以致一直轮不到（很难轮到）它们。饥饿的进程可能是一个或多个。仅涉及一个进程的死锁有可能存在吗?为什么?*图简单的死锁例子我们先来看一个申请不同类型资源的死锁例子：假定有两个进程Pl和P2，设F和T都是可重用资源。于是Pl和P2可有如下形式：*四、产生死锁的四个必要条件⑴互斥条件:资源在一段时间内只能被一个进程所使用。（临界资源）⑵请求和保持条件:一个进程请求资源得不到满足而等待,但不释放已占有的资源。（部分分配)⑶不剥夺条件:一个资源仅能被占有它的进程所释放，而不能被其他进程剥夺。（主动释放）⑷环路等待条件:存在一个进程资源的环路链，链中每一个进程占用着某些资源，又在等待另一个进程占有的资源。解决死锁的方法一般可分为:预防、避免、检测和解除四种.*死锁的排除方法1鸵鸟算法2预防死锁3避免死锁4检测和解除死锁*解决死锁的最简单方法就是鸵鸟算法。即像鸵鸟一样，当遇到危险时，将头埋进沙子里，假装毫无问题。当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。以UNIX系统为例，它潜在地存在死锁，但它并不花功夫去检测和解除死锁，而是忽略不去理它。1鸵鸟算法（置之不理）*2预防死锁根据产生死锁的四个必要条件，只要使其中之一不能成立，死锁就不会出现。但必要条件1是由设备的固有特性所决定的，不仅不能改变，相反还应加以保证，因此实际上只有三种方法。预防死锁是一种较易实现的方法，已被广泛使用，但由于所施加的限制条件往往太严格，可能导致系统资源利用率和系统吞吐量降低。1．破坏请求和保持条件2．破坏不剥夺条件3．破坏环路等待条件*系统要求任一进程必须预先申请它所需的全部资源，而且仅当该进程的全部资源要求能得到满足时，系统才能给予一次性分配，然后启动该进程运行，但是在分配时只要有一种资源不满足，系统就不会给进程分配资源。进程运行期间，不会再请求新的资源，所以，再分配就不会发生（摒弃了部分分配）。缺点：资源严重浪费进程运行延迟1．破坏“请求和保持条件”(静态分配策略)*采用的策略：一个已经占有了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经占有的所有资源，待以后需要时再重新申请。缺点：1）实现比较复杂，且要付出很大代价；2）还因为反复地申请和释放资源，而使进程的执行无限地推迟，延长了周转时间，增加了系统的开销，降低了系统吞吐量（例如打印机打印的结果不连续）2.防止“不剥夺”条件的出现*3.防止“环路等待”条件的出现(层次分配策略)优点:资源利用率和系统吞吐量与另两种方法相比有较明显的改善缺点：1）为系统中各种类型的资源所分配的序号必须相对稳定，这就限制了新设备类型的增加；2）进程实际使用资源的顺序与系统规定的顺序不同而造成资源的浪费；这种方法的基本思想是：资源被分成多个层次,一个进程得到某一层的一个资源后,它只能再申请较高一层的资源;当一个进程要释放某层的一个资源时,必须先释放所占用的较高层的资源;当一个进程获得了某一层的一个资源后,它想再申请该层中的另一个资源,就必须先释放该层中的已占用资源.*3死锁避免如果操作系统能保证所有的进程在有限的时间内得到需要的全部资源,则称系统处于安全状态,否则称系统是不安全的.避免死锁与预防死锁的区别在于:预防死锁是设法至少破坏产生死锁的必要条件之一，严格地防止死锁的出现。避免死锁，它是在进程请求分配资源时，采用银行家算法等防止系统进入不安全状态。*在资源的动态分配的过程中，使用某种方法去防止系统进入不安全状态，从而避免死锁的发生。系统状态：安全状态：指系统能按照某种顺序如
，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成(称为序列为安全序列)。非安全状态：即在某个时刻系统中不存在一个安全序列，则称系统处于不安全状态或非安全状态。注意:1）安全序列不一定只有一个2）系统只要处在安全状态，就肯定不会发生死锁3）系统处在不安全状态下时，未必一定会发生死锁虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质是如何使系统不进入不安全状态。（银行家算法）*安全状态的例子例：假定系统有三个进程P1、P2、P3，共有12台磁带机。进程P1、P2和P3分别需要10台、4台和9台。设在T0时刻，进程P1、P2和P3已经获得5台、2台和2台，还有3台空闲没有分配。进程最大需求已分配可用P11053P2P34229T0时刻系统是安全的。这时存在一个安全序列*银行家算法银行家算法是最有代表性的避免死锁算法，是Dijkstra提出的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。*银行家可以把一定数量的资金供多个用户周转使用,为保证资金的安全,银行家规定:(1)当一个用户对资金的最大需求量不超过很行家现有的资金时可接纳该用户.(2)用户可以分期贷款,但贷款的总数不能超过最大需求量;(3)当银行家现有的资金不能满足用户的尚需总数时,对用户的贷款可推迟支付,但总能使用户在有限的时间里得到贷款;(4)当用户得到所需的全部资金后,一定能在有限的时间里归还所有资金银行家算法是通过动态地检测系统中资源分配情况和进程对资源的需求情况来决定如何分配资源的，在能确保系统处于安全状态时才能把资源分配给申请者，从而避免系统发生死锁。*要记住的一些变量的名称1Available（可利用资源总数）某类可利用的资源数目，其初值是系统中所配置的该类全部可用资源数目。2Max：某个进程对某类资源的最大需求数3Allocation：某类资源已分配给某进程的资源数。4Need：某个进程还需要的各类资源数。Need=Max-Allocation系统把进程请求的资源(Request)分配给它以后要修改的变量Available:=Available-Request;Allocation:=Allocation+Request;Need:=Need-Request;*例题：假定系统中有五个进程{P0、P1、P2、P3、P4}和三种类型的资源{A，B，C}，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图资源情况进程AllocationABCMaxABCNeedABCAvailableABCP0P1P2P3P401032290222243320075330221100274312200011431332*332122200资源情况进程AllocationABCMaxABCNeedABCAvailableABCP0P1P2P3P4010322902222433200302211002743122600011431332753资源情况进程NeedABCworkABCWork＋AllocationABCAllocationABCP0finish532truetruetruetruetrue011211532743743431002745745600302104710477430101057最大值已分配还需要可用工作向量Work.它表示系统可提供给进程继续运行所需要的各类资源的数目10,57P1P3P4P2*230020302资源情况进程AllocationABCMaxABCNeedABCAvailableABCP0P1P2P3P4010322902222433200(302)302211002743122(020)600011431332(230)753资源情况进程NeedABCworkABCWork＋AllocationABCAllocationABCP2finish532truetruetruetruetrue0112115327437434310027457457430107557556003021057若P1发出请求向量Request（1，0，2）10,57P1P3P4P0*210资源情况进程AllocationABCMaxABCNeedABCAvailableABCP0P1P2P3P4010322902222433302302211002743020600011431230(210)753资源情况进程NeedABCworkABCWork＋AllocationABCAllocationABCfinishflase若P0发出请求向量Request（0，2，0）10,57(030)(723)若P1发出请求向量Request（0，2，0）*3.7死锁的检测与解除死锁的检测与解除技术是指定期启动一个软件检测系统的状态，若发现有死锁存在，则采取措施恢复之。(1)死锁的检测：实质是确定是否存在环路等待现象，一旦发现这种环路便认定死锁存在，并识别出该环路所涉及的有关进程，以供系统采取适当的措施来解除死锁。最常用的是一种基于进程---资源分配图和死锁定理的检测死锁算法。*进程----资源分配图（RAG图）系统死锁可用进程----资源分配图来描述，该图是由一组结点和一组边所组成的。（用圆圈代表一个进程，用方框代表一类资源，由于一种类型的资源可能有多个，可用方框中的一个点代表一类资源中的一个资源）几个概念：请求边，分配边P1P2r1r2请求边资源分配图分配边*封锁进程：是指某个进程由于请求了超过系统中现有的未分配资源数目的资源，而被系统封锁的进程。非封锁进程：即没有被系统封锁的进程。进程---资源分配图的化简方法：假设某个进程---资源分配图中存在一个进程Pi，此刻Pi是非封锁进程，那么可以进行如下化简：当Pi有请求边时，首先将其请求边变成分配边(即满足Pi的资源请求)，而一旦Pi的所有资源请求都得到满足，Pi就能在有限的时间内运行结束，并释放其所占用的全部资源，此时Pi只有分配边，删去这些分配边（实际上相当于消去了Pi的所有请求边和分配边），使Pi成为孤立结点。（反复进行）在经过一系列的简化后，若能消去图中的所有边，使所有的进程都成为孤立结点，则称该图是可完全简化的；反之则是不可完全简化的。*死锁定理：系统中某个时刻S为死锁状态的充要条件是S时刻系统的资源分配图是不可完全简化的。P1P2r1r2P1P2r1r2P1P2r1r2*判定死锁准则：(1)如果RAG中未出现任何环，则此时系统内不存在死锁；(2)如果RAG中出现了环，且处于此环中的每类资源均只有一个个体，则有环就有死锁;此时环路是存在死锁的充分必要条件；(3)如果RAG中出现了环，但处于此环中的每类资源的个数不全为1，则环的存在只是产生死锁的必要条件而不是充分条件。此时是否有死锁，还要通过对RAG的化简而定。P1P2P3R1R2R3R4P1P2R1R2R3*判定死锁准则：(1)如果RAG中未出现任何环，则此时系统内不存在死锁；(2)如果RAG中出现了环，且处于此环中的每类资源均只有一个个体，则有环就就有死锁;此时环路是存在死锁的必要充分条件；(3)如果RAG中出现了环，但处于此环中的每类资源的个数不全为1，则环的存在只是产生死锁的必要条件而不是充分条件。此时是否有死锁，还要通过对RAG的化简而定。P1P2P3R1R2R3R4P4P3P2P1R1R2*例题:化简如图所示的资源分配图，并说明有无进程处于死锁状态？P0P1P2P3P4R0R1R2R3R4R4R3P0P1P2P3P4*资源分配图中存在环路并不一定发生死锁,因为循环等待资源仅是死锁发生的必要条件,而不是充分条件.如:P1P2P3R1R2R3有环有死锁P4P3P2P1R1R2有环无死锁*死锁的解除：是与检测死锁相配套的一种措施，用于将进程从死锁状态下解脱出来。常用的方法有：1、立即结束所有进程的执行,并重新启动操作系统.2、撤消进程：最简单撤消进程的方法是使全部死锁的进程夭折掉；另一方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，死锁状态消除为止。3、剥夺资源（挂起进程）:使用挂起/激活机构挂起一些进程，剥夺它们的资源以解除死锁，待条件满足时，再激活进程。目前挂起法比较受到重视。5解除死锁*采用剥夺资源的方法解决死锁问题时应考虑三个问题:(1)抢夺哪些进程的哪些资源;(2)被抢夺者的恢复;(3)进程的饿死;*系统中并发运行进程由于共享资源或相互通信，如果调度不当，可能导致系统死锁。解决死锁的方法有三种：(1)预防死锁，它是通过破坏死锁的四个必要条件实现的。(2)避免死锁，它是在进程请求分配资源时，采用银行家算法等防止系统进入不安全状态。(3)检测和解除死锁，它是通过设置一个死锁检测机构进行死锁检测，一旦检测出来，通过逐一撤消进程使系统恢复。小结：*选择题:1.进程从运行态到等待态可能是()运行进程执行了P操作B.进程调度程序的调度运行进程的时间片用完D.运行进程执行了V操作2.在()的情况下,系统出现死锁.计算机系统发生了重大故障B.有多个封锁的进程同时存在若干进程因竞争资源而无休止地相互等待对方释放已占有的资源资源数大大小于进程数或进程同时申请的资源数大大超过资源总数3.银行家算法是一种()算法.A.死锁解除B.死锁避免C.死锁预防D.死锁检测ACB
浙公网安备 33021202002483