algorithm - 如何实现无锁跳过列表

Question

我需要实现一个无锁跳过列表。我试图寻找文件。不幸的是，我发现的只是无锁单链表（有多种形式）。但是如何实现无锁跳过列表呢？

Answer 1

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

在 SO 问题Skip List vs. Binary Tree和Skip Lists中有相关的讨论、文献链接和实现（不一定是无锁的）- 曾经使用过它们吗？.

Answer 2

本文提出了一个无锁和无等待的跳过列表。实施起来很简单——我在几周前作为2010 年英特尔线程挑战赛的一部分实施了这一点（请参阅页面中间的 SkipList 选项卡。）

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