2.9 死锁检测
在进行多线程编程时，会限制多个线程对同一个临界区的访问，需要对这个临界区进行加锁。这种封锁通常讲究封锁的顺序，如果两个线程以不同的顺序封锁，就可能产生死锁。在数据库中也一样，例如PostgreSQL数据库中的轻量锁有多种类型，如果在不同的会话中（线程或进程）以不同的顺序进行轻量锁的封锁，就可能产生死锁。自旋锁和轻量锁属于系统锁，它们目前没有死锁检测的机制，所以需要数据库内核开发人员在开发过程中谨小慎微地规避死锁的产生条件，注意避免产生死锁。
而对于事务中的锁，则不能要求数据库的DBA在编写SQL的过程中实时地注意对各种数据库对象加锁。数据库的事务锁对DBA透明，这就需要数据库内核的开发人员来解决可能产生的死锁问题。
对于事务中的死锁，可以做如下定义：假设有一组事务{T1,T2,T3,…,Tn}，其中每个事务都在等待该集合中的另一个事务，这时该组事务中的每个事务都无法进行下一步动作，这就产生了死锁。对于事务中的死锁，不同的数据库有不同的处理方法。例如可以采用预防的方法避免死锁，这种方法把死锁扼杀在摇篮里；再如可以限制锁申请的优先级，这样就可以避免产生互相等待的情况。
在PostgreSQL数据库中，对申请事务锁的顺序没有严格的限制，在申请锁时也没有严格的检查，因此不可避免会发生死锁。PostgreSQL采用了另一种方法来做死锁检测：事务会定时对获得锁的事务和等待中的事务做检测，如果检测到死锁，则终止其中一个事务。
假设事务T1在等待事务T2，可以用一个有向图来表示，如图2-21所示。
图2-21 事务之间的等待关系
由死锁的定义可知，每个事务都在等待集合中的另一个事务，由于这个集合是一个有限集，因此在这个等待的链条中就会产生环，死锁检测的过程就变成了在有向图中找“环”的过程。
在常规锁申请过程中，假设事务A持有表的共享锁或排他锁，当事务B申请表的排他锁时，它就需要进入等待状态，即有等待关系B->A，PostgreSQL称这种等待的边为实边（Hard Edge）。
另一种情况，假设事务A持有共享锁，而事务B要申请的是排他锁，那么事务B就进入等待队列，此时又有事务C申请共享锁，事务C申请的共享锁和事务A持有的共享锁虽然不冲突，但是它和等待队列中的事务B持有的排他锁冲突，所以事务C也需要进入等待队列。虽然事务B和事务C都在等待队列中，但它们之间存在冲突关系C->B，我们称它们之间等待的边为虚边（Soft Edge）。实边和虚边如图2-22所示。
图2-22 实边和虚边
在死锁检测过程中，需要注意事务等待图中的实边和虚边。假设等待图中有环（也就是存在死锁可能），而且这个等待环全部是由实边构成的，那么此时只能中断某个事务来打破这个环。因为这个等待环已经实际构成，所以已经无法通过调整事务的顺序来解除死锁。
假如等待环中存在一条或多条虚边，由于虚边的两个顶点都在等待队列中，也就是说它们还没有真正持有锁，此时还有机会调整等待队列的顺序。或许通过调整等待顺序就可以将这个环打破，从而不用终止任何事务就能避免死锁问题。（在锁的申请过程中已经做了这种优化，只不过考虑性能的因素，当时的优化较为简单，不可能覆盖所有情况。因此在死锁检测过程中，一旦出现虚边，就开始考虑等待队列重排，争取在不终止事务的情况下打破死锁的可能。）
在会话（Backend）启动时，每个会话都会注册一个死锁检测定时器，它的主要作用就是提示进行死锁检测。
其中，CheckDeadLockAlert作为定时任务会定时设定一个死锁检测的标志got_deadlock_timeout。当事务处于等待状态时，ProcSleep函数会根据这个标志来决定是否进行死锁检测（此时正处于等待状态）。
死锁检测的主入口函数是CheckDeadLock函数，死锁检测操作在这个函数中实现。需要注意的是，死锁检测的过程是互斥的，也就是说在死锁检测开始的时候，锁表就需要被保护起来，避免其他人修改锁表。由于死锁检测的过程就是检测锁持有和锁等待队列的过程，这个过程中应该避免有人修改锁的持有状态及等待队列的等待顺序。不过，如果一个事务只通过本地锁表或者通过Fast Path就能获得锁，则它不会受死锁检测的影响。
定时任务一旦被触发，就开始检查当前的主锁表中是否有可能产生死锁，也就是在等待链中检测是否有环。大家可能在刷题的时候遇到过如何找到链表中的环的问题，通常的答案是通过快慢指针的方法来获得链表的环，但PostgreSQL没有这样做，它通过记录visitedProcs数组的方法来找到链表中的环。当它要检查一个会话（PGPROC）时，它就将这个会话和vistiedProcs中的会话逐个比对，查看待检查的会话是否已经存在于visitedProcs中。如果没有找到相同的会话，则说明现在还没有环。此时将当前检查的会话也被保存到visitedProcs中，然后开始检查下一个会话。需要注意的是，环的检查是有目标的，它只关心当前会话（事务）是否会构成环。也就是说，即使在死锁检测过程中检查到了环，但是这个环和当前的会话（事务）没有关系，则也不会报死锁错误。
等待图的构成主要是节点PGPROC和EDGE两个结构体，其中每个PGPROC都代表了一个会话或进程，每个应用程序和数据库建立连接之后都会有一个新的PGPROC与之相对应，也可以称之为一个会话或一个后台进程（本章中也可以代表一个事务）。EDGE是等待图的一个边，由等待者和被等待者构成。
如果在环中包含续边，则可以尝试通过调整等待队列来消除环，新的等待队列保存在waitOrders数组中，每个数组元素都是一个等待队列，由WAIT_ORDER结构体保存这样的队列。
在环的查找过程中，可以被调整的虚边被记录在possibleConstraints中，在每次向前推进时都会从possibleConstraints找到一个虚边进行探索，被探索的虚边被保存在curConstraints中，这两个数组的长度要足够大，例如curConstraints的长度为MaxBackends，被调整的虚边的数量不能超过这个值。
DeadLockCheckRecurse函数会不断地被递归调用，如果遇到实边构成的环，它就会停止探测并报死锁错误；而如果有虚边构成的环，它就会尝试在curConstraints中推进探测的Configuration。
TestConfiguration函数负责做以下两件事。
• 根据当前的Configuration（也就是curConstraints）产生新的等待队列，TopoSort函数根据输入的锁（lock）及虚边数组（constraints）信息，通过拓扑排序的方法获得一个新的等待队列（ordering）。
• 使用新的等待队列检测是否存在环，优先查找实边构成的环，如果找到则直接报死锁错误，否则开始尝试查找虚边构成的环；如果有虚边构成的环，则将当前的虚边保存到possibleConstraints中。
找环操作是在FindLockCycle函数中实现的，它不停地递归调用FindLockCycleRecurse函数来分别查找实边构成的环和虚边构成的环。
接下来分析一下FindLockCycleRecurseMember函数，它主要分成两部分，第一部分是找实边构成的环，如果找到就会报死锁错误。
FindLockCycleRecurseMember函数的第二部分是找含有虚边的环，如果发现虚边，就将虚边保存到possibleConstraints中。这里需要注意的是，在查找环的过程中，它会优先从waitOrders中选择等待队列，如果waitOrders数组中没有对应锁的等待队列，才会使用锁本身的等待队列。
