等待图死锁检测结果

死锁是分布式系统中一个根本性的问题。一个进程可以以任意顺序请求资源，而某个进程在持有其他资源的同时仍然可以请求这些资源。所谓死锁，就是一组进程陷入僵局的情况——因为分布式系统中的每个进程都持有某些资源，而这些资源又被其他进程所需要。

示例：如果有三个进程p1、p2和p3，其中p1正在获取资源r1，而资源r1又被另一个进程p2所需要。此时，就会发生死锁现象。这就是所谓的“死锁”。

在上面的图表中，我们发现从P1到P2，然后再回到P1，形成了一个循环。因此，我们可以认为该系统处于死锁状态。关于死锁的问题，通常在分布式系统中被研究，所使用的模型包括以下几种：

• 该系统仅包含可重复使用的资源。
• 这些进程只能独占性地访问资源。
• 每种资源都只有一份。

死锁检测

这种僵局检测算法分为两种类型：

• 等待式图算法（单一实例）
• 银行家算法（多实例法）

等待式图算法

这是一种资源分配图的变体。在这种算法中，图中的顶点仅由进程构成。如果“等待图”中存在循环，那么可以认为系统处于死锁状态。在从资源分配图转换为“等待图”时，我们需要释放这些资源。

• 资源分配图：包含各种进程和资源。
• 等待图形：在从资源分配图转换过程中，仅包含那些经过处理后的流程，同时会移除原有的资源。

算法

以下是需要遵循的步骤：

• 步骤1：从资源分配图中选取第一个流程（Pi），然后查看该流程获取资源的路径。i启动一个与该特定进程相关的等待图形。
• 步骤2：为“Wait-for-Graph”创建一条路径，这条路径上不会包含来自当前进程的资源。i→ 下一个流程(P)j），从下一个流程中得来（P）j) 找到一种资源/Rj这些资产将由下一个流程来接收。k即从流程(P)中释放出来的东西。j).
• 步骤3：请对所有流程都重复步骤2的操作。
• 步骤4：在完成所有流程之后，如果我们发现系统处于一个闭环循环状态，那么系统就处于死锁状态，此时就会检测到死锁现象。

示例1：

假设有一个资源分配图，其中包含4个进程：P1、P2、P3、P4，以及4种资源：R1、R2、R3、R4。使用基于“等待时间”的死锁检测算法来判断该图中是否存在死锁情况。

首先，处理进程P1正在等待资源R1。而资源R1被处理进程P2获取了。为上述资源分配图创建一个等待状态图。

现在我们可以看到，存在一条从P1到P2的路径。因为P1正在等待由P2获得的资源R1。在移除资源R1之后，图的结构就会如下所示。

从P2出发，我们可以观察到一条从P2到P3的路径。因为P2正在等待R4的到达，而R4是由P3来处理的。所以，在去掉资源R4之后，从P2到P3的路径如下所示。

从P3出发，我们可以找到一条通往P4的路径。因为P4正在等待P3的到达，而P3已经被P4占领了。在移除R3之后，图的样子就如下所示。

在这里，我们可以看到，Process P4正在等待R2的响应，而R2是由Process P1来处理的。因此，最终的“等待图”如下所示：

注意：最后，在这张图中，我们发现了一个循环结构。因为过程P4又回到了过程P1，而过程P1正是起点（即，这是一个闭环）。根据算法规则，如果我们发现了一个闭环结构，那么系统就处于死锁状态。所以，我们可以说，这个系统目前处于死锁状态。

示例2：

现在，考虑另一个资源分配图，该图中包含4个进程：P1、P2、P3、P4，以及3种资源：R1、R2、R3。使用基于“Wait for Graph”的死锁检测算法，来判断该图中是否存在死锁情况。

首先，处理P1正在等待资源R1。而资源R1被处理P2获取了。为上述资源分配图创建一个等待状态图。

现在我们可以看到，从P1到P2有一条路径，同样地，从P1到P4也有一条路径。因为P1正在等待R1的完成，而R1是由P2完成的；同时，P1还在等待R2的完成，而R2则是由P4完成的。在去掉了R1和R2之后，图的样子如下所示。

从P2出发，我们可以观察到一条从P2到P3的路径。因为P2正在等待R3的到达，而R3是由P3来处理的。所以，在移除资源R3之后，从P2到P3的路径就变成了这样的样子。

在这里，我们可以看到Process P4正在等待R3的响应，而R3是由P3来处理的。因此，在移除Resource R3之后，Wait-for-Graph的显示效果如下所示。

在这个图中，我们没有发现任何循环路径，因为没有任何进程返回到起点。因此，根据算法规则，如果系统存在循环路径的话，那么系统就会处于死锁状态。但在这里，我们并没有发现任何循环路径，所以系统并不处于死锁状态。系统目前处于安全状态。

注意：在示例2中，虽然看起来像是一个循环过程，但实际上并没有任何进程能够再次回到起点或第一个阶段。因此，这里并不存在真正的闭环。

基于Wait-for-Graph的死锁检测算法存在的问题

对于每一个被标记为“WFG检测算法”的资源，如果资源数量很多的话，那么计算时间将会非常长。解决这个问题的方法就是：不必在每次有资源请求时都调用该算法。而是可以在一定时间间隔后才调用该算法。

• 可扩展性在拥有大量进程和资源的庞大系统中，图结构的维护成本会非常高。
• 间接费用/管理费用持续更新边信息（即处理等待关系的过程）会增加运行时的开销。
• 虚假的僵局检测如果频繁地检查该图结构，那么所出现的临时等待现象可能会被误认为是死锁现象。
• 延迟检测如果很少被触发的话，那么真正的死锁现象可能会在被发现之前持续很长时间。
• 复杂性在动态图中进行循环检测需要额外的计算资源。
• 分布式系统问题由于存在部分信息缺失以及消息传输延迟的问题，因此构建全球等待图是非常困难的。