深入理解 JUC:关于线程安全队列的若干总结

前面的几篇文章中,我们对于 JUC 包中提供的线程安全队列的设计与实现进行了全面的分析。JUC 包为 java 开发人员提供了丰富的线程安全队列实现,以满足不同的性能和应用场景需求。然而,不知道你是否与我一样,在学习了各个线程安全队列的实现机制之后,反而有点犯迷糊,这些线程安全队列我们在具体编码时该如何选择呢?于是我打算写一篇总结性的文章,对各个线程安全队列的特性进行总结。

image

上面这幅图展示了 JUC 线程安全队列的类继承关系,总的来说线程安全队列分为 Queue 和 Deque 两大类,本文主要关注 Queue。在 Queue 的范围内可以进一步将线程安全队列分为阻塞队列和非阻塞队列,目前只有 ConcurrentLinkedQueue 是非阻塞队列,其它都是阻塞队列。

接口说明

由上面的类继承关系图可知,在整个 Queue 的继承关系中包含 3 个接口,即 Queue 接口、BlockingQueue 接口,以及 TransferQueue 接口,这 3 个接口依次成继承关系。

Queue 接口

Queue 接口继承自 Collection 接口,增加了队列相关的操作,定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
public interface Queue<E> extends Collection<E> {

boolean add(E e);
boolean offer(E e);

E poll();
E peek();
E element();

E remove();

}

针对该接口各方法的含义说明如下:

  • add:往队列中添加元素,如果成功则返回 true,对于有界队列来说,如果队列已满则抛出 IllegalStateException 异常。
  • offer:往队列中添加元素,如果成功则返回 true,对于有界队列来说,如果队列已满则返回 false,而不是抛出异常。
  • poll:移除队列头结点,并返回结点元素值,如果队列为空则返回 null。
  • peek:仅获取头结点元素值而不删除结点,如果队列为空则返回 null。
  • element:仅获取头结点元素值而不删除结点,如果队列为空则抛出 NoSuchElementException 异常。
  • remove:移除队列头结点,并返回结点元素值,如果队列为空则抛出 NoSuchElementException 异常。

BlockingQueue 接口

BlockingQueue 接口继承自 Queue 接口,用于描述阻塞队列。当队列无法及时响应用户请求时,例如当我们尝试从空队列中获取元素,或者继续往已满的有界队列中添加元素,BlockingQueue 定义了以下 4 种响应形式:

  1. 抛出异常。
  2. 立即返回特殊值,例如 null 或 false。
  3. 无限期阻塞当前请求,直到队列状态变为可用。
  4. 超时阻塞当前请求,直到队列状态变为可用。

BlockingQueue 接口的定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public interface BlockingQueue<E> extends Queue<E> {

boolean offer(E e);
boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException;
boolean add(E e);
void put(E e) throws InterruptedException;

E poll(long timeout, TimeUnit unit) throws InterruptedException;
E take() throws InterruptedException;

boolean remove(Object o);

boolean contains(Object o);
int remainingCapacity();

int drainTo(Collection<? super E> c);
int drainTo(Collection<? super E> c, int maxElements);

}

针对该接口各方法的含义说明如下:

  • offer:往队列中添加元素,如果成功则返回 true,对于有界队列来说,如果队列已满则返回 false,而不是抛出异常。BlockingQueue 同时还声明了超时版本的 offer 方法。
  • add:往队列中添加元素,如果成功则返回 true,对于有界队列来说,如果队列已满则抛出 IllegalStateException 异常。
  • put:往队列中添加元素,对于有界队列来说,如果队列已满则阻塞当前请求,期间支持响应中断。
  • poll:移除队列头结点,并返回结点元素值,如果队列为空则等待指定时间,并在超时时返回 null,期间支持响应中断。
  • take:仅获取头结点元素值而不删除结点,如果队列为空则阻塞等待,期间支持响应中断。
  • remove:接收一个参数,从队列中删除值等于该参数的结点,如果存在多个结点满足要求,则删除第一个。
  • contains:接收一个参数,判断队列中是否存在值等于该参数的结点。
  • remainingCapacity:返回队列的剩余容量,如果是无界队列,则返回 Integer.MAX_VALUE
  • drainTo:从队列中移除所有(或指定个数)结点,并将结点元素放入参数指定的集合中返回,相对于逐个移除更加高效。

TransferQueue 接口

TransferQueue 接口在 JDK 1.7 被引入,用于描述一种全新的阻塞队列。LinkedTransferQueue 实现自 TransferQueue 接口,并且是目前(JDK 1.8)该接口的唯一实现类。TransferQueue 接口继承自 BlockingQueue 接口,由 BlockingQueue 描述的阻塞队列在队列为空或者已满时,相应的出队列线程或入队列线程会阻塞等待,而 TransferQueue 则更进一步。以入队列操作为例,当线程成功将元素添加到由 TransferQueue 描述的阻塞队列中后,该线程通常会一直阻塞直到某个出队列线程从队列中取走该入队列线程添加的元素。

TransferQueue 在 BlockingQueue 接口的基础上增加了以下方法:

1
2
3
4
5
6
7
8
9
10
11
public interface TransferQueue<E> extends BlockingQueue<E> {

void transfer(E e) throws InterruptedException;

boolean tryTransfer(E e);
boolean tryTransfer(E e, long timeout, TimeUnit unit) throws InterruptedException;

boolean hasWaitingConsumer();
int getWaitingConsumerCount();

}

针对各方法的含义说明如下:

  • transfer:生产者将元素直接传递给正在等待的消费者,而不执行入队列操作,如果没有正在等待的消费者则无限期等待,期间支持响应中断。
  • tryTransfer:生产者将元素直接传递给正在等待的消费者,而不执行入队列操作,如果没有正在等待的消费者则返回 false,提供相应的超时版本。
  • hasWaitingConsumer:检查是否存在正在等待的消费者。
  • getWaitingConsumerCount:返回当前正在等待的消费者数目(近似值)。

由上述接口方法释义我们可以了解到,TransferQueue 系的队列支持在两个线程之间直接交换数据,而无需先将数据落地存储到队列中,如果确实需要落地,则线程可以随数据一起在队列上等待。

特性总结

了解了线程安全队列接口的相关定义,下面对实现了这些接口的具体线程安全队列各自的特性做一个总结。

基本属性

队列 数据结构 是否阻塞 是否有界 是否允许 NULL 值 安全机制 备注
ConcurrentLinkedQueue 链表 CAS
ArrayBlockingQueue 数组 ReentrantLock
LinkedBlockingQueue 链表 ReentrantLock
PriorityBlockingQueue 最小堆(数组) 几乎无界,但受制于底层数组长度限制 ReentrantLock 线程安全的优先级队列
DelayQueue PriorityQueue ReentrantLock 队列元素需要实现 Delayed 接口,即所有的元素都具备过期属性,并按照过期的先后顺序在队列中进行组织
SynchronousQueue Dual Stack / Dual Queue CAS 不同于一般线程安全队列,主要应用于线程之间的协同,类比“生产者-消费者”模式
LinkedTransferQueue Dual Queue CAS 可以看作是 ConcurrentLinkedQueue、SynchronousQueue(公平模式)和 LinkedBlockingQueue 的超集,并且更加实用和高效

API 说明

队列 add offer offert(timeout) put poll poll(timeout) take peek element remove size
ConcurrentLinkedQueue 委托给 offer 接口 往队尾追加元素,无容量限制,始终返回 true 不支持 不支持 移除并返回队头元素,如果队列为空则返回 null 不支持 不支持 仅返回队头元素,如果队列为空则返回 null 仅返回队头元素,如果队列为空则抛 NoSuchElementException 异常 移除并返回队头元素,如果队列为空则抛 NoSuchElementException 异常 近似值
ArrayBlockingQueue 往队尾追加元素,成功则返回 true,失败则抛出 IllegalStateException 异常 往队尾追加元素,成功则返回 true,失败则返回 false 往队尾追加元素,成功则返回 true,失败则先等待一段时间,而不是立即返回 false 往队尾追加元素,成功则立即返回,失败则持续等待,直到队列有空闲容量 移除并返回队头元素,如果队列为空则立即返回 null 移除并返回队头元素,如果队列为空则先等待一段时间,而不是立即返回 null 移除并返回队头元素,如果队列为空则等待直到有新的元素可以返回 仅返回队头元素,如果队列为空则返回 null 仅返回队头元素,如果队列为空则抛 NoSuchElementException 异常 移除并返回队头元素,如果队列为空则抛 NoSuchElementException 异常 精确值
LinkedBlockingQueue 往队尾追加元素,成功则返回 true,失败则抛出 IllegalStateException 异常 往队尾追加元素,成功则返回 true,失败则返回 false 往队尾追加元素,成功则返回 true,失败则先等待一段时间,而不是立即返回 false 往队尾追加元素,成功则立即返回,失败则持续等待,直到队列有空闲容量 移除并返回队头元素,如果队列为空则立即返回 null 移除并返回队头元素,如果队列为空则先等待一段时间,而不是立即返回 null 移除并返回队头元素,如果队列为空则等待直到有新的元素可以返回 仅返回队头元素,如果队列为空则返回 null 仅返回队头元素,如果队列为空则抛 NoSuchElementException 异常 移除并返回队头元素,如果队列为空则抛 NoSuchElementException 异常 精确值
PriorityBlockingQueue 委托给 offer 接口 往队尾追加元素,因为是无界队列所以一般都会成功,期间可能会执行扩容操作,如果容量到达上限则 OOM 委托给 offer 接口 委托给 offer 接口 移除并返回队头(最高优先级)元素,如果队列为空则立即返回 null 移除并返回队头(最高优先级)元素,如果队列为空则先等待一段时间,而不是立即返回 null 移除并返回队头(最高优先级)元素,如果队列为空则等待直到有新的元素可以返回 仅返回队头(最高优先级)元素,如果队列为空则返回 null 仅返回队头元素,如果队列为空则抛 NoSuchElementException 异常 移除并返回队头元素,如果队列为空则抛 NoSuchElementException 异常 精确值
DelayQueue 委托给 offer 接口 往队尾追加元素,因为是无界队列所以一般都会成功,期间可能会执行扩容操作,如果容量到达上限则 OOM 委托给 offer 接口 委托给 offer 接口 移除并返回队头(已到期)元素,如果队列为空或没有到期的元素则立即返回 null 移除并返回队头(已到期)元素,如果队列为空或没有到期的元素则先等待一段时间,而不是立即返回 null 移除并返回队头(已到期)元素,如果队列为空或没有到期的元素则等待直到有新的元素到期 仅返回队头(最先到期,此时可能还未到期)元素,如果队列为空则返回 null 仅返回队头(最先到期,此时可能还未到期)元素,如果队列为空则抛 NoSuchElementException 异常 移除并返回队头(已到期)元素,如果队列为空或没有到期的元素则抛 NoSuchElementException 异常 精确值
SynchronousQueue 委托给 offer 接口,入队列失败则抛出 IllegalStateException 异常 往队尾追加元素,成功(说明队列中存在待匹配的元素)则返回 true,失败(说明队列中不存在待匹配的元素)则返回 false 往队尾追加元素,如果队列中存在待匹配的元素则入队列成功,返回 true,否则等待指定时间,如果仍然没有可以匹配的元素则入队列失败,返回 false 往队尾追加元素,并一直等待直到被匹配 移除并返回队列中第一个与之匹配的结点元素,如果不存在则立即返回 null 移除并返回队列中第一个与之匹配的结点元素,如果不存在则先等待一段时间,而不是立即返回 null 移除并返回队列中第一个与之匹配的结点元素,如果不存在则等待直到有匹配的元素可以返回 始终返回 null 始终抛 NoSuchElementException 异常 移除并返回队列中第一个数据结点元素,如果不存在则抛 NoSuchElementException 异常 始终返回 0
LinkedTransferQueue 往队尾追加元素,因为是无界队列,所以始终返回 true 往队尾追加元素,因为是无界队列,所以始终返回 true 往队尾追加元素,因为是无界队列,所以始终返回 true,并且不会因为队列已满而阻塞等待 往队尾追加元素,因为是无界队列,所以不会因为队列已满而阻塞等待 移除并返回队列中第一个数据结点元素,如果不存在则立即返回 null 移除并返回队列中第一个数据结点元素,如果不存在则先等待一段时间,而不是立即返回 null 移除并返回队列中第一个数据结点元素,如果不存在则等待直到有新的元素可以返回 仅返回队列中的第一个数据节点元素,如果不存在则返回 null 仅返回队列中的第一个数据节点元素,如果不存在则抛 NoSuchElementException 异常 移除并返回队列中的第一个数据节点元素,如果不存在则抛 NoSuchElementException 异常 精确值(O(n)