聊聊死锁检测算法的核心逻辑

上次跟一个找工作的后端开发学弟聊天，他说面试的时候被问死锁检测算法，支支吾吾答不上来，回去翻了好几篇博客还是没搞明白核心到底在哪，说那些文章全是干巴巴的概念，越看越晕。其实吧，死锁这玩意儿说复杂也复杂，说简单也简单，核心逻辑捋顺了，不管是面试还是干活都能拎得清，根本不用死记硬背那么多概念。

死锁检测算法的基本定位

很多新手上来就混淆几个概念，把死锁预防、死锁避免和死锁检测搞成一团，其实你得先分清楚，死锁检测到底是做什么的？简单说，前面两种都是提前出手，不让死锁发生。死锁检测不是这样，它允许死锁出现，只是要你及时发现它在哪里，是什么导致的，方便后续处理。

为什么会有这种设计思路？你想啊，如果要求所有系统都提前预防死锁，那资源利用率得多低？比如要求进程一次性把所有需要的资源都申请到手才开始运行，那很多进程占着资源不用，其他进程干等着，整个系统的效率就掉下去了。反过来，允许偶尔出现死锁，但是靠死锁检测及时找到它，杀掉一两个卡住的进程释放资源，整个系统还能正常跑，资源利用率反而更高，这也是现在大部分大型系统都用这种思路的原因。

什么时候需要运行死锁检测

不是所有系统都要时时刻刻跑死锁检测的，这点很多人都没搞清楚。比如那种小型的嵌入式设备，就跑一两个固定的进程，根本不存在多个进程抢资源的情况，那自然没必要浪费性能跑检测。还有一些对实时性要求极高的系统，哪怕死锁一分钟都出大事，这种就干脆提前做好预防，根本不给死锁发生的机会，也不用做检测。

什么时候必须做？那肯定是大型并发系统啊，比如电商后台、分布式数据库、云原生的容器集群，几十上百个进程同时跑，资源争抢是家常便饭，这种时候就得定期跑死锁检测。我之前碰见过一个做电商的朋友，就是嫌检测占性能，给关了，结果大促的时候突然系统整个卡壳，找了两个小时才发现是死锁，光退款就赔了小十万，说起来都是泪。所以说该开的检测还是得开，别省那点性能吃大亏。

死锁检测算法的核心逻辑其实就两步

说出来你可能不信，不管是什么类型的死锁检测，不管是单体系统还是分布式系统，核心逻辑翻来覆去就两步，根本没那么多花里胡哨的东西。第一步，梳理清楚当前系统里所有进程和资源的占有等待关系，谁占着哪个资源，哪个进程在等谁占着的资源，把这个关系理清楚。第二步，在这个关系里找循环等待的链路，只要找到了，那就肯定存在死锁了。

举个最简单的例子，进程A占着数据库的写锁，等着拿进程B占着的缓存锁；进程B占着缓存锁，又等着拿进程A占着的写锁，这不就是一个典型的循环等待吗？一找一个准，死锁直接实锤。就这么简单，那些复杂的实现方法，其实都是在这个核心逻辑上做优化，本质没变。

常见实现方式的差异在哪

现在大家常说的几种实现，其实都是围绕核心逻辑做适配。比如资源分配图化简法，就是刚才说的把关系画成图，先把那些没在等待的进程和它们占的资源去掉，剩下的图里如果还有环，那就是死锁，这种方法直观，适合小系统。银行家算法其实是提前预判，就是在分配资源之前先算一下，如果把这个资源分给请求的进程，后续会不会出现循环等待，本质上还是找会不会有死锁，也算检测的一种延伸。

还有那种最简单的超时检测，就是说一个进程等资源超过一定时间还没拿到，就默认它死锁了，直接杀掉。这种方法简单粗暴，不用算那么多复杂的关系，省系统资源，适合对精度要求不高的场景，缺点就是可能误杀，有些只是慢不是死锁，结果也被杀了，不过总比整个系统卡着强吧。

现在分布式系统越来越火，很多人说分布式死锁难搞，其实核心逻辑还是一样的，还是找循环。只不过原来的关系都在一个节点上，现在资源分散在不同节点，就得把各个节点的等待链路收集起来，再统一找循环。我之前帮朋友排查过一次分布式死锁，他们原来每个节点自己做检测，结果每个节点看自己都没问题，因为循环跨了三个节点，每个节点只看到一部分，后来改成全局收集再检测，一下子就找到问题了。所以说核心逻辑没变，只是实现的时候要跟着架构调整而已。

讲了这么多，其实核心就是那句话，别被那些复杂的名词唬住，把最底层的逻辑捋清楚了，再看各种实现方法就很容易明白。不管是面试背题，还是实际排查问题，顺着核心逻辑推，都不会错到哪去。你说是不是这么个理儿？