java - 有界无锁阻塞队列吗？

Question

目前我们有 LinkedBlockingQueue 和 ConcurrentLinkedQueue。

LinkedBlockingQueue 可以有界，但它使用锁。

ConcurrentLinkedQueue 不使用锁，但它不受限制。而且它不会阻塞，这使得轮询变得困难。

显然，我不能有一个既阻塞又无锁(无等待或非阻塞或其他)的队列。我不要求学术定义。

有谁知道主要是无锁(不在热路径中使用锁)、空时阻塞(无需忙等待)和有界(满时阻塞)的队列实现？堆外解决方案也很受欢迎。

我听说过 LMAX Disruptor，但它看起来根本不像队列。

我也很高兴知道非通用解决方案(单一生产者单一消费者、SPMC、MPSC)

如果没有已知的实现，我也很高兴知道可能的算法。

Answer 1

无锁数据结构使用原子读写(例如 compare-and-swap )来消除对锁的需求。当然，这些数据结构永远不会阻塞。

你所描述的是一个使用无锁机制进行非阻塞调用的队列，例如remove() 使用非空队列，同时使用锁来阻塞，例如remove() 在空队列上。

正如您可能意识到的那样，这是不可能实现的。例如，如果您要在弹出操作之后查看队列实际上是否为空，然后继续阻塞，那么在您阻塞时，队列可能已经有一个或多个项目被另一个线程插入。