Mitchell Merritt 分布式死锁检测算法

基本算法

模型

采用最基本的 wait-for 图模型，即每个节点是一个 process，每条边代表起点对应的 process 需要的被终点 process 持有。

对每个节点，有两个 label，一个 public，一个 private。

算法流程

• 所有进程开始时会被分配一个唯一的 label，此时 public_label == private_label == 这个 label
• 当一个进程（process_waiting）开始等待其他进程（process_waited）时，添加等待边：

  new_label = max(process_waiting.process_waiting, process_waited.public_label) + 1
  process_waiting.public_label = new_label
  process_waiting.private_label = new_label
  

• 当一个进程结束等待（可能成功获取了需要的资源，也可能运行超时）后，只需断开等待边即可
• 等待中的进程（process_waiting）需要时不时地检查它正等待的那个进程（process_waited）的 public_label 是否大于自己的，如果大于，则 process_waiting.public_label = process_waited.public_label
• 进程发现自己的 public_label 再次等于自己的 private_label，则说明发生了死锁，此时可以终结自己断开死锁环

改进

对于有优先级的系统，我们再给每个进程添加 public_priority 和 private_priority 属性。

• 在“时不时检查”这一步，如果 process_waited.public_label > process_waiting.public_label || (process_waited.public_label == process_waiting.public_label && process_waiting.public_priority > process_waited.public_priority)，则：

  process_waiting.public_label = process_waited.public_label
  process_waiting.public_priority = min(process_waited.public_priority, process_waiting.private_priority)
  

• 进程发现自己的 process_waited.public_label == process_waiting.public_label && process_waited.public_priority == process_waiting.public_priority && process_waiting.public_priority == process_waiting.private_priority，则说明发生了死锁，且自己是死锁环中优先级最低的，此时可以终结自己断开死锁环

评价

实践上可能效率还不如直接中心化死锁检测……