专栏首页架构说每日一题:死锁检测和图的拓扑排序

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

题目

抽象模型

检测模型

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

一言以蔽之: 死锁的发生, 必然意味着有向图(依赖关系)的构建存在环.   关于检测模型, 我们可以这么假定, 锁为有向边, 申请锁的线程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.

本文分享自微信公众号 - 架构说(JiaGouS),作者:从青铜到王者

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-06-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Uber 的 Docker Mysql 应用

    背景介绍 Uber的MySQL集群规模很大,超过1000个集群,共有4000多个数据库服务器。 问题 起初是使用Puppet管理,写了很多脚本,再加上一些人工操...

    dys
  • 10种常用的图算法直观可视化解释

    图已经成为一种强大的建模和捕获真实场景中的数据的手段,比如社交媒体网络、网页和链接,以及GPS中的位置和路线。如果您有一组相互关联的对象,那么您可以使用图来表示...

    deephub
  • 给广大码农分享福利:一个业界良心的github仓库,中文计算机资料

    我今天查资料时无意发现的,https://github.com/CyC2018/CS-Notes

    Jerry Wang
  • 给广大码农分享福利:一个业界良心的github仓库,中文计算机资料

    版权声明:本文为博主汪子熙原创文章,未经博主允许不得转载。 https://jerry.blog....

    Jerry Wang
  • 图由两个部分组成,一是点node,二是边edge。 图的表示方法由邻接表法和邻接矩阵法。当然还有其他的方式。 如下所示,有一无向图,其邻接表和邻接矩阵示意图为:

    用户1145562
  • 浅谈SD-WAN的故障排除

    当SD-WAN出现问题或者您怀疑它导致应用程序出现问题时,您会怎么做?当然是,排除故障。

    SDNLAB
  • 云帮(ACP)7月升级:重构负载均衡,优化后端组件功能

    Rainbond开源
  • 拓扑排序

    在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该...

    风骨散人Chiam
  • MySQL高可用复制管理工具: Orchestrator使用

    在上一篇中大致介绍了Orchestrator的功能、配置和部署,当然最详细的说明可以查阅官方文档。本文开始对Orchestrator的各方面进行测试和说明。

    田帅萌
  • MySQL高可用复制管理工具: Orchestrator使用

    在上一篇「MySQL高可用复制管理工具:Orchestrator介绍」中大致介绍了Orchestrator的功能、配置和部署,当然最详细的说明可以查阅官方文档。...

    田帅萌
  • MySQL高可用复制管理工具: Orchestrator使用

    在上一篇「MySQL高可用复制管理工具:Orchestrator介绍」中大致介绍了Orchestrator的功能、配置和部署,当然最详细的说明可以查阅官方文档。...

    用户1278550
  • 什么是事件驱动架构(EDA)?

    Simply put, the event is a significant change in state, which is triggered when ...

    一个会写诗的程序员
  • 云帮(ACP)7月升级:重构负载均衡,优化后端组件功能

    以应用为中的无服务器PaaS——云帮ACP基于容器技术研发,社区版针对个人、企业完全免费,您可以自由的下载与传播。借助它您可以实现:

    Rainbond开源
  • InnoDB数据锁–第4部分“调度”

    在本系列博客中,我将描述InnoDB如何对数据(表和行)加锁,以向用户提供查询是按顺序执行的错觉,以及在最近的发行版中如何对此进行了改进。

    MySQLSE
  • 图的拓扑排序的算法实现,C语言,栈,超详细版本

    拓扑排序在工程管理领域中的应用广泛,可用于判断工程能否顺利开展,即判断有向图中是否存在回路。对于一个有向图,先由键盘输入其顶点和弧的信息,采用恰当存储结构保存该...

    Java架构师必看
  • 拓扑排序,YYDS!

    很多读者留言说要看「图」相关的算法,那就满足大家,结合算法题把图相关的技巧给大家过一遍。

    labuladong
  • MySQL监视工具MEM

    MySQL在企业版里提供了一个监视工具——MySQL Enterprise Monitor 简称MEM。可以使用MEM对MySQL实例和主机进行监视,发现潜在的...

    MySQLSE
  • (七):C++分布式实时应用框架 2.0

    版权声明:本文版权及所用技术归属smartguys团队所有,对于抄袭,非经同意转载等行为保留法律追究的权利!

    smartguys
  • 谈谈MySql的死锁问题

    线上某服务时不时报出如下异常(大约一天二十多次):“Deadlock found when trying to get lock;”。

    xcbeyond

扫码关注云+社区

领取腾讯云代金券