2

下面是我在一次采访中被问到的问题，我相信这个问题有很多解决方案，但我想知道什么是最好的解决方案（stackoverflow 非常适合这个问题:)）。

问：我们有一个树状结构并有三个线程。现在我们必须执行三个操作：插入、删除和查找。你将如何设计这个？

我的方法：我将使用互斥锁进行插入和删除操作，因为我希望一次只执行一个线程插入或删除。而在查找的情况下，我将允许所有三个线程进入函数但保留一个计数（计数信号量），以便这次无法执行插入和删除操作。同样，当插入或删除操作进行时，不允许线程进行查找，插入和删除的情况相同。

现在他交叉质疑我，因为我一次只允许插入一个线程，所以如果需要插入不同叶子上的两个节点，那么我的方法仍然一次允许一个，这会卡住。

我的方法好吗？还有什么其他方法？

4

1 回答 1

3

像这样怎么样？类似于交通路障（断路）。

  • 每个节点将有两个标志说leftClear_f并rightClear_f指示clear-path前面
  • 树将只有一个互斥锁

查找操作：

  • 如果设置了指示前方路径正在修改的标志，则到达conditional_wait并等待信号。
  • 收到信号后检查标志并继续。

插入操作

  • 按照Lookup直到您到达插入位置。
  • 在检查它们的状态后，获取 MutEx 并设置parent_node它们的相关标志。child_node
  • 释放互斥体，以便并行Delete/Insert可以发生在其他有效的完整路径上
  • 插入操作后获取 MutEx 并更新parent_node和child_nodes 中的相关标志。

除删除节点外，删除操作 与插入操作相同。

PS：您也可以在其他地方维护Insert或处理节点的详细信息。Delete如有必要/需要，其他操作可以跳过损坏的路径！这听起来很复杂但可行。

于 2013-01-28T09:27:08.263 回答