分布式系统中的死锁检测

在本文中，您将学习分布式系统中的死锁检测，包括其方法、处理策略、问题和解决方法。

什么是分布式死锁？

当在分布式系统中使用分布式事务或并发控制时，可能会发生分布式死锁。它可以通过分布式技术（如边缘追踪）或在死锁检测器处从局部等待图（WFG）创建全局等待图来识别。幻象死锁是在分布式系统中被检测到，但由于内部系统延迟而实际并不存在的死锁。

在分布式系统中，死锁既不能预防也无法避免，因为系统规模太大。因此，只能进行死锁检测。分布式系统的死锁检测技术需要满足以下要求：

1. 进展性 (Progress)

该方法能够检测到系统中的所有死锁。

2. 安全性 (Safety)

该方法必须能够检测到所有系统死锁。

分布式系统中检测死锁的方法

分布式系统中检测死锁的各种方法如下：

1. 集中式方法

在集中式方法中，只有一个资源负责检测死锁，这种方法简单易用。但其缺点包括：单个节点工作负载过大和单点故障（即整个系统依赖于一个节点，如果该节点发生故障，整个系统就会崩溃），从而降低了系统的可靠性。

2. 分层式方法

在分布式系统中，这是集中式和分布式死锁检测方法的结合。在这种策略中，一个节点管理一组选定的节点或节点集群，这些节点或集群负责死锁检测。

3. 分布式方法

在分布式技术中，多个节点协同工作以检测死锁。由于工作负载平均分配到所有节点，因此不存在单点故障。这也助于提高死锁检测的速度。

死锁处理策略

分布式系统中各种死锁处理策略如下：

1. 处理死锁主要有三种方法：死锁预防、死锁避免和死锁检测。
2. 在分布式系统中，处理死锁变得更加复杂，因为没有任何一个站点拥有系统当前状态的完整信息，而且每次站点间的通信都存在有限且不可预测的延迟。
3. 操作系统使用死锁避免方法来确定系统是处于安全状态还是不安全状态。进程必须告知操作系统为完成其执行可能请求的最大资源数量。
4. 死锁预防通常通过两种方式实现：让一个进程在开始执行前一次性获取所有必需的资源，或者抢占已拥有资源的进程。
5. 在分布式系统中，这种方法效率极低且不切实际。
6. 要检测死锁，需要检查进程资源交互的状态，以确定是否存在循环等待。
7. 处理分布式系统中的死锁的最佳方式似乎是死锁检测。

死锁检测的问题

分布式系统中死锁检测的各种问题如下：

1. 基于死锁检测的死锁处理需要解决两个基本问题：首先，检测现有的死锁；其次，解决已检测到的死锁。
2. 检测死锁又涉及两个问题：维护等待图（WFG）和在WFG中搜索循环的存在。
3. 在分布式系统中，一个循环可能涉及多个站点。搜索循环在很大程度上依赖于系统WFG在整个系统中的表示方式。

死锁检测的解决方法

分布式系统中死锁检测的各种解决方法如下：

1. 死锁解决包括打破系统WFG中现有的等待依赖关系。
2. 这包括回滚多个死锁进程，并将其资源分配给死锁中被阻塞的进程，以便它们能够恢复执行。

分布式系统中的死锁检测算法

分布式系统中各种死锁检测算法如下：

1. 路径推送算法
2. 边缘追踪算法
3. 基于扩散计算的算法
4. 基于全局状态检测的算法

路径推送算法

路径推送算法通过维护一个显式的全局WFG来检测分布式死锁。其主要思想是为分布式系统的每个站点创建一个全局WFG。当这类算法中的一个站点执行死锁计算时，它会将其本地WFG发送给所有相邻站点。“路径推送算法”这个术语源于其传递全局WFG路径的特点。

边缘追踪算法

边缘追踪方法通过沿着图的边缘发送称为“探针”的特殊消息来验证分布式图结构中的循环。这些探针消息不同于请求和响应消息。如果一个站点收到了它之前发送过的相应探针，它就可以取消循环的形成。

基于扩散计算的算法

在该算法中，死锁检测计算扩散到系统的WFG上。这些技术使用回声算法来检测死锁，底层的分布式计算叠加在此计算之上。如果此计算失败，发起者则报告一个死锁全局状态检测。

基于全局状态检测的算法

基于全局状态检测的死锁检测算法利用了以下事实：

1. 可以在不冻结底层计算的情况下获取分布式系统的一致性快照。
2. 如果在快照收集开始前系统中存在一个稳定属性，该属性将被保留下来。