6 Deadlocks¶

死锁：指多个进程因竞争共享资源而造成相互等待的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。

Example

对于信号量 A 和 B 来说，初始化都是1

P0            |P1
wait (A);     |wait(B)
wait (B);     |wait(A)

P0 和 P1 就形成了死锁

6.1 Deadlock Characterization¶

产生死锁的四个必要条件：

互斥：在一个时间点只有一个进程可以使用资源
占有并等待：一个进程已经持有了至少一个资源，但又请求新的资源，而这些新资源正被其他进程持有，导致当前进程阻塞，但它并不释放已持有的资源。
不可抢占，不剥夺：一个资源只能由持有它的进程在完成任务后自愿释放，不能被系统强行剥夺。
循环等待：有一个闭环的等待链

下面介绍一个检测死锁的重要工具 Resource-Allocation Graph（资源分配图）

顶点分为两类：进程节点（\(P_i\)）和资源类型节点（\(R_j\)）
边分为两种：
请求边（\(P_i→R_j\)）：表示进程希望获取该资源
分配边（\(R_j→P_i\)）：表示资源已被分配给该进程

Example

通过这个图判断死锁的一个基本的思路就是

如果无环，那么不可能有死锁
有环且每个资源都只有一个实例，那么就是死锁，否则概率死锁

那么更加严谨一些，我们提出死锁定理：S为死锁状态的充分条件是：尚且仅当S状态的资源分配图是不可完全简化的。

资源分配图的简化

第一步：先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞（“不阻塞”即：系统有足够的空闲资源分配给它）的

第二步：把不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来

第三步：看剩下的进程有哪些是不阻塞的，然后又把它们逐个变成孤立的点。

第四步：最后，所有的资源和进程都变成孤立的点。这样的图就叫做“可完全简化”

6.2 Methods for Handling Deadlocks¶

死锁处理有三种不同的策略

保证系统永远不会出现死锁的情况，方法有死锁预防，死锁避免
允许系统出现死锁，然后修复，方法有死锁检测，死锁接触
忽略死锁问题，假设死锁永远不会出现（被现在大多数操作系统使用）

6.3 Deadlock Prevention¶

我们通过破坏死锁发生的四个必要条件之一以防止死锁的发生

互斥：对于不可共享资源（如打印机、磁带机），必须保证互斥使用，否则会导致数据混乱。这个条件不能被打破
占有并等待：可以选择当一个进程请求资源时，它必须不持有任何其他资源。这样就可以破坏这个条件，实现方式为在进程开始执行前，一次性申请所有需要的资源，只有全部资源都可用时才允许进程运行。如果某个资源暂时不可用，则进程等待直到全部资源都能分配。或者说允许进程在完全释放当前所有资源后再请求新的资源可能造成的问题就是资源利用率低以及可能产生饥饿
不可抢占：如果一个进程正在持有某些资源，并请求另一个无法立即分配给它的资源，那么它必须释放当前所持有的所有资源。被剥夺的资源会被加入到该进程正在等待的资源列表中。进程只有在能够重新获取其原有的资源以及它所请求的新资源时，才会被重新启动。【允许资源抢占以破坏条件】
循环等待：对所有资源类型强加一个全局的、完全的排序（total ordering），并要求每个进程必须按照这个顺序递增地请求资源。这样可能会导致灵活性变差

6.4 Deadlock Avoidance¶

与“死锁预防”不同，“死锁避免”不是破坏某个必要条件，而是在资源分配前进行安全性检查，确保系统始终处于一个“安全状态”，从而避免进入可能导致死锁的状态。

我们要求系统具备一些事先的额外信息。最简单且最有用的模型要求每个进程声明它可能需要的每种资源类型的最大数量。死锁避免算法会动态地检查资源分配状态，以确保永远不会出现循环等待条件。

安全状态

安全状态是指系统的一种状态，在此状态开始系统能按某种顺序（如\(P_1\)、\(P_2\) …… \(P_n\)）来为各个进程分配其所需资源，直至最大需求，使每个进程都可顺序地一个个地完成。这个序列（\(P_1\)、\(P_2\) …… \(P_n\)）称为安全序列。若系统此状态不存在一个安全序列，则称系统处于不安全状态

如果系统处于安全状态，则不会发生死锁。如果系统处于不安全状态，则可能发生死锁。死锁避免的目标是：确保系统永远不会进入不安全状态。由此提出一些算法

对于每种资源类型只有一个实例，可以采用资源分配图。对于每种资源类型有多个实例的情况，可以使用银行家算法。

6.4.1 Resource-Allocation Graph Algorithm¶

Claim edge（需求边） 是一条从进程 \(P_i\) 指向资源 \(R_j\) 的虚线箭头。

当进程实际发出请求时，虚线的 claim edge 会变成实线的 request edge。\(P_i→R_j\) 从虚线变为实线。

当资源被成功分配给进程后，request edge（实线）会变成 assignment edge（分配边）。分配边的方向反过来了：从资源指向进程 → \(R_j→P_i\)

算法：假设进程Pi申请资源Rj。只有在需求边 \(P_i\) → \(R_j\) 变成分配边 \(R_j\) → \(P_i\) 而不会导致资源分配图形成环时，才允许申请。

6.4.2 Banker's Algorithm¶

参考

银行家算法

银行家算法(Banker's algorithm)弥补了资源分配图算法只适用于每个资源类别中都只有一个实例的情况的缺陷，它支持每个资源类别不止一个的情况，但是效率不如分配图算法。类似于资源分配图算法需要在最开始给出所有 claim edge，银行家算法要求每个进程/线程给出执行过程中所需要的各类资源的最大量，同时维护一些数据以动态地计算安全状态。High level 地来讲，就是需要动态地检测某个资源申请是否会导致系统进入不安全状态，如果会导致系统进入不安全状态，则等待资源足够再分配。

更具体的来说，需要维护这些东西（假设问题中有 n 个进程/线程和 m 种资源）：

data structure

Available[m]: number of available resources of each type.
Max[n][m]: maximum demand of each thread.
Allocation[n][m]: number of resources of each type currently allocated to each thread.
Need[n][m]: remaining resource need of each thread.
Need[i][j] = Max[i][j] - Allocation[i][j] always holds true.
所以逻辑上这个式子应当是冗余的，但是取名有利于之后的流程阐述，所以我在这里保留；

银行家算法分为两个部分，分别是安全算法(safety algorithm)和资源请求算法(resource request algorithm)。前者检测当前状态是否处于不安全状态，后者以前者为基础，判断是否允许当前资源请求发生。

安全算法¶

首先初始化两个向量：

Work：长度为 m（资源种类数），初始值为当前可用资源 Available。
Finish[i]：长度为 n（进程数），初始全为 false，表示所有进程都未完成。

寻找可完成的进程：找到一个进程 i，满足：

该进程尚未完成：Finish[i] == false
该进程所需资源 ≤ 当前可用资源：Need[i] ≤ Work 如果找不到这样的进程，跳转到第 4 步。

模拟进程完成：

将该进程已分配的资源归还给系统：Work = Work + Allocation[i]
标记该进程已完成：Finish[i] = true
返回第 2 步继续查找下一个可完成的进程。

判断系统是否安全：若所有进程的 Finish[i] 都为 true，说明存在一个安全序列，系统处于安全状态；否则为不安全状态。

资源请求算法¶

Request_i[j] = k 的意思是进程 \(P_i\) 希望得到 \(k\) 个 \(R_j\) 资源

检查请求是否合法：

若 Request_i ≤ Need_i，表示进程的请求未超过其最大需求，继续下一步；
否则，触发错误，因为进程请求的资源超过了它之前声明的最大值，这是不允许的。

检查资源是否可用：

若 Request_i ≤ Available，说明当前系统有足够的可用资源满足请求，进入第 3 步；
否则，进程必须等待，直到资源可用。

模拟分配并检查安全性：

假设将资源分配给进程 P_i，临时修改系统状态：
Available = Available - Request_i（减少可用资源）
Allocation_i = Allocation_i + Request_i（增加该进程已分配资源）
Need_i = Need_i - Request_i（更新剩余需求）
调用安全算法（Safety Algorithm）检查系统是否仍处于安全状态：
如果系统是安全的 → 真实分配资源给 \(P_i\)；
如果系统不安全 → 拒绝请求，恢复原状态，\(P_i\) 必须等待。

Example

(1) Safe

(2) Yes

(3) No

(4) No

6.5 Deadlock Detection¶

6.5.1 Single Instance of Each Resource Type¶

化简资源分配图为等待图，节点就是进程，箭头 \(P_i\rightarrow P_j\) 代表 \(P_i\) 在等待 \(P_j\)。检测死锁的过程就是检查当前等待图是否有环。

6.5.2 Several Instances of a Resource Type¶

Available（可用资源向量）：一个长度为 m 的向量，表示每种资源类型的可用实例数量。

Allocation（分配矩阵）：一个 n×m 的矩阵，表示每个进程当前已分配的各类资源数量。

Request（请求矩阵）：一个 n×m 的矩阵，表示每个进程当前对各类资源的请求量。

整个检测流程如下

设 Work 和 Finish 分别为长度为 m 和 n 的向量。初始化：

(a) Work = Available (b) 对于 i = 1,2,...,n，若 Allocation_i ≠ 0，则 Finish[i] = false；否则，Finish[i] = true。

寻找一个下标 i，使得同时满足： (a) Finish[i] == false (b) Request_i ≤ Work

如果不存在这样的 i，则转到步骤 4。

将当前进程 \(P_i\) 的分配资源加到工作向量 \(\text{Work}=\text{Work}+\text{Allocation}_i\) 标记该进程已完成：Finish[i]=true，返回步骤 2 继续查找下一个可完成的进程。
如果存在某个进程\(P_i\)（\(1\leq i\leq n\)），其 Finish[i]=false ，则系统处于死锁状态。此时，所有满足 Finish[i]=false 的进程\(P_i\)均为死锁进程。

该算法的时间复杂度为 \(O(m\times n^2)\)，用于检测系统是否处于死锁状态。

6.5.3 Detection-Algorithm Usage¶

我们应该何时调用、以及多久调用一次？决于以下两个因素：

死锁发生的频率

如果系统中死锁频繁发生，则应更频繁地运行检测算法（如定期执行），以尽早发现并处理。
如果死锁很少发生，可以减少检测频率，以节省系统开销。

需要回滚多少个进程

检测到死锁后，通常需要终止或回滚部分进程来释放资源。
若涉及的进程较多，恢复代价高，因此应谨慎选择检测时机，避免频繁触发大规模回滚。

6.6 Recovery from Deadlock¶

打破死锁两种方法：

进程终止
抢占资源

6.6.1 Process Termination¶

对于进程终止的方法，可以选择

终止所有死锁进程，简单直接可以一次性结束所有处于死锁状态的进程。优点是快速解决死锁。缺点就是代价高，可能浪费大量已执行的工作，影响用户体验。
逐个终止进程，直到死锁环被打破，每次只终止一个进程，然后重新检查是否仍存在死锁。优点是尽量减少终止的进程数量，降低损失。缺点就是恢复过程较慢，可能需要多次尝试。

选择终止哪个进程时，需考虑多个因素：

进程的优先级（Priority of the process）→ 优先终止低优先级进程，保留重要任务。
进程已计算的时间和剩余完成时间（How long process has computed, and how much longer to completion） → 优先终止已完成较少、剩余时间较长的进程，避免浪费更多资源。
进程已使用的资源量（Resources the process has used） → 优先终止占用资源少的进程，释放资源更高效。
进程完成所需资源（Resources process needs to complete）→ 优先终止需求资源多的进程，因为其释放的资源可能更多。
需要终止多少个进程（How many processes will need to be terminated）→ 选择能最小化总终止数的方案。
进程是交互式还是批处理（Whether the process is interactive or batch）→ 优先终止批处理进程，因为它们通常不与用户交互，中断影响较小；保留交互式进程以保证用户体验。

6.6.2 Resource Preemption¶

从某个进程手中强行收回资源，并将其分配给其他进程，以打破死锁循环。

系统需要选择一个或多个“受害者”进程，从中抢占资源。目标是最小化恢复成本

抢占资源后，被选中的“受害者”进程需要回退到之前的一个安全状态，然后重新启动该进程，从那个安全点开始执行。

如果不加控制，同一个进程可能反复被选为“受害者”，导致它永远无法完成。所以在选择受害者时，可以将“回退次数”纳入代价函数

评论区

对你有帮助的话请给我个赞和 star =>

欢迎跟我探讨！！！