LinkedBlockingQueue与ConcurrentLinkedQueue的区别

Question

我的问题与早前提出的这个问题有关。当我在生产者和消费者线程之间使用队列进行通信时，人们通常会推荐使用LinkedBlockingQueue还是ConcurrentLinkedQueue？

从使用中的优缺点来说，它们各有千秋。

就API层面而言，主要区别在于LinkedBlockingQueue可以选择性地设定上限。

- Adamski

Answer 1

对于生产者/消费者线程，我不确定 ConcurrentLinkedQueue 是否是一个合理的选择 - 它没有实现 BlockingQueue，而这是我认为生产者/消费者队列的基本接口。你需要调用 poll()，如果没有找到任何内容，则稍等片刻再次轮询等待新项目进来，从而导致延迟，并且当它为空时效率低下（由于从睡眠中不必要地唤醒）。

从 BlockingQueue 文档中可以看到:

BlockingQueue 的实现主要设计用于生产者-消费者队列。

我知道它并没有严格说明只有阻塞队列才应该用于生产者/消费者队列，但即便如此，还是应该考虑使用阻塞队列。

- Jon Skeet

---

谢谢 Jon - 我没有注意到那个。那么，何时/为什么会使用ConcurrentLinkedQueue？ - Adamski

当您需要从多个线程访问队列，但不需要在其上“等待”时。 - Jon Skeet

如果您的线程正在检查多个队列，那么ConcurrentLinkedQueue也非常有用。例如，在多租户服务器中。假设出于隔离原因，您不使用单个阻塞队列和租户鉴别器。 - LateralFractal

你的情况只适用于使用有界队列，在无界队列中，take()和put()仅比ConcurrentLinkedQueue消耗更多的资源（在同步方面）。尽管如此，在生产者-消费者场景中使用有界队列是最好的选择。 - amarnath harish

在我看来，ConcurrentLinkedQueue只是一个可用于多线程环境的链表。最好的类比是ConcurrentHashMap和HashMap。 - Nishit

Answer 2

这个问题值得更好的回答。

Java的ConcurrentLinkedQueue基于著名的Maged M. Michael和Michael L. Scott的算法，用于非阻塞无锁队列。

“非阻塞”这个术语在这里指争用资源（我们的队列），意味着无论平台调度程序做什么，比如中断线程，或者如果相关线程太慢，争用同一资源的其他线程仍然能够继续进行。例如，如果涉及锁定，持有锁的线程可能会被中断，等待该锁的所有线程都将被阻塞。Java中的内部锁（使用synchronized关键字）在性能方面也可能带来严重的惩罚——例如当涉及biased locking并且存在争用时，或者在VM决定在自旋优雅期间“膨胀”锁并阻止竞争线程之后……因此，在许多情况下（低/中等争用场景），对原子引用进行比较和设置可以更加高效，这正是许多非阻塞数据结构所做的。

Java的ConcurrentLinkedQueue不仅是非阻塞的，而且具有一个很棒的特性，即生产者不与消费者竞争。在单生产者/单消费者场景（SPSC）中，这意味着几乎没有竞争。在多生产者/单消费者场景中，消费者不会与生产者竞争。当多个生产者尝试offer()时，此队列确实存在竞争，但这是并发的定义。它基本上是一个通用且高效的非阻塞队列。

至于它不是BlockingQueue，嗯，阻塞线程等待队列是设计并发系统的可怕方式。不要这样做。如果您无法想出如何在生产者/消费者场景中使用ConcurrentLinkedQueue，则切换到更高级别的抽象，例如良好的Actor框架。

- Alexandru Nedelcu

---

根据你上一个段落，为什么你认为排队等待是设计并发系统的一种糟糕方式？如果我们有一个由10个线程组成的线程组，从任务队列中获取任务，当任务队列少于10个任务时阻塞会有什么问题？ - Pacerier

你不能轻率地使用“异常糟糕”的总体评价，因为那些你说要使用的演员框架往往使用线程池，而线程池本身就使用BlockingQueue。如果你需要一个高度反应灵敏的系统，并且知道如何处理背压（阻塞队列所缓解的问题），那么非阻塞显然更好。但是，通常情况下，阻塞IO和阻塞队列可以比非阻塞更有效，特别是如果你有长时间运行的任务，它们是IO绑定的，无法被分割成更小的任务。 - Adam Gent

@AdamGent - 演员框架确实有基于阻塞队列的邮箱实现，但在我看来，这是一个错误，因为阻塞不能跨异步边界工作，因此只适用于演示。对我来说，这一直是令人沮丧的源泉，例如Akka处理溢出的概念是阻塞而不是放弃消息，直到版本2.4发布之前还没有解决。话虽如此，我并不认为有用例可以优于阻塞队列。您还混淆了两件不应混淆的事情。我没有谈论阻塞I/O。 - Alexandru Nedelcu

@AlexandruNedelcu，虽然我基本上同意您关于背压的观点，但我还没有看到过从头到尾都是“无锁”的系统。无论是Node.js、Erlang还是Golang，在技术栈的某个地方，它都使用了某种等待策略，无论是阻塞队列（锁）还是CAS自旋，它都是阻塞的，并且在某些情况下，传统的锁策略更快。由于一致性的原因，不使用锁非常困难，这在阻塞IO和调度程序中尤为重要，它们是生产者/消费者。ForkJoinPool适用于短时间运行的任务，它仍然具有CAS自旋锁。 - Adam Gent

@AlexandruNedelcu 如果你能向我展示如何使用ConcurrentLinkedQueue（顺便说一下，它没有边界，因此我的弱反压力论点不成立）来实现生产者/消费者模式，这是调度程序和线程池所需的模式，那么我会屈服并承认BlockingQueue永远不应该被使用（而且你不能欺骗并委托给其他东西进行调度，比如akka，因为它反过来也会阻塞/等待，因为它是生产者/消费者）。 - Adam Gent

Answer 3

LinkedBlockingQueue 队列为空或已满时，相应的消费者/生产者线程会被阻塞。但这种阻塞特性是有代价的：每个put或take操作在生产者或消费者（如果有多个）之间存在锁竞争，因此在具有许多生产者/消费者的场景中，操作可能会变慢。

ConcurrentLinkedQueue 不使用锁，而是使用CAS进行其添加/轮询操作，可能会减少许多生产者和消费者线程之间的竞争。但作为一种“无等待”的数据结构，ConcurrentLinkedQueue 在空时不会阻塞，这意味着消费者将需要通过“繁忙等待”来处理poll()返回的null值，例如消费者线程占用CPU。

因此，哪一个更好取决于消费者线程的数量、它们的生产/消费速率等。每种情况都需要进行基准测试。

有一个特定的用例，ConcurrentLinkedQueue 明显更好的情况是当生产者首先生产某些东西，并通过将工作放入队列来完成其工作，只有在消费者开始消耗时，才知道他们会在队列为空时完成。（这里没有生产者-消费者之间的并发，但只有生产者-生产者和消费者-消费者之间的并发）

- dcernahoschi

---

这里有一个疑问。您提到消费者在队列为空时会等待，那么它要等多久？谁会通知它不要等待？ - Brinal

@brindal 我所知道的唯一等待的方法就是在循环中等待。这是一个重大问题，在这里的答案中没有得到太多关注。仅仅运行一个等待数据的循环就会使用大量的处理器时间。当风扇开始加速时，你就会知道了。唯一的解决办法是在循环中加入睡眠。因此，在数据流不一致的系统中存在问题。也许我误解了AlexandruNedelcu的答案，但操作系统本身就是一个并发系统，如果它充满了非阻塞事件循环，那将是极其低效的。 - orodbhen

好的，但如果使用“无界阻塞队列”，是否比基于* CAS *的并发“ConcurrentLinkedQueue”更好？ - amarnath harish

@orodbhen 放置睡眠也不能消除浪费。操作系统必须做很多工作才能将线程从睡眠状态中唤醒、调度和运行。如果消息尚不可用，则您的操作系统所做的工作就会白费。我建议最好使用BlockingQueue，因为它是专门为生产者-消费者问题设计的。 - Nishit

实际上，我对“消费/生产速率”部分非常感兴趣，那么如果速率变高，哪一个更好呢？ - http8086

ConcurrentLinkedQueue 中没有 take() 方法，也没有 put() 方法。 - Wuaner

Answer 4

另一种解决方案（不适用于大规模应用）是会合通道：java.util.concurrent SynchronousQueue。

- Ovidiu Lupas

Answer 5

如果您的队列是不可扩展的，并且仅包含一个生产者/消费者线程，则可以使用无锁队列（无需锁定数据访问）。

- Rahul

Answer 6

ConcurrentLinkedQueue.poll使用CAS来维护线程安全性。
LinkedBlockingQueue.poll使用ReentrantLock！因此它更慢。但提供阻塞功能。
ConcurrentLinkedQueue只是一个线程安全的链表。

- Apurva Singh