转载

LinkedBlockingQueue vs ConcurrentLinkedQueue

1. 简单的开篇

LinkedBlockingQueue和 ConcurrentLinkedQueue 是 Java 高并发场景中最常使用的队列。尽管这两个队列经常被用作并发场景的数据结构，但它们之间仍有细微的特征和行为差异。

在这篇文章中，我将和大家一起探讨这两者之间的异同点。欢迎大家在留言讨论~

2. LinkedBlockingQueue

首先 LinkedBlockingQueue 是一个 “可选且有界” 的阻塞队列实现，你可以根据需要指定队列的大小。

接下来，我将创建一个 LinkedBlockingQueue ，它最多可以包含100个元素：

BlockingQueue<Integer> boundedQueue = new LinkedBlockingQueue<>(100);

当然，我们也可以通过不指定大小，来创建一个无界的 LinkedBlockingQueue ：

BlockingQueue<Integer> unboundedQueue = new LinkedBlockingQueue<>();

无界队列表示在创建时未指定队列的大小。因此，队列可以随着元素的添加而动态增长。但是，如果没有剩余内存，则队列将抛出 java.lang.OutOfMemory 错误。

这里留下一个问题给大家思考：创建无界队列是好还是坏呢?

我们还可以从现有的集合来创建 LinkedBlockingQueue ：

Collection<Integer> listOfNumbers = Arrays.asList(1,2,3,4,5);
BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(listOfNumbers);

LinkedBlockingQueue 实现了 BlockingQueue 接口，该接口为它提供了阻塞性质 。

阻塞队列表示如果访问线程已满（当队列有界时）或变为空，则队列将阻塞该线程。如果队列已满，则添加新元素将阻塞访问线程，除非新元素有可用空间。类似地，如果队列为空，则访问元素会阻塞调用线程：

ExecutorService executorService = Executors.newFixedThreadPool(1);
LinkedBlockingQueue<Integer> queue = new LinkedBlockingQueue<>();
executorService.submit(() -> {
  try {
    queue.take();
  } 
  catch (InterruptedException e) {
    // exception handling
  }
});

在上面的代码片段中，我们正在访问一个空队列。因此， take() 方法阻塞调用线程。

LinkedBlockingQueue 的阻塞特性与一些开销相关。这个代价是因为每个 put 或 take 操作在生产者线程或使用者线程之间都是锁争用的。因此，在许多生产者和消费者的情况下， put 和take 动作可能会慢一些。

3. ConcurrentLinkedQueue

首先声明， ConcurrentLinkedQueue 是一个无边界、线程安全且无阻塞的队列

创建一个空的 ConcurrentLinkedQueue :

ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue();

同上面一样，我们也可以从现有集合创建 ConcurrentLinkedQueue ：

Collection<Integer> listOfNumbers = Arrays.asList(1,2,3,4,5);
ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>(listOfNumbers);

不同于 LinkedBlockingQueue ， ConcurrentLinkedQueue 是非阻塞的队列。因此，即使队列为空(empty)，它也不会阻塞线程。相反，它会返回空（null）。虽然它是无界的，但如果没有额外的内存来添加新元素，它依旧会抛出 java.lang.OutOfMemory 错误。

除了非阻塞之外， ConcurrentLinkedQueue 还有其他特性。

在任何生产者-消费者场景中，消费者都不会满足于生产者；但是，多个生产者将相互竞争：

int element = 1;
ExecutorService executorService = Executors.newFixedThreadPool(2);
ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();
 
Runnable offerTask = () -> queue.offer(element);
 
Callable<Integer> pollTask = () -> {
  while (queue.peek() != null) {
    return queue.poll().intValue();
  }
  return null;
};
 
executorService.submit(offerTask);
Future<Integer> returnedElement = executorService.submit(pollTask);
assertThat(returnedElement.get().intValue(), is(equalTo(element)));

第一个任务 offerTask 向队列中添加元素，第二个任务 pollTask 从队列中检索元素。 pollTask 首先检查队列中的元素，因为 ConcurrentLinkedQueue 是非阻塞的，并且可以返回 null 值。

4. 求同

LinkedBlockingQueue 和 ConcurrentLinkedQueue 都是队列实现，并具有一些共同特征。让我们讨论一下这两个队列的相似之处：

都 实现 Queue 接口
它们都使用 linked nodes 存储节点
都适用于并发访问场景

5. 存异

尽管这两种队列都有某些相似之处，但也有一些实质性的特征差异：

特性	LinkedBlockingQueue	ConcurrentLinkedQueue
阻塞性	阻塞队列，并实现 blocking queue 接口	非阻塞队列，不实现 blocking queue 接口
队列大小	可选的有界队列，这意味着可以在创建期间定义队列大小	无边界队列，并且没有在创建期间指定队列大小的规定
锁特性	基于锁的队列	无锁队列
算法	锁的实现基于 “双锁队列（two lock queue）” 算法	依赖于 Michael&Scott算法来实现无阻塞、无锁队列
实现	在双锁队列算法机制中， LinkedBlockingQueue 使用两种不同的锁， putLock 和 takeLock 。 put/take 操作使用第一个锁类型， take/poll 操作使用另一个锁类型	使用CAS（ Compare And Swap ）进行操作
阻塞行为	当队列为空时，它会阻塞访问线程	当队列为空时返回 null，它不会阻塞访问线程