如何实现无锁跳过列表

Question

我需要实现一个无锁跳过列表。我试着去找文件。不幸的是，我发现的都是无锁的单链表(有很多种)。但是，如何实现无锁跳过列表呢？

Answer 1

无锁跳过列表在The Art of Multiprocessor Programming一书和技术报告Practical lock-freedom中进行了描述，该技术报告基于PhD关于该主题的论文。跳过列表的讨论从第53页开始。基于这些源代码的示例实现包含在this google code project中。

在SO questions Skip List vs. Binary Tree和Skip Lists - ever used them?中有相关的讨论、文献和实现的链接(不一定是无锁的)。

Answer 2

This paper提供了一个无锁和无等待的跳跃列表。它的实现很简单--几周前我将其作为Intel Threading Challenge 2010的一部分实现(请参阅页面中间的SkipList选项卡)。

Java包含一个并发跳过列表java.util.concurrent.ConcurrentSkipListMap的实现。