multithreading - 是否有任何有效的(子)树锁定机制？

Question

我有一棵树T，它的节点可以通过它们的路径寻址(节点的有效负载包含一些可以粘合在一起形成路径的名称)。我想要的是某种机制(算法、辅助数据结构等)，允许在给定路径 P0 的情况下，以这种方式锁定整个子树:

• 尝试锁定任何路径 P1(其中 P1 以 P0 开头，即 P1 属于锁定的子树)将导致锁定因为 P1 是 P0 的锁(好吧，它可能不是同一个锁，但是对 P1 的操作应该等到 P0 锁是免费的);
• 但是当P0锁被释放时，P2的任何锁，其中P2以P0开头，< em>但不是 P2 以P1 开头，即P2 子树和P1 子树不同，将授予不同的锁两条路径，等等。

我解决了这个任务几次，但我最终得到了一个过于复杂的代码，它很困惑，并且使用了某种树来存储锁本身，这比我试图锁定的树更重。

如果我的问题不清楚，如果您想查看一些图纸/图表或任何有帮助的东西，请告诉我。

Answer 1

免责声明:这与我在 2009 年做的 HW 作业非常相似，所以我只记得基本思路，而不是细节。无论如何，我建议以下想法:

树中的每个节点都有自己的锁。每个锁定操作都从树的根部开始，然后向下到达所需的节点，锁定向下的每个节点。如果遇到锁定节点(不是根节点)，则锁定操作终止(不成功)，或设置为等待并重试(如忙等待)。如果根本身被锁定，它可能是另一个正在发生的操作的临时锁定。如果根未被锁定但内部节点被锁定，则它被真正锁定。
解锁可能会有所不同，不确定是否有必要沿着根目录向下走。 (可能是，所以这值得检查)。

编辑:
在锁定所需节点后处理树时，还要将树路径上的节点标记为在其子树中锁定了一些节点。这样，当您锁定一个节点时，您可以知道该子树中是否有一个节点已被锁定。