死 锁 Deadlock

死锁 Deadlock 在多道程序系统中，多个进程并发运行，共享资源，从而提高了资源的利用率。但是若对资源的管理和使用不当，在一定条件下会导致系统发生一种随机性故障――死锁。在一些系统中，比如实时控制系统，系统一旦发生死锁将导致灾难性的后果。 死锁Deadlock：是计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象（僵局），如无外力作用，这些进程将永远不能再向前推进。

陷入死锁状态的进程称为死锁进程，所占用的资源或者需要它们进行某种合作的其它进程就会相继陷入死锁，最终可能导致整个系统处于瘫痪状态。

资源的概念 OS是计算机系统中资源的管理者，而进程是竞争资源的基本单位，故对系统中所有进程的资源分配工作，都由OS完成。 研究资源分配时，我们必须搞清该资源是可以被几个进程同时使用，还是只能为一个进程使用，资源的不同使用性质正是引起系统死锁的原因。

资源的分类 根据资源性质：可剥夺（抢占）和不可剥夺（抢占）资源。 可抢占资源: 指资源占有进程虽然需要使用该资源，但另一个进程却强行把资源从占有者进程处抢来。 不可抢占资源: 指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。

根据使用方式：共享资源和独享资源。 根据使用期限；永久资源和临时性资源。 CPU、主存、硬盘，该类资源可为几个进程共同使用（可抢占） 资源 打印机，读卡机，磁带驱动器，可为某个进程独享（不可抢占） 可顺序重复使用的资源 由一个进程产生，被另外一个进程使用短暂时间 之后便无用的资源

产生死锁的原因 竞争资源: 当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁； 竞争临界资源 竞争临时性资源 2 进程推进的顺序不当 : 进程在运行过程中，请求和释放资源的顺序不当，导致进程的死锁。

竞争资源 竞争临界资源引起死锁 P1占用资源B, P2占用资源A, P1要求使用资源A, P2要求使用资源B

竞争资源 竞争临时性资源(如进程通信中的消息) S1、S2、S3是临时资源 P1 S1 S3 P2 P3 S2 P1：Release(S1);Request(S3) P2：Release(S2);Request(S1) P3：Release(S3);Request(S2) 不可能发生死锁, S1、S2、S3是临时资源 P1 S1 S3 P2 P3 S2 P1：Request(S3);Release(S1) P2：Request(S1);Release(S2) P3：Request(S2);Release(S3) 可能发生死锁

进程推进顺序不当 3和4推进方式 将引发死锁

不会发生死锁的情况

永久性资源产生死锁的必要条件 1 互斥条件:进程访问的是临界资源，那个资源一次只能被一个进程所使用。 2 请求和保持条件:（部分分配）一个进程在请求新的资源的同时，保持对某些资源的占有。 3 不剥夺条件:一个资源仅能被占有它的进程所释放，而不能被其他进程剥夺。 4 环路等待条件:存在一个进程的环路链，链中每一个进程占用有着某个或某些资源，又在等待链中的另一个进程占有的资源。

涉及死锁的四个问题 1 预防死锁 2 避免死锁 3 检测死锁 4 解除死锁 设法不让系统产生死锁, 通过设置某些限制性条件去破坏产生死锁的4个必要条件中的一个或几个来实现。易导致系统资源利用利和系统吞吐量的下降。 2 避免死锁 资源的动态分配过程中,用某种方法去防止系统进入不安全状态。 3 检测死锁 及时检测出死锁的发生,精确确定与死锁有关的进程和资源,为解除死锁创造条件。 4 解除死锁 常用的方法是撤销或挂起一些进程,以便回收部分资源,再将这些资源分配给已处于阻塞状态的进程,使之继续运行。

鸵鸟算法（置之不理） 解决死锁的最简单方法就是鸵鸟算法。即像鸵鸟一样，当遇到危险时，将头埋进沙子里，假装毫无问题。 当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。 以UNIX系统为例，它潜在地存在死锁，但它并不花功夫去检测和解除死锁，而是忽略不去理它。

预防死锁 1 互斥条件 2 请求和保持条件 3 不剥夺条件 4 环路等待条件 根据生产死锁的四个必要条件，只要使用其中之一不能成立，死锁就不会出现。但必要条件(1)是由设备的固有特性所决定的，不仅不能改变，相反还应加以保证，因此实际上只有三种方法。 预防死锁是一种较易实现的方法，已被广泛使用，但由于所施加的限制条件往往太严格，可能导致系统资源利用率和系统吞吐量降低。

1.资源静态分配法（摒弃请求和保持条件） 系统要求任一进程必须预先申请它所需的全部资源，而且仅当该进程的全部资源要求能得到满足时，系统才能给予一次性分配，然后启动该进程运行，但是在分配时只要有一种资源不满足，系统就不会给进程分配资源。进程运行期间，不会再请求新的资源，所以，再分配就不会发生（摒弃了部分分配）。 特点： 资源严重浪费 进程延迟进行

2.资源暂时释放法(破坏“不剥夺”条件) 采用的策略：一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请。 实现比较复杂，且要付出很大代价；此外，还因为反复地申请和释放资源，而使进程的执行无限地推迟，延长了周转时间，增加了系统的开销，降低了系统吞吐量。（例如打印机打印的结果不连续）

3.资源有序使用法(破坏“环路等待”条件) 采用资源顺序使用法，基本思想是：把系统中所有资源类型线性排队，并按递增规则赋予每类资源以唯一的编号。例如输入机＝1，打印机＝2，磁带机＝3，磁盘＝4等等。进程申请资源时，必须严格按资源编号的递增顺序进行，否则系统不予分配。 优点： 资源利用率和系统吞吐量与另两种方法相比有较明显的改善。 缺点： 为系统中各种类型的资源所分配的序号必须相对稳定，这就限制了新设备类型的增加 作业实际使用资源的顺序与系统规定的顺序不同而造成资源的浪费

避免死锁 避免死锁与预防死锁的区别在于，预防死锁是设法至少破坏产生死锁的必要条件之一，严格地防止死锁的出现。 避免死锁，它是在进程请求分配资源时，采用银行家算法(资源安全分配算法)等防止系统进入不安全状态。

系统的安全状态 系统状态： 安全状态：指系统能按照某种顺序如<P1,P2,…,Pn> (称为<P1,P2,…,Pn>序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。 非安全状态：即在某个时刻系统中不存在一个安全序列，则称系统处于不安全状态或非安全状态。 虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质是如何使系统不进入不安全状态。

安全状态的例子 进程 最大需求 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 例：假定系统有三个进程P1、P2、P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。设在T0时刻，进程P1、P2和P3已经获得5台、2台和2台，还有3台空闲没有分配。 进程 最大需求 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 T0时刻系统时安全的。这时存在一个安全序列<P2，P1，P3> 不安全序列< P3, P2, P1 > <P1, P2, P3 >....

虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质是如何使系统不进入不安全状态。 系统的状态可能通过下述来描述： 进程剩余申请数＝最大申请数－占有数。 可分配资源数＝总数－占有数之和。

银行家算法 N: 表示进程总数 M: 表示系统资源类型数 银行的一个主要业务是借贷款, 为了满足顾客申请借款的要求, 同时又能使银行在规定的时限内收回自己的投资, 银行家必须研究一种合理的借贷次序为多个顾客贷款。 银行家算法是最有代表性的避免死锁算法，是Dijkstra提出的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。为实现银行家算法，系统中必须设置若干数据结构。 N: 表示进程总数 M: 表示系统资源类型数

银行家算法中的数据结构 1 可利用资源向量Available(一维数组) 2 最大需求矩阵Max(二维数组) 是一个含有m个元素，其中的每一个元素代表一类可利用的资源数目，其初值是系统中所配置的该类全部可用资源数目。如果Available[j]=k， 表示系统中现有Rj类资源k个。 2 最大需求矩阵Max(二维数组) 是一个含有nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i,j)=k， 表示进程i需要Rj类资源的最大数目为k。 3 分配矩阵Allocation(二维数组) 是一个含有nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation(i,j)=k， 表示进程i当前已分得Rj类资源k个。

4 进程当前资源请求向量Request(一维数组) 当某进程i需要系统资源时,就将其对各类资源的请求数送入Request数组中 5 布尔向量Finish(一维数组) 代表每一个进程是否能得足够的系统资源并顺利结束运行。 6 需求矩阵Need (二维数组) 是一个含有n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need(i,j)=k， 表示进程i还需要Rj类资源k个，方能完成其任务。 Need(i,j)= Max(i,j)-Allocation(i,j) 7 系统工作向量Work(一维数组) 代表系统中可供进程继续运行的各类资源的数目。

银行家算法 当进程Pi需要请求系统资源时,将其对各类资源的需求数量送入Request数组中, 并按下述步骤进行检查： 1 如果Request(j)≤Need(i,j),则转向步骤2；否则认为出错。(因为它所需要的资源数已超过它所宣布的最大值) 2 如果Request(j)≤Available(j),则转向步骤3；否则，表示系统中尚无足够的资源，Pi必须等待 3 系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值： Available(j)=Available(j)-Request(j); Allocation(i,j)=Allocation(i,j)+Request(j); Need(i,j)= Need(i,j)- Request(j); 4 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 j取值为1~M

安全性算法 1 工作向量Work初始化。表示系统可提供给进程继续运行所需要的各类资源的数目，它含有M个元素， Work(j)=Available(j) (j: 1~M) Finish向量表示系统是否有足够的资源分配给进程，开始时 Finish[i]=false ( i : 1 ~ N ) 2 从进程集合中找到一个能满足下述条件的进程：①Finish[i]=false; ②Need(i,j)≤Work(j) 。如找到，执行步骤3；否则执行步骤4。 3 此时若进程Pi获得资源后，可顺利执行，直至完成，并会释放出分配给它的资源，故执行： Work(j)=Work(j)+Allocation(i,j); Finish[i]:=true; 判断所有的Finish(k)是否为true,若是则系统安全,算法结束 Goto step2; 4 系统已经找不到一个令可以令所有进程均执行完成的安全分配序列 系统处于不安全状态, 算法结束。

银行家算法举例 银行家算法的特点 系统资源的利用率比预防死锁的方法要高 不能适应系统资源数量和进程数目的变化 要求进程必须事先说明它们的最大资源需求量 算法的实现需要一些系统开销

死锁的检测 死锁的检测和恢复技术是指定期启动一个软件检测系统的状态，若发现有死锁存在，则采取措施恢复之。 死锁状态的检测思想 检查死锁的办法就是由软件检查系统中由进程和资源构成的有向图是否构成一个或多个环路，若是，则存在死锁，否则不存在。 死锁的检测：实质是确定是否存在环路等待现象，一旦发现这种环路便认定死锁存在，并识别出该环路所涉及的有关进程，以供系统采取适当的措施来解除死锁。最常用的是一种基于资源分配图RAG和死锁定理的检测死锁算法

资源分配图（RAG） 系统死锁可用资源分配图来描述，该图是由一组结点N和一组边E所组成的一对偶G=(N,E)。（用圆圈代表一个进程，用方框代表一类资源，由于一种类型的资源可能有多个，可用方框中的一个点代表一类资源中的一个资源） 几个概念：进程结点, 资源结点, 请求边，分配边 P1 独立结点 : P3 非独立结点: P1, P2 请求R2 R1 R2 P3 P2 资源分配图

资源分配图的化简 封锁进程：是指某个进程由于请求了超过了系统中现有的未分配资源数目的资源，而被系统封锁的进程。 非封锁进程：即没有被系统封锁的进程资源分配图的化简方法：假设某个RAG中存在一个进程Pi，此刻Pi是非封锁进程，那么可以进行如下化简：当Pi有请求边时，首先将其请求边变成分配边(即满足Pi的资源请求)，而一旦Pi的所有资源请求都得到满足，Pi就能在有限的时间内运行结束，并释放其所占用的全部资源，此时Pi只有分配边，删去这些分配边（实际上相当于消去了Pi的所有请求边和分配边），使Pi成为孤立结点。（反复进行） 完全可化简/不可化简/非完全可化简

RAG的化简 P1 P1 P2 R1 R2 P1 R2 R1 R2 R1 P2 P2 完全可化简, 非封锁进程P1, P2 P1 R1 R2

死锁定理 在进程申请资源而阻塞, 但进程不主动释放它已占用资源的前提下, 系统在某个时刻的状态S为死锁状态的充要条件是S时刻系统的资源分配图是不可完全简化的。 在经过一系列的简化后，若能消去图中的所有边，使所有的进程都成为孤立结点，则称该图是可完全简化的；反之的是不可完全简化的。资源分配图中不能化简的进程即为死锁进程。

检测算法中的数据结构 R1 权值:边的数目 Request请求矩阵 Allocation资源分配矩阵 L进程向量 P1 ... Rm P1 1 .... P2 ..... Pn R1 R2 ... Rm P1 2 P2 1 ..... Pn P1 P2 ..... ... Pn P1 Available可用资源向量 Work工作向量 R1 R2 R1 R2 ... Rm 1 R1 R2 ... Rm 1 P2 只需在某个进程执行新的资源请求而又不能被立即满足时才进行死锁检测

解除死锁 是与检测死锁相配套的一种措施，用于将进程从死锁状态下解脱出来。常用的方法有： 撤消死锁进程: 挂起进程（剥夺资源） 最简单撤消进程的方法是使全部死锁的进程夭折掉； 是按照某种顺序逐个地撤消进程，直至有足够的资源可用，死锁状态消除为止 挂起进程（剥夺资源） 使用挂起/激活机构挂起一些进程，剥夺它们的资源以解除死锁，待条件满足时，再激活进程。 目前挂起法比较受到重视。