www.876873.xyz

在关系型数据库的工程实现中，死锁检测（Deadlock Detection）是整个锁体系中最消耗计算资源的核心算法。死锁绝对不是应用层抛出的一个简单报错，而是一场发生在共享内存中，涉及硬件中断、有向图算法（DFS）、轻量级闩锁（LWLock）拦截与内存指针重排的物理级战役。

我们现在彻底剥离所有的概念包装，完全基于 PostgreSQL 底层的 C 语言指针流转，按操作系统的绝对时间轴，对死锁检测的整个生命周期进行“慢动作逐帧拆解”。

---

第一帧：物理蛰伏与时钟挂载（deadlock_timeout 的工程妥协）

【物理背景】

假设进程 PGPROC_A 试图获取 LOCK_2，但通过底层位运算发现 LOCK_2 的 grantMask 与自身的请求掩码发生绝对冲突（例如申请 3 级锁，但表上挂着 8 级强锁）。

【拆解动作】

1. 状态入列：PGPROC_A 生成一个契约结构体挂入 LOCK_2->procLocks，同时将其自身的内存地址（进程指针）追加到 LOCK_2->waitProcs（休眠队列）的尾部。
2. 指针定格：内核将 PGPROC_A->waitLock 指针，死死指向 LOCK_2。这在图论中相当于画出了等待图的第一条半成品边。
3. 时钟挂载与断电：在调用系统底层的 SemSleep() 交出 CPU 算力陷入沉睡的前一个纳秒，内核向操作系统的定时器注册了一个倒计时器。这个倒计时器的参数就是著名的 deadlock_timeout（默认 1000 毫秒）。
4. 架构师推演：为什么不立刻检测？因为构建有向等待图（WFG）并进行深度优先搜索（DFS）的时间复杂度是 $O(V+E)$。如果在双十一等高并发场景下，每一次正常的锁排队都去执行 $O(V+E)$ 的图遍历，数据库会被自己的死锁检测器瞬间榨干 CPU 算力。因此，死锁检测必须是“惰性”的，用 1 秒钟的休眠来过滤掉 99.9% 的正常排队。

---

第二帧：硬件打断与全局冻结（触发 CheckDeadLock）

【物理动作】

1. 中断唤醒：1000 毫秒倒计时结束。操作系统底层触发硬件级别的 SIGALRM 时钟中断。
2. 状态核验：该中断强行向休眠中的 PGPROC_A 发出通电信号。PGPROC_A 醒来后，第一件事是检查自己是否真的拿到了锁（比对 PROCLOCK->holdMask）。发现请求位依然是 0，确认自己是被时钟强行叫醒的。
3. 引擎跳转：内核控制流发生硬跳转，强制 PGPROC_A 载入死锁检测的核心 C 语言函数：CheckDeadLock()。
4. 全局冻结（极其昂贵的操作）：为了防止在顺藤摸瓜排查指针时，其他进程修改了内存链表导致段错误（Segmentation Fault）。PGPROC_A 必须瞬间申请并死死握住锁管理器的核心分区轻量级锁（LockManager LWLocks）。此时，全库所有关于重量级锁的申请和释放操作，遭遇物理级物理阻塞。

---

第三帧：内存指针的 DFS 图遍历（WFG 拓扑生成）

此时，PGPROC_A 化身为探测器，开始在内存中顺着指针画图：

1. 确立起点与目标：探测器读取自身 PGPROC_A->waitLock，发现指针指向 LOCK_2。
2. 寻找持锁元凶（找硬边）：探测器顺着 LOCK_2 结构体，去遍历挂在它身上的 procLocks 双向链表。它会逐一比对链表里每一个 PROCLOCK 结构体的 holdMask。只要发现 holdMask 中包含与 PGPROC_A 冲突的掩码位（例如存在 8 级锁），就顺着这个 PROCLOCK 的 PGPROC 指针往上摸。
3. 锁定下一个节点：探测器摸到了 PGPROC_B。在内存逻辑中，正式确立一条有向图边：PGPROC_A $\rightarrow$ PGPROC_B。
4. 递归下潜：探测器继续读取 PGPROC_B->waitLock，发现 PGPROC_B 正在等待 LOCK_1。
5. 再次遍历与闭环（Cycle Detected）：探测器遍历 LOCK_1->procLocks 链表，寻找谁霸占着 LOCK_1。最终，指针顺藤摸瓜，指向了内存地址为 PGPROC_A 的结构体。
6. 算法判决：DFS 递归栈在执行地址匹配时，发现当前遍历到的节点地址，与搜索起点的节点地址呈现 完全重合。死锁闭环在底层 C 语言的指针拓扑中被物理实锤。

---

第四帧：拓扑研判与软边缘重排（内核的最后抢救）

在确认闭环后，PostgreSQL 内核并不会立刻执行斩杀，而是会执行一种极其精妙的**“软等待重排（Soft Edge Rearrangement）”**算法。

【硬等待与软等待的物理界定】

• 硬边（Hard Edge）：你等待的锁，被别人实实在在地攥在手里（对方的 holdMask 对应位为 1）。这种边在物理上是绝对不可逾越的。
• 软边（Soft Edge）：你等待的锁，别人也还没拿到，但是别人排在休眠队列（waitProcs）的更前面。你是因为队列顺序而被迫等他。

【重排逻辑】

如果死锁探测器在 WFG 图中发现闭环是由“软边”构成的，它会尝试在内存中直接修改 LOCK->waitProcs 双向链表的物理顺序。

• 探测器将排在后面的进程指针强行 unlink（摘除），并 insert（插入）到前面的进程之前。
• 如果仅仅通过交换链表的排队位置，就能让图论算法重新计算时不再出现闭环，那么死锁警报解除，PGPROC_A 释放 LWLock 闩锁，重新调用 SemSleep 回去继续排队，没有任何事务会被牺牲。

---

第五帧：物理斩杀与内存撕裂（AbortTransaction）

如果所有的重排尝试都宣告失败（例如全是由实打实的 holdMask 占有构成的纯硬边闭环），必须执行斩首。

1. 牺牲者选定：为了追求极致的代码执行效率，内核通常直接判定触发 CheckDeadLock() 的当前进程（即 PGPROC_A）为牺牲者（Victim）。
2. 释放全局冻结：PGPROC_A 释放此前持有的分区 LWLock，让全库其他无关的并发请求恢复运转。
3. 抛出异常与撕裂：PGPROC_A 向前端抛出 ERROR: deadlock detected 异常信号。执行引擎强制进入 AbortTransaction() 回滚流程。
4. 链表大清理：
   • PGPROC_A 沿着自己的 PGPROC_A->myProcLocks 链表，将自己持有的所有 PROCLOCK 契约结构体从资源表中强行摘除。
   • 调用 pfree() 物理释放这些结构体的内存。
5. 状态掩码重算与精准通电：
   • PGPROC_A 原本霸占的 LOCK_1 的 grantMask 被重新计算（掩码位清零）。
   • 锁管理器顺势看向 LOCK_1->waitProcs 的队列头部，提取出 PGPROC_B 的进程指针。
   • 调用操作系统底层原语 SemWakeup。PGPROC_B 的 CPU 核心瞬间获得通电，成功进行位运算并拿到 LOCK_1。物理死锁彻底破除。

---

这就是死锁检测的极致工程拆解。它不是一个被动发生的报错，而是一场由定时器中断触发、通过LWLock 冻结全局、基于内存指针进行 DFS 图遍历，并在最后穷尽软边缘链表重排后，才不得不执行的内存清理机制。这种深度的底层逻辑体系，完全对标了数据库原厂内核研发或高级架构师的排障视角。