2.4 死锁
思维导图
一、死锁的概念
1. 死锁的定义
在多道程序中，由于多个进程的并发执行，改善了系统资源的利用率，并提高了系统的处理能力。然而多个进程的并发执行也带来了新的问题——死锁。所谓死锁，是指多个进程因竞争关系而造成的一种僵局（相互等待），若无外力作用，这些进程都将无法向前推进。
2. 死锁产生的原因
（1）系统资源的竞争
通常系统中拥有不可剥夺资源，其数量不足以满足多个进程运行的必须，使得进程在运行过程中，会因为争夺资源陷入僵局。只有对不可剥夺资源的竞争才会产生死锁，对可剥夺资源的竞争是不会引起死锁的。
（2）进程推进顺序非法
进程在运行过程中，请求和释放资源的顺序不当，同样会导致死锁。信号量使用不当也会造成死锁，进程间彼此互相等待对方发来的消息，也会使得这些进程间无法继续向前推进。
（3）死锁产生的必要条件
死锁的产生必须同时满足以下四个条件：
- 互斥条件：进程要求对所分配的资源进行排他性控制，即在一段时间内资源仅为一个进程所有；
- 不剥夺条件：进程所获得的资源在未使用完之前不能被其他进程强行夺走；
- 请求并保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，但又对自己获得的资源不释放；
- 循环等待条件：存在一种进程资源的循环等待链，链中每个进程已获得的资源被链中另一个进程请求。即存在一个处于等待态的进程集合 {P1，P2，...，Pn}，其中 Pi 等待的资源被 Pi+1 占用，Pn 等待的资源又被 P0 占用。
注意：发生死锁时一定有循环等待，但是发生循环等待时不一定发生死锁！循环等待不一定发生死锁的原因时，同类资源数大于一。若系统中每类资源都只有一个资源，则会变成死锁。
二、死锁的处理策略
为使系统不发生死锁，必须设法破坏产生死锁的四个必要条件之一，或允许死锁发生，但当死锁发生时必须能检测并实现恢复。
1. 死锁预防
设置某些限制条件，破坏死锁的四个必要条件中的一个或多个，以防止死锁发生。
2. 避免死锁
在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。
3. 死锁检测及解除
无需采取任何限制性措施，允许进程在允许过程中发生死锁。通过系统检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁。
4. 死锁处理策略的比较
| 措施 | 资源分配策略 | 各种可能模式 | 主要优点 | 主要缺点 |
|---|---|---|---|---|
| 死锁预防 | 保守，宁可资源闲置 | 一次请求所有资源，资源剥夺，资源按序分配 | 适用于突发式处理的进程，不必进行剥夺 | 效率低，进程初始化时间延长；剥夺次数过多；不使灵活申请新资源 |
| 死锁避免 | 使“预防”和“检测”的折中（在运行时判断是否可能死锁） | 寻找可能的安全允许顺序 | 不必进行剥夺 | 必须直到将来的资源请求；进程不能被长时间阻塞 |
| 死锁检测 | 宽松，只要允许就分配资源 | 定期检查死锁是否已经发生 | 不延长进程初始化时间，允许对死锁进行现场化处理 | 通过剥夺解除死锁，造成损失 |
三、死锁预防
防止死锁的发生只需要破坏死锁产生四个必要条件之一即可。
1. 破坏互斥条件
若系统资源都能共享使用，则系统不会进入死锁状态。但实际上的系统不可能所有资源共享，因此这种方法只能在特定的场合使用。
2. 破坏不剥夺条件
当一个已保持了某些不可剥夺资源的进程请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。
该策略实施起来比较复杂，释放已获得的资源可能造成前一阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。这种方法常用于状态容易保存和恢复的资源，如 CPU。
3. 破坏请求并保持条件
采用预先静态分配方法，即进程在允许前一次申请完它需要的全部资源，在它资源未满足前，不把它投入允许。一旦投入允许，这些资源就一直归它所有，不再提出其它资源请求，这就就不会发生死锁。
这种方式实现简单，但是缺点也十分明显，系统资源被严重浪费，其中有些资源可能仅存在允许初期或运行快结束时才使用，甚至根本不使用。而且还会导致“饥饿”现象，由于个别资源长期被其它进程占用，将致使等待该资源的进程迟迟不能开始。
4. 破坏循环等待条件
为了破坏循环等待条件，可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次性申请完。也就是说，只要进程提出申请分配资源 Ri，则该进程在以后的资源申请中就只能申请编号大于 Ri 的资源。
这种方法的问题在于编号必须相对稳定，这就限制了新类型设备的增加；尽管在编号时已考虑到大多数作业使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费；此外，这种按规定申请资源的方法也必定会给用户编程造成麻烦。
四、死锁避免
避免死锁同样属于事先预防策略，但并不事先采取某种限制措施破坏死锁的必要条件 ，而在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法能够获得较好的系统性能。
1. 系统安全状态
避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算资源分配的安全性。若此次分配不会导致系统进入不安全的状态，则将系统资源分配给每个进程；否则进程等待。
所谓安全状态，是指系统能按某种进程推进顺序为每个进程 Pi 分配其所需要的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。此时就称这个推进顺序为安全序列，若系统无法找到一个安全序列，则称这个系统处于不安全状态。
假设系统中有三个进程 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，即只要系统按此进程序列分配资源，那么每个进程都能顺利完成。若在 T0 时刻后，系统分配 1 台磁带机给 P3，则此时系统便进入不安全状态，因为此时已经无法再找到一个安全序列。
并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。
2. 银行家算法
银行家算法是著名的死锁避免算法，其思想是：把操作系统当作银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 操作系统按照银行家制定的规则为操作系统分配资源。当进程首次申请资源时，要测试该进程对资源的最大需求量，若系统现存的资源可以满足它的最大需求量，则按照当前的申请量分配资源，否则就推迟分配；当进程在执行中申请资源时，先测试该进程已占用的资源数与本次申请的资源数是否超过该进程对资源的最大需求量。若超过则拒绝分配资源，若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
（1）数据结构描述
可利用资源向量 Available：含有 m 个元素的数组，其中每个元素代表一类可用资源的数目。 Available[j] = K 表示系统中 现有 Rj 类资源 K 个。
最大需求矩阵 Max：n * m 矩阵，定义系统中 n 个进程中的每个进程对 m 类资源的最大需求。简单来说，一行代表一个进程，一列代表一类资源。Max[i, j] = K 表示该进程需要 Rj 类资源的最大数目为 K。
分配矩阵 Allocation：n * m 矩阵，定义系统中每类资源当前已分配给每个进程的资源数。Allocation][i, j] = K 表示进程 i 当前已分得 Rj 类的资源数目为 K。
需求矩阵 Need：n * m 矩阵，表示每个进程尚需的各类资源数。Need[i, j] = K 表示进程 i 还需要 Rj 类资源的数目为 K。
上述三个矩阵存在如下关系： $$ Need = Max - Allocation $$
（2）银行家算法描述
设 Request 是进程 Pi 的请求向量，Request_i[j] = K 表示进程 Pi 需要 j 类资源 K 个，当 Pi 发出资源请求后，系统按下述步骤进行检查：
-
若 Request_i[j] <= Need[i, j]，则转向步骤 2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值；
-
若 Request_i[j] <= Available[j]，则转向步骤 3；否则，表示尚无足够资源，Pi 须等待；
-
系统试探着把资源分配给进程 Pi，并修改下面数据结构中的数值： $$ Available = Available - Request\ Allocation[i, j] = Allocation[i, j] + Request_i[j]\ Need[i, j]= Need[i, j] - Request_i[j] $$
-
系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程 Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态， 让进程等待。
（3）安全性算法
- 初始时安全序列为空。
- 从 Need 矩阵中找出符合条件的行；改行对应的进程不在安全序列中，而且该行小于等于 Available 向量，找到后，把对应的进程加入安全序列；若找不到，则执行步骤 4；
- 进程 Pi 进入安全序列后，可顺利执行，直至完成，并释放分配给它的资源，故而执行
Available = Available + Allocation[i]，其中 Allocation[i] 表示进程 Pi 代表的在 Allocation 矩阵中对应的行，返回步骤 2； - 若此时安全序列中已有所有进程，则系统处于安全状态，否则系统处于不安全状态。
3. 安全性算法举例
假定系统中有 5 个进程{P0, P1, P2, P3, P4}和 3 类资源A B C，各种资源的数量分别为10、5、7，在 T0 时刻的资源分配情况见下表：
| 进程 \ 资源情况 | Max A B C |
Allocation A B C |
Available A B C |
|---|---|---|---|
| P0 | 7 5 3 | 0 1 0 | 3 3 2 (2 3 6) |
| P1 | 3 2 2 | 2 0 0 (3 0 2) |
|
| P2 | 9 0 2 | 3 0 2 | |
| P3 | 2 2 2 | 2 1 1 | |
| P4 | 4 3 3 | 0 0 2 |
-
从题目中我们可以提取 Max 矩阵和 Allocation 矩阵，这两个矩阵相减可得到 Need 矩阵： $$ \begin{bmatrix} 7 & 5 & 3 \ 3 & 2 & 2 \ 9 & 0 & 2 \ 2 & 2 & 2 \ 4 & 3 & 3 \ \end{bmatrix} - \begin{bmatrix} 0 & 1 & 0 \ 2 & 0 & 0 \ 3 & 0 & 2 \ 2 & 1 & 1 \ 0 & 0 & 2 \ \end{bmatrix} = \begin{bmatrix} 7 & 4 & 3 \ 1 & 2 & 2 \ 6 & 0 & 0 \ 0 & 1 & 1 \ 4 & 3 & 1 \ \end{bmatrix} \ Max \qquad\quad Allocation \qquad\quad Need $$
-
然后，将 Available 向量与 Need 矩阵的各行进行比较，找出比 Available 矩阵小的行；
-
释放 Pi 所占的资源，即把 Pi 进程对应的 Allocation 矩阵中的一行与 Available 向量相加，然后更新需求矩阵： $$ (3 3 2) + (2 0 0) = (5 3 2) = Available \ {\begin{bmatrix} 7 & 4 & 3 \ 6 & 0 & 0 \ 0 & 1 & 1 \ 4 & 3 & 1 \ \end{bmatrix}} $$
去掉了对应的一行，再用更新后的 Available 向量和 Need 矩阵重复步骤 2，最后得到一个安全序列 {P1, P3, P4, P2, P0}。
五、死锁检测和解除
若系统为进程分配资源时不采取任何措施，则应该提供死锁检测和解除的手段。
1. 资源分配图
系统死锁可利用资源分配图来描述：
圆圈代表一个进程，框代表一类资源。由于一种类型的资源可能有多个，因此用框中的一个圆代表一类资源中的一个资源。从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源；从资源到进程的边称为分配边，表示该资源已有一个资源分配给了该进程。
2. 死锁定理
可以通过将资源分配图简化的方法来检测系统状态S是否为死锁状态。简化方法如下：
1) 在资源分配图中，找出既不阻塞又不是孤点的进程 Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之成为孤立的结点。在图 a中，P1是满足这一条件的进程结点，将 P1 的所有边消去，便得到图 b 所示的情况。
2) 进程 Pi 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在上图中，进程P2 就满足这样的条件。根据第 1 条中的方法进行一系列简化后,若能消去图中所有的边，则称该图是可完全简化的，如图所示。
S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的,该条件为死锁定理。
3. 死锁解除
一旦检查出死锁，就应当立即采取相应的措施来解除死锁。死锁解除的主要方法有：
- 资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其它死锁进程。但应当防止被挂起的进程长时间得不到资源而处于资源匮乏的状态。
- 撤销进程法：强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行；
- 进程回退法：让一个或多个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺，要求系统保持进程的历史信息，设置还原点。