09 | 隊列：隊列在線程池等有限資源池中的應(yīng)用
我們知道，CPU資源是有限的，任務(wù)的處理速度與線程個數(shù)并不是線性正相關(guān)。相反，過多的線程反而會導(dǎo)致CPU頻繁切換，處理性能下降。所以，線程池的大小一般都是綜合考慮要處理任務(wù)的特點和硬件環(huán)境，來事先設(shè)置的。
當(dāng)我們向固定大小的線程池中請求一個線程時，如果線程池中沒有空閑資源了，這個時候線程池如何處理這個請求？是拒絕請求還是排隊請求？各種處理策略又是怎么實現(xiàn)的呢？
實際上，這些問題并不復(fù)雜，其底層的數(shù)據(jù)結(jié)構(gòu)就是我們今天要學(xué)的內(nèi)容，隊列（queue）。
如何理解“隊列”？
隊列這個概念非常好理解。你可以把它想象成排隊買票，先來的先買，后來的人只能站末尾，不允許插隊。 **先進者先出，這就是典型的“ ** 隊列****
”。
我們知道，棧只支持兩個基本操作： 入棧push() 和 出棧pop()。隊列跟棧非常相似，支持的操作也很有限，最基本的操作也是兩個：
入隊enqueue() ，放一個數(shù)據(jù)到隊列尾部； 出隊dequeue() ，從隊列頭部取一個元素。
所以，隊列跟棧一樣，也是一種 操作受限的線性表數(shù)據(jù)結(jié)構(gòu) 。
隊列的概念很好理解，基本操作也很容易掌握。作為一種非?；A(chǔ)的數(shù)據(jù)結(jié)構(gòu)，隊列的應(yīng)用也非常廣泛，特別是一些具有某些額外特性的隊列，比如循環(huán)隊列、阻塞隊列、并發(fā)隊列。它們在很多偏底層系統(tǒng)、框架、中間件的開發(fā)中，起著關(guān)鍵性的作用。比如高性能隊列Disruptor、Linux環(huán)形緩存，都用到了循環(huán)并發(fā)隊列；Java
concurrent并發(fā)包利用ArrayBlockingQueue來實現(xiàn)公平鎖等。
順序隊列和鏈?zhǔn)疥犃?/h2>
我們知道了，隊列跟棧一樣，也是一種抽象的數(shù)據(jù)結(jié)構(gòu)。它具有先進先出的特性，支持在隊尾插入元素，在隊頭刪除元素，那究竟該如何實現(xiàn)一個隊列呢？
跟棧一樣，隊列可以用數(shù)組來實現(xiàn)，也可以用鏈表來實現(xiàn)。用數(shù)組實現(xiàn)的棧叫作順序棧，用鏈表實現(xiàn)的棧叫作鏈?zhǔn)綏?。同樣，用?shù)組實現(xiàn)的隊列叫作 順序隊列
，用鏈表實現(xiàn)的隊列叫作 鏈?zhǔn)疥犃?/strong> 。
我們先來看下基于數(shù)組的實現(xiàn)方法。我用Java語言實現(xiàn)了一下，不過并不包含Java語言的高級語法，而且我做了比較詳細(xì)的注釋，你應(yīng)該可以看懂。
// 用數(shù)組實現(xiàn)的隊列
public class ArrayQueue {
// 數(shù)組：items，數(shù)組大?。簄
private String[] items;
private int n = 0;
// head表示隊頭下標(biāo)，tail表示隊尾下標(biāo)
private int head = 0;
private int tail = 0;
// 申請一個大小為capacity的數(shù)組
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入隊
public boolean enqueue(String item) {
// 如果tail == n 表示隊列已經(jīng)滿了
if (tail == n) return false;
items[tail] = item;
++tail;
return true;
}
// 出隊
public String dequeue() {
// 如果head == tail 表示隊列為空
if (head == tail) return null;
// 為了讓其他語言的同學(xué)看的更加明確，把--操作放到單獨一行來寫了
String ret = items[head];
++head;
return ret;
}
}
比起棧的數(shù)組實現(xiàn)，隊列的數(shù)組實現(xiàn)稍微有點兒復(fù)雜，但是沒關(guān)系。我稍微解釋一下實現(xiàn)思路，你很容易就能明白了。
對于棧來說，我們只需要一個 棧頂指針 就可以了。但是隊列需要兩個指針：一個是head指針，指向隊頭；一個是tail指針，指向隊尾。
你可以結(jié)合下面這幅圖來理解。當(dāng)a、b、c、d依次入隊之后，隊列中的head指針指向下標(biāo)為0的位置，tail指針指向下標(biāo)為4的位置。
當(dāng)我們調(diào)用兩次出隊操作之后，隊列中head指針指向下標(biāo)為2的位置，tail指針仍然指向下標(biāo)為4的位置。
你肯定已經(jīng)發(fā)現(xiàn)了，隨著不停地進行入隊、出隊操作，head和tail都會持續(xù)往后移動。當(dāng)tail移動到最右邊，即使數(shù)組中還有空閑空間，也無法繼續(xù)往隊列中添加數(shù)據(jù)了。這個問題該如何解決呢？
你是否還記得，在數(shù)組那一節(jié)，我們也遇到過類似的問題，就是數(shù)組的刪除操作會導(dǎo)致數(shù)組中的數(shù)據(jù)不連續(xù)。你還記得我們當(dāng)時是怎么解決的嗎？對，用 數(shù)據(jù)搬移
！但是，每次進行出隊操作都相當(dāng)于刪除數(shù)組下標(biāo)為0的數(shù)據(jù)，要搬移整個隊列中的數(shù)據(jù)，這樣出隊操作的時間復(fù)雜度就會從原來的O(1)變?yōu)镺(n)。能不能優(yōu)化一下呢？
實際上，我們在出隊時可以不用搬移數(shù)據(jù)。如果沒有空閑空間了，我們只需要在入隊時，再集中觸發(fā)一次數(shù)據(jù)的搬移操作。借助這個思想，出隊函數(shù)dequeue()保持不變，我們稍加改造一下入隊函數(shù)enqueue()的實現(xiàn)，就可以輕松解決剛才的問題了。下面是具體的代碼：
// 入隊操作，將item放入隊尾
public boolean enqueue(String item) {
// tail == n表示隊列末尾沒有空間了
if (tail == n) {
// tail ==n && head==0，表示整個隊列都占滿了
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)隊列的tail指針移動到數(shù)組的最右邊后，如果有新的數(shù)據(jù)入隊，我們可以將head到tail之間的數(shù)據(jù)，整體搬移到數(shù)組中0到tail-
head的位置。
這種實現(xiàn)思路中，出隊操作的時間復(fù)雜度仍然是O(1)，但入隊操作的時間復(fù)雜度還是O(1)嗎？你可以用我們第3節(jié)、第4節(jié)講的算法復(fù)雜度分析方法，自己試著分析一下。
接下來，我們再來看下 基于鏈表的隊列實現(xiàn)方法 。
基于鏈表的實現(xiàn)，我們同樣需要兩個指針：head指針和tail指針。它們分別指向鏈表的第一個結(jié)點和最后一個結(jié)點。如圖所示，入隊時，tail->next=
new_node, tail = tail->next；出隊時，head =
head->next。我將具體的代碼放到GitHub上，你可以自己試著實現(xiàn)一下，然后再去GitHub上跟我實現(xiàn)的代碼對比下，看寫得對不對。
循環(huán)隊列
我們剛才用數(shù)組來實現(xiàn)隊列的時候，在tail==n時，會有數(shù)據(jù)搬移操作，這樣入隊操作性能就會受到影響。那有沒有辦法能夠避免數(shù)據(jù)搬移呢？我們來看看循環(huán)隊列的解決思路。
循環(huán)隊列，顧名思義，它長得像一個環(huán)。原本數(shù)組是有頭有尾的，是一條直線?，F(xiàn)在我們把首尾相連，扳成了一個環(huán)。我畫了一張圖，你可以直觀地感受一下。
我們可以看到，圖中這個隊列的大小為8，當(dāng)前head=4，tail=7。當(dāng)有一個新的元素a入隊時，我們放入下標(biāo)為7的位置。但這個時候，我們并不把tail更新為8，而是將其在環(huán)中后移一位，到下標(biāo)為0的位置。當(dāng)再有一個元素b入隊時，我們將b放入下標(biāo)為0的位置，然后tail加1更新為1。所以，在a，b依次入隊之后，循環(huán)隊列中的元素就變成了下面的樣子：
通過這樣的方法，我們成功避免了數(shù)據(jù)搬移操作?？雌饋聿浑y理解，但是循環(huán)隊列的代碼實現(xiàn)難度要比前面講的非循環(huán)隊列難多了。要想寫出沒有bug的循環(huán)隊列的實現(xiàn)代碼，我個人覺得，最關(guān)鍵的是，
確定好隊空和隊滿的判定條件 。
在用數(shù)組實現(xiàn)的非循環(huán)隊列中，隊滿的判斷條件是tail == n，隊空的判斷條件是head == tail。那針對循環(huán)隊列，如何判斷隊空和隊滿呢？
隊列為空的判斷條件仍然是head == tail。但隊列滿的判斷條件就稍微有點復(fù)雜了。我畫了一張隊列滿的圖，你可以看一下，試著總結(jié)一下規(guī)律。
就像我圖中畫的隊滿的情況，tail=3，head=4，n=8，所以總結(jié)一下規(guī)律就是：(3+1)%8=4。多畫幾張隊滿的圖，你就會發(fā)現(xiàn)，當(dāng)隊滿時，
(tail+1)%n=head 。
你有沒有發(fā)現(xiàn)，當(dāng)隊列滿時，圖中的tail指向的位置實際上是沒有存儲數(shù)據(jù)的。所以，循環(huán)隊列會浪費一個數(shù)組的存儲空間。
Talk is cheap，如果還是沒怎么理解，那就show you code吧。
public class CircularQueue {
// 數(shù)組：items，數(shù)組大?。簄
private String[] items;
private int n = 0;
// head表示隊頭下標(biāo)，tail表示隊尾下標(biāo)
private int head = 0;
private int tail = 0;
// 申請一個大小為capacity的數(shù)組
public CircularQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入隊
public boolean enqueue(String item) {
// 隊列滿了
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
return true;
}
// 出隊
public String dequeue() {
// 如果head == tail 表示隊列為空
if (head == tail) return null;
String ret = items[head];
head = (head + 1) % n;
return ret;
}
}
阻塞隊列和并發(fā)隊列
前面講的內(nèi)容理論比較多，看起來很難跟實際的項目開發(fā)扯上關(guān)系。確實，隊列這種數(shù)據(jù)結(jié)構(gòu)很基礎(chǔ)，平時的業(yè)務(wù)開發(fā)不大可能從零實現(xiàn)一個隊列，甚至都不會直接用到。而一些具有特殊特性的隊列應(yīng)用卻比較廣泛，比如阻塞隊列和并發(fā)隊列。
阻塞隊列
其實就是在隊列基礎(chǔ)上增加了阻塞操作。簡單來說，就是在隊列為空的時候，從隊頭取數(shù)據(jù)會被阻塞。因為此時還沒有數(shù)據(jù)可取，直到隊列中有了數(shù)據(jù)才能返回；如果隊列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會被阻塞，直到隊列中有空閑位置后再插入數(shù)據(jù)，然后再返回。
你應(yīng)該已經(jīng)發(fā)現(xiàn)了，上述的定義就是一個“生產(chǎn)者-消費者模型”！是的，我們可以使用阻塞隊列，輕松實現(xiàn)一個“生產(chǎn)者-消費者模型”！
這種基于阻塞隊列實現(xiàn)的“生產(chǎn)者-
消費者模型”，可以有效地協(xié)調(diào)生產(chǎn)和消費的速度。當(dāng)“生產(chǎn)者”生產(chǎn)數(shù)據(jù)的速度過快，“消費者”來不及消費時，存儲數(shù)據(jù)的隊列很快就會滿了。這個時候，生產(chǎn)者就阻塞等待，直到“消費者”消費了數(shù)據(jù)，“生產(chǎn)者”才會被喚醒繼續(xù)“生產(chǎn)”。
而且不僅如此，基于阻塞隊列，我們還可以通過協(xié)調(diào)“生產(chǎn)者”和“消費者”的個數(shù)，來提高數(shù)據(jù)的處理效率。比如前面的例子，我們可以多配置幾個“消費者”，來應(yīng)對一個“生產(chǎn)者”。
前面我們講了阻塞隊列，在多線程情況下，會有多個線程同時操作隊列，這個時候就會存在線程安全問題，那如何實現(xiàn)一個線程安全的隊列呢？
線程安全的隊列我們叫作 并發(fā)隊列
。最簡單直接的實現(xiàn)方式是直接在enqueue()、dequeue()方法上加鎖，但是鎖粒度大并發(fā)度會比較低，同一時刻僅允許一個存或者取操作。實際上，基于數(shù)組的循環(huán)隊列，利用CAS原子操作，可以實現(xiàn)非常高效的并發(fā)隊列。這也是循環(huán)隊列比鏈?zhǔn)疥犃袘?yīng)用更加廣泛的原因。在實戰(zhàn)篇講Disruptor的時候，我會再詳細(xì)講并發(fā)隊列的應(yīng)用。
解答開篇
隊列的知識就講完了，我們現(xiàn)在回過來看下開篇的問題。線程池沒有空閑線程時，新的任務(wù)請求線程資源時，線程池該如何處理？各種處理策略又是如何實現(xiàn)的呢？
我們一般有兩種處理策略。第一種是非阻塞的處理方式，直接拒絕任務(wù)請求；另一種是阻塞的處理方式，將請求排隊，等到有空閑線程時，取出排隊的請求繼續(xù)處理。那如何存儲排隊的請求呢？
我們希望公平地處理每個排隊的請求，先進者先服務(wù)，所以隊列這種數(shù)據(jù)結(jié)構(gòu)很適合來存儲排隊請求。我們前面說過，隊列有基于鏈表和基于數(shù)組這兩種實現(xiàn)方式。這兩種實現(xiàn)方式對于排隊請求又有什么區(qū)別呢？
基于鏈表的實現(xiàn)方式，可以實現(xiàn)一個支持無限排隊的無界隊列（unbounded
queue），但是可能會導(dǎo)致過多的請求排隊等待，請求處理的響應(yīng)時間過長。所以，針對響應(yīng)時間比較敏感的系統(tǒng)，基于鏈表實現(xiàn)的無限排隊的線程池是不合適的。
而基于數(shù)組實現(xiàn)的有界隊列（bounded
queue），隊列的大小有限，所以線程池中排隊的請求超過隊列大小時，接下來的請求就會被拒絕，這種方式對響應(yīng)時間敏感的系統(tǒng)來說，就相對更加合理。不過，設(shè)置一個合理的隊列大小，也是非常有講究的。隊列太大導(dǎo)致等待的請求太多，隊列太小會導(dǎo)致無法充分利用系統(tǒng)資源、發(fā)揮最大性能。
除了前面講到隊列應(yīng)用在線程池請求排隊的場景之外，隊列可以應(yīng)用在任何有限資源池中，用于排隊請求，比如數(shù)據(jù)庫連接池等。
實際上，對于大部分資源有限的場景，當(dāng)沒有空閑資源時，基本上都可以通過“隊列”這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)請求排隊。
內(nèi)容小結(jié)
今天我們講了一種跟棧很相似的數(shù)據(jù)結(jié)構(gòu)，隊列。關(guān)于隊列，你能掌握下面的內(nèi)容，這節(jié)就沒問題了。
隊列最大的特點就是先進先出，主要的兩個操作是入隊和出隊。跟棧一樣，它既可以用數(shù)組來實現(xiàn)，也可以用鏈表來實現(xiàn)。用數(shù)組實現(xiàn)的叫順序隊列，用鏈表實現(xiàn)的叫鏈?zhǔn)疥犃?。特別是長得像一個環(huán)的循環(huán)隊列。在數(shù)組實現(xiàn)隊列的時候，會有數(shù)據(jù)搬移操作，要想解決數(shù)據(jù)搬移的問題，我們就需要像環(huán)一樣的循環(huán)隊列。
循環(huán)隊列是我們這節(jié)的重點。要想寫出沒有bug的循環(huán)隊列實現(xiàn)代碼，關(guān)鍵要確定好隊空和隊滿的判定條件，具體的代碼你要能寫出來。
除此之外，我們還講了幾種高級的隊列結(jié)構(gòu)，阻塞隊列、并發(fā)隊列，底層都還是隊列這種數(shù)據(jù)結(jié)構(gòu)，只不過在之上附加了很多其他功能。阻塞隊列就是入隊、出隊操作可以阻塞，并發(fā)隊列就是隊列的操作多線程安全。
思考
除了線程池這種池結(jié)構(gòu)會用到隊列排隊請求，你還知道有哪些類似的池結(jié)構(gòu)或者場景中會用到隊列的排隊請求呢？
今天講到并發(fā)隊列，關(guān)于如何實現(xiàn)無鎖并發(fā)隊列，網(wǎng)上有非常多的討論。對這個問題，你怎么看呢？
歡迎留言和我分享，我會第一時間給你反饋。
