总阅读量:次

⭐⭐⭐ Spring Boot 项目实战 ⭐⭐⭐ Spring Cloud 项目实战
《Dubbo 实现原理与源码解析 —— 精品合集》 《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》 《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》 《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》 《Java 面试题 + Java 学习指南》

摘要: 原创出处 飞天小牛肉 「飞天小牛肉」欢迎转载，保留摘要，谢谢！

🙂🙂🙂关注微信公众号：【芋道源码】有福利：

  1. RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表
  2. RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址
  3. 您对于源码的疑问每条留言都将得到认真回复。甚至不知道如何读源码也可以请教噢。
  4. 新的源码解析文章实时收到通知。每周更新一篇左右。
  5. 认真的源码交流微信群。

前言

死锁避免算法大部分小伙伴应该都能说出来 “银行家算法”，死锁检测算法确实不常问也不常见，最近在一篇 Bilibili 的三面面经中看见了死锁检测算法，遂写出此文。

死锁检测模型

在并发系统中，多个进程可能会因为资源竞争而陷入死锁。死锁检测模型提供了一种机制，通过将系统状态抽象为资源分配图，来识别死锁的存在。在这个图中，每个进程和资源都被表示为节点，资源和进程之间的有向边表示资源的分配和请求。

可证明结论：

  • 无环安全状态：如果资源分配图是一个无环图，系统处于安全状态，因为存在一种资源分配序列可以使得所有进程顺利完成。

  • 环存在不确定性：如果图中存在环，系统处于不安全状态，但不一定处于死锁状态

    • 当每种资源类型只有一个实例时，死锁一定发生
    • 如果资源类型有多个实例，系统也可能通过资源的动态分配来避免死锁

每种资源类型一个实例

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此一定会发生死锁。

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。具体算法描述如下：

  1. 初始化：创建一个资源分配图，用有向边表示资源和进程之间的关系。
  2. 深度优先搜索（DFS）：从任意一个进程开始，进行深度优先搜索。
  3. 标记访问：在搜索过程中，对访问过的节点（进程）进行标记。
  4. 检测环：如果在搜索中遇到了已经被标记的节点，说明存在环，即检测到死锁。

详细算法步骤：

  1. 选择一个未访问的进程作为起点。
  2. 进行DFS，访问其相邻的资源节点。
  3. 标记该进程为已访问。
  4. 如果从该进程出发可以回到任何已标记的进程，则存在死锁。
  5. 如果所有进程都被访问且没有形成环，则没有死锁。

每种资源类型多个实例

上图中，有三个进程四个资源，每个数据代表的含义如下：

  • E 向量：资源总量
  • A 向量：资源剩余量
  • C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量（P1、P2、P3 三个进程）
  • R 矩阵：每个进程请求的资源数量

进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，因此我们让 P3 先执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。这样的话 P2 就可以执行了，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行了。所有的进程都可以顺利执行，所以没有死锁。具体算法描述如下：

  1. 初始化：定义E（资源总量）、A（资源剩余量）、C（进程拥有的资源矩阵）和R（进程请求的资源矩阵）。
  2. 寻找可执行进程：选择一个请求资源不超过A的进程执行。
  3. 资源分配：将该进程请求的资源分配给它，并更新A和C。
  4. 进程完成：当进程执行完毕后，将其拥有的资源释放回A，并更新C。如果所有线程都可以顺利执行完毕，则没有死锁

详细算法步骤：

  1. 标记所有进程为未标记。
  2. 从所有未标记的进程中选择一个，其请求的资源向量Ri小于等于A。
  3. 将该进程的资源需求从A中减去，并更新C矩阵，标记该进程为已执行。
  4. 如果没有这样的进程，检查是否有任何进程可以执行。如果没有，则检测到死锁
  5. 重复步骤2和3，直到所有进程都被标记为已执行或检测到死锁

总结

总结下：

  • 对于每种资源类型一个实例的场景，若有环则必死锁；其死锁检测算法基于图论中的环检测技术，将死锁检测问题转化为有向图中的环判断问题
  • 对于没中资源类型多个实例的场景，有环不一定死锁；其死锁检测算法通过模拟资源分配和回收过程，检测是否存在一系列进程可以顺利获取资源完成执行，从而判断系统是否处于死锁状态
文章目录
  1. 1. 前言
  2. 2. 死锁检测模型
  3. 3. 每种资源类型一个实例
  4. 4. 每种资源类型多个实例
  5. 5. 总结