Java中的无锁并发链表

Question

我想使用像这篇论文中描述的那样的链表。但是，我在网上没有找到任何Java实现。

如果没有上述链表的Java实现，我认为我会使用java.util.concurrent.ConcurrentLinkedQueue<E>。这是一个好选择吗（它并不真正是一个链表）？

如果这不是一个好的选择，是否有人知道一个可靠的Java并发（线程安全）无等待（无锁）链表实现？

- ptikobj

---

它在任何形式下都不是无锁的（它使用锁来添加/删除）- 哎呀，目标注释消失了...（它是关于LinkedBlockingDeque的）。 - bestsss

好的，大问题是，你为什么认为你想要任何形式的并发列表？大多数列表方法在共享并发结构上没有意义。为什么要获取第n个元素？获取第n个元素到底意味着什么？像大小这样的东西是短暂的，除了用于监视之外没有任何价值。你能解释一下你想如何使用它吗？http://permalink.gmane.org/gmane.comp.java.jsr.166-concurrency/6321 - Jed Wesley-Smith

我想要实现一个单例的“物理”缓冲区，它被n个“逻辑”缓冲区使用，每个逻辑缓冲区仅由其起始和结束元素定义，以便我在内存中没有冗余的数据表示。 - ptikobj

嗯，我仍然不明白你试图解决什么问题，你只是概述了一个解决方案。然而，在并发算法中，您确实需要在内存和隔离之间进行权衡，因为协调对同一内存的访问和修改的成本可能是禁止性的。例如，可以参考Guy Steele的演讲：http://www.infoq.com/presentations/Thinking-Parallel-Programming - Jed Wesley-Smith

Answer 1

ConcurrentLinkedQueue 是一个出色的无锁队列，它可以实现并发的单向链表操作。

但需要注意的是，如果仅使用 iterator() (+.remove()) 而不使用 poll 或 peek 方法，则可能会导致内存泄漏。

这是一个优秀的Queue（队列）。

- bestsss

---

JDK 7 中有一个 ConcurrentLinkedDeque。 - Peter Lawrey

假设我想要使用ConcurrentLinkedDeque，安装当前的JDK7预览版有多安全？ - ptikobj

实际上，在Java中实现它（队列，双端队列）相当简单。由于有GC，没有ABA问题。总体而言，并发/无锁算法如果有GC，则更容易...或者只需获取JDK7的源代码并在JDK6上运行，您（很可能）需要Unsafe，但这不是问题，如果将代码放入引导路径中。为了确保我没有出错，我将检查最新的JDK7源代码，并告诉您该代码是否可以安全地回溯（复制）到jdk6中。 - bestsss

实际上忘了（关于CLD）：“经验上，微基准测试表明，相对于ConcurrentLinkedQueue，该类别增加了约40％的开销，这感觉像是我们所能希望的最好情况。” 因此，除非真正需要执行pollLast（）... - bestsss

如果我重新思考我的应用程序，我认为使用队列而不是链表来解决我的问题应该相对容易。我只需要重新实现一些已经编写好的东西。 - ptikobj