代码之家 › 专栏 › 技术社区 › thr

(更多)在线程二叉树中旋转节点时有效锁定

tree concurrency data-structures multithreading c#

thr · 技术社区 · 16 年前

所以,我提出了一种在二进制树中旋转时锁定节点的方案,多个线程同时具有读写访问权限,这涉及到每次旋转锁定四个节点,这似乎是一个非常多的问题?我想有一种方法比我想出的更聪明的方法来减少所需的锁定,但是google没有出现太多(无论如何,我可能使用了错误的术语)。

这是我当前的方案,橙色和红色节点要么被旋转移动,要么被旋转更改,需要被锁定,绿色节点与任何受旋转影响但自身不受其影响的节点相邻。

binary tree rotation

我想应该有更好的方法来做到这一点,我的一个想法是对受影响的四个节点进行快照,在快照中旋转它们,然后用快照节点替换当前节点(假设在我进行旋转时没有任何变化)-这将允许我几乎无锁,但考虑到旋转是一个相当快的操作(重新分配三个指针),恐怕内存开销可能很大?

我想我在寻找如何有效地做到这一点的方法(不是双关语)。

6 回复 | 直到 13 年前

Thomas Danecker 16 年前

看看不可变的二叉树。您必须更改更多的节点(每个节点都更改为根节点),但这不会更改插入的复杂性 log n 两种方式。实际上,它甚至可以提高性能,因为您不需要任何同步代码。

例如,eric lippert在c中写了一些关于不可变avl树的文章。最后一个是: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

user82238 16 年前

据我所见,无锁算法缺少引用计数,这使得它们的一般使用成了问题;您不知道必须指向某个元素的指针是否有效——可能该元素已消失。

瓦洛瓦用一些奇怪的内存分配安排来解决这个问题 在实践中没有用处 .

我能看到的实现无锁平衡树的唯一方法是使用修改后的mcas,在mcas中还可以执行递增/递减操作,这样就可以保持引用计数。我还没有看到mcas是否可以这样修改。

Daniel Earwicker 16 年前

考虑到锁本身通常占用一些重要的资源,整个数据结构通常只有一个锁。我猜你是在试图避免这种情况,这一定是一个非常特殊的场景,你有很多CPU密集型的工作线程不断更新树?

通过使每个n个节点共享一个锁,可以获得一个平衡。输入旋转操作时,请查找受影响节点使用的唯一锁集。大多数时候它只是一把锁。

Antti Huima 16 年前

最佳解决方案取决于您的应用程序。但是,如果您有一个类似内存中的数据库,并且希望对其进行并发更新,并且希望具有非常细粒度的锁定,那么您还可以查看不需要像二进制树那样频繁地进行节点旋转的b树。它们也是自动平衡的,不像二叉树,二叉树需要更多的旋转来保持平衡(例如splay树或avl树)。

如果您想对树进行事务性修改,那么可以使用功能性b树(thomas danecker称之为不可变树)。这是一种“写时复制”的二叉树,您只需要锁定根节点。所以你只需要一把锁。在实践中,这些操作的复杂性与二叉树相同,因为函数二叉树上的所有操作都是o(log n),而且每当你从任何树上下来时,你花费的对数时间都是相同的。

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

Ben Manes 16 年前

John Valois paper 简要描述了一种使用辅助节点实现二叉搜索树的方法。我正在使用辅助节点方法 design 并发LinkedHashMap的。你可能可以在citeserx(一个非常宝贵的资源)上找到许多关于并发树的论文。除非确实有必要,否则我会放弃使用树作为并发数据收集,因为树由于重新平衡而往往具有较差的并发特性。通常更务实的方法,比如跳过列表,效果更好。

Joe Seigh 16 年前

我用写时部分拷贝的方法来实现二进制树的读锁自由。我在这里发布了一个不完整的实现 http://groups.google.com/group/comp.programming.threads/msg/6c0775e9882516a2?hl=en&