基于图或树的锁定协议

在本文中，我们将详细了解基于图的协议的概念。

引言

基于图的协议需要事先了解数据项的访问顺序。利用这些信息，可以构建非两阶段的锁定协议。此协议也称为树锁定协议，因为数据项都排列成树状。

数据库管理系统中基于图或树的锁定协议是什么意思？

在基于图或树的锁定协议中，主要用于数据库管理系统，其中数据项排列成层级树结构。在基于图的锁定协议中，图中的每个节点代表一个数据项，边主要定义了所选项目集之间的父子关系。

当事务需要访问所有数据时，它们需要根据本文稍后讨论的协议规则在相应节点上获取锁。一个关键规则是，事务只有在已经锁定其父节点的节点时才能锁定该节点，第一个锁除外。所有锁都是互斥的，这意味着在同一时间只有一个事务可以持有对数据项的锁。

这种层级结构和锁定顺序可以防止等待-图（wait-for graph）中出现循环，从而确保将来不会发生死锁。与其他强制执行严格两阶段锁定过程的锁定协议不同，树锁定允许事务随时释放锁，从而提高了并发性。

树锁定协议的特点

树锁定协议的各种关键特点

• 数据项排列成层级树状结构。
• 事务在锁定子节点之前必须锁定父节点。
• 这种锁定顺序可确保安全和一致的访问。
• 事务在使用后可以随时释放锁。
• 与两阶段锁定不同，它提供了更大的灵活性，提高了并发性，而不会影响性能。

树锁定协议的规则定义如下：

• 除非事务锁定它，否则不能访问任何数据项。所有锁都是互斥锁。
• 锁定节点不会自动锁定被锁定节点的任何后代节点。
• 已被事务 T 锁定并解锁的数据项 x 不能被 T 重新锁定。
• 事务锁定的第一个项可以是任何数据项，包括根节点。
• 除非事务已成功锁定其父节点，否则事务不能锁定一个节点，除非是事务锁定的数据项。
• 数据项可以随时解锁。

为了说明树锁定协议的概念，让我们考虑以下数据项，它们按所示方式组织：

此处，数据项 X0、X1、X2、X3、X4、X5、X6、X7、X8、X9 和 X10 按所示排列。因此，我们对访问顺序有先前的了解。数据项 X0 也是树的根。数据项 X1 是数据 X4 的父项，换句话说，数据项 X1 是数据项 X4 的祖先。从 X0 和 X1 的有向边表示 X1 是父项 X0 的子项。

以下三个事务遵循树协议，仅表示此图上的锁定和解锁指令：

T1 需要 X0、X2、X6、X9、X1 和 X3 的互斥锁

T2 需要 X2、X6、X10、X5 和 X7 的互斥锁

T3 需要 X5、X7 和 X8 的互斥锁

下面给出了一种基于这些事务的可能调度：

调查表

上述调度是使用树锁定协议的规则绘制的。因此，我们观察到该事务不是 2PL。正如我们所见，事务 T1 在完成处理后可以释放对数据项 X2 的锁定，从而允许 T3 并发进行。但在 2pl 的情况下则不可能。因此，这种基于图的协议有助于提高并发性。

上面绘制的调度等价于串行调度 T3 -> T2 -> T1。其中也不会有循环。因此，基于图或树的锁定协议可确保可串行化。

树锁定协议相对于两阶段锁定（2PL）的主要优势是：

• 与 2PL 不同，树锁定协议不会发生死锁，因为调度中没有循环，因此不需要回滚。
• 与 2PL 不同，在 2PL 中，事务必须长时间等待其他事务锁定的数据项，但在树锁定协议中，事务可以随时解锁数据项，从而缩短等待时间并提高并发性。

树锁定协议的缺点

树锁定协议的主要缺点是，根据规则，除非事务锁定它，否则不能访问任何数据项，因此事务可能需要锁定它不访问的数据项。假设事务需要访问数据库图中所示的 X0 和 X7 数据项。

那么事务不仅必须锁定 X0 和 X7，还必须锁定 X2 和 X5 数据项。这些额外的锁定会导致锁定开销增加，并可能增加额外的等待时间。它还会导致并发性下降。

树锁定协议的主要缺点之一是级联回滚的可能性更高。由于事务通常在层级结构中锁定相关数据，因此如果一个事务失败或被回滚，那么依赖于它的其他事务也可能需要被回滚。这种多米诺骨牌效应增加了恢复成本，并降低了整体系统性能。当多个事务紧密连接时，这会成为一个更大的问题，使得错误处理更加困难，并相应地减慢数据库操作的速度。

基于图的协议与两阶段锁定（2PL）协议的比较

实际应用

1. 数据库系统：该协议负责管理并发事务，确保数据的一致性，并在多用户环境（如银行系统或在线购物平台）中防止冲突或死锁。
2. 分布式文件系统：它控制对共享文件的访问，从而允许多个用户读取或写入而不损坏数据，尤其是在文件具有层级结构时（树锁定非常适合此处）。
3. 操作系统：负责管理进程间的资源分配，尤其是在资源具有依赖性或层级结构时，通过使用这些协议，个人可以避免死锁，而不会影响性能。

常见问题解答

数据库管理系统（DBMS）中使用基于图或树锁定协议的各种常见问题如下：

问题 1：基于图的并发控制协议如何避免死锁？

答案：在数据库管理系统（DBMS）中，基于图的并发控制协议使用有向图来避免死锁，其中每个节点代表一个事务，边表示依赖关系或等待。

当事务请求资源时，协议会检查添加相应边是否会产生循环。循环表示死锁情况，因此如果检测到循环，系统将立即回滚或中止参与打破循环的事务之一。

问题 2：部分排序如何为数据库管理系统中的基于图的并发控制做出贡献？

答案：基于图的并发控制中的部分排序通过定义一些操作的清晰顺序来帮助组织事务，而无需强制所有操作的严格顺序。它主要允许系统根据资源冲突轻松识别哪些事务必须在其他事务之前发生。

这种排序可以防止依赖图中的循环，从而减少发生死锁的机会。通过仅管理必要的顺序关系，它可以在保持一致性和避免事务冲突的同时，提高并发性和系统效率。

问题 3：树锁定协议通常用于哪里？

答案：树锁定协议在 DBMS 中通常使用的有效领域如下：

• 多用户数据库系统。
• 分布式文件系统。
• 操作系统。

结论

结论是，基于图或树的锁定协议提供了一种清晰、有组织的方式，通过利用层级结构来高效地管理数据访问。它有效防止死锁，并允许事务提前解锁项目，从而提高并发性。虽然由于所需的父锁可能导致锁定开销增加，但其确保安全、可预测访问的能力使其对于复杂的、多用户的数据库系统非常宝贵。