隊(duì)列：隊(duì)列在線程池等有限資源池的應(yīng)用

我們知道，CPU 資源是有限的，任務(wù)的處理速度與線程個(gè)數(shù)并不是線性正相關(guān)。相反，過多的線程反而會導(dǎo)致 CPU 頻繁切換，處理性能下降。所以，線程池的大小一般都是綜合考慮要處理任務(wù)的特點(diǎn)和硬件環(huán)境，來事先設(shè)置的。

當(dāng)我們向固定大小的線程池中請求一個(gè)線程時(shí)，如果線程池中沒有空閑資源了，這個(gè)時(shí)候線程池如何處理這個(gè)請求？是拒絕請求還是排隊(duì)請求？各種處理策略又是怎么實(shí)現(xiàn)的呢？

實(shí)際上，這些問題并不復(fù)雜，其底層的數(shù)據(jù)結(jié)構(gòu)就是我們今天要學(xué)的內(nèi)容，隊(duì)列（queue）。

如何理解“隊(duì)列”？

隊(duì)列這個(gè)概念非常好理解。你可以把它想象成排隊(duì)買票，先來的先買，后來的人只能站末尾，不允許插隊(duì)。先進(jìn)者先出，這就是典型的“隊(duì)列”。

我們知道，棧只支持兩個(gè)基本操作：入棧 push()和出棧 pop()。隊(duì)列跟棧非常相似，支持的操作也很有限，最基本的操作也是兩個(gè)：入隊(duì) enqueue()，放一個(gè)數(shù)據(jù)到隊(duì)列尾部；出隊(duì) dequeue()，從隊(duì)列頭部取一個(gè)元素。

隊(duì)列和棧

所以，隊(duì)列跟棧一樣，也是一種操作受限的線性表數(shù)據(jù)結(jié)構(gòu)。

隊(duì)列的概念很好理解，基本操作也很容易掌握。作為一種非常基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，隊(duì)列的應(yīng)用也非常廣泛，特別是一些具有某些額外特性的隊(duì)列，比如循環(huán)隊(duì)列、阻塞隊(duì)列、并發(fā)隊(duì)列。它們在很多偏底層系統(tǒng)、框架、中間件的開發(fā)中，起著關(guān)鍵性的作用。比如高性能隊(duì)列 Disruptor、Linux 環(huán)形緩存，都用到了循環(huán)并發(fā)隊(duì)列；Java concurrent 并發(fā)包利用 ArrayBlockingQueue 來實(shí)現(xiàn)公平鎖等。

順序隊(duì)列和鏈?zhǔn)疥?duì)列

我們知道了，隊(duì)列跟棧一樣，也是一種抽象的數(shù)據(jù)結(jié)構(gòu)。它具有先進(jìn)先出的特性，支持在隊(duì)尾插入元素，在隊(duì)頭刪除元素，那究竟該如何實(shí)現(xiàn)一個(gè)隊(duì)列呢？

跟棧一樣，隊(duì)列可以用數(shù)組來實(shí)現(xiàn)，也可以用鏈表來實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)的棧叫作順序棧，用鏈表實(shí)現(xiàn)的棧叫作鏈?zhǔn)綏?。同樣，用?shù)組實(shí)現(xiàn)的隊(duì)列叫作順序隊(duì)列，用鏈表實(shí)現(xiàn)的隊(duì)列叫作鏈?zhǔn)疥?duì)列。

我們先來看下基于數(shù)組的實(shí)現(xiàn)方法。我用 Java 語言實(shí)現(xiàn)了一下，不過并不包含 Java 語言的高級語法，而且我做了比較詳細(xì)的注釋，你應(yīng)該可以看懂。

// 用數(shù)組實(shí)現(xiàn)的隊(duì)列
public class ArrayQueue {
  // 數(shù)組：items，數(shù)組大?。簄
  private String[] items;
  private int n = 0;
  // head 表示隊(duì)頭下標(biāo)，tail 表示隊(duì)尾下標(biāo)
  private int head = 0;
  private int tail = 0;
 
  // 申請一個(gè)大小為 capacity 的數(shù)組
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }
 
  // 入隊(duì)
  public boolean enqueue(String item) {
    // 如果 tail == n 表示隊(duì)列已經(jīng)滿了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }
 
  // 出隊(duì)
  public String dequeue() {
    // 如果 head == tail 表示隊(duì)列為空
    if (head == tail) return null;
    // 為了讓其他語言的同學(xué)看的更加明確，把 -- 操作放到單獨(dú)一行來寫了
    String ret = items[head];
    ++head;
    return ret;
  }
}

比起棧的數(shù)組實(shí)現(xiàn)，隊(duì)列的數(shù)組實(shí)現(xiàn)稍微有點(diǎn)兒復(fù)雜，但是沒關(guān)系。我稍微解釋一下實(shí)現(xiàn)思路，你很容易就能明白了。

對于棧來說，我們只需要一個(gè)棧頂指針就可以了。但是隊(duì)列需要兩個(gè)指針：一個(gè)是 head 指針，指向隊(duì)頭；一個(gè)是 tail 指針，指向隊(duì)尾。

你可以結(jié)合下面這幅圖來理解。當(dāng) a、b、c、d 依次入隊(duì)之后，隊(duì)列中的 head 指針指向下標(biāo)為 0 的位置，tail 指針指向下標(biāo)為 4 的位置。

當(dāng)我們調(diào)用兩次出隊(duì)操作之后，隊(duì)列中 head 指針指向下標(biāo)為 2 的位置，tail 指針仍然指向下標(biāo)為 4 的位置。

你肯定已經(jīng)發(fā)現(xiàn)了，隨著不停地進(jìn)行入隊(duì)、出隊(duì)操作，head 和 tail 都會持續(xù)往后移動(dòng)。當(dāng) tail 移動(dòng)到最右邊，即使數(shù)組中還有空閑空間，也無法繼續(xù)往隊(duì)列中添加數(shù)據(jù)了。這個(gè)問題該如何解決呢？

你是否還記得，在數(shù)組那一節(jié)，我們也遇到過類似的問題，就是數(shù)組的刪除操作會導(dǎo)致數(shù)組中的數(shù)據(jù)不連續(xù)。你還記得我們當(dāng)時(shí)是怎么解決的嗎？對，用數(shù)據(jù)搬移！但是，每次進(jìn)行出隊(duì)操作都相當(dāng)于刪除數(shù)組下標(biāo)為 0 的數(shù)據(jù)，要搬移整個(gè)隊(duì)列中的數(shù)據(jù)，這樣出隊(duì)操作的時(shí)間復(fù)雜度就會從原來的 O(1) 變?yōu)?O(n)。能不能優(yōu)化一下呢？

實(shí)際上，我們在出隊(duì)時(shí)可以不用搬移數(shù)據(jù)。如果沒有空閑空間了，我們只需要在入隊(duì)時(shí)，再集中觸發(fā)一次數(shù)據(jù)的搬移操作。借助這個(gè)思想，出隊(duì)函數(shù) dequeue() 保持不變，我們稍加改造一下入隊(duì)函數(shù) enqueue() 的實(shí)現(xiàn)，就可以輕松解決剛才的問題了。下面是具體的代碼：

// 入隊(duì)操作，將 item 放入隊(duì)尾
  public boolean enqueue(String item) {
    // tail == n 表示隊(duì)列末尾沒有空間了
    if (tail == n) {
      // tail ==n && head==0，表示整個(gè)隊(duì)列都占滿了
      if (head == 0) return false;
      // 數(shù)據(jù)搬移
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // 搬移完之后重新更新 head 和 tail
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  }

從代碼中我們看到，當(dāng)隊(duì)列的 tail 指針移動(dòng)到數(shù)組的最右邊后，如果有新的數(shù)據(jù)入隊(duì)，我們可以將 head 到 tail 之間的數(shù)據(jù)，整體搬移到數(shù)組中 0 到 tail-head 的位置。

這種實(shí)現(xiàn)思路中，出隊(duì)操作的時(shí)間復(fù)雜度仍然是 O(1)，但入隊(duì)操作的時(shí)間復(fù)雜度還是 O(1) 嗎？你可以用我們第 3 節(jié)、第 4 節(jié)講的算法復(fù)雜度分析方法，自己試著分析一下。

接下來，我們再來看下基于鏈表的隊(duì)列實(shí)現(xiàn)方法。

基于鏈表的實(shí)現(xiàn)，我們同樣需要兩個(gè)指針：head 指針和 tail 指針。它們分別指向鏈表的第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)。如圖所示，入隊(duì)時(shí)，tail->next= new_node, tail = tail->next；出隊(duì)時(shí)，head = head->next。我將具體的代碼放到 Github 上，你可以自己試著實(shí)現(xiàn)一下，然后再去 Github 上跟我實(shí)現(xiàn)的代碼對比下，看寫得對不對。

循環(huán)隊(duì)列
我們剛才用數(shù)組來實(shí)現(xiàn)隊(duì)列的時(shí)候，在 tail==n 時(shí)，會有數(shù)據(jù)搬移操作，這樣入隊(duì)操作性能就會受到影響。那有沒有辦法能夠避免數(shù)據(jù)搬移呢？我們來看看循環(huán)隊(duì)列的解決思路。

循環(huán)隊(duì)列，顧名思義，它長得像一個(gè)環(huán)。原本數(shù)組是有頭有尾的，是一條直線?，F(xiàn)在我們把首尾相連，扳成了一個(gè)環(huán)。我畫了一張圖，你可以直觀地感受一下。

我們可以看到，圖中這個(gè)隊(duì)列的大小為 8，當(dāng)前 head=4，tail=7。當(dāng)有一個(gè)新的元素 a 入隊(duì)時(shí)，我們放入下標(biāo)為 7 的位置。但這個(gè)時(shí)候，我們并不把 tail 更新為 8，而是將其在環(huán)中后移一位，到下標(biāo)為 0 的位置。當(dāng)再有一個(gè)元素 b 入隊(duì)時(shí)，我們將 b 放入下標(biāo)為 0 的位置，然后 tail 加 1 更新為 1。所以，在 a，b 依次入隊(duì)之后，循環(huán)隊(duì)列中的元素就變成了下面的樣子：

在用數(shù)組實(shí)現(xiàn)的非循環(huán)隊(duì)列中，隊(duì)滿的判斷條件是 tail == n，隊(duì)空的判斷條件是 head == tail。那針對循環(huán)隊(duì)列，如何判斷隊(duì)空和隊(duì)滿呢？

隊(duì)列為空的判斷條件仍然是 head == tail。但隊(duì)列滿的判斷條件就稍微有點(diǎn)復(fù)雜了。我畫了一張隊(duì)列滿的圖，你可以看一下，試著總結(jié)一下規(guī)律。

就像我圖中畫的隊(duì)滿的情況，tail=3，head=4，n=8，所以總結(jié)一下規(guī)律就是：(3+1)%8=4。多畫幾張隊(duì)滿的圖，你就會發(fā)現(xiàn)，當(dāng)隊(duì)滿時(shí)，(tail+1)%n=head。

你有沒有發(fā)現(xiàn)，當(dāng)隊(duì)列滿時(shí)，圖中的 tail 指向的位置實(shí)際上是沒有存儲數(shù)據(jù)的。所以，循環(huán)隊(duì)列會浪費(fèi)一個(gè)數(shù)組的存儲空間。

Talk is cheap，如果還是沒怎么理解，那就 show you code 吧。

public class CircularQueue {
  // 數(shù)組：items，數(shù)組大?。簄
  private String[] items;
  private int n = 0;
  // head 表示隊(duì)頭下標(biāo)，tail 表示隊(duì)尾下標(biāo)
  private int head = 0;
  private int tail = 0;
 
  // 申請一個(gè)大小為 capacity 的數(shù)組
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }
 
  // 入隊(duì)
  public boolean enqueue(String item) {
    // 隊(duì)列滿了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }
 
  // 出隊(duì)
  public String dequeue() {
    // 如果 head == tail 表示隊(duì)列為空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}

阻塞隊(duì)列和并發(fā)隊(duì)列

前面講的內(nèi)容理論比較多，看起來很難跟實(shí)際的項(xiàng)目開發(fā)扯上關(guān)系。確實(shí)，隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)很基礎(chǔ)，平時(shí)的業(yè)務(wù)開發(fā)不大可能從零實(shí)現(xiàn)一個(gè)隊(duì)列，甚至都不會直接用到。而一些具有特殊特性的隊(duì)列應(yīng)用卻比較廣泛，比如阻塞隊(duì)列和并發(fā)隊(duì)列。

阻塞隊(duì)列其實(shí)就是在隊(duì)列基礎(chǔ)上增加了阻塞操作。簡單來說，就是在隊(duì)列為空的時(shí)候，從隊(duì)頭取數(shù)據(jù)會被阻塞。因?yàn)榇藭r(shí)還沒有數(shù)據(jù)可取，直到隊(duì)列中有了數(shù)據(jù)才能返回；如果隊(duì)列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會被阻塞，直到隊(duì)列中有空閑位置后再插入數(shù)據(jù)，然后再返回。

你應(yīng)該已經(jīng)發(fā)現(xiàn)了，上述的定義就是一個(gè)“生產(chǎn)者 - 消費(fèi)者模型”！是的，我們可以使用阻塞隊(duì)列，輕松實(shí)現(xiàn)一個(gè)“生產(chǎn)者 - 消費(fèi)者模型”！

這種基于阻塞隊(duì)列實(shí)現(xiàn)的“生產(chǎn)者 - 消費(fèi)者模型”，可以有效地協(xié)調(diào)生產(chǎn)和消費(fèi)的速度。當(dāng)“生產(chǎn)者”生產(chǎn)數(shù)據(jù)的速度過快，“消費(fèi)者”來不及消費(fèi)時(shí)，存儲數(shù)據(jù)的隊(duì)列很快就會滿了。這個(gè)時(shí)候，生產(chǎn)者就阻塞等待，直到“消費(fèi)者”消費(fèi)了數(shù)據(jù)，“生產(chǎn)者”才會被喚醒繼續(xù)“生產(chǎn)”。

而且不僅如此，基于阻塞隊(duì)列，我們還可以通過協(xié)調(diào)“生產(chǎn)者”和“消費(fèi)者”的個(gè)數(shù)，來提高數(shù)據(jù)的處理效率。比如前面的例子，我們可以多配置幾個(gè)“消費(fèi)者”，來應(yīng)對一個(gè)“生產(chǎn)者”。

前面我們講了阻塞隊(duì)列，在多線程情況下，會有多個(gè)線程同時(shí)操作隊(duì)列，這個(gè)時(shí)候就會存在線程安全問題，那如何實(shí)現(xiàn)一個(gè)線程安全的隊(duì)列呢？

線程安全的隊(duì)列我們叫作并發(fā)隊(duì)列。最簡單直接的實(shí)現(xiàn)方式是直接在 enqueue()、dequeue() 方法上加鎖，但是鎖粒度大并發(fā)度會比較低，同一時(shí)刻僅允許一個(gè)存或者取操作。實(shí)際上，基于數(shù)組的循環(huán)隊(duì)列，利用 CAS 原子操作，可以實(shí)現(xiàn)非常高效的并發(fā)隊(duì)列。這也是循環(huán)隊(duì)列比鏈?zhǔn)疥?duì)列應(yīng)用更加廣泛的原因。在實(shí)戰(zhàn)篇講 Disruptor 的時(shí)候，我會再詳細(xì)講并發(fā)隊(duì)列的應(yīng)用。

解答開篇

隊(duì)列的知識就講完了，我們現(xiàn)在回過來看下開篇的問題。線程池沒有空閑線程時(shí)，新的任務(wù)請求線程資源時(shí)，線程池該如何處理？各種處理策略又是如何實(shí)現(xiàn)的呢？

我們一般有兩種處理策略。第一種是非阻塞的處理方式，直接拒絕任務(wù)請求；另一種是阻塞的處理方式，將請求排隊(duì)，等到有空閑線程時(shí)，取出排隊(duì)的請求繼續(xù)處理。那如何存儲排隊(duì)的請求呢？

我們希望公平地處理每個(gè)排隊(duì)的請求，先進(jìn)者先服務(wù)，所以隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)很適合來存儲排隊(duì)請求。我們前面說過，隊(duì)列有基于鏈表和基于數(shù)組這兩種實(shí)現(xiàn)方式。這兩種實(shí)現(xiàn)方式對于排隊(duì)請求又有什么區(qū)別呢？

基于鏈表的實(shí)現(xiàn)方式，可以實(shí)現(xiàn)一個(gè)支持無限排隊(duì)的無界隊(duì)列（unbounded queue），但是可能會導(dǎo)致過多的請求排隊(duì)等待，請求處理的響應(yīng)時(shí)間過長。所以，針對響應(yīng)時(shí)間比較敏感的系統(tǒng)，基于鏈表實(shí)現(xiàn)的無限排隊(duì)的線程池是不合適的。

而基于數(shù)組實(shí)現(xiàn)的有界隊(duì)列（bounded queue），隊(duì)列的大小有限，所以線程池中排隊(duì)的請求超過隊(duì)列大小時(shí)，接下來的請求就會被拒絕，這種方式對響應(yīng)時(shí)間敏感的系統(tǒng)來說，就相對更加合理。不過，設(shè)置一個(gè)合理的隊(duì)列大小，也是非常有講究的。隊(duì)列太大導(dǎo)致等待的請求太多，隊(duì)列太小會導(dǎo)致無法充分利用系統(tǒng)資源、發(fā)揮最大性能。

除了前面講到隊(duì)列應(yīng)用在線程池請求排隊(duì)的場景之外，隊(duì)列可以應(yīng)用在任何有限資源池中，用于排隊(duì)請求，比如數(shù)據(jù)庫連接池等。實(shí)際上，對于大部分資源有限的場景，當(dāng)沒有空閑資源時(shí)，基本上都可以通過“隊(duì)列”這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)請求排隊(duì)。

內(nèi)容小結(jié)

今天我們講了一種跟棧很相似的數(shù)據(jù)結(jié)構(gòu)，隊(duì)列。關(guān)于隊(duì)列，你能掌握下面的內(nèi)容，這節(jié)就沒問題了。

隊(duì)列最大的特點(diǎn)就是先進(jìn)先出，主要的兩個(gè)操作是入隊(duì)和出隊(duì)。跟棧一樣，它既可以用數(shù)組來實(shí)現(xiàn)，也可以用鏈表來實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)的叫順序隊(duì)列，用鏈表實(shí)現(xiàn)的叫鏈?zhǔn)疥?duì)列。特別是長得像一個(gè)環(huán)的循環(huán)隊(duì)列。在數(shù)組實(shí)現(xiàn)隊(duì)列的時(shí)候，會有數(shù)據(jù)搬移操作，要想解決數(shù)據(jù)搬移的問題，我們就需要像環(huán)一樣的循環(huán)隊(duì)列。

循環(huán)隊(duì)列是我們這節(jié)的重點(diǎn)。要想寫出沒有 bug 的循環(huán)隊(duì)列實(shí)現(xiàn)代碼，關(guān)鍵要確定好隊(duì)空和隊(duì)滿的判定條件，具體的代碼你要能寫出來。

除此之外，我們還講了幾種高級的隊(duì)列結(jié)構(gòu)，阻塞隊(duì)列、并發(fā)隊(duì)列，底層都還是隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，只不過在之上附加了很多其他功能。阻塞隊(duì)列就是入隊(duì)、出隊(duì)操作可以阻塞，并發(fā)隊(duì)列就是隊(duì)列的操作多線程安全。

課后思考

除了線程池這種池結(jié)構(gòu)會用到隊(duì)列排隊(duì)請求，你還知道有哪些類似的池結(jié)構(gòu)或者場景中會用到隊(duì)列的排隊(duì)請求呢？

今天講到并發(fā)隊(duì)列，關(guān)于如何實(shí)現(xiàn)無鎖并發(fā)隊(duì)列，網(wǎng)上有非常多的討論。對這個(gè)問題，你怎么看呢？

相關(guān)代碼鏈接

https://github.com/LHYintheCode/algo

經(jīng)典評論

1.分布式應(yīng)用中的消息隊(duì)列，也是一種隊(duì)列結(jié)構(gòu)
2.考慮使用CAS實(shí)現(xiàn)無鎖隊(duì)列，則在入隊(duì)前，獲取tail位置，入隊(duì)時(shí)比較tail是否發(fā)生變化，如果否，則允許入隊(duì)，反之，本次入隊(duì)失敗。出隊(duì)則是獲取head位置，進(jìn)行cas。

循環(huán)隊(duì)列的長度設(shè)定需要對并發(fā)數(shù)據(jù)有一定的預(yù)測，否則會丟失太多請求。

隊(duì)列也是一種“操作受限”的線性表，只支持兩種基本操作：入隊(duì)和出隊(duì)。

隊(duì)列的應(yīng)用非常廣泛，特別是一些具有某些額外特性的隊(duì)列，比如循環(huán)隊(duì)列、阻塞隊(duì)列、并發(fā)隊(duì)列。它們在很多偏底層的系統(tǒng)、框架、中間件的開發(fā)中，起著關(guān)鍵性的作用。比如高性能隊(duì)列 Disruptor、Linux 環(huán)形緩存，都用到了循環(huán)并發(fā)隊(duì)列；Java concurrent 并發(fā)包利用 ArrayBlockingQueue 來實(shí)現(xiàn)公平鎖等。
關(guān)于如何實(shí)現(xiàn)無鎖并發(fā)隊(duì)列
可以使用 cas + 數(shù)組的方式實(shí)現(xiàn)。
隊(duì)列的其他應(yīng)用
分布式消息隊(duì)列，如 kafka 也是一種隊(duì)列。

對于第一個(gè)思考題:
1.像windows操作系統(tǒng)的消息隊(duì)列，略高級一些帶有優(yōu)先級。還有qt中的信號與槽函數(shù)機(jī)制，使用connect鏈接，其中的參數(shù)就是設(shè)置為把窗口界面消息放到消息隊(duì)列，然后一次取出。比如優(yōu)先級消息，窗口系統(tǒng)關(guān)閉，優(yōu)先級高，則就直接執(zhí)行關(guān)閉操作。
2.sockets網(wǎng)絡(luò)連接隊(duì)列。
3.數(shù)據(jù)庫連接隊(duì)列。
4.還有一種集群操作，很多客戶端像服務(wù)端請求資源，處理高并發(fā)大量請求。把這些請求放到隊(duì)列中。