[發明專利]基于反轉單鏈表的鎖無關消息隊列實現方法

有效

• 申請號: 201310102077.5
• 申請日: 2013-03-27
• 公開（公告）號: CN103176837A
• 公開（公告）日: 2013-06-26
• 發明（設計）人: 周克利;唐杰;武港山
• 申請（專利權）人: 南京大學
• 主分類號: G06F9/46
• 分類號: G06F9/46
• 代理公司: 南京天翼專利代理有限責任公司 32112
• 代理人: 黃明哲

技術領域

本發明屬于計算機分布式領域，涉及在2線程架構的1個寫線程和1個讀線程程序中，實現鎖無關的消息隊列，為一種基于反轉單鏈表的鎖無關消息隊列實現方法。

背景技術

在當前的服務器架構中，為了充分利用硬件資源，提高程序效率，大多數采取了多線程架構，而最常見的是有一個等待網絡、終端等事件的等待線程，一個處理客戶端消息、服務器主邏輯的主線程，一個用于2個線程間通訊的消息隊列。

傳統的消息隊列采取了鎖機制來保證同步、互斥。但鎖機制會導致線程獲取鎖的時候，會進入等待睡眠狀態，從而引發線程間的切換。而線程間的切換又是非常消耗資源的操作。在處理海量請求的服務器中，對消息隊列的訪問非常頻繁，那么產生線程切換的概率也非常高，從而使得服務器處理效率直線下降。

而在鎖無關數據結構的探索中，當今最常用的就是基于原子指令CAS（Compare?And?Swap）來實現鎖無關。雖然CAS的效率要比鎖機制高很多，但CAS也并不是一個廉價的指令。在海量消息處理的服務器中，CAS帶來的效率損失也不能不讓使用者謹慎。

發明內容

本發明要解決的技術問題是：如何在拋棄鎖機制以及CAS等昂貴的原子指令的前提下，實現2線程架構下的鎖無關消息隊列。

本發明的技術方案為：基于反轉單鏈表的鎖無關消息隊列實現方法，用于2線程服務器架構，包括a)基于反轉單鏈表的鎖無關消息隊列的數據結構，b)基于所述數據結構實現的兩個鎖無關方法的操作函數：Push函數和Pop函數；2線程間通過所述鎖無關消息隊列，在所述鎖無關方法下進行通訊，其中：

1）、反轉單鏈表的數據結構為：

struct?List?Element{

????????????struct?ListElement*prev；

???}；

反轉單鏈表中，每個鏈表元素只有一個指向其前一項鏈表元素的指針prev；

2）基于所述反轉單鏈表的鎖無關消息隊列的數據結構為：

2a)設有一個指向反轉單鏈表的鏈表頭的head指針；

2b)設有一個指向反轉單鏈表的鏈表尾的tail指針；

2c)設有一個指向上次Pop出去元素項的last指針；

3）基于所述鎖無關消息隊列的Push函數，包括以下幾個要素：

3a)head指針只在最開始時為NULL，此時tail指針也為NULL，這種情況下，在Push第一個消息Push結束前，Pop函數總是返回NULL；

3b)在Push第一個消息時，對tail的賦值要在Push函數返回之前最后一個執行，使得Pop函數在Push函數結束前，總是返回NULL；

3c)每個新來的消息，都分配一個struct?ListElement數據結構，即反轉單鏈表的數據結構，并將其賦值；

3d)對于每一個消息項，Push函數在將其鏈入消息隊列之前對其執行寫操作，當其在消息隊列里以后，Push函數不對其進行任何修改；

3e)只有Push函數永遠不會被訪問的元素項，才能由Pop釋放內存；

3f)剛剛Pop出去的元素項不會被立即釋放，而是存在last指針里，只有再次Pop出其他元素項時，last指針當前指向的元素項才會被釋放；

4）基于所述鎖無關消息隊列的Pop函數，分為以下情況：

4a)如果tail==NULL&&last==NULL，那么消息隊列處于未初始化狀態，Pop返回NULL；

4b)如果tail==NULL&&last!=NULL，那么tail=last→prev，如果這時候tail還為NULL，說明消息隊列為空，Pop返回NULL；

4c)如果tail!=NULL，那么tail指向的是一個正確的消息項，需要更新last指針，如果last指針之前不為NULL，則將其內存釋放，讓last指向最新釋放的消息項，并將tail值更新為tail=tail→prev；

在2線程的服務器架構下，其中一個線程A為收發網絡消息數據包的通訊線程，另一個線程B為處理服務器內部邏輯的主線程，這2個線程間通過所述鎖無關消息隊列和操作函數進行通訊：

a)定義一個基于反轉單鏈表的鎖無關消息隊列：MsgQueue；

b)線程A從網絡收到消息數據包Packet，執行MsgQueue.Push(Packet)，即將收到的消息數據包通過Push函數添加進鎖無關消息隊列里；