Java并發程式設計：阻塞隊列

我們讨論了同步容器(hashtable、vector），也讨論了并發容器（concurrenthashmap、copyonwritearraylist），這些工具都為我們編寫多線程程式提供了很大的友善。今天我們來讨論另外一類容器：阻塞隊列。

　　在前面我們接觸的隊列都是非阻塞隊列，比如priorityqueue、linkedlist（linkedlist是雙向連結清單，它實作了dequeue接口）。

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

　　一.幾種主要的阻塞隊列

　　自從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；否則傳回取得的元素；

　　三.阻塞隊列的實作原理

　　前面談到了非阻塞隊列和阻塞隊列中常用的方法，下面來探讨阻塞隊列的實作原理，本文以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 {

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 {

while (count == 0)

notempty.await();

notempty.signal(); // propagate to non-interrupted thread

e x = extract();

return x;

　　跟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){

system.out.println("隊列空，等待資料");

queue.wait();

} catch (interruptedexception e) {

e.printstacktrace();

queue.notify();

queue.poll();          //每次移走隊首元素

system.out.println("從隊列取走一個元素，隊列剩餘"+queue.size()+"個元素");

class producer extends thread{

produce();

private void produce() {

while(queue.size() == queuesize){

system.out.println("隊列滿，等待有空餘空間");

queue.offer(1);        //每次插入一個元素

system.out.println("向隊列取中插入一個元素，隊列剩餘空間："+(queuesize-queue.size()));

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

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

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

private arrayblockingqueue<integer> queue = new arrayblockingqueue<integer>(queuesize);

queue.take();

queue.put(1);

　　有沒有發現，使用阻塞隊列代碼要簡單得多，不需要再單獨考慮同步和線程間通信的問題。

　　在并發程式設計中，一般推薦使用阻塞隊列，這樣實作可以盡量地避免程式出現意外的錯誤。

　　阻塞隊列使用最經典的場景就是socket用戶端資料的讀取和解析，讀取資料的線程不斷将資料放入隊列，然後解析線程不斷從隊列取資料解析。還有其他類似的場景，隻要符合生産者-消費者模型的都可以使用阻塞隊列。

最新内容請見作者的github頁：http://qaseven.github.io/