無鎖數據結構：隊列
隊列多種多樣，不同之處在于消息生產者、消費的數量不同；在于是基于預先分配的buffer有界隊列，還是基于List的無界隊列；在于是否支持優先級；在于是無鎖非阻塞，還是有鎖；在于嚴格遵守FIFO，公平還是非公平等等。
眾所周知，更多特定的隊列需求，勢必需要更加有效的算法。本文中，只考慮隊列最常見的版本，多個生產者對多個消費者，無界并發隊列，因此不考慮優先級。
我猜隊列想必是研究人員最喜歡的數據結構，因為它簡單，但卻比棧復雜，因為它有兩端而非一端。正是因為有兩端，那么一個有趣的問題就出來了：如何在多線程環境下管理它們呢？各種版本的隊列算法紛紛發表，想要做一個全面的描述是不可能的了。我提煉其中一些最流行的算法簡要介紹一下，首先從經典隊列開始。
經典隊列
經典隊列是一個帶有兩端，即頭和尾的列表。從頭部讀取數據，從尾部寫入數據。
一個標準的簡單隊列
下面的代碼拷貝自《無鎖數據結構：簡介》
struct Node {
Node * m_pNext ;
};
class queue {
Node * m_pHead ;
Node * m_pTail ;
public:
queue(): m_pHead( NULL ), m_pTail( NULL ) {}
void enqueue( Node * p )
{
p->m_pNext = nullptr;
if ( m_pTail )
m_pTail->m_pNext = p;
else
m_pHead = p ;
m_pTail = p ;
}
Node * dequeue()
{
if ( !m_pHead ) return nullptr ;
Node * p = m_pHead ;
m_pHead = p->m_pNext ;
if ( !m_pHead )
m_pTail = nullptr ;
return p ;
}
};
這里就不要過多糾結于此，它不適用于并發，列出來只是為了印證主題，說明該隊列有多簡單。本文會向大家展示，該隊列適用于并發場景時，其簡單算法做了哪些變動。
Michael和Scott的算法被認為是無鎖隊列的經典算法。
以下代碼來自libcds庫，它是經典算法的一種簡單實現。若想查看全部代碼，請看cds::intrusive::MSQueue類。代碼中包含有注釋，避免大家讀起來乏味：
bool enqueue( value_type& val )
{
/*
實現細節：NODE_TYPE和VALUE_TYPE-
是不一樣的，因此需要類型轉換。
為了簡單起見，我們假定node_traits :: to_node_ptr -
僅僅是的static_cast<node_type *>( &val )
*/
node_type * pNew = node_traits::to_node_ptr( val ) ;
typenamegc::Guardguard; // A guard, for example, Hazard Pointer
// Back-off strategy (of the template-argument class)
back_offbkoff;
node_type * t;
// As always in lock-free, we’ll deal with it, till we make the right thing...
while ( true ) {
/*
保護m_pTail, 在讀取該字段時
可以規避已刪除內存被讀的情形
*/
t = guard.protect( m_pTail, node_to_value() );
node_type * pNext = t->m_pNext.load(
memory_model::memory_order_acquire);
/*
有趣的是：該算法假定
m_pTail不能指向尾部（Tail），
而是希望通過進一步的調用實現對Tail正確的設置。
多線程互助就是一個典型的例子
*/
if ( pNext != nullptr ) {
// 在接下來的線程之后
// 有必要有效地清理Tail
m_pTail.compare_exchange_weak( t, pNext,
std::memory_order_release, std::memory_order_relaxed);
/*
全部必須從新開始，即使CAS不成功；
CAS不成功的，意味著在我們讀取m_pTail之前，它已經被改變
*/
continue ;
}
node_type * tmp = nullptr;
if ( t->m_pNext.compare_exchange_strong( tmp, pNew,
std::memory_order_release,
std::memory_order_relaxed ))
{
// Have successfully added a new element to the queue.
break ;
}
/*
執行失敗- 即CAS運算沒有成功
這意味著有人先我們到達
檢測到有并發，為了不惡化CAS
調用back_off函數
我們及時地做一個短時間的回退
*/
bkoff();
}
/*
通常，我們可以利用元素計數器
顯而易見，此計數器是不很準確：
元素早已添加，我們現在的才進行計數
這樣的計數器只能作為元素數量的清單，
不能作為一個空隊列符號
*/
++m_ItemCounter ;
/*
最后，試著改變m_pTail的Tail。
不用在意成功與否，
如果沒有成功，
它們會在dequeue()方法的Oops!注解前后被清理掉
*/
m_pTail.compare_exchange_strong( t, pNew,
std::memory_order_acq_rel, std::memory_order_relaxed );
/*
本算法返回必然是true。
其它算法，比如有界隊列，
當隊列已滿時，可以返回false
為了保證接口的一致性，enqueue()
總是返回成功的標志
*/
return true;
}
value_type * dequeue()
{
node_type * pNext;
back_offbkoff;
// We need 2 Hazard Pointers for dequeue
typenamegc::templateGuardArray<2> guards;
node_type * h;
// Keep trying till we can execute it…
while ( true ) {
// Read and guard our Head m_pHead
h = guards.protect( 0, m_pHead, node_to_value() );
// and the element that follows the Head
pNext = guards.protect( 1, h->m_pNext, node_to_value() );
// Check: is what we have just read
// remains bounded?..
if ( m_pHead.load(std::memory_order_relaxed) != h ) {
// no, - someone has managed to spoil everything...
// Start all over again
continue;
}
/*
此標記顯示隊列已空
注意與tail不同的是，
H=head始終不會錯的
*/
if ( pNext == nullptr )
return nullptr; // the queue is empty
/*
此處讀取tail，但未采用Hazard Pointer對其進行保護
我們對其指向的上下文（數據結構中字段）不感興趣
*/
node_type * t = m_pTail.load(std::memory_order_acquire);
if ( h == t ) {
/*
糟糕，有頭無尾
元素緊隨頭之后，
并且尾指向頭。
我想到了應該糾錯的時候了
*/
m_pTail.compare_exchange_strong( t, pNext,
std::memory_order_release, std::memory_order_relaxed);
// After helping them, we have to start over.
// Therefore, the CAS result is not important for us
continue;
}
// The most important thing is to link a new Head
// That is, we move down the list
if ( m_pHead.compare_exchange_strong( h, pNext,
std::memory_order_release, std::memory_order_relaxed ))
{
// Success! Terminate our infinite loop
break;
}
/*
倘若失敗，意味著有其干預；
不干擾它們，退回去小歇片刻
*/
bkoff() ;
}
// Change the not very useful counter of elements,
// see the comment in enqueue
--m_ItemCounter;
// It’s the call of 'remove the h element' functor
dispose_node( h );
/*
/*
有趣的是，
返回[ex] Head后面的元素，
但pNext仍然在隊列中-
這是隊列的新頭部！
*/
*/
return pNext;
}
正如大家所看到的，隊列由一個有頭有尾的單鏈表組成。
算法的核心是什么呢？通過常規的CAS控制兩個指針——這倆指針分別指向頭部的和尾部。實際上得到的隊列永遠不為空。查看代碼，是否有任何一處對頭和尾做了nullptr檢查？沒有吧。非空的隊列構造器中，添加啞元素（dummy element）給它，作為頭和尾。出隊返回一個元素，該元素作為一個新的頭啞元素，其前面的啞元素被移除。
（譯者注：所謂啞元素，僅是為了占一個位置，讓鏈表永遠不為空，從而簡化判斷的邊緣條件，其數據部分沒有任何意義）
在設計侵入式隊列時必須考慮，返回指針是隊列的一部分，僅在下一次出隊時可以移除它。
其次，算法假定尾部指針不指向最后一個元素。每一次讀取尾部，需檢查尾部是否包含下一個m_pNext元素。倘若該指針不為nullptr ， 說明tail位置不對，應該后移。但這里有另外一個陷阱：或許tail會指向head前面的元素。為了避免這一點，出隊方法中對m_pTail->m_pNext做了隱式地檢查：先讀取head，m_pHead->m_pNext元素緊隨其后，確保pNext != nullptr。接著看到head等于tail，tail后面必然還有元素，即pNext，此時應該后移tail。這是一個典型的線程互助案例，它在無鎖編程中很常見。
2000年，小范圍的算法優化被提出 。 該觀點認為出隊方法中的MSQueue算法，在每一次的循環迭代中，讀取tail是沒有必要的；只有在成功更新head時，才有必要讀取tail，驗證tail是否真的指向最后一個元素。因此，可以在某種程度上減少加載m_pTail的壓力。這個優化參見libcds庫中的cds::intrusive::MoirQueue類。
菜籃隊列
2007年，一個MSQueue有趣的 變體 被引入。無鎖領域久負盛名的研究者Nir Shavit和他的助理們，采用不同的方法優化了Michael和Scott經典的無鎖隊列。
Nir Shavit將隊列作為一組邏輯菜籃，短時間內，每一個都可以插入一個新元素。一旦這個時間點過了，一個新的菜籃就會被創建。
每個菜籃包含一組無序元素，這種定義看似違反了隊列-FIFO的基本特性；也就是說隊列變成了非公平。FIFO是針對菜籃的，而非菜籃中的元素。倘若菜籃用來插入的時間段非常短暫，我們可以忽視菜籃中無序項。（譯者注：時間短意味著，沒放幾個就創建了新的菜籃，因此可以近似地看做是FIFO）
如何確定時間段的長短呢？菜籃隊列作者認為，實際上，無需確定該時間短長短。讓我們回頭看一眼MSQueue隊列，在入隊運算中（enqueue），當并發很高時，CAS改變尾部（tail）無法正常工作；這就是為什么在MSQueue調用回退（back-off）的原因，在并發情況下加入元素，無法保證隊列中元素項的排序。就是這個邏輯菜籃。正好說明，抽象的邏輯菜籃就是一種回退策略。
在此，我不想過多地談論代碼實現，因此就不提供具體代碼了。MSQueue例子已經很好的向我闡述了，無鎖代碼確實相當的簡潔。有計劃查看代碼實現的，請參看libcds庫中cds::intrusive::BasketQueue類，cds/intrusive/basket_queue.h文件。同時，為了解釋本算法，我從Nir Shavit及其同事的工作中拷貝了另一張圖：
1、A、B、C三個線程打算往隊列中插入項。它們看到尾部（tail）在正確的位置，并試圖并發改變tail（還記得在MSQueue中，尾部（tail）可以不指向隊列中最后的元素）。
2、A線程獲勝，成功插入一個新項。B和C則失敗了——它們的tail的CAS運算沒有成功執行。因此 ， 它倆開始基于之前的讀到的tail舊值，往菜籃中插入各自的項。
3、B線程先一步成功插入，與此同時，D線程調用入隊（enqueue），成功完成項插入，并改變了尾部（tail）。
4、C線程此后也完成了插入，請看，它將項插入隊列中間位置。在這個插入過程中，C使用的指向舊tail的指針，在線程進入運算但未成功執行CAS時，就已經讀取此指針了。
需要注意的是，在插入過程中，插入項可能被放入隊列head前面。比如圖NR 4中C前面的項：當C線程執行入隊（enqueue）時，其它線程刪除C前面的項。（譯者注，舊的頭部被刪除了）
為了防止此類情形出現，建議采用邏輯刪除，即用一個特殊刪除標簽標記待刪除元素。這就要求指向項的標簽和指針必須為原子性讀取，我們在指向pNext項指針的最低有效位（lsb）中存入此標簽。這是可以接受的，現代系統中內存分配都是以4個字節對齊，因為指針最低有效位的2個比特一直為零。所以我們創造了標記指針方法，該方法被廣泛地應用于無鎖數據結構中。當然未來我們會多次碰到此方法。應用邏輯刪除，即在CAS幫助下，將pNext最低位比特值設為1，這樣就可以避免插入項在head前面的情形出現。這樣插入依舊由CAS來完成，與此同時，待刪除項在最低位值為1.因此，CAS可能會失敗。（當然，在插入項時，我們無需獲取整個標記指針，只有最高有效位（msb）包含地址；我們假定最低有效位等于零）。
菜籃隊列最后一項改進是刪除項實體，據觀察，在每次成功調用出隊時，改變頭部令人不爽，因為CAS會被調用，正如你所知道的那樣，這個操作太笨重了。因此，我們僅在存在好幾個邏輯刪除元素之后，才會改變頭部。（在libcds庫中，缺省值是三）。同樣，當隊列為空時，我們也可以改變頭部（head）。可以說，在菜籃隊列中，頭部是變化跳動的。
所有對經典無鎖隊列優化設計都是在高并發這個背景下展開的。
樂觀方式
2004年 Nir Shavit和Edya Ladan Mozes在MSQueue引入另一種叫做 樂觀的優化方式 。
他們注意到Michael和Scott的算法中，出隊運算僅需要一個CAS，而入隊需要兩個CAS，如上圖所示。
而入隊中第二個CAS甚至在低加載時。能顯著降低性能，因為在現代處理器中，CAS是一個相當重量級運算。是否在某種程度上可以處理掉這個不足呢？
試想MSQueue::enqueue中存在兩個CAS會怎樣？第一個CAS添加新項到tail ， 使得pTail->pNext。第二個CAS將尾部向后移動。那么可否用一個原子性記錄而非CAS改變pNext字段呢？確實可以，假定單鏈表的方向與以往不一樣，并非從頭到尾，而是從尾到頭。因此可以采用原子性store（pNew->pNext = pTail）完成pNew->pNext任務，接著再通過CAS改變pTail。不過一旦改變了單鏈表方向，接下來如何進行出隊運算呢？因為方向改變，pHead->pNext 必然不會存在了。
樂觀隊列作者建議改用一個雙鏈表。
但問題是，針對CAS的無鎖雙鏈表有效算法迄今還未可知。已知的算法有DCAS，但沒有對應的硬件實現。針對CAS的MCAS（CAS for M unbounded memory cells）仿真算法，但沒那么有效（需要2M + 1 CAS），充其量就是一個理論的玩意。
作者給出了以下方法：鏈表從尾部到頭部的鏈接依舊是一致的（隊列中并不需要next鏈接，但它可以處理入隊第一個CAS）。正是由于從頭到尾相反的方向，最重要的鏈接-prev-并不能真正的一致，意味著允許出現這種違例的。找出此類違例，我們就可以重建正確的表，放在next引用后面。如何檢測此類違例了？事實上，這個相當簡單：pHead->prev->next != pHead。如果這個不等在出隊（dequeue）被發現， fix_list這個輔助處理過程就會被調用。
摘自libcds庫cds::intrusive::OptimisticQueue類
void fix_list( node_type * pTail, node_type * pHead )
{
// pTail and pHead are already protected by Hazard Pointers
node_type * pCurNode;
node_type * pCurNodeNext;
typename gc::template GuardArray<2> guards;
pCurNode = pTail;
while ( pCurNode != pHead ) { // Till we reach the head
pCurNodeNext = guards.protect(0, pCurNode->m_pNext, node_to_value() );
if ( pHead != m_pHead.load(std::memory_order_relaxed) )
break;
pCurNodeNext->m_pPrev.store( pCurNode, std::memory_order_release );
guards.assign( 1, node_traits::to_value_ptr( pCurNode = pCurNodeNext ));
}
}
fix_list從隊列的尾查至頭，用正確的pNext引用，正確的pPrev。
列表從頭至尾的違例也是有可能的，更多的是因為延遲，而非重加載。延遲是因為操作系統替換或線程中斷。具體請看 OptimisticQueue::enqueue中的代碼：
bool enqueue( value_type& val )
{
node_type * pNew = node_traits::to_node_ptr( val );
typename gc::template GuardArray<2> guards;
back_offbkoff;
guards.assign( 1, &val);
node_type * pTail = guards.protect( 0, m_pTail, node_to_value());
while( true ) {
// 從尾至頭形成一個直接列表
pNew->m_pNext.store( pTail, std::memory_order_release );
// Trying to change the tail
if ( m_pTail.compare_exchange_strong( pTail, pNew,
std::memory_order_release, std::memory_order_relaxed ))
{
/*
從頭到尾形成一個相反的列表
操作系統可以中斷、替換。
結果，pTail從隊列中被替換掉，即出隊
（不用擔心，pTail會被Hazard Pointer保護，因此具有不可被移除性）
*/
pTail->m_pPrev.store( pNew, std::memory_order_release );
break ; // Enqueue done!
}
/*
CAS沒有成功，pTail已被改變，（記住C++11中CAS特點：
第一個元素傳的是引用）
Hazard Pointer保護新的pTail
*/
guards.assign( 0, node_traits::to_value_ptr( pTail ));
// High contention – let’s step back
bkoff();
}
return true;
}
這段代碼證明了我們所做出的優化：建立pPrev列表（對我們最重要了），希望能成功。倘若發現直接列表和反向列表之間有錯位，我們不得不花時間確認了（運行fix_list）。
那么，底線在哪里？入隊和出隊各自都有一個CAS。代價就是一旦列表被檢測出違例，就會運行fix_list。代價究竟有多大？實驗結果會告訴我們。
大家可以在cds/intrusive.optimistic_queue.h文件，以及libcds庫中的cds::intrusive::OptimisticQueue類中找到源代碼。
無等待隊列
為了完整地闡述經典隊列，我們應該談談無等待隊列算法。
無等待幾乎是算法中最嚴格的，算法的執行時間必須可限定并且可預測。在實踐中，無等待算法通常比諸如無鎖、無干擾算法性能要低。但它們數量眾多，實現起來也不復雜。
許多無等待算法結構是相當標準：不是執行一運算（例如入隊/出隊），而是先聲明 —— 存儲帶參數的運算描述于一些可公開訪問的共享存儲中 ， 接著不停地開啟并發線程。接著它們瀏覽存儲中的描述符，并試著執行該代碼。結果，很多線程以很高的負載執行相同的任務，僅有一個線程成功。
諸如此類的C++算法實現復雜度，主要涉及如何實現存儲，以及處理描述符的內存分配。
libcds庫沒有實現無等待隊列，是因為該隊列作者在其研究中，性能測試結果不盡人意。
測試結果
本文中，我決定提供以上算法的測試結果。
測試是綜合性的，測試機為雙核處理器，Debian Linux，Intel Dual Xeon X5670 2.93 GHz, 6 cores per processor + hyperthreading，總共24邏輯處理器。測試過程中，機器閑置達百分之九十。
編譯器為GCC4.8.2，優化參數為-O3 -march=native -mtune=native。
測試隊列來自cds::container命名空間，因此，它們是非侵入式的，即每個元素執行各種的內存分配。隨后我們會將隊列與采用互斥量（mutex）的std::queue<T, std::deque<T>>和std::queue<T, std::list<T>>標準同步實現做比較。
T類型為兩個整型的數據結構。所有無鎖隊列都基于Hazard Pointer。
持久性測試
該測試相當特殊，有一千萬對入隊/出隊運算。第一部分，測試執行一千萬入隊，75%為入隊運算，剩余25%為出隊運算，即一千萬的入隊運算，二百五十萬的出隊運算）。第二部分，出隊運算執行七百五十萬次，直到隊列為空。
測試遵循以下理念：減小緩存分配器的不利影響，當然前提是分配器含有緩存。
測試時間的絕對值：
大家看到了什么？
首先映入眼簾的是，有鎖std::queue<T, std::deque<T>>被證明是最快的。怎么可能呢？我認為這個跟內存有關：std::deque以N元素的塊來分配內存，而非每個元素。這暗示我們應該移除測試中分配器的影響，這會帶來相當長的延遲，另外，還有互斥量。當然， libcds的所有侵入式容器版本，沒有為元素分配內存。理應對它們進行測試。
顯而易見，無鎖隊列，針對MSQueue所有縝密的優化開出了豐碩的果實，即便不是那么完美。
生產者和消費者測試
這個測試相當切合實際，隊列中包含N個生產者，N個消費者，分別執行百萬條寫運算，百萬條讀運算。圖表中的線程數，為生產者和消費者的線程數之和。
測試時間的絕對值：
此處可以看出無鎖隊列是相當優雅，勝出者為OpimisticQueue。這就是說該無鎖數據結構的所有假設被證明都是正確的。
本測試接近實際情形，隊列中沒有出現大量元素堆積現象。為什么呢？個人認為，分配器內在的優化在起作用。確實如此，在最后階段，隊列的存在不是為了大量元素堆積，而是削峰，通常隊列中是不存在元素的。
關于棧的補充說明
既然談到測試，就來談談棧。
本文以及前文所涉及的無鎖棧，針對Treiber棧，我移除了回退（back-off）。不論實現，亦或者偽碼描述、C++完整產品實現，理應單獨作為一篇文章。不過我可能永遠不會寫，因為其中所涉及的代碼是在太多。實際上，你會發現移除回退（back-off）之后，若你查看源碼，完全不同。截止目前，只有libcds庫里有。
同樣，我也提供了綜合測試結果，測試機器和前面的一樣。
生產者和消費者測試：一些線程會寫入棧中即壓棧，而另一些線程會讀取棧即彈棧。一組相同數量的生產者和消費者，生產者和消費者的線程總數都是百萬級。標準的棧，其同步由互斥量完成。
測試時間的絕對值：
顯而易見，圖表本身就可以很好地說明事實。
移除回退（back-off）之后，什么促使性能的顯著增加？好像是因為壓棧、彈棧相互抵消。然而，我們查看內部統計，就會發現百萬個執行僅有十萬到十五萬個壓棧、彈棧相互抵消，大約為0.1%。而移除回退整個進入數大約為三十五萬。這說明移除回退最大的優勢就是一些線程在負載高的時候休眠，進而自動降低了整個棧的負載。現實的例子，移除回退（back-off）的休眠線程會持續大約5毫秒。
總結
本文闡述了經典無鎖隊列，展示了列表元素。該對列顯著的特點就是存在兩個并發端-頭部和尾部。接著縝密地闡述了Michael和Scott經典算法的一些改進。我希望你會對此感興趣，并能在每天的生活中用到它。
從測試結果看，盡管隊列是無鎖的，但神奇的CAS并沒有帶來任何特別的性能提升。因此，很有必要尋找其它一些方法消除瓶頸即頭部和尾部，在某種程度上實現隊列并行工作。
來自：http://blog.jobbole.com/109648/