树结构和线程

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]),进行处理然后离开.该计划蜿蜒在树周围,通过与父母和孩子的链接,采取各种复杂的路径.该程序还将增长树,即添加新节点并相应地修改其他节点的父/子链接(树永远不会缩小).我尝试确保每个线程一次只锁定一个节点,以避免死锁的风险.但后来我遇到了问题 - 如果我正在添加一个新节点,那么我可能想要锁定节点的父节点,以便我可以调整其子节点列表.在没有死锁或两个线程尝试修改同一节点中的数据的情况下让所有人工作将变得有点噩梦.是否有一些指导原则我应该关注何时以及锁定/解锁哪些节点我应该遵循 - 或者我是否必须超级智能并找出可能发生的每个事件的排列？

Answer 1

一个简单的规则:在锁定多个项目时避免死锁总是在任何地方以相同的顺序锁定它们.因此,如果您有项目A,B,C和D,则应始终将其锁定在字母顺序而不是其他内容中.如果您已锁定C并确定您需要B,那么您必须释放C然后锁定B并重新锁定C.

我认为,在一棵树上,你可以随时从顶部向下锁定.如果您需要锁定父级,则根据需要释放并重新获取锁.

还有其他方案也可以,但这个方案很简单.

编辑:您可以在这里阅读一些相关内容.