死锁的概念

    死锁的定义

在多道程序系统中，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力。然而多个进程的并发执行也带来了新的问题一一死锁。所谓死锁是指多个进程因竞争资源而造成的一种僵局 （互相等待），若无外力作用，这些进程都将无法向前推进。

下面我们通过一些实例来说明死锁现象：

先看生活中的一个实例，在一条河上有一座桥，桥面很窄，只能容纳一辆汽车通行。如果有两辆汽车分别从桥的左右两端驶上该桥，则会出现下述的冲突情况：此时，左边的汽车占有了桥面左边的一段，要想过桥还需等待右边的汽车让出桥面右边的一段；右边的汽车占有了桥面右边的一段 ，要想过桥还需等待左边的汽车让出桥面左边的一段。此时，若左右两边的汽车都只能向前行驶，则两辆汽车都无法过桥。

在计算机系统中也存在类似的情况。例如，某计算机系统中只有一台打印机和一台输入设备，进程 P1正占用输入设备，同时又提出使用打印机的请求，但此时打印机正被进程 P2 所占用，而P2未释放打印机之前 ，又提出请求使用正被 P1占用着的输入设备 。这样两个进程相互无休止地等待下去，均无法继续执行，此时两个进程陷入死锁状态。

    死锁产生的原因

(1）系统资源的竞争

通常系统中拥有的不可剥夺资源，其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局，如磁带机、打印机等。只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源的竞争是不会引起死锁的。

(2）进程推进顺序非法

进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁。 例如，并发进程 P1 、P2 分别保持了资源 R1， R2，而进程 P1申请资源R2，进程 P2 申请资源 R1时，两者都会因为所需资源被占用而阻塞。

信号量使用不当也会造成死锁。进程间彼此相互等持对方发来的消息，结果也会使得这些进程无法继续向前进。例如，进程 A 等待进程 B发的消息，进程B又在等待进程 A 发的消息， 可以看出进程 A 和B 不是因为竞争同一资源，而是在等待对方的资源导致死锁。

(3）死锁产生的必要条件

产生死锁必须同时满足以下四个条件，只要其中任一条件不成立，死锁就不会发生。 

互斥条件：进程要求对所分配的资源 （如打印机） 进行排他性控制，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。 

不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放 （只能是主动释放）。 

请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源己被其他进程占有，此时请求进程被阻塞，但对自己己获得的资源保持不放。

循环等待条件：存在一种进程资源的循环等待链，链中每一个进程己获得的资源同时被链中下一个进程所请求。即存在一个处于等待状态的进程集合｛P1，P2，...，Pn ｝ ，其中 Pi 等待的资源被 P（i + 1）占有 （i=0,1，... ，n - 1),  Pn 等待的资源被 P0占有，如图所示。

直观上看 ，循环等待条件似乎和死锁的定义一样，其实不然。按死锁定义构成等待环所要求的条件更严，它要求 Pi等待的资源必须由P(i + 1）来满足，而循环等待条件则无此限制。例如，系统中有两台输出设备 ，P0占有一台，PK 占有另一台，且 K 不属于集合｛0，1，...，n}。Pn 等待一台输出设备，它可以从 P0获得，也可能从 PK 获得。因此，虽然 Pn、P0和其他一些进程形成了循环等待圈，但PK 不在圈内，若PK 释放了输出设备 ，则可打破循环等待，如图所示。因此循环等待只是死锁的必要条件。

资源分配图含圈而系统又不一定有死锁的原因是同类资源数大于1。但若系统中每类资源都只有一个资源，则资源分配图含圈就变成了系统出现死锁的充分必要条件。

要注意区分不可剥夺条件与请求和保持条件，用一个简单的例子来说明：如果你手上拿着一个苹果 （即使你不打算吃），别人不能把你手上的苹果拿走，那就是不可剥夺条件；如果你左手拿着一个苹果 ，允许你右手再去拿一个苹果 ，那就是请求和保持条件。

死锁的处理策略 

为使系统不发生死锁，必须设法破坏产生死锁的四个必要条件之一  ，或者允许死锁产生，但当死锁发生时能检测出死锁，并有能力实现恢复。

    预防死锁

设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个，以防止发生死锁。

    避免死锁

在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。

    死锁的检测及解除

无需采取任何限制性措施 ，允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁。

预防死锁和避免死锁都属于事先预防策略，但预防死锁的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低；避免死锁的限制条件相对宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来较为复杂。

死锁的几种处理策略的比较见下表

死锁预防 

防止死锁的发生只需破坏死锁产生的四个必要条件之一即可。 

    破坏互斥条件

如果允许系统资源都能共享使用，则系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行，而且在有的场合应该保护这种互斥性。

    破坏不剥夺条件  

当一个己保持了某些不可剥夺资源的进程，请求新的资源而得不到满足时  ，它必须释放己经保持的所有资源，待以后需要时再重新申请。这意味着，一个进程已占有的资源会被暂时释放，或者说是被剥夺了，从而破坏了不可剥夺条件 。

该策略实现起来比较复杂，释放已获得的资源可能造成前一阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。

    破坏请求和保持条件

采用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行后，这些资源就一直归它所有，也不再提出其他资源请求，这样就可以保证系统不会发生死锁。

这种方式实现简单 ，但缺点也显而易见，系统资源被严重浪费 ，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。而且还会导致 “饥饿” 现象，当由于个别资源长期被其他进程占用时，将致使等待该资源的进程迟迟不能开始运行。

    破坏循环等待条件

为了破坏循环等待条件，可采用顺序资源分配法 。首先给系统中的资源编号，规定每个进程， 必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源Ri，则该进程在以后的资源申请中，只能申请编号大于 Ri 的资源。

这种方法存在的问题是，编号必须相对稳定，这就限制了新类型设备的增加：尽管在为资源编号时己考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费；此外，这种按规定次序申请资源的方法，也必然会给用户的编程带来麻烦。

死锁避免

避免死锁同样是属于事先预防的策略，但并不是事先采取某种限制措施破坏死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态 ，以避免发生死锁。这种方法所施加的限制条件较弱，可以获得较好的系统性能。

    系统安全状态

避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态 ，则将资源分配给进程；否则， 让进程等待。

所谓安全状态 ，是指系统能按某种进程推进顺序 （Pl, P2，...，Pn），为每个进程Pi 分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序地完成。此时称 P1, P2,  ···,Pn  为安全序列。如果系统无法找到一个安全序列，则称系统处于不安全状态。 假设系统中有三个进程 P1 、P2 和P3，共有 12 台磁带机。进程P1 总共需要 10 台磁带机，P2 和 P3 分 别需要 4 台和 9 台。假设在T0 时刻，进程 P1、P2 和 P3 己分别获得 5 台、2 台和 2 台，尚有 3 台未分配，见下表：

则在 T0时刻是安全的，因为存在一个安全序列P2、P1、P3，即只要系统按此进程序列分配资源，则每个进程都能顺利完成。若在T0时刻后，系统分配1台磁带机给P3，则此时系统便进入不安全状态，因为此时己无法再找到一个安全序列。

并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态； 反之，只要系统处于安全状态，系统便可以避免进入死锁状态。

    银行家算法

银行家算法是最著名的死锁避免算法。它提出的思想是：把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源 ，当进程首次申请资游时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源 ，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程己占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

死锁检测和解除

前面介绍的死锁预防和避免算法，都是在为进程分配资源时施加限制条件或进行检测 ，若系统为进程分配资源时不采取任何措施，则应该提供死锁检测和解除的手段。

    资源分配图

系统死锁，可利用资源分配图来描述。如图所示，用圆圈代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫请求边，表示该进程申请一个单位的该类资源；从资源到进程的边叫分配边 ，表示该类资源已经有一个资源被分配给了该进程。

在上图所示的资源分配图中，进程 P1 已经分得了两个R1资源，并又请求一个R2资源；进程 P2 分得了一个 R1 和 一个 R2 资源，并又请求一个 R1资源。

    死锁定理

可以通过将资源分配图简化的方法来检测系统状态 S 是否为死锁状态。简化方法如下：

1） 在资源分配图中，找出既不阻塞又不是孤点的进程Pi（ 即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中己有空闲资源数量，如上图中，R1没有空闲资源，R2有一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之成为孤立的结点。 在图(a）中，P1是满足这一条件的进程结点，将P1的所有边消去，便得到图(b）所示的情况。

在这里要注意一个问题，判断某种资源是否有空间，应该用它的资源数量减去它在资源分配图中的出度，如上图中，R1资源数有 3，而出度也是 3。 所以 R1没有空闲资源，R2的资源数是 2，出度是1，所以R2有1个空闲资源。

2） 进程 Pi 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在上图中，进程P2 就满足这样的条件。根据 1）中的方法进行一系列简化后，若能消去图中所有的边，则称该图是可完全简化的，如图(c）所示。

S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的，该条件为死锁定理。

    死锁解除

一旦检测出死锁，就应立即采取相应的措施，以解除死锁。死锁解除的主要方法有：

1）资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。

2）撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。

3） 进程回退法。让一 （或多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。

本节小结

    为什么会产生死锁？产生死锁有什么条件？

由于系统中存在一些不可剥夺资源，而当两个或两个以上的进程占有自身资源，并请求对方资源时，会导致每个进程都无法向前推进，这就是死锁。死锁产生的必要条件有四个，分别是互斥条件、不剥夺条件 、请求并保持条件和循环等待条件。

互斥条件是指进程要求分配的资源是排他性的，即最多只能同时给一个进程使用。 不剥夺条件是指进程在使用资源完毕之前 ，资源不能被强制夺走。 请求并保持条件是指进程占有自身本来拥有的资源并要求其他资源。 循环等待条件是指存在一种进程资源的循环等待链 。

    有什么办法可以解决死锁问题？ 

死锁的处理策略可以分为预防死锁、避免死锁和死锁的检测及解除。

死锁的预防是通过设立一些限制条件，破坏死锁的一些必要条件，让死锁无法发生。 死锁的避免是在动态分配资源的过程中，用一些算法防止系统进入不安全状态 ，从而避免死锁。

死锁的检测和解除是在死锁产生前不采取任何措施，只检测当前系统有没有发生死锁。若有， 则采取一些措施解除死锁。

本节的知识架构图如下：