分布式数据库管理系统 - 死锁处理

---

---

本章概述了数据库系统中的死锁处理机制。我们将研究集中式和分布式数据库系统中的死锁处理机制。

什么是死锁？

死锁是数据库系统的一种状态，其中两个或多个事务相互等待对方持有的数据项。死锁可以通过等待图中的循环来指示。这是一个有向图，其中顶点表示事务，边表示等待数据项。

例如，在下面的等待图中，事务T1正在等待被T3锁定的数据项X。T3正在等待被T2锁定的Y，而T2正在等待被T1锁定的Z。因此，形成了一个等待循环，任何事务都不能继续执行。

集中式系统中的死锁处理

有三种经典的死锁处理方法，即：

• 死锁预防。
• 死锁避免。
• 死锁检测和解除。

这三种方法都可以整合到集中式和分布式数据库系统中。

死锁预防

死锁预防方法不允许任何事务获取会导致死锁的锁。约定是，当多个事务请求锁定相同的数据项时，只有一个事务可以获得锁。

最流行的死锁预防方法之一是在开始执行之前预先获取所有锁。在这种方法中，事务在开始执行之前获取所有锁，并在整个事务期间保持这些锁。如果另一个事务需要任何已获取的锁，则必须等到所有需要的锁都可用。使用这种方法，可以防止系统死锁，因为没有任何等待的事务持有任何锁。

死锁避免

死锁避免方法在死锁发生之前处理死锁。它分析事务和锁以确定等待是否会导致死锁。

该方法可以简述如下。事务开始执行并请求它们需要锁定的数据项。锁管理器检查锁是否可用。如果可用，锁管理器分配数据项，并且事务获取锁。但是，如果该项被其他事务以不兼容模式锁定，则锁管理器将运行一个算法来测试将事务保持在等待状态是否会导致死锁。相应地，算法决定事务是否可以等待或应该中止其中一个事务。

为此，有两种算法，即**等待-死亡 (wait-die)** 和 **攻击-等待 (wound-wait)**。让我们假设有两个事务 T1 和 T2，其中 T1 试图锁定已被 T2 锁定的数据项。算法如下：

• **等待-死亡 (Wait-Die)** - 如果 T1 比 T2 旧，则允许 T1 等待。否则，如果 T1 比 T2 新，则中止 T1 并稍后重新启动。

• **攻击-等待 (Wound-Wait)** - 如果 T1 比 T2 旧，则中止 T2 并稍后重新启动。否则，如果 T1 比 T2 新，则允许 T1 等待。

死锁检测和解除

死锁检测和解除方法定期运行死锁检测算法，并在存在死锁时解除死锁。当事务发出锁定请求时，它不会检查死锁。当事务请求锁时，锁管理器检查它是否可用。如果可用，则允许事务锁定数据项；否则，允许事务等待。

由于在授予锁定请求时没有任何预防措施，因此某些事务可能会死锁。为了检测死锁，锁管理器定期检查等待图中是否存在循环。如果系统死锁，锁管理器将从每个循环中选择一个受害者事务。受害者被中止并回滚；然后稍后重新启动。一些用于受害者选择的方 法包括：

• 选择最年轻的事务。
• 选择拥有最少数据项的事务。
• 选择执行更新次数最少的事务。
• 选择具有最小重启开销的事务。
• 选择属于两个或多个循环的事务。

这种方法主要适用于事务量少且需要快速响应锁定请求的系统。

分布式系统中的死锁处理

分布式数据库系统中的事务处理也是分布式的，即同一事务可能在多个站点上进行处理。分布式数据库系统中存在的两个主要死锁处理问题在集中式系统中不存在，它们是**事务位置**和**事务控制**。一旦解决了这些问题，就可以通过任何死锁预防、死锁避免或死锁检测和解除方法来处理死锁。

事务位置

分布式数据库系统中的事务在多个站点上处理，并使用多个站点中的数据项。数据处理量在这些站点之间并不均匀分布。处理的时间段也各不相同。因此，同一事务可能在某些站点处于活动状态，而在其他站点处于非活动状态。当两个冲突的事务位于一个站点时，可能发生其中一个事务处于非活动状态的情况。这种情况在集中式系统中不会出现。这个问题称为事务位置问题。

这个问题可以通过菊花链模型来解决。在这个模型中，事务在从一个站点移动到另一个站点时携带某些详细信息。一些详细信息包括所需表列表、所需站点列表、已访问表和站点列表、尚待访问的表和站点列表以及已获取锁及其类型的列表。事务通过提交或中止终止后，应将信息发送到所有相关站点。

事务控制

事务控制与指定和控制分布式数据库系统中处理事务所需的站点有关。关于在哪里处理事务以及如何指定控制中心有很多选择，例如：

• 可以选择一台服务器作为控制中心。
• 控制中心可能会从一台服务器移动到另一台服务器。
• 控制责任可以由多台服务器共享。

分布式死锁预防

就像集中式死锁预防一样，在分布式死锁预防方法中，事务应该在开始执行之前获取所有锁。这可以防止死锁。

事务进入的站点被指定为控制站点。控制站点向数据项所在站点发送消息以锁定这些项。然后等待确认。当所有站点都确认已锁定数据项后，事务开始。如果任何站点或通信链路发生故障，则事务必须等到它们被修复。

虽然实现简单，但这 种方法有一些缺点：

• 预先获取锁需要很长时间来处理通信延迟。这会增加事务所需的时间。

• 如果站点或链路发生故障，事务必须等待很长时间才能使站点恢复。同时，在运行的站点中，项目被锁定。这可能会阻止其他事务执行。

• 如果控制站点发生故障，则无法与其他站点通信。这些站点继续保持其锁定的数据项处于锁定状态，从而导致阻塞。

分布式死锁避免

与集中式系统一样，分布式死锁避免在死锁发生之前处理死锁。此外，在分布式系统中，需要解决事务位置和事务控制问题。由于事务的分布式特性，可能会发生以下冲突：

• 同一站点中两个事务之间的冲突。
• 不同站点中两个事务之间的冲突。

发生冲突时，根据分布式等待-死亡或分布式攻击-等待算法，可以中止其中一个事务或允许其等待。

让我们假设有两个事务 T1 和 T2。T1 到达站点 P 并试图锁定已被 T2 锁定的数据项。因此，在站点 P 处发生冲突。算法如下：

• 分布式等待-死亡 (Wound-Die)

  • 如果 T1 比 T2 旧，则允许 T1 等待。在站点 P 接收到一条消息，表明 T2 已在所有站点成功提交或中止后，T1 可以恢复执行。

  • 如果 T1 比 T2 新，则中止 T1。站点 P 的并发控制向 T1 已访问的所有站点发送消息以中止 T1。控制站点在 T1 已在所有站点成功中止时通知用户。

• 分布式等待-等待 (Wait-Wait)

  • 如果 T1 比 T2 旧，则需要中止 T2。如果 T2 在站点 P 处于活动状态，则站点 P 中止并回滚 T2，然后将此消息广播到其他相关站点。如果 T2 已离开站点 P 但在站点 Q 处于活动状态，则站点 P 广播 T2 已被中止；然后站点 L 中止并回滚 T2 并将此消息发送到所有站点。

  • 如果 T1 比 T2 新，则允许 T1 等待。在站点 P 接收到一条消息，表明 T2 已完成处理后，T1 可以恢复执行。

分布式死锁检测

就像集中式死锁检测方法一样，允许死锁发生，并在检测到时将其移除。当事务发出锁定请求时，系统不会执行任何检查。对于实现，创建全局等待图。全局等待图中存在循环表示死锁。但是，很难发现死锁，因为事务等待网络上的资源。

另外，死锁检测算法可以使用计时器。每个事务都关联一个计时器，该计时器设置为事务预计完成的时间段。如果事务在此时间段内未完成，则计时器超时，表明可能存在死锁。

另一个用于死锁处理的工具是死锁检测器。在集中式系统中，只有一个死锁检测器。在分布式系统中，可以有多个死锁检测器。死锁检测器可以查找其控制的站点上的死锁。在分布式系统中，死锁检测有三种方法，即：

• 集中式死锁检测器 − 指定一个站点作为中央死锁检测器。

• 分层死锁检测器 − 多个死锁检测器按层次结构排列。

• 分布式死锁检测器 − 所有站点都参与检测和消除死锁。