树形结构和线程

Question

我有一个速度关键的多线程程序，涉及树形数据结构。实现如下：

typedef struct
{
    // data pertaining to linkages, defining the architecture of the tree
    int parent_node;
    int child_node[MAX_CHILD_NODES];
    int number_of_children;

    // data pertaining to info at each node
    float interesting_info_A;
    char interesting_info_B[STRING_LEN];
    long interesting_info_C;
}
node_type;

node_type node[MAX_NUMBER_OF_NODES];

CRITICAL_SECTION node_critsec[MAX_NUMBER_OF_NODES];

程序通过node_critsec[]控制进入和离开关键部分。所以当我需要处理节点n的interesting_info_A/B/C时，我会进入该节点的临界区(node_critsec[n])，做好处理后再离开。该程序绕着树结构游走，沿着父子链接走各种复杂的路径。程序还会增加树的大小，即添加新节点，并相应地修改其他节点的父子链接（树不会缩小）。为了避免死锁的风险，我尽量确保每个线程一次只锁定一个节点。但是，如果我要添加一个新节点，那么我可能会想锁定该节点的父节点，以便我可以调整其子节点列表。让这一切正常工作而又不出现死锁或两个线程试图修改同一个节点中的数据是有点棘手的问题。我是否应该遵循一些指导原则来锁定/解锁何时和哪些节点，还是我必须非常聪明地解决可能发生的每种情况？

- Mick

---

你能解释一下你遇到死锁的地方吗？这意味着你的图中可能有循环（不是树），或者在遍历过程中你没有在获取子锁之前放弃父锁，这很容易纠正。 - Tyler McHenry

据我所知，有些算法是自下而上的，而其他算法则是自上而下的，等等。我认为他的意思是在将新节点添加到父节点列表之前需要保持锁定该新节点，否则另一个线程可能会窃取新节点或出现错误（不一致状态：parent_node设置为未列出此节点为子节点的节点）。我不知道这种数据结构是否是最优的，但他对于需要使用此数据结构进行同步假设是正确的。 - gimpf

@Tyler McHenry：我现在实际上并没有遇到死锁问题，尽管过去曾经遇到过。我遇到死锁问题的时候，通常是由于其中一个线程同时锁定了两个不同的节点。而我现在遇到的问题是两个不同的线程正在处理相同节点的数据。 - Mick

Answer 1

一个简单的规则：为了避免在锁定多个项目时发生死锁，必须始终以相同的顺序锁定它们。因此，如果您有A、B、C和D四个项目，您应该始终按字母顺序锁定它们，而不是其他方式。如果您已经锁定了C并且决定需要B，则必须释放C，然后锁定B并重新锁定C。

在树中，我想您可以始终从上到下锁定。如果需要锁定父级，则根据需要释放和重新获取锁定。

还有其他工作同样好的方案，但这个方案很直接。

编辑：您可以在这里阅读一些相关信息。

- Clinton Pierce

---

假设它是正确的，我喜欢那个声音。简单而不失优雅。 - Mick

我赞同这是一个正确的方案。我特别喜欢从上往下锁定树，如果你想锁定一个节点的父节点，你需要释放当前节点的锁，移动到父节点，并按顺序锁定这对节点。 - J Teller

Answer 2

如果树的增长相对不常见，一种可能性是使用读/写锁，允许多个读取器但只有一个写入器。使用单个R/W锁来锁定遍历期间的树本身（获取读取锁）。任意数量的线程都可以这样做。当线程需要添加新节点时，它将获取写锁。这将在更新期间阻止所有读取器。请注意，您可能需要设置读/写锁以优先考虑编写者，以避免使其饥饿。

使用该机制将消除单个线程为各个节点获取多个关键部分的需要，从而简化该过程。

- Mark Wilkins

---

不幸的是，增长树是非常普遍的。 - Mick

@Mick：新节点是如何添加到父节点中的？它们按特定顺序添加（例如 b 树样式）吗？还是子节点只是添加到现有节点末尾（在位置 number_of_children 处）？ - Mark Wilkins

不幸的是，机制比我问题中简化的代码更复杂...为了正确回答你的问题，我需要解释太多的东西。但是clintp的答案很可能解决我所有的问题。 - Mick

Answer 3

这很像文件系统中的节点锁定。如果你正在寻找参考材料，可以查看Linux、BSD、Open Solaris中的VFS层...但是要注意，它可能会非常复杂，因此可能不是最好的参考例子。

除了clintp提出的观点外，我想再补充一些内容（请注意他的建议）。

1. 当您需要整个树的访问权限时，使用互斥锁锁定它，完成后解锁它可能是值得的。尽管此临界区单线程化了应用程序，但快速而安全地启动和运行它非常有用。谁知道，这提供的性能可能已经足够了。如果不是，至少让您继续前进。如果您使用读写信号量代替互斥锁，则可以稍微放宽瓶颈；所有写入都变成单线程，而读取可以并发进行。

2. 列出您想要对树执行的所有操作，并将它们分类（读取、写入、更新、移动、重命名、删除等），并确定您想要的并发度。从您所写的内容来看，您需要的不仅是只读。您是否希望线程A能够读取线程B未锁定写入的节点？我通过经验告诉你，跳过此步骤可能会浪费你很多时间。

希望这能帮到您。

- Sparky