DBMS - 死锁

在多进程系统中，死锁是在共享资源环境中出现的不希望出现的情况，其中一个进程无限期地等待另一个进程持有的资源。

例如，假设一组交易 {T₀, T₁, T₂, ...,T_n}。 T₀ 需要一个资源 X 来完成它的任务。 资源 X 由 T₁ 持有，T₁ 正在等待由 T₂ 持有的资源 Y。 T₂ 正在等待由 T₀ 持有的资源 Z。 因此，所有进程都在等待对方释放资源。 在这种情况下，没有一个进程可以完成它们的任务。 这种情况称为死锁。

死锁不利于系统。 如果系统陷入死锁，死锁中涉及的事务要么回滚，要么重新启动。

预防死锁

为了防止系统中出现任何死锁情况，DBMS 会积极检查即将执行事务的所有操作。 DBMS 检查操作并分析它们是否会造成死锁情况。 如果发现可能出现死锁情况，则永远不允许执行该事务。

有一些死锁预防方案使用事务的时间戳排序机制来预先确定死锁情况。

Wait-Die 方案

在这种方案中，如果一个事务请求锁定一个资源（数据项），而该资源（数据项）已经被另一个事务持有冲突锁，那么可能会出现两种可能性之一−

• 如果 TS(T_i) < TS(T_j) − 即 T_i，它正在请求一个冲突的锁，比 T_j 更旧 − 然后允许 T_i 等待直到数据项可用。

• 如果 TS(T_i) > TS(t_j) − 即 T_i 比 T_j 更年轻 − 则 T_i 死亡。 T_i 稍后会以随机延迟但具有相同的时间戳重新启动。

此方案允许较旧的事务等待但杀死较年轻的事务。

Wound-Wait 方案

在这个方案中，如果一个事务请求锁定一个资源（数据项），而该资源（数据项）已经被另一个事务持有冲突锁，则可能会出现两种可能性之一 −

• 如果 TS(T_i) < TS(T_j)，则 T_i 强制 T_j 回滚 − 那就是 T_i 伤害 T_j。T_j 稍后会以随机延迟但具有相同的时间戳重新启动。

• 如果是 TS(T_i) > TS(T_j)，则强制 T_i 等待，直到资源可用。

该方案，允许年轻交易等待； 但是当较旧的事务请求较年轻的事务持有的项目时，较旧的事务会强制较年轻的事务中止并释放该项目。

在这两种情况下，稍后进入系统的事务都会中止。

避免死锁

中止事务并不总是一种实用的方法。 相反，可以使用死锁避免机制来提前检测任何死锁情况。 诸如"wait-for"等待图表之类的方法是可用的，但它们仅适用于那些事务是轻量级且资源实例较少的系统。 在庞大的系统中，死锁预防技术可能会很好地发挥作用。

Wait-for 等待图表

这是一种可用于跟踪是否可能出现任何死锁情况的简单方法。 对于进入系统的每笔交易，都会创建一个节点。 当事务 T_i 请求对某个项目（例如 X，该项目由某个其他事务 T_j 持有）进行锁定时，会创建从 T_i 到 T_j 的有向边。 如果 T_j 释放项 X，则它们之间的边被删除并且 T_i 锁定数据项。

系统为等待其他人持有的某些数据项的每个事务维护此等待图。 系统会不断检查图中是否存在循环。

在这里，我们可以使用以下两种方法中的任何一种 −

• 首先，不允许对已被另一个事务锁定的项目的任何请求。 这并不总是可行的，并且可能导致饥饿，即事务无限期地等待数据项并且永远无法获取它。

• 第二个选项是回滚其中一个事务。 回滚较年轻的事务并不总是可行的，因为它可能比较旧的事务更重要。 在一些相关算法的帮助下，选择了一个要中止的事务。 这个交易被称为victim，这个过程被称为victim selection。