DBMS 中的死锁

死锁是两种或多种事务无限期地等待对方释放锁定的条件。在 DBMS 中，死锁被认为是最令人头疼的并发问题之一，因为没有任何任务能够完成，并且永远处于等待状态。

例如：在学生表中，事务 T1 持有某些行的锁定，并需要更新成绩表中的某些行。与此同时，事务 T2 持有成绩表中某些行的锁定，并需要更新 T1 事务持有的学生表中的行。

现在，主要问题出现了。事务 T1 正在等待 T2 释放其锁定，同样，事务 T2 正在等待 T1 释放其锁定。所有活动都停止了，并陷入停滞状态。这种情况将一直持续下去，直到 DBMS 检测到死锁并中止其中一个事务。

以下是发生死锁的必要条件列表：

• 循环等待：当两个或多个事务无限期地相互等待对方释放所持有的锁时。
• 部分分配：当一个事务获得了部分所需的数据项，但不是所有数据项，因为它们可能被其他事务独占锁定。
• 非抢占式调度：一次只能由一个事务访问的数据项。
• 互斥：一次只能由一个事务独占锁定数据项。

为了避免死锁，至少应该满足上述必要条件中的一个。

死锁避免

• 当数据库陷入死锁状态时，避免死锁比中止或重启数据库更好。这是对时间和资源的浪费。
• 死锁避免机制用于提前检测任何死锁情况。像“等待图”这样的方法用于检测死锁情况，但这种方法只适用于小型数据库。对于大型数据库，可以使用死锁预防方法。

死锁检测

在数据库中，当一个事务无限期地等待获取锁时，DBMS 应该检测该事务是否涉及死锁。锁管理器维护一个等待图来检测数据库中的死锁循环。

等待图

• 这是死锁检测的适用方法。在此方法中，根据事务及其锁创建一个图。如果创建的图中有循环或闭环，则存在死锁。
• 系统为每个等待其他事务持有的数据的事务维护一个等待图。系统会持续检查图中是否存在任何循环。

上述场景的等待图如下所示：

死锁预防

• 死锁预防方法适用于大型数据库。如果资源以不会发生死锁的方式分配，则可以预防死锁。
• 数据库管理系统分析事务的操作，看它们是否可能创建死锁情况。如果可能，DBMS 绝不允许该事务执行。

每个事务都有一个唯一的标识符，称为时间戳。它通常基于事务的状态，并在事务开始时分配。例如，如果事务 T1 在事务 T2 之前开始，那么与事务 T1 对应的时间戳将小于与事务 T2 对应的时间戳。时间戳决定了一个事务应该等待还是中止并回滚。被中止的事务保留其时间戳值，因此也保留了其优先级。

已提出以下使用时间戳的死锁预防方案。

• 等待-死亡（Wait-Die）方案
• 伤亡等待（Wound Wait）方案

这两种技术的一个显著缺点是，即使某些事务实际上并未导致死锁，它们也会被不必要地中止和重启。

等待-死亡（Wait-Die）方案

在此方案中，如果一个事务请求的资源已被另一个事务持有冲突锁，则 DBMS 仅检查两个事务的时间戳。它允许较旧的事务等待直到资源可用为止。

假设有两个事务 Ti 和 Tj，并且 TS(T) 是任何事务 T 的时间戳。如果 T2 持有某个其他事务的锁，而 T1 正在请求 T2 持有的资源，则 DBMS 执行以下操作：

1. 检查 TS(Ti) < TS(Tj) - 如果 Ti 是较老的事务，而 Tj 持有某些资源，则允许 Ti 等待直到数据项可用。这意味着如果较老的事务正在等待由较年轻事务锁定的资源，则允许较老的事务等待资源直到其可用。
2. 检查 TS(T_i) < TS(Tj) - 如果 Ti 是较老的事务并持有某些资源，而 Tj 正在等待它，则 Tj 被终止并稍后以随机延迟重启，但时间戳相同。

在上述表示中，T1 是请求事务，T2 是持有数据项锁的事务，t(Ti) 是事务 Ti 的时间戳。

考虑一个具有以下时间戳的事务示例：

如果 T1 请求一个被事务 T2 锁定的数据项，那么 T1 必须等待直到 T2 完成并且它获取的所有锁都被释放，因为 t(T1) < t(T2)。另一方面，如果事务 T3 请求一个被事务 T2 锁定的数据项，T3 必须中止并回滚（即死亡），因为 t(T3) < t(T2)。

伤亡等待（Wound Wait）方案

在上述表示中，T1 是请求事务，T2 是持有数据项锁的事务，t(Ti) 是事务 Ti 的时间戳。

考虑一个具有以下时间戳的事务示例：

如果 T1 请求一个被事务 T2 锁定的数据项，那么 T1 必须等待直到 T2 完成并且它获取的所有锁都被释放，因为 t(T1) < t(T2)。另一方面，如果事务 T3 请求一个被事务 T2 锁定的数据项，那么 T3 必须等待，因为 t(T3) > t(T2)。

以下是等待-死亡（Wait-Die）方案和伤亡等待（Wound Wait）方案之间的区别：

死锁检测与恢复

在死锁检测方案中，死锁检测算法会定期检查系统状态，看是否发生死锁，如果系统中存在死锁，则尝试从死锁中恢复。

为了检测死锁，系统必须具备以下信息：

系统必须提供一种算法，使用这些信息，即关于数据项当前分配信息，来检查系统是否进入了死锁状态。如果存在死锁，系统会尝试从死锁中恢复。

死锁恢复

如果用于死锁检测的等待图包含死锁情况，即存在循环，则应移除这些循环以从死锁中恢复。恢复死锁最常用的技术是回滚一个或多个事务，直到系统不再显示死锁状况。

选择要回滚的事务是基于以下考量：

受害者选择：可能有很多事务涉及死锁，即死锁事务。因此，为了从死锁中恢复，应该回滚其中一些事务。被回滚的事务称为受害者事务，这个过程称为受害者选举。

要回滚的事务是刚刚开始或尚未进行太多更改的事务。避免选择已经进行了许多更新且运行时间很长的事务。

回滚：一旦决定了要回滚的事务，我们就应该确定当前事务应该回滚到什么程度。最简单的解决方案之一是完全回滚，即中止事务并重新启动它。然而，事务应该回滚到打破死锁所需的程度。此外，还应维护当前正在执行的事务状态的附加信息。

饥饿：为了从死锁中恢复，我们必须确保同一个事务不会反复被选为回滚的受害者。如果这种情况不被避免，事务将永远无法完成。为了避免饥饿，一个事务作为受害者被选中的次数应该是有限的。

一个广泛使用的解决方案是计算被选为受害者的事务的回滚次数。

关于 DBMS 死锁的选择题

1. 下列哪项不是发生死锁的必要条件？

答案：c

解释：以下是发生死锁的必要条件：

2. 系统中存在死锁的充要条件是等待图包含？

答案：c

解释：当等待图包含循环时，系统中存在死锁。

3. 下列哪项不是死锁中的等待方案？

答案：c

解释：以下是各种死锁等待方案：

4. 死锁条件由 ___ 机制提前检测。

答案：c

说明

死锁条件由死锁避免机制提前检测。

• 在伤亡等待（Wound Wait）方案中，如果较老的事务请求由年轻事务持有的资源，则较老的事务会强制年轻事务杀死该事务并释放资源。在短暂延迟后，年轻事务会以相同的时间戳重新启动。
• 如果较老的事务持有了年轻事务请求的资源，那么年轻事务会被要求等待，直到较老的事务释放它。
• 它基于抢占式技术。
  • 系统应该拥有关于并发事务组的信息。
  • 关于每个事务的数据项当前分配的信息。
  • 它必须拥有关于每个事务正在等待的数据项的当前集合的信息。
  • 循环等待
  • 部分分配
  • 抢占式调度
  • 互斥
  • 循环等待
  • 部分分配
  • 非抢占式调度
  • 互斥
  • 环
  • 双向
  • 方向
  • 旋转
  • 等待-死亡（Wait-Die）方案
  • 伤亡等待（Wound Wait）方案
  • 等待方案
  • 等待-死亡（Wait-Die）方案
  • 伤亡等待（Wound Wait）方案
  • 死锁检测
  • 死锁检测
  • 死锁避免
  • 死锁恢复