java 多線程阻塞隊列與阻塞方法與和非阻塞方法

Queue是什么

隊列，是一種數據結構。除了優先級隊列和LIFO隊列外，隊列都是以FIFO（先進先出）的方式對各個元素進行排序的。無論使用哪種排序方式，隊列的頭都是調用remove()或poll()移除元素的。在FIFO隊列中，所有新元素都插入隊列的末尾。隊列都是線程安全的，內部已經實現安全措施，不用我們擔心

Queue中的方法

Queue中的方法不難理解，6個，每2對是一個也就是總共3對。看一下JDK API就知道了：

注意一點就好，Queue通常不允許插入Null，盡管某些實現（比如LinkedList）是允許的，但是也不建議。

使用非阻塞隊列的時候有一個很大問題就是：它不會對當前線程產生阻塞，那么在面對類似消費者-生產者的模型時，就必須額外地實現同步策略以及線程間喚醒策略，這個實現起來就非常麻煩。但是有了阻塞隊列就不一樣了，它會對當前線程產生阻塞，比如一個線程從一個空的阻塞隊列中取元素，此時線程會被阻塞直到阻塞隊列中有了元素。當隊列中有元素后，被阻塞的線程會自動被喚醒（不需要我們編寫代碼去喚醒）。這樣提供了極大的方便性。

一.幾種主要的阻塞隊列

自從Java 1.5之后，在java.util.concurrent包下提供了若干個阻塞隊列，主要有以下幾個：

　　ArrayBlockingQueue：基于數組實現的一個阻塞隊列，在創建ArrayBlockingQueue對象時必須制定容量大小。并且可以指定公平性與非公平性，默認情況下為非公平的，即不保證等待時間最長的隊列最優先能夠訪問隊列。

　　LinkedBlockingQueue：基于鏈表實現的一個阻塞隊列，在創建LinkedBlockingQueue對象時如果不指定容量大小，則默認大小為Integer.MAX_VALUE。

　　PriorityBlockingQueue：以上2種隊列都是先進先出隊列，而PriorityBlockingQueue卻不是，它會按照元素的優先級對元素進行排序，按照優先級順序出隊，每次出隊的元素都是優先級最高的元素。注意，此阻塞隊列為無界阻塞隊列，即容量沒有上限（通過源碼就可以知道，它沒有容器滿的信號標志），前面2種都是有界隊列。

　　DelayQueue：基于PriorityQueue，一種延時阻塞隊列，DelayQueue中的元素只有當其指定的延遲時間到了，才能夠從隊列中獲取到該元素。DelayQueue也是一個無界隊列，因此往隊列中插入數據的操作（生產者）永遠不會被阻塞，而只有獲取數據的操作（消費者）才會被阻塞。

二.阻塞隊列中的方法 VS 非阻塞隊列中的方法

1.非阻塞隊列中的幾個主要方法：

add(E e):將元素e插入到隊列末尾，如果插入成功，則返回true；如果插入失敗（即隊列已滿），則會拋出異常；

remove()：移除隊首元素，若移除成功，則返回true；如果移除失敗（隊列為空），則會拋出異常；

offer(E e)：將元素e插入到隊列末尾，如果插入成功，則返回true；如果插入失敗（即隊列已滿），則返回false；

poll()：移除并獲取隊首元素，若成功，則返回隊首元素；否則返回null；

peek()：獲取隊首元素，若成功，則返回隊首元素；否則返回null

對于非阻塞隊列，一般情況下建議使用offer、poll和peek三個方法，不建議使用add和remove方法。因為使用offer、poll和peek三個方法可以通過返回值判斷操作成功與否，而使用add和remove方法卻不能達到這樣的效果。注意，非阻塞隊列中的方法都沒有進行同步措施。

//在這篇筆記中沒有介紹非阻塞隊列，大部分阻塞隊列都可以有非阻塞方法和阻塞方法

2.阻塞隊列中的幾個主要方法：

阻塞隊列包括了非阻塞隊列中的大部分方法，上面列舉的5個方法在阻塞隊列中都存在，但是要注意這5個方法在阻塞隊列中都進行了同步措施。除此之外，阻塞隊列提供了另外4個非常有用的方法：

put(E e)

take()

offer(E e,long timeout, TimeUnit unit)

poll(long timeout, TimeUnit unit)

put方法用來向隊尾存入元素，如果隊列滿，則等待；

take方法用來從隊首取元素，如果隊列為空，則等待；

offer方法用來向隊尾存入元素，如果隊列滿，則等待一定的時間，當時間期限達到時，如果還沒有插入成功，則返回false；否則返回true；

poll方法用來從隊首取元素，如果隊列空，則等待一定的時間，當時間期限達到時，如果取到，則返回null；否則返回取得的元素；

注意：

1、必須要使用take()方法在獲取的時候達成阻塞結果
2、使用poll()方法將產生非阻塞效果

三.阻塞隊列的實現原理

前面談到了非阻塞隊列和阻塞隊列中常用的方法，下面來探討阻塞隊列的實現原理，本文以ArrayBlockingQueue為例，其他阻塞隊列實現原理可能和ArrayBlockingQueue有一些差別，但是大體思路應該類似，有興趣的朋友可自行查看其他阻塞隊列的實現源碼。

首先看一下ArrayBlockingQueue類中的幾個成員變量：

public class ArrayBlockingQueue<E> extends AbstractQueue<E>
implements BlockingQueue<E>, java.io.Serializable {
private static final long serialVersionUID = -817911632652898426L;
/** The queued items */
private final E[] items;
/** items index for next take, poll or remove */
private int takeIndex;
/** items index for next put, offer, or add. */
private int putIndex;
/** Number of items in the queue */
private int count;
/*
* Concurrency control uses the classic two-condition algorithm
* found in any textbook.
*/
/** Main lock guarding all access */
private final ReentrantLock lock;
/** Condition for waiting takes */
private final Condition notEmpty;
/** Condition for waiting puts */
private final Condition notFull;
}

可以看出，ArrayBlockingQueue中用來存儲元素的實際上是一個數組，takeIndex和putIndex分別表示隊首元素和隊尾元素的下標，count表示隊列中元素的個數。

lock是一個可重入鎖，notEmpty和notFull是等待條件。

下面看一下ArrayBlockingQueue的構造器，構造器有三個重載版本：

public ArrayBlockingQueue(int capacity) {
}
public ArrayBlockingQueue(int capacity, boolean fair) {
?
}
public ArrayBlockingQueue(int capacity, boolean fair,
????????????????????????? Collection<? extends E> c) {
}

第一個構造器只有一個參數用來指定容量，第二個構造器可以指定容量和公平性，第三個構造器可以指定容量、公平性以及用另外一個集合進行初始化。

然后看它的兩個關鍵方法的實現：put()和take()：

public void put(E e) throws InterruptedException {
??? if (e == null) throw new NullPointerException();
??? final E[] items = this.items;
??? final ReentrantLock lock = this.lock;
??? lock.lockInterruptibly();
??? try {
??????? try {
??????????? while (count == items.length)
??????????????? notFull.await();
??????? } catch (InterruptedException ie) {
??????????? notFull.signal(); // propagate to non-interrupted thread
??????????? throw ie;
??????? }
??????? insert(e);
??? } finally {
??????? lock.unlock();
??? }
}

從put方法的實現可以看出，它先獲取了鎖，并且獲取的是可中斷鎖，然后判斷當前元素個數是否等于數組的長度，如果相等，則調用notFull.await()進行等待，如果捕獲到中斷異常，則喚醒線程并拋出異常。

當被其他線程喚醒時，通過insert(e)方法插入元素，最后解鎖。

我們看一下insert方法的實現：

private void insert(E x) {
??? items[putIndex] = x;
??? putIndex = inc(putIndex);
??? ++count;
??? notEmpty.signal();
}

它是一個private方法，插入成功后，通過notEmpty喚醒正在等待取元素的線程。

下面是take()方法的實現：

public E take() throws InterruptedException {
??? final ReentrantLock lock = this.lock;
??? lock.lockInterruptibly();
??? try {
??????? try {
??????????? while (count == 0)
??????????????? notEmpty.await();
??????? } catch (InterruptedException ie) {
??????????? notEmpty.signal(); // propagate to non-interrupted thread
??????????? throw ie;
??????? }
??????? E x = extract();
??????? return x;
??? } finally {
??????? lock.unlock();
??? }
}

跟put方法實現很類似，只不過put方法等待的是notFull信號，而take方法等待的是notEmpty信號。在take方法中，如果可以取元素，則通過extract方法取得元素，下面是extract方法的實現：

private E extract() {
??? final E[] items = this.items;
??? E x = items[takeIndex];
??? items[takeIndex] = null;
??? takeIndex = inc(takeIndex);
??? --count;
??? notFull.signal();
??? return x;
}

跟insert方法也很類似。

其實從這里大家應該明白了阻塞隊列的實現原理，事實它和我們用Object.wait()、Object.notify()和非阻塞隊列實現生產者-消費者的思路類似，只不過它把這些工作一起集成到了阻塞隊列中實現。

四.示例和使用場景

下面先使用Object.wait()和Object.notify()、非阻塞隊列實現生產者-消費者模式：

public class Test {
??? private int queueSize = 10;
??? private PriorityQueue<Integer> queue = new PriorityQueue<Integer>(queueSize);
?
??? public static void main(String[] args)? {
??????? Test test = new Test();
??????? Producer producer = test.new Producer();
??????? Consumer consumer = test.new Consumer();
?
??????? producer.start();
??????? consumer.start();
??? }
?
??? class Consumer extends Thread{
?
??????? @Override
??????? public void run() {
??????????? consume();
??????? }
?
??????? private void consume() {
??????????? while(true){
??????????????? synchronized (queue) {
??????????????????? while(queue.size() == 0){
??????????????????????? try {
??????????????????????????? System.out.println("隊列空，等待數據");
??????????????????????????? queue.wait();
??????????????????????? } catch (InterruptedException e) {
??????????????????????????? e.printStackTrace();
??????????????????????????? queue.notify();
??????????????????????? }
??????????????????? }
??????????????????? queue.poll();????????? //每次移走隊首元素
??????????????????? queue.notify();
??????????????????? System.out.println("從隊列取走一個元素，隊列剩余"+queue.size()+"個元素");
??????????????? }
??????????? }
??????? }
??? }
?
??? class Producer extends Thread{
?
??????? @Override
??????? public void run() {
??????????? produce();
??????? }
?
??????? private void produce() {
??????????? while(true){
??????????????? synchronized (queue) {
??????????????????? while(queue.size() == queueSize){
??????????????????????? try {
??????????????????????????? System.out.println("隊列滿，等待有空余空間");
??????????????????????????? queue.wait();
??????????????????????? } catch (InterruptedException e) {
??????????????????????????? e.printStackTrace();
??????????????????????????? queue.notify();
??????????????????????? }
??????????????????? }
??????????????????? queue.offer(1);??????? //每次插入一個元素
??????????????????? queue.notify();
??????????????????? System.out.println("向隊列取中插入一個元素，隊列剩余空間："+(queueSize-queue.size()));
??????????????? }
??????????? }
??????? }
??? }
}

這個是經典的生產者-消費者模式，通過阻塞隊列和Object.wait()和Object.notify()實現，wait()和notify()主要用來實現線程間通信。

具體的線程間通信方式（wait和notify的使用）在后續問章中會講述到。

下面是使用阻塞隊列實現的生產者-消費者模式：

public class Test {
private int queueSize = 10;
private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);
public static void main(String[] args) {
Test test = new Test();
Producer producer = test.new Producer();
Consumer consumer = test.new Consumer();
producer.start();
consumer.start();
}
class Consumer extends Thread{
@Override
public void run() {
consume();
}
private void consume() {
while(true){
try {
queue.take();
System.out.println("從隊列取走一個元素，隊列剩余"+queue.size()+"個元素");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
class Producer extends Thread{
@Override
public void run() {
produce();
}
private void produce() {
while(true){
try {
queue.put(1);
System.out.println("向隊列取中插入一個元素，隊列剩余空間："+(queueSize-queue.size()));
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}