BlockingQueue详解
BlockingQueue简介
BlockingQueue:是一个阻塞队列。其功能用于生产者-消费者模式
而消费者线程则在队列尾部消费元素
通过这种方式能够达到将任务的生产和消费进行隔离的目的
BlockingQueue最典型的两个实现：ArrayBlockingQueue和LinkedBlockingQueue
下文笔者将讲述BlockingQueue API 及ArrayBlockingQueue和LinkedBlockingQueue的实现原理
1. BlockingQueue使用方式
BlockingQueue继承自Queue接口，也就是说其实现了队列相关的诸如offer，put，take，poll等一系列操作。如下是BlockingQueue的接口定义：
public interface BlockingQueue extends Queue { // 尝试往队列尾部添加元素，添加成功则返回true，添加失败则抛出IllegalStateException异常 boolean add(E e); // 尝试往队列尾部添加元素，添加成功则返回true，添加失败则返回false boolean offer(E e); // 尝试往队列尾部添加元素，如果队列满了，则阻塞当前线程，直到其能够添加成功为止 void put(E e) throws InterruptedException; // 尝试往队列尾部添加元素，如果队列满了，则最多等待指定时间， // 如果在等待过程中还是未添加成功，则返回false，如果在等待 // 过程中被中断，则抛出InterruptedException异常 boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException; // 尝试从队列头部取出元素，如果队列为空，则一直等待队列中有元素 E take() throws InterruptedException; // 尝试从队列头部拉取元素，如果队列为空，则最多等待指定时间， // 如果等待过程中拉取到了新元素，则返回该元素， // 如果等待过程被中断，则抛出InterruptedException异常 E poll(long timeout, TimeUnit unit) throws InterruptedException; // 获取当前队列剩余可存储元素的数量 int remainingCapacity(); // 从队列中移除指定对象 boolean remove(Object o); // 判断队列中是否存在指定对象 boolean contains(Object o); // 将队列中的元素转移到指定的集合中 int drainTo(Collection c); // 从队列中最多转移maxElements个元素到指定集合中 int drainTo(Collection c, int maxElements);}BlockingQueue功能:
提供一个阻塞队列，供使用者能够通过其阻塞特性，在队列头部和尾部移除和添加元素，从而达到在多线程环境将任务的生产和消费进行分离的目的。
添加和移除主要是通过add，offer，put和take，poll方法来进行的
而这些方法的效率是非常高的
因为其只需要在队列两端进行时间复杂度O(1)的操作
即使有多线程的竞争，但由于锁定时间非常短，因而通过多线程的偏向锁等特性
BlockingQueue还提供了其他的操作，主要包含计算剩余余量，移除指定对象，判断是否包含指定对象和将集合中元素移动到集合中。
2. ArrayBlockingQueue实现原理
对于ArrayBlockingQueue，顾名思义，其底层存储结构是一个数组，而我们在创建一个ArrayBlockingQueue的时候，是必须指定其能够存储的元素的数量的，因而通过这种方式，我们就可以保证数组的大小始终固定，而不会出现需要迁移数据的操作。这里我们首先看一下ArrayBlockingQueue的数据结构：
public class ArrayBlockingQueue extends AbstractQueue implements BlockingQueue, java.io.Serializable { // 用于存储当前添加到队列中的元素，使用以Object进行存储，而在取数据时进行转型 final Object[] items; // 记录了当前可以被取到的元素的下标索引，该索引位置是存在实际元素的 int takeIndex; // 记录了当前可以存放元素的下标索引，该索引位置是空置的， // 如果队列满了，则该索引位置指向的元素就不为空 int putIndex; // 记录了当前队列中存在的元素个数 int count; // 声明的全局锁，用于控制队列的存储元素等各个操作 final ReentrantLock lock; // 通过lock创建的一个等待条件，用于当队列为空时，阻塞当前尝试从队列中取元素的线程 private final Condition notEmpty; // 通过lock创建的一个等待条件，用于当队列满了时，阻塞当前尝试往队列中添加元素的线程 private final Condition notFull; transient Itrs itrs = null;}通过上述数据结构可以看出，ArrayBlockingQueue是通过一个循环数组的方式来实现存储元素的，这里takeIndex记录了当前可以取元素的索引位置，而putIndex则记录了下一个元素可以存储的位置。当队列满了时，takeIndex和putIndex将指向同一个元素，这里则可以通过count字段来判断当前是处于满状态还是空置状态。通过声明一个全局的锁来控制所有操作的控制权限，也就是说，对于ArrayBlockingQueue而言，其任何一个操作都是阻塞其他操作的。这里notEmpty和notFull则是由lock创建得来的，通过这两个分离的等待条件，可以实现队列两端线程添加和移除操作的分离。如下是ArrayBlockingQueue的入队和出队操作的源码：
private void enqueue(E x) { final Object[] items = this.items; items[putIndex] = x; // 将新元素放置到putIndex处 if (++putIndex == items.length) // 如果放置后putIndex达到了数组顶部，则将其循环至0号索引处 putIndex = 0; count++; notEmpty.signal(); // 由于添加了元素，说明队列不为空，则唤醒一个正在等待获取元素的线程}private E dequeue() { final Object[] items = this.items; @SuppressWarnings("unchecked") E x = (E) items[takeIndex]; // 取出takeIndex位置的元素，作为返回值返回 items[takeIndex] = null; // 重置takeIndex处的元素 if (++takeIndex == items.length) // 如果takeIndex达到了队列顶部，则将其循环至0号索引处 takeIndex = 0; count--; // 更新元素总量 if (itrs != null) // 更新迭代器数据 itrs.elementDequeued(); notFull.signal(); // 由于移除了元素，说明队列不满，则唤醒一个尝试往队列添加元素的线程 return x;}可以看到，这里enqueue()和dequeue()方法是入队和出队的核心方法。在enqueue()方法中，当成功入队之后，其会唤醒一个正在等待取出元素的线程；在dequeue()方法中，当成功出队之后，其会唤醒一个正在等待添加元素的线程。对于外层调用，这里我们主要以阻塞的put()和offer()方法为例进行讲解：
public void put(E e) throws InterruptedException { checkNotNull(e); // 检查元素是否为空，不为空则抛出异常 final ReentrantLock lock = this.lock; lock.lockInterruptibly(); // 锁定当前操作 try { while (count == items.length) // 在循环中检查，以防止当前线程是被意外唤醒的 notFull.await(); // 如果当前队列已满，则当前线程进入等待状态，并释放锁 enqueue(e); // 如果通过了while判断，说明队列不满，并且当前线程获取到了锁，则元素入队 } finally { lock.unlock(); // 操作完成，释放当前的锁 }}public E take() throws InterruptedException { final ReentrantLock lock = this.lock; lock.lockInterruptibly(); // 锁定当前的线程 try { while (count == 0) // 在循环中检查，以防止当前线程被意外唤醒 notEmpty.await(); // 如果当前队列为空，则当前线程进入等待状态，并释放锁 return dequeue(); // 如果通过了while判断，说明队列不为空，并且当前线程获取到了锁，则元素出队 } finally { lock.unlock(); // 操作完成，释放当前锁 }}在put()和take()操作中，首先都是通过while条件进行前置判断，对于put操作，如果队列满了，则在notFull中进行等待，对于take()操作，如果队列为空，则在notEmpty中进行等待，并且释放锁。在队列中有空闲空间或有元素时，才会继续执行put()或take()操作。
3. LinkedBlockingQueue实现原理
对于LinkedBlockingQueue，其底层是通过一个单项链表实现的，由于单项链表需要有一个指向下一个节点的指针，因而其必须使用一个对象（这里是Node）来存储当前元素的值和下一个节点的索引。如下是LinkedBlockingQueue的数据结构：
public class LinkedBlockingQueue extends AbstractQueue implements BlockingQueue, java.io.Serializable { // 记录了当前队列最多可以存储的元素的个数，如果不指定，则默认为Integer.MAX_VALUE private final int capacity; // 记录了当前队列中已经存储的元素个数 private final AtomicInteger count = new AtomicInteger(); // 记录了当前队列的头结点的指针，该节点中是不存储实际的元素的，头部的元素在下一个节点中存储。 // 这么处理的目的是，当队列为空时，头指针和尾指针都可以指向同一个不存储任何元素的Node节点。 transient Node head; // 记录了当前队列尾部节点的指针 private transient Node last; // 从队列中取元素的锁 private final ReentrantLock takeLock = new ReentrantLock(); // 通过takeLock创建的一个Condition对象，用于控制队列中没有元素时阻塞尝试获取元素的线程 private final Condition notEmpty = takeLock.newCondition(); // 往队列中存入元素的锁 private final ReentrantLock putLock = new ReentrantLock(); // 通过putLock创建的一个Condition对象，用于控制队列满了时阻塞尝试往队列中添加元素的线程 private final Condition notFull = putLock.newCondition(); // 当前用于存储元素的Node对象，其有一个next指针，记录了下一个节点的索引 static class Node { E item; Node next; Node(E x) { item = x; } }}通过上面的数据结构可以看出，LinkedBlockingQueue使用一个head指针指向了队列的头节点，使用一个last指针指向了队列的尾节点，使用capacity指定了队列最多能够存储的元素个数，使用count记录当前已经存储的元素个数，如此就可以对一个单向链表进行完全定性。这里为了实现阻塞的特性，LinkedBlockingQueue分别为队列头部和尾部声明了两个锁，并且创建了两个等待Condition。当往队列添加元素时，使用putLock锁定队列尾部，如果队列满了，则将该线程添加到notFull的Condition中，并且释放锁；当从队列总取元素时，使用takeLock锁定队列头部，如果队列为空，则将该线程添加到notEmpty的Condition中，并且释放锁。这里我们首先看一下LinkedBlockingQueue的入队和出队操作：
private void enqueue(Node node) { // 将队列尾部节点的next指针指向新的节点，并且更新last指针指向最新的尾部节点 last = last.next = node;}private E dequeue() { Node h = head; Node first = h.next; // 指向当前存储元素的指针 h.next = h; // 处理头节点的next指针，以便能更快的GC head = first; // 将头节点指向其下一个节点 E x = first.item; // 获取头部节点的元素作为返回值 first.item = null; // 更新头节点为空置的节点 return x;}可以看到，对于链表的入队和出队操作，其是非常简单的，这里仅仅只是单纯的入队和出队，并没有相关的锁的操作。我们还是通过阻塞的put()和take()方法来对LinkedBlockingQueue进行讲解：
public void put(E e) throws InterruptedException { if (e == null) throw new NullPointerException(); int c = -1; Node node = new Node(e); final ReentrantLock putLock = this.putLock; final AtomicInteger count = this.count; putLock.lockInterruptibly(); // 锁定队列尾部 try { while (count.get() == capacity) { // 在循环中判断，以防止当前线程被意外唤醒 notFull.await(); // 如果当前队列已满，则使当前线程进入等待状态 } enqueue(node); // 这里说明队列队列没满，并且当前线程获取到了锁，那么将元素压入队列 c = count.getAndIncrement(); // 更新元素个数 if (c + 1 1) // 该判断说明取出元素中队列中还是有元素，那么继续唤醒后面等待的线程 notEmpty.signal(); } finally { takeLock.unlock(); // 释放当前的锁 } if (c == capacity) // 当前判断说明尝试存入元素的Condition中有等待的线程，这里因为取了元素， // 因而队列中有空闲空间，因此唤醒正在等待存入元素的线程 signalNotFull(); return x;}上面的入队和出队操作中，基本都是先判断前置条件是否成立，即队列未满或不为空，如果成立，当前线程才有权限进行入队和出队操作。在操作完成之后，当前线程还会唤醒正在等待尝试获取或取出元素的线程。
ArrayBlockingQueue和LinkedBlockingQueue区别:
1.两者底层数据结构不同
ArrayBlockingQueue是通过循环数组来实现的
LinkedBlockingQueue是通过单向链表来实现的；
2.两者阻塞方式不同
ArrayBlockingQueue使用了一个全局锁来处理所有的操作
无论是队列头部还是尾部，只要一个线程获取到了锁，那么其他所有的线程将都会被阻塞
只不过由于锁定的时间非常短，因而这种消耗可以忽略不计；
LinkedBlockingQueue为队列头部和尾部分别使用了两个不同的锁
在元素入队和出队操作时，两者几乎是互不干扰的；
3.两者初始化大小不同
ArrayBlockingQueue必须指定一个初始化大小
LinkedBlockingQueue可以指定初始大小，也可以不指定，不指定时默认为 Integer.MAX_VALUE。
