DIV CSS 佈局教程網

深入解析 Java 多線程中的阻塞隊列 BlockingQueue
編輯:JavaScript基礎知識     

在多執行緒程式設計裡,生產者與消費者之間需要一個「緩衝地帶」,而阻塞隊列正是為此而生的一種容器。它和普通隊列最大的差別在於多了兩項附加能力:當隊列為空時,取元素的執行緒會自動進入等待,直到隊列裡出現資料;當隊列已滿時,放元素的執行緒同樣會停下腳步,等待空間釋放。本文將從概念出發,梳理 JDK 提供的各類阻塞隊列、延遲隊列的實現思路,並以 ArrayBlockingQueue 為例剖析其底層原理。

一、阻塞隊列到底是什麼

生產者負責往隊列裡投遞任務,消費者負責從隊列裡取走任務,而阻塞隊列就是兩者共享的那個容器。正因為有了「自動阻塞、自動喚醒」的機制,開發者不必再手寫 wait/notify 的協調邏輯,只要專注於業務本身。

阻塞隊列通常提供四類操作語義:

  • 拋出異常:隊列已滿時繼續插入,會拋出 IllegalStateException;隊列為空時取出元素,則拋出 NoSuchElementException。
  • 返回特殊值:插入方法回傳成敗布林值,取移除方法在無資料時回傳 null。
  • 永遠阻塞:隊列滿時,put 會掛起生產者執行緒;隊列空時,take 會掛起消費者執行緒,直到條件滿足或被中斷。
  • 超時退出:阻塞一段指定時間後仍未成功,執行緒自動放棄並返回。

二、JDK 內建的七種阻塞隊列

  1. ArrayBlockingQueue:基於陣列的有界阻塞隊列。
  2. LinkedBlockingQueue:基於鏈表的有界阻塞隊列。
  3. PriorityBlockingQueue:支援優先級排序的無界阻塞隊列。
  4. DelayQueue:以優先級隊列實現的無界延遲隊列。
  5. SynchronousQueue:不儲存任何元素的阻塞隊列。
  6. LinkedTransferQueue:基於鏈表的無界傳輸隊列。
  7. LinkedBlockingDeque:基於鏈表的雙端阻塞隊列。

ArrayBlockingQueue:陣列實現的有界隊列

元素按先進先出(FIFO)排列。預設情況下不保證公平,也就是說被阻塞的執行緒不一定按阻塞先後獲得資源。公平模式指的是:先被阻塞的生產者可以先插入元素,先被阻塞的消費者可以先取走元素。代價是吞吐量的下降。開啟公平模式只需在建構時多傳一個參數:

ArrayBlockingQueue fairQueue = new ArrayBlockingQueue(1000, true);

公平性由可重入鎖實現,源碼中的建構子一目了然:

public ArrayBlockingQueue(int capacity, boolean fair) {
    if (capacity <= 0) throw new IllegalArgumentException();
    this.items = new Object[capacity];
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull = lock.newCondition();
}

LinkedBlockingQueue:鏈表實現的有界隊列

預設與最大容量均為 Integer.MAX_VALUE,同樣遵循 FIFO 原則。由於採用鏈表,插入與移除不需要搬移元素,在高併發寫入場景下往往比陣列版本更從容。

PriorityBlockingQueue:帶優先級的無界隊列

預設按元素的自然順序排列,也可以透過 comparator 自訂規則,元素最終按升序出隊。需要注意的是它並非嚴格意義上的 FIFO。

DelayQueue:延時才能取出的隊列

內部以 PriorityQueue 實現,元素必須實作 Delayed 介面,並在建立時指定延遲時間,只有延時期滿才能被取出。常見用途包括:

  • 快取系統:用 DelayQueue 保存快取項與其過期時間,另起一個執行緒輪詢,一旦能取出即代表該快取已失效。
  • 定時任務調度:把當天待執行的任務與觸發時間放進隊列,取到即執行,JDK 中的相關元件便是類似思路。

由於依賴優先級排序,Delayed 的實作類別必須覆寫 compareTo,例如讓延遲時間最久的元素排在隊尾:

public int compareTo(Delayed other) {
    if (other == this) return 0;
    if (other instanceof ScheduledFutureTask) {
        ScheduledFutureTask x = (ScheduledFutureTask) other;
        long diff = time - x.time;
        if (diff < 0) return -1;
        else if (diff > 0) return 1;
        else if (sequenceNumber < x.sequenceNumber) return -1;
        else return 1;
    }
    long d = (getDelay(TimeUnit.NANOSECONDS) - other.getDelay(TimeUnit.NANOSECONDS));
    return (d == 0) ? 0 : ((d < 0) ? -1 : 1);
}

SynchronousQueue:不儲存元素的傳球者

每一個 put 都必須等到一個 take 來接手,否則無法繼續。它更像一名傳球手,把生產者處理好的資料直接交到消費者手上,自身不保留任何內容,特別適合「一對一交接」的場景。實測中它的吞吐量往往高於 LinkedBlockingQueue 與 ArrayBlockingQueue。

LinkedTransferQueue:多了 transfer 能力的隊列

相比其他實現,它額外提供了 transfer 與 tryTransfer。

transfer 方法:若已有消費者在等待接收,元素會立刻被交出去;若沒有,元素會掛在鏈表的 tail 節點上,直到真正被消費才回傳。

Node pred = tryAppend(s, haveData);
return awaitMatch(s, pred, e, (how == TIMED), nanos);

首行嘗試把承載資料的節點掛成 tail,次行則讓執行緒等待配對成功。等待過程會先自旋,自旋消耗 CPU,因此在自旋若干次後改用 Thread.yield() 讓出時間片。

tryTransfer 方法:用來試探元素能否直接交付。若無消費者等待則立刻回傳 false,無論對方是否接收都不阻塞。帶超時參數的重載版本則會最多等待指定時間,成功交付回傳 true,逾時回傳 false。

LinkedBlockingDeque:雙端阻塞隊列

允許從隊列兩端插入與移除元素。多出一個入口,意味著多執行緒同時入隊時的競爭大約減半。它額外提供了 addFirst、addLast、offerFirst、offerLast、peekFirst、peekLast 等方法:以 First 結尾的這類操作針對隊首,以 Last 結尾則針對隊尾。另外 add 等同於 addLast,remove 等同於 removeFirst,而 take 等同於 takeFirst。初始化時可以指定容量以防無限膨脹,它也常用於「工作竊取」演算法。

三、如何實作 Delayed 介面

可以參考 ScheduledThreadPoolExecutor 中的 ScheduledFutureTask。首先在建立物件時用 time 欄位記錄可用時間:

ScheduledFutureTask(Runnable r, V result, long ns, long period) {
    super(r, result);
    this.time = ns;
    this.period = period;
    this.sequenceNumber = sequencer.getAndIncrement();
}

接著透過 getDelay 查詢還需等待多久:

public long getDelay(TimeUnit unit) {
    return unit.convert(time - now(), TimeUnit.NANOSECONDS);
}

從建構子可以看出延時參數以奈秒為單位。自行設計時建議統一採用奈秒,因為 getDelay 可以指定任意單位,若基準單位精度不足,換算時容易出現誤差。此外,當 time 早於當前時間,getDelay 會回傳負值。

四、延遲隊列的實現思路

核心邏輯很樸素:消費者取元素時,若元素尚未到齊延時,就把當前執行緒掛起。

long delay = first.getDelay(TimeUnit.NANOSECONDS);
if (delay <= 0) return q.poll();
else if (leader != null) available.await();

五、阻塞隊列的底層實現原理

以下以 ArrayBlockingQueue 為例,其他實現思路大致相近,細節可對照源碼自行研究。先看幾個關鍵成員:

public class ArrayBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {

    /** 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;

    /** 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;
}

元素實際存放在陣列 items 中,takeIndex 與 putIndex 分別指向隊首、隊尾的下一個可寫位置,count 記錄當前元素個數。lock 是可重入鎖,notEmpty 與 notFull 則是兩個等待條件,構成典型的「雙條件演算法」。

建構子有三個重載版本:

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

分別對應:僅指定容量;指定容量與公平性;指定容量、公平性並以既有集合初始化。

put 方法

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();
            throw ie;
        }
        insert(e);
    } finally {
        lock.unlock();
    }
}

方法先取得可中斷鎖,判斷元素個數是否已等於陣列長度,若是則在 notFull 條件上等待;一旦捕獲中斷異常,先 signal 喚醒後續等待者再把異常拋出,避免信號丟失。被喚醒後呼叫 insert 完成入隊,最後在 finally 中解鎖。

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

插入成功後立刻透過 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();
            throw ie;
        }
        E x = extract();
        return x;
    } finally {
        lock.unlock();
    }
}

結構與 put 幾乎對稱,只是等待的信號換成 notEmpty。取到元素後呼叫 extract:

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

取出元素後將原位置清空,有助於垃圾回收,並透過 notFull 喚醒等待寫入的執行緒。

由此可見,阻塞隊列的實現思路與我們用 wait()、notify() 搭配非同步集合手寫生產者-消費者並無本質差別,只是 JDK 把這套協調邏輯封裝進了容器內部,讓使用方式變得清爽許多。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved