1 简介

死锁是系统中的一个基本问题。进程可以按任何顺序请求资源，同时可以在保留其他资源的再请求额外资源。
这死锁的发生通常是指一组进程被阻塞的现场，
这是系统中的每个进程都持有一些资源，并且其他一些进程需要获取的资源正好是已被使用的资源。

死锁检测算法有两种类型：

Wait-for-Graph 算法（单实例） — 一般看着是 RAG资源分配图的变体。
Banker’s Algorithm (Multiple Instance)

2 等待图 （WFG） 算法

构建 WFG − 第一步是构建一个显示进程之间 waitfor 关系的等待图 （WFG）。
它是 Resource Allocation （资源分配） 图形的变体。
它们的区别是：

 资源分配图RAG： 包含进程和资源。
  等待图WFG：仅包含从 Resource Allocation Graph 转换时删除 Resources 后 Processes。

在这个算法中，我们只将进程作为图中的顶点。
如果 Wait-for-Graph 包含一个循环，那么我们可以说系统处于 Deadlock 状态。
现在，我们将讨论如何在算法方法中将 Resource Allocation 图（RAG）转换为 WFG(Wait-for-Graph)。
在从 Resource Allocation Graph 转换为 Wait-for-Graph 时，我们需要删除资源。

每个进程都由一个圆圈表示，如果前者正在等待后者持有的资源，则会从一个进程绘制一个箭头到另一个进程。

检查周期 − 在 WFG 中查找周期。如果存在循环，则表示系统死锁。

识别死锁的进程 − 识别周期中涉及的进程。这些进程处于死锁状态，并等待其他进程占用的资源。

确定资源类型 - 确定死锁中涉及的资源类型，以及每个进程持有和请求的资源。

采取纠正措施 - 采取纠正措施，通过释放资源、中止进程或抢占资源来打破僵局。一旦死锁被打破，系统就可以继续进行正常操作。

重新检查周期 − 采取纠正措施后，重新检查 WFG 的周期。如果没有更多周期，则系统不再死锁，并且可以恢复正常操作。

为了确认是否存在死锁，我们可以在 WFG 上使用循环检测算法。该算法将检测循环并识别 P2 和 P3 之间的潜在死锁。然后，我们可以采取适当的措施来解决死锁并防止它将来发生。

• WAF算法步骤

步骤1：从资源分配图中获取第一个进程 （Pi），并检查它获取资源的路径 （R我），然后使用该特定进程启动 wait-for-graph。

步骤2：为 Wait-for-Graph 创建一个路径，其中当前进程中将不包含 Resource （P我） 到下一个进程 （Pj），从下一个过程 （Pj） 查找资源 （Rj） 将被下一个进程获取 （Pk），该 （Pj).

步骤3：对所有过程重复步骤 2。

步骤4：完成所有进程后，如果我们发现一个闭环循环，则系统处于死锁状态，并检测到死锁。

3 实例

如下一个资源分配图RAG，其中包含 4 个进程 P1、P2、P3、P4 和 4 个资源 R1、R2、R3、R4。使用 Wait for Graph based deadlock detection 算法查找 Graph 中是否存在死锁。

步骤1：首先取正在等待资源 R1 的进程 P1，资源 R1 被进程 P2 获取，开始对上述资源分配图进行等待图。

P1

步骤2：现在我们可以观察到，有一条从 P1 到 P2 的路径，因为 P1 正在等待 P2 获取的 R1。现在，在删除资源 R1 之后，Graph 将如下所示。

P1 —> P2

步骤3：从 P2 我们可以观察到从 P2 到 P3 的路径，因为 P2 正在等待 P3 获取的 R4。所以在删除资源 R4 后，从 P2 到 P3 的路径是这样的。

P1 —> P2 —> P3

步骤4：从 P3 中，我们找到了一条通往 P4 的路径，因为它正在等待 P4 获取的 P3。删除 R3 后，图形如下所示。

P1 —> P2 —> P3 —> P4

步骤5：在这里，我们可以发现进程 P4 正在等待 P1 获取的 R2。所以最后 Wait-for-Graph 如下：

步骤6：最后，在这个图表中，我们发现了一个循环，因为过程 P4 再次回到过程 P1，这是一个起点（即，它是一个闭环）。

所以，根据算法，如果我们发现了一个闭环，那么系统就处于死锁状态。所以在这里我们可以说系统处于死锁状态。

需要注意的是，即使它看起来像一个循环，但是没有流程回到起点（即，没有闭环）。
所以，根据算法，如果我们发现了一个闭环，那么系统就处于死锁状态。但在这里我们没有找到任何闭环，所以系统没有处于死锁状态。系统处于安全状态。

注意：如上图即使它看起来像一个循环，但从P1出发的进程请求没有最终回到P1，而是在等待P3，因此没有进程到达第一个进程或再次起点。所以没有闭环不构成死锁。

4 小结分析

优势

  可以处理多种类型的资源

  适用于具有大量进程的系统

  提供死锁的清晰可视化

弊端

  对于大型系统来说可能很耗时

  如果对同一资源有多个请求，则可能会提供误报

假设所有资源都是预先分配的，这在某些系统中可能并非如此。
对于我们称为 WFG 检测算法的每个资源，如果有很多资源，CPU 的计算时间会非常长。解决方案是，而不是为每个无法立即授予的资源请求调用此算法。