logo标签列表

在线索二叉树中旋转节点时实现更高效的锁定

c#multithreadingdata-structuresconcurrencytree
3
所以，我想出了一种方案，在二叉树旋转时锁定节点，多个线程同时读取和写入，每次旋转需要锁定四个节点，这似乎太多了？我想肯定有比我更聪明的人想出了减少所需锁定的方法，但是谷歌并没有找到太多（我可能使用了错误的术语）。
这是我的当前方案，橙色和红色节点被旋转移动或更改，需要锁定，绿色节点与任何受旋转影响的节点相邻，但本身不受影响。 二叉树旋转 我想肯定有更好的方法来做到这一点，我想到的一个想法是拍摄受影响的四个节点的快照，对它们进行旋转，然后用快照节点替换当前节点（假设我在旋转时没有发生任何变化）-这将使我几乎无需锁定，但我担心内存开销可能太大，考虑到旋转是一个相当快速的操作（重新分配三个指针）？
我想我正在寻找如何有效地完成此操作的指针。
图片链接已损坏。 - Steve Konves
6个回答
4
看看不可变的二叉树。您需要更改更多节点（每个节点到根），但这不会改变插入的复杂度，即两种方式都是对数级别的 log n 。实际上，这甚至可能提高性能，因为您不需要任何同步代码。
例如，Eric Lippert在C＃中编写了一些关于不可变avl树的文章。最后一篇是：C＃中的不可变性第九部分：学术？加上我的AVL树实现
谢谢，我一定会去看这篇文章。 - thr
1

就编程而言，无锁算法似乎缺乏引用计数，这使得它们的通用性受到问题的影响。你无法确定指向某个元素的指针是否有效 - 也许该元素已经消失了。

瓦洛伊通过一些奇特的内存分配方案来解决这个问题，但实际上并没有什么用处。

我所能想到的实现无锁平衡树的唯一方法是使用修改后的MCAS，其中你还可以进行增量/减量，以便维护引用计数。 我还没有查看过是否可以以这种方式修改MCAS。

0

通常整个数据结构只需要一个锁，因为锁本身通常会占用一些严重的资源。我猜想，由于您试图避免这种情况，这一定是一种非常专业的场景，其中有很多CPU密集型工作线程不断更新树？

您可以通过使每N个节点共享一个锁来获得平衡。在进入旋转操作时，找到受影响节点使用的唯一锁集合。大多数情况下，它只会是一个锁。

锁定整个结构非常低效，如果我有100万个节点和大约10个线程在处理它们，阻塞整棵树将会严重影响性能。 - thr
是的，这就是我问的原因。但我也不确定100万个锁会有多实用。 - Daniel Earwicker
0

最佳解决方案取决于您的应用程序。但是，如果您有一个内存数据库，并且希望对其进行并发更新，并且希望具有非常细粒度的锁定，则还可以查看B树，因为它们不需要像二叉树那样经常进行节点旋转。与二叉树不同，它们也是自动平衡的，而二叉树需要更多的旋转来保持平衡（例如Splay或AVL树）。

如果您想对树进行事务性修改，则可以使用函数式B树（Thomas Danecker称之为不可变树）。这些是一种“写时复制”二叉树，唯一需要锁定的是根节点。因此，您只需要一个锁。在实践中，操作的复杂度与二叉树相同，因为所有函数式二叉树上的操作都是O（log n），并且每当您向下遍历任何树时，都会花费相同的对数时间。

每个节点都有一个锁最可能不是正确的解决方案。

0

John Valois的论文简要描述了使用辅助节点实现二叉搜索树的方法。我正在使用辅助节点方法来设计并发LinkedHashMap。您可以在CiteSeerX上找到许多其他关于并发树的论文（这是一个非常宝贵的资源）。除非真正必要，否则我建议不要使用树作为并发数据集，因为它们由于重新平衡而具有较差的并发特性。通常更实用的方法，比如跳表，会更好些。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接