0

是否有人知道任何支持排名操作(即找到第 k 个元素)的无锁跳过列表实现和/或研究论文?或者,有没有人知道为什么这样的操作永远行不通的根本原因?

奖励积分:

不假设垃圾收集的实施。根据我的经验,很多研究论文都忽略了内存管理。

支持:

有关如何在常规跳过列表中完成排名操作的描述:William Pugh 的“跳过列表食谱”

对于更好的无锁跳过列表描述之一:Keir Fraser 的“Practical lock-freedom”

更好的无锁跳过列表实现之一: http ://www.1024cores.net/home/parallel-computing/concurrent-skip-list

4

1 回答 1

1

keyvaluelevel不同,它们是skiplist中元素的局部属性,不受与其他元素的操作的影响,元素的rank,即它在列表中的位置,是一个随着元素的插入和删除而变化的属性以较低的等级。因此,对于并发跳过列表,元素的排名是非常短暂的,因为它可能在任何时刻被同时运行的插入或删除较低排名元素的操作更改。

例如,假设您通过 1 级列表对第k个元素进行线性搜索。在您执行k步的那一刻,并发修改可能会添加或删除任意数量的先前元素,因此您刚刚找到的元素的当前等级实际上是未知的。此外,当线程执行k次前向迭代时,可以在其当前位置和开始搜索时第k个元素之间进行并发更改。因此,搜索的结果既不是当前排名为k的元素,也不是搜索开始时排名为k的元素。这只是一些随机元素!

简而言之,对于并发列表,元素的排名是一个定义不明确的概念,按排名搜索是一个定义不明确的操作。这是它永远无法工作的根本原因,也是实现者永远不应该为提供这样的操作而烦恼的根本原因。

于 2012-02-03T23:27:56.670 回答