每日一题：死锁检测和图的拓扑排序

题目

抽象模型

检测模型

死锁的发生, 必然意味着有向图(依赖关系)的构建存在环.

一言以蔽之: 死锁的发生, 必然意味着有向图(依赖关系)的构建存在环. 　　关于检测模型, 我们可以这么假定, 锁为有向边, 申请锁的线程A为起点, 拥有锁的线程B为终点. 这样就形成线程A到线程B的一条有向边. 而众多的锁(边)和线程(点), 就构成了一个有向图. 　　于是乎, 一个死锁检测的算法, 就转变为图论中有向图的环判断问题. 而该问题, 可以借助成熟的拓扑遍历算法轻易实现.

死锁发生条件：

1. 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链， 即进程集合{P1，P2，···，Pn}中的 P1 正在等待一个 P2 占用的资源 ；P2 正在等待 P3 占用的资源，……， Pn 正在等待已被 P0 占用的资源

可证明结论：

• 如果资源分配图没有环，那么系统就不处于死锁状态 如果没有环存在，那么资源的分配会使得系统处于安全状态；
• 如果图有环，那么系统可能处于死锁状态: 如果有环存在那么分配会导致系统处于非安全状态

1. 如果每一种资源类型只有一个实例，那么死锁一定发生
2. 如果一种资源类型有多个实例，则可能死锁

死锁检测：

• 每当一个线程获得了锁，会在线程和锁相关的数据结构中（map、graph等等）将其记下。除此之外，每当有线程请求锁，也需要记录在这个数据结构中。
• 当一个线程请求锁失败时，这个线程可以遍历锁的关系图看看是否有死锁发生

系统资源分配图（system resource-allocation graph） 二元组G=（V，E）

• 一个顶点的集合V和边的集合E(图定义定点和边结合) V被分为两个部分

P={P1,P2,...,Pn},含有系统中全部的进程

R={R1,R2,...,Rm},含有系统中全部的资源

• 申请边：有向边Pi->Rj,表示进程Pi申请了资源Rj的一个实例 （图的出度）
• 分配边：有向边Rj->Pi,表示资源Rj的一个实例分配给进程P （图的入读）

练习

Daily Challenge 207. 课程表 （c++）

示例代码

https://ivanzz1001.github.io/records/post/cplusplus/2018/11/15/linux-deadlock-detect#4-%E4%BD%BF%E7%94%A8pstack%E5%92%8Cgdb%E5%B7%A5%E5%85%B7%E5%AF%B9%E6%AD%BB%E9%94%81%E7%A8%8B%E5%BA%8F%E8%BF%9B%E8%A1%8C%E5%88%86%E6%9E%90

使用pstack和gdb工具对死锁程序进行分析

6. 利用valgrind(DRD+Helgrind)来分析死锁

项目

• https://blog.csdn.net/zdy0_2004/article/details/44652323

塔山

[1] 死锁问题分析的利器：Helgrind https://www.valgrind.org/docs/manual/hg-manual.html

[2] MySQL 死锁检测源码分析https://leviathan.vip/2020/02/02/mysql-deadlock-check/

https://dev.mysql.com/doc/refman/8.0/en/innodb-deadlock-example.html

[3] How to detect and find out a program is in deadlock?

[4] https://www.valgrind.org/docs/manual/hg-manual.html 官方手册 必须看

7.3. Detected errors: Inconsistent Lock Orderings

In this section, and in general, to "acquire" a lock simply means to lock that lock, and to "release" a lock means to unlock it.

Helgrind monitors the order in which threads acquire locks. This allows it to detect potential deadlocks which could arise from the formation of cycles of locks. Detecting such inconsistencies is useful because, whilst actual deadlocks are fairly obvious, potential deadlocks may never be discovered during testing and could later lead to hard-to-diagnose in-service failures.

The simplest example of such a problem is as follows.

• Imagine some shared resource R, which, for whatever reason, is guarded by two locks, L1 and L2, which must both be held when R is accessed.
• Suppose a thread acquires L1, then L2, and proceeds to access R. The implication of this is that all threads in the program must acquire the two locks in the order first L1 then L2. Not doing so risks deadlock.
• The deadlock could happen if two threads -- call them T1 and T2 -- both want to access R. Suppose T1 acquires L1 first, and T2 acquires L2 first. Then T1 tries to acquire L2, and T2 tries to acquire L1, but those locks are both already held. So T1 and T2 become deadlocked.