原文來(lái)自于： http://www.parallellabs.com/2010/10/25/practical-concurrent-queue-algorithm/
多線程隊(duì)列（Concurrent Queue）的使用場(chǎng)合非常多，高性能服務(wù)器中的消息隊(duì)列，并行算法中的Work Stealing等都離不開(kāi)它。對(duì)于一個(gè)隊(duì)列來(lái)說(shuō)有兩個(gè)最主要的動(dòng)作：添加（enqueue）和刪除（dequeue）節(jié)點(diǎn)。在一個(gè)（或多個(gè)）線程在對(duì)一個(gè)隊(duì)列進(jìn)行enqueue操作的同時(shí)可能會(huì)有一個(gè)（或多個(gè)）線程對(duì)這個(gè)隊(duì)列進(jìn)行dequeue操作。因?yàn)閑nqueue和dequeue都是對(duì)同一個(gè)隊(duì)列里的節(jié)點(diǎn)進(jìn)行操作，為了保證線程安全，一般在實(shí)現(xiàn)中都會(huì)在隊(duì)列的結(jié)構(gòu)體中加入一個(gè)隊(duì)列鎖（典型的如pthread_mutex_t q_lock），在進(jìn)行enqueue和dequeue時(shí)都會(huì)先鎖住這個(gè)鎖以鎖住整個(gè)隊(duì)列然后再進(jìn)行相關(guān)的操作。這樣的設(shè)計(jì)如果實(shí)現(xiàn)的好的話一般性能就會(huì)很不錯(cuò)了。以鏈表實(shí)現(xiàn)的隊(duì)列的結(jié)構(gòu)體一般是這樣的：
|
01
02
03
04
05
|
struct queue_t {
node_t *head;
node_t *tail;
pthread_mutex_t q_lock;
};
|
但是，這其中其實(shí)有一個(gè)潛在的性能瓶頸：enqueue和dequeue操作都要鎖住整個(gè)隊(duì)列，這在線程少的時(shí)候可能沒(méi)什么問(wèn)題，但是只要線程數(shù)一多，這個(gè)鎖競(jìng)爭(zhēng)所產(chǎn)生的性能瓶頸就會(huì)越來(lái)越嚴(yán)重。那么我們可不可以想辦法優(yōu)化一下這個(gè)算法呢？當(dāng)然可以！如果我們仔細(xì)想一想enqueue和dequeue的具體操作就會(huì)發(fā)現(xiàn)他們的操作其實(shí)不一定是沖突的。例如：如果所有的enqueue操作都是往隊(duì)列的尾部插入新節(jié)點(diǎn)，而所有的dequeue操作都是從隊(duì)列的頭部刪除節(jié)點(diǎn)，那么enqueue和dequeue大部分時(shí)候都是相互獨(dú)立的，我們大部分時(shí)候根本不需要鎖住整個(gè)隊(duì)列，白白損失性能！那么一個(gè)很自然就能想到的算法優(yōu)化方案就呼之欲出了：我們可以把那個(gè)隊(duì)列鎖拆成兩個(gè)：一個(gè)隊(duì)列頭部鎖（head lock)和一個(gè)隊(duì)列尾部鎖(tail lock)。這樣這樣的設(shè)計(jì)思路是對(duì)了，但是如果再仔細(xì)思考一下它的實(shí)現(xiàn)的話我們會(huì)發(fā)現(xiàn)其實(shí)不太容易，因?yàn)橛袃蓚€(gè)特殊情況非常的tricky（難搞）：第一種就是往空隊(duì)列里插入第一個(gè)節(jié)點(diǎn)的時(shí)候，第二種就是從只剩最后一個(gè)節(jié)點(diǎn)的隊(duì)列中刪除那個(gè)“最后的果實(shí)”的時(shí)候。
為什么難搞呢？當(dāng)我們向空隊(duì)列中插入第一個(gè)節(jié)點(diǎn)的時(shí)候，我們需要同時(shí)修改隊(duì)列的head和tail指針，使他們同時(shí)指向這個(gè)新插入的節(jié)點(diǎn)，換句話說(shuō)，我們此時(shí)即需要拿到head lock又需要拿到tail lock。而另一種情況是對(duì)只剩一個(gè)節(jié)點(diǎn)的隊(duì)列進(jìn)行dequeue的時(shí)候，我們也是需要同時(shí)修改head和tail指針使他們指向NULL，亦即我們需要同時(shí)獲得head和tail lock。有經(jīng)驗(yàn)的同學(xué)會(huì)立刻發(fā)現(xiàn)我們進(jìn)入危險(xiǎn)區(qū)了！是什么危險(xiǎn)呢？死鎖！多線程編程中最臭名昭著的一種bug就是死鎖了。例如，如果線程A在鎖住了資源1后還想要獲取資源2，而線程B在鎖住了資源2后還想要獲取資源1，這時(shí)兩個(gè)線程誰(shuí)都不能獲得自己想要的那個(gè)資源，兩個(gè)線程就死鎖了。所以我們要小心奕奕的設(shè)計(jì)這個(gè)算法以避免死鎖，例如保證enqueue和dequeue對(duì)head lock和tail lock的請(qǐng)求順序（lock ordering）是一致的等等。但是這樣設(shè)計(jì)出來(lái)的算法很容易就會(huì)包含多次的加鎖/解鎖操作，這些都會(huì)造成不必要的開(kāi)銷，尤其是在線程數(shù)很多的情況下反而可能導(dǎo)致性能的下降。我的親身經(jīng)歷就是在32線程時(shí)這個(gè)思路設(shè)計(jì)出來(lái)的算法性能反而下降了10%左右，原因就是加鎖/解鎖的開(kāi)銷增加了。
好在有聰明人早在96年就想到了一個(gè)更妙的算法。這個(gè)算法也是用了head和tail兩個(gè)鎖，但是它有一個(gè)關(guān)鍵的地方是它在隊(duì)列初始化的時(shí)候head和tail指針不為空，而是指向一個(gè)空節(jié)點(diǎn)。在enqueue的時(shí)候只要向隊(duì)列尾部添加新節(jié)點(diǎn)就好了。而dequeue的情況稍微復(fù)雜點(diǎn)，它要返回的不是頭節(jié)點(diǎn)，而是head->next，即頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。先來(lái)看偽代碼：
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
typedef struct node_t {
TYPE value;
node_t *next
} NODE;
typedef struct queue_t {
NODE *head;
NODE *tail;
LOCK q_h_lock;
LOCK q_t_lock;
} Q;
initialize(Q *q) {
node = new_node() // Allocate a free node
node->next = NULL // Make it the only node in the linked list
q->head = q->tail = node // Both head and tail point to it
q->q_h_lock = q->q_t_lock = FREE // Locks are initially free
}
enqueue(Q *q, TYPE value) {
node = new_node() // Allocate a new node from the free list
node->value = value // Copy enqueued value into node
node->next = NULL // Set next pointer of node to NULL
lock(&q->q_t_lock) // Acquire t_lock in order to access Tail
q->tail->next = node // Link node at the end of the queue
q->tail = node // Swing Tail to node
unlock(&q->q_t_lock) // Release t_lock
｝
dequeue(Q *q, TYPE *pvalue) {
lock(&q->q_h_lock) // Acquire h_lock in order to access Head
node = q->head // Read Head
new_head = node->next // Read next pointer
if new_head == NULL // Is queue empty?
unlock(&q->q_h_lock) // Release h_lock before return
return FALSE // Queue was empty
endif
*pvalue = new_head->value // Queue not empty, read value
q->head = new_head // Swing Head to next node
unlock(&q->q_h_lock) // Release h_lock
free(node) // Free node
return TRUE // Queue was not empty, dequeue succeeded
}
|
發(fā)現(xiàn)玄機(jī)了么？是的，這個(gè)算法中隊(duì)列總會(huì)包含至少一個(gè)節(jié)點(diǎn)。dequeue每次返回的不是頭節(jié)點(diǎn)，而是頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)中的數(shù)據(jù)：如果head->next不為空的話就把這個(gè)節(jié)點(diǎn)的數(shù)據(jù)取出來(lái)作為返回值，同時(shí)再把head指針指向這個(gè)節(jié)點(diǎn)，此時(shí)舊的頭節(jié)點(diǎn)就可以被free掉了。這個(gè)在隊(duì)列初始化時(shí)插入空節(jié)點(diǎn)的技巧使得enqueue和dequeue徹底相互獨(dú)立了。但是，還有一個(gè)小地方在實(shí)現(xiàn)的時(shí)候需要注意：對(duì)第一個(gè)空節(jié)點(diǎn)的next指針的讀寫(xiě)。想象一下，當(dāng)一個(gè)線程對(duì)一個(gè)空隊(duì)列進(jìn)行第一次enqueue操作時(shí)剛剛運(yùn)行完第25行的代碼（對(duì)該空節(jié)點(diǎn)的next指針進(jìn)行寫(xiě)操作）；而此時(shí)另一個(gè)線程對(duì)這個(gè)隊(duì)列進(jìn)行第一次dequeue操作時(shí)恰好運(yùn)行到第33行（對(duì)該空節(jié)點(diǎn)的next指針進(jìn)行讀操作），它們其實(shí)還是有沖突！不過(guò)，好在一般來(lái)講next指針是32位數(shù)據(jù)，而現(xiàn)代的CPU已經(jīng)能保證多線程程序中內(nèi)存對(duì)齊了的32位數(shù)據(jù)讀寫(xiě)操作的原子性，而一般來(lái)講編譯器會(huì)自動(dòng)幫你對(duì)齊32位數(shù)據(jù)，所以這個(gè)不是問(wèn)題。唯一需要注意的是我們要確保enqueue線程是先讓要添加的新節(jié)點(diǎn)包含好數(shù)據(jù)再把新節(jié)點(diǎn)插入鏈表（也就是不能先插入空節(jié)點(diǎn)，再往節(jié)點(diǎn)中填入數(shù)據(jù)），那么dequeue線程就不會(huì)拿到空的節(jié)點(diǎn)。其實(shí)我們也可以把q_t_lock理解成生產(chǎn)者的鎖，q_h_lock理解成消費(fèi)者的鎖，這樣生產(chǎn)者（們）和消費(fèi)者（們）的操作就相互獨(dú)立了，只有在多個(gè)生產(chǎn)者對(duì)同一隊(duì)列進(jìn)行添加操作時(shí)，以及多個(gè)消費(fèi)者對(duì)同一隊(duì)列進(jìn)行刪除操作時(shí)才需要加鎖以使訪問(wèn)互斥。
通過(guò)使用這個(gè)算法，我成功的把一個(gè)32線程程序的性能提升了11%！可見(jiàn)多線程中的鎖競(jìng)爭(zhēng)對(duì)性能影響之大！此算法出自一篇著名的論文：M. Michael and M. Scott. Simple, Fast, and Practical Non-Blocking and Blocking Concurren Queue Algorithms. 如果還想做更多優(yōu)化的話可以參考這篇論文實(shí)現(xiàn)相應(yīng)的Non Blocking版本的算法，性能還能有更多提升。當(dāng)然了，這個(gè)算法早已被集成到j(luò)ava.util.concurrent里了（即LinkedBlockingQueue），其他的并行庫(kù)例如Intel的TBB多半也有類似的算法，如果大家能用上現(xiàn)成的庫(kù)的話就不要再重復(fù)造輪子了。為什么別造并行算法的輪子呢？因?yàn)楦咝阅艿牟⑿兴惴▽?shí)在太難正確地實(shí)現(xiàn)了，尤其是Non Blocking，Lock Free之類的“火箭工程”。有多難呢？Doug Lea提到j(luò)ava.util.concurrent中一個(gè)Non Blocking的算法的實(shí)現(xiàn)大概需要1年的時(shí)間，總共約500行代碼。所以，對(duì)最廣大的程序員來(lái)說(shuō)，別去寫(xiě)Non Blocking, Lock Free的代碼，只管用就行了，我看見(jiàn)網(wǎng)上很多的Non Blocking阿，無(wú)鎖編程的算法實(shí)現(xiàn)啊什么的都非常地害怕，誰(shuí)敢去用他們貼出來(lái)的這些代碼啊？我之所以推薦這個(gè)two lock的算法是因?yàn)樗膶?shí)現(xiàn)相對(duì)Non Blocking之類的來(lái)說(shuō)容易多了，非常具備實(shí)用價(jià)值。雖然這篇論文出現(xiàn)的很早，但是我在看了幾個(gè)開(kāi)源軟件中多線程隊(duì)列的實(shí)現(xiàn)之后發(fā)現(xiàn)他們很多還是用的本文最開(kāi)始提到的那種一個(gè)鎖的算法。如果你想要實(shí)現(xiàn)更高性能的多線程隊(duì)列的話，試試這個(gè)算法吧！
Update: 多線程隊(duì)列算法有很多種，大家應(yīng)根據(jù)不同的應(yīng)用場(chǎng)合選取最優(yōu)算法（例如是CPU密集型還是IO密集型）。本文所列的算法應(yīng)用在這樣一個(gè)多線程程序中：每個(gè)線程都擁有一個(gè)隊(duì)列，每個(gè)隊(duì)列可能被本線程進(jìn)行dequeue操作，也可以被其他線程進(jìn)行dequeue（即work stealing），線程數(shù)不超過(guò)CPU核心數(shù)，是一個(gè)典型的CPU/MEM密集型客戶端單寫(xiě)者多讀者場(chǎng)景。