Java中的阻塞队列

Java中的阻塞队列

1. 什么是阻塞队列

阻塞队列相比普通队列，支持下面两个操作：

• 支持阻塞的插入方法。队列满时，插入元素的线程可以阻塞等待队列变为不满。
• 支持阻塞的移除方法。队列为空时，获取元素的线程可以阻塞等待队列变为非空。

阻塞队列常常用于生产者消费者场景。

在阻塞队列不可用时，这两个附加操作提供了四种处理方式：

方法/处理方式	抛出异常	返回特殊值	一直阻塞	超时退出
插入方法	add(e)	offer(e)	put(e)	offer(e,time,unit)
移除方法	remove()	poll()	take()	poll(time,unit)
检查方法	element()	peek()	不可用	不可用

• 抛出异常：当队列满时再插入元素，会抛出IllegalStateException("Queuefull")异常；当队列空时再获取元素，会抛出NoSuchElementException异常。
• 返回特殊值：当往队列插入元素时，插入成功返回 true。当从队列取出元素时，没有则返回 null。
• 一直阻塞：当阻塞队列满时，如果put元素，队列会一直阻塞生产者线程，直到队列可用或者响应中断退出。当队列空时，如果消费者线程从队列take元素，队列会阻塞消费者线程，知道队列不为空。
• 超时退出：当阻塞队列满时，如果生产者线程往队列里插入元素，队列会阻塞生产者线程一段时间，如果超过指定时间，生产者线程就会退出。

2. Java中的阻塞队列

JDK7 提供了下列 7 个阻塞队列：

• ArrayBlockingQueue。一个由数组结构组成的有界阻塞队列。

• LinkedBlockingQueue。一个由链表结构组成的有界阻塞队列。

• PriorityBlockingQueue。一个支持优先级排序的无界阻塞队列。

• DelayQueue。一个使用优先级队列实现的无界阻塞队列。

• SynchronousQueue。一个不存储元素的阻塞队列。

• LinkedTransferQueue。一个由链表结构组成的无界阻塞队列。

• LinkedBlockingDeque。一个由链表结构组成的双向阻塞队列。

2.1 ArrayBlockingQueue

ArrayBlockingQueue是一个数组实现的有界阻塞队列，按照 FIFO 原则对元素排序。

默认状态下线程竞争该队列是不公平的，但可以用以下代码创建一个公平的阻塞队列：

ArrayBlockingQueue fairQueue = new ArrayBlockingQueue(1000,true);

公平性使用一个公平的可重入锁实现的。

2.2 LinkedBlockingQueue

LinkedBlockingQueue是一个链表实现的有界阻塞队列。

默认和最大长度是Integer.MAX_VALUE，按照先入先出原则进行排序。

2.3 PriorityBlockingQueue

PriorityBlockingQueue是支持优先级的无界阻塞队列，默认情况下元素自然顺序升序排列，也可以自定义Comparator。

2.4 DelayQueue

DelayQueue是一个支持延时获取元素的无界阻塞队列。队列使用PriorityQueue实现，队列中的元素必须实现Delayed接口，在创建元素时指定多久才能从队列中获取当前元素。

可以用在以下场景：

• 缓存系统的设计。可以用DelayQueue保存缓存元素的有效期，使用一个线程循环查询DelayQueue，一旦能获取元素，说明有效期到了。
• 定时任务调度。可以用DelayQueue保存当前将执行的任务和执行时间，一旦从DelayQueue获取任务就开始执行，比如TimerQueue就是用DelayQueue实现的。

2.5 SynchronousQueue

SynchronousQueue是一个不存储元素的阻塞队列，每一个put操作必须等待一个take操作，否则不能继续put。

SynchronousQueue可以看成一个传球手，负责把生产者线程处理的数据直接传递给消费者线程。队列本身不存储元素，非常适合传递性场景，吞吐量很高。

2.6 LinkedTransferQueue

LinkedTransferQueue是一个链表结构的无界阻塞队列。相对于其他阻塞队列，LinkedTransferQueue多了tryTransfer()和transfer()方法。

transfer()方法

如果当前有消费者正在等待接收元素，比如take()方法或poll()方法，transfer()方法可以把生产者传入的元素立即transfer()给消费者。如果没有消费者在等待接收元素，transfer()方法会将元素存放在队列的tail节点，并等到该元素被消费者消费了才返回。

tryTransfer()方法

tryTransfer()方用来试探生产者传入的元素能否直接传给消费者。如果没有消费者等待接收元素，就返回false。

tryTransfer()方法无论消费者是否接收，方法立即返回，而transfer()方法必须等待消费者消费了才返回。

2.7 LinkedBlockingDeque

LinkedBlockingDeque是一个由链表结构组成的双向阻塞队列。

由于是双向队列，多了addFirst()、addLast()、offerFirst()等方法。

这个队列可以用于工作窃取模式中。

3. 阻塞队列实现原理

JDK 使用通知模式实现阻塞队列。

• 当生产者往满的队列里添加元素时，会阻塞住生产者。

• 当消费者消费了一个队列中的元素后，会通知生产者当前队列可用。

上面的两步在 JDK 中使用了 Condition 实现。

当往队列里插入元素，而队列不可用时，阻塞生产者主要通过LockSupport.park(this)来实现。