死锁

1.死锁的概念

1.1死锁的定义

多个进程并发执行，由于竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法推进，这就是死锁现象。

例如：系统中只有一台打印机和一台输入设备，若进程p1正在占用输入设备，同时又提出使用打印机的请求；而进程p2正在占用打印机，同时又提出请求输入设备的请求。这样两个进程相互无休止地互相等待，均无法继续执行，此时这两个进程进入死锁状态。

1.2死锁产生的原因

①系统资源的竞争

只有对不可剥夺资源的竞争（如打印机） 才可能产生死锁，对可剥夺资源的竞争是不会产生死锁的。

②进程推进顺序非法

进程在运行过程中，请求和释放资源的顺序不当，同样会导致死锁。如1.1的例子。

③死锁产生的必要条件： 死锁产生必须同时满足以下四个条件，任意一条不成立，便不会产生死锁：

• 互斥条件： 各个进程必须互斥的对系统分配的资源（临界资源）进行排他性使用。
• 不可剥夺条件： 进程使用完临界资源之前，不能被其他资源强行夺走，只能自行释放。
• 请求并保持条件：进程已经保持了一个临界资源，但又提出了新的申请临界资源要求，而该临界资源被其他进程占有，此时，请求进程被阻塞，但又保持对自己占有的临界资源保持不放。
• 循环等待条件: 存在一种进程资源的循环等待链条，每个进程已获得的临界资源同时被下一个资源所请求。

2.死锁的预防

预防死锁只需要破坏死锁的四个必要条件之一即可：

①破坏互斥条件

②破坏不可剥夺条件： 当进程的新资源不可取得时，释放自己已有的资源，待以后需要时重新申请。 但这种方法可能导致迁移阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。

③破坏请求并保持条件：进程在运行前一次申请完它所需要的全部资源，在它的资源为满足前，不把它投入运行。一旦投入运行，这些资源都归它所有，不能被剥夺。但这种方法系统资源被严重浪费，而且可能导致饥饿现象，由于个别进程长时间占用某个资源，导致等待该资源的进程迟迟无法运行。

④破坏循环等待条件： 给资源编号，规定每个进程必须按编号递增地顺序请求资源，同类资源一次性申请完。这种方法存在问题是发生作业使用资源地顺序与系统规定的顺序不同，造成系统地浪费，并且给编程带来麻烦。

这四种方法都有各自的缺陷，我们一般不采用。

3.死锁的避免

避免死锁同样属于事先预防地策略，但不是破坏死锁地必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。

3.1系统安全状态

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

安全状态：系统能按照某种进程推进顺序为每个进程分配其所需地资源，直至满足每个进程对资源地最大需求，使每个进程可顺序完成。

并非所有不安全状态都是死锁状态，但当系统进入不安全状态后便可能进入死锁状态；只要处于死锁状态，则一定处于不安全序列状态。

如：进程p1,p2,p3，共有12台磁带机。在t时刻，p1，p2，p3所需要资源和已分配资源如下表：

在t时刻是安全的，因为存在一个安全序列p2、p1、p3，按照这个顺序分配资源，每个进程都能顺利完成。

3.2银行家算法

银行家算法是著名的死锁避免算法，核心思想是：把操作系统视为银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 规定：

• 进程运行前先声明对各种资源的最大需求量
• 若银行家资金能够达到进程声明的最大需求量便能将所有资金收回，否则一分钱受不了，产生坏账。

例:某时刻进程的资源使用情况如下表，此时的安全序列为：

安全序列不存在，此时已经处于不安全序列状态。

判断过程如下：

• 可用资源(0, 2, 1)大于p1进程所需，可以成功完成p1进程回收p1资源后，可用资源为(0, 2, 1) + (2, 0, 0) = (2, 2, 1)。
• 可用资源(2, 1, 1)大于p4进程所需，可以成功完成p4资源，回收p4资源后，可用资源为(2, 2, 1) + (0, 0, 1) = (2, 2, 2)。
• 可用资源(2, ,2 , 2)既无法完成p2进程所需，又不够p3进程所需，为不安全序列状态。

4.死锁的检测和解除

若系统在分配资源是不采取任何措施，应该提供死锁检测和避免手段。

4.1资源分配图

用圆圈代表一个进程，用框代表一类资源。从进程到资源的有向边称为请求边，表示该进程从该类资源申请一个资源；从从资源到进程的边称为分配边，表示该类资源已有一个资源分配给该进程。

如：进程p1已经分配了2个R1资源，并请求了一个R2资源；进程p2分配了一个R1，一个R2资源，并申请了一个R1资源。

4.2死锁定理

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

• 找出既不阻塞又不孤点的进程Pi(找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有的空闲资源数量)。
• 消除与Pi所有相邻的请求边和分配边，使之成为孤立的节点。
• 循环以上两条。

总结来说就是：依次消除与不阻塞进程相邻的边，直到无边可消除。

如果能消除所有的边，则没有产生死锁；否则产生死锁。

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

例如：p1是既不阻塞又不孤点的进程，消去与它相邻的所有边。

p2既不阻塞又不孤点，消去与它相邻的所有边。

消去了所有边，不是死锁状态。

4.3死锁解除

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

• 资源剥夺法。 挂起某些死锁进程，抢占它的资源，分配给其他死锁进程。
• 撤销进程法。 强制撤销部分进程并剥夺这些进程的资源，让其他进程顺利执行。
• 进程回退法。