多線程（十九、阻塞隊列-LinkedBlockingQueue）

LinkedBlockingQueue簡介

1、LinkedBlockingQueue底層數據結構基于單鏈表實現，與ArrayBlockingQueue不同。
2、既可以在初始構造時就指定隊列的容量，也可以不指定，如果不指定，那么它的容量大小默認為Integer.MAX_VALUE。
3、區別于ArrayBlockingQueue的全局鎖，LinkedBlockingQueue維護了兩把鎖——takeLock和putLock。
takeLock用于控制出隊的并發，putLock用于入隊的并發。同一時刻，只能有一個線程能執行入隊或者出隊操作，但是，入隊和出隊之間可以并發執行，即同一時刻，可以同時有一個線程進行入隊，另一個線程進行出隊，這樣就可以提升吞吐量。

LinkedBlockingQueue構造

LinkedBlockingQueue使用了一個原子變量AtomicInteger記錄隊列中元素的個數，以保證入隊/出隊并發修改元素時的數據一致性

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

    /**
     * 隊列容量.
     * 如果不指定, 則為Integer.MAX_VALUE
     */
    private final int capacity;

    /**
     * 隊列中的元素個數，原子類時間并發
     */
    private final AtomicInteger count = new AtomicInteger();

    /**
     * 隊首指針.
     * head.item == null
     */
    transient Node<E> head;

    /**
     * 隊尾指針.
     * last.next == null
     */
    private transient Node<E> last;

    /**
     * 出隊鎖
     */
    private final ReentrantLock takeLock = new ReentrantLock();

    /**
     * 隊列空時，出隊線程在該條件隊列等待
     */
    private final Condition notEmpty = takeLock.newCondition();

    /**
     * 入隊鎖
     */
    private final ReentrantLock putLock = new ReentrantLock();

    /**
     * 隊列滿時，入隊線程在該條件隊列等待
     */
    private final Condition notFull = putLock.newCondition();

    /**
     * 鏈表結點定義
     */
    static class Node<E> {
        E item;

        Node<E> next;   // 后驅指針

        Node(E x) {
            item = x;
        }
    }

}

主要方法：

1、插入元素-put

/**
 * 在隊尾插入指定的元素.
 * 如果隊列已滿，則阻塞線程.
 */
public void put(E e) throws InterruptedException {
    if (e == null) throw new NullPointerException();
    int c = -1;
    Node<E> node = new Node<E>(e);
    final ReentrantLock putLock = this.putLock;
    final AtomicInteger count = this.count;
    putLock.lockInterruptibly();            // 獲取“入隊鎖”
    try {
        while (count.get() == capacity) {   // 隊列已滿, 則線程在notFull上等待
            notFull.await();
        }
        enqueue(node);                      // 將新結點鏈接到“隊尾”

        /**
         * c+1 表示的元素個數.
         * 如果，則喚醒一個“入隊線程”
         */
        c = count.getAndIncrement();        // c表示入隊前的隊列元素個數
        if (c + 1 < capacity)               // 入隊后隊列未滿, 則喚醒一個“入隊線程”
            notFull.signal();
    } finally {
        putLock.unlock();
    }

    if (c == 0)                             // 隊列初始為空, 則喚醒一個“出隊線程”
        signalNotEmpty();
}

注意點：
1、每入隊一個元素后，如果隊列還沒滿，則需要喚醒其它可能正在等待的“入隊線程”
2、每入隊一個元素，都要判斷下隊列是否空了，如果空了，說明可能存在正在等待的“出隊線程”，后面來的出隊線程也會進行無用的等待，所以需要喚醒它，提升性能。
3、入隊元素后，避免直接嘗試喚醒出隊線程，否則會要求去拿出隊鎖，這樣持有鎖A的同時，再去嘗試獲取鎖B，很可能引起死鎖

2、刪除元素-take

/**
 * 從隊首出隊一個元素
 */
public E take() throws InterruptedException {
    E x;
    int c = -1;
    final AtomicInteger count = this.count;
    final ReentrantLock takeLock = this.takeLock;   // 獲取“出隊鎖”
    takeLock.lockInterruptibly();
    try {
        while (count.get() == 0) {                  // 隊列為空, 則阻塞線程
            notEmpty.await();
        }
        x = dequeue();
        c = count.getAndDecrement();                // c表示出隊前的元素個數
        if (c > 1)                                  // 出隊前隊列非空, 則喚醒一個出隊線程
            notEmpty.signal();
    } finally {
        takeLock.unlock();
    }
    if (c == capacity)                              // 隊列初始為滿，則喚醒一個入隊線程
        signalNotFull();
    return x;
}
/**
 * 隊首出隊一個元素.
 */
private E dequeue() {
    Node<E> h = head;
    Node<E> first = h.next;
    h.next = h;         // help GC
    head = first;
    E x = first.item;
    first.item = null;
    return x;
}

注意點：
1、每出隊一個元素前，如果隊列非空，則需要喚醒其它可能正在等待的“出隊線程”
2、每出隊一個元素，都要判斷下隊列是否滿，如果是滿的，說明可能存在正在等待的“入隊線程”，需要喚醒它

總結：

1、隊列大小不同。ArrayBlockingQueue初始構造時必須指定大小，而LinkedBlockingQueue構造時既可以指定大小，也可以不指定（默認為Integer.MAX_VALUE）；
2、底層數據結構不同。ArrayBlockingQueue底層采用數組作為數據存儲容器，而LinkedBlockingQueue底層采用單鏈表作為數據存儲容器；
3、兩者的加鎖機制不同。ArrayBlockingQueue使用一把全局鎖，即入隊和出隊使用同一個ReentrantLock鎖；而LinkedBlockingQueue進行了鎖分離，入隊使用一個ReentrantLock鎖（putLock），出隊使用另一個ReentrantLock鎖（takeLock）；
4、LinkedBlockingQueue不能指定公平/非公平策略（默認都是非公平），而ArrayBlockingQueue可以指定策略。