[發(fā)明專利]基于反轉(zhuǎn)單鏈表的鎖無關(guān)消息隊(duì)列實(shí)現(xiàn)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310102077.5
• 申請(qǐng)日: 2013-03-27
• 公開（公告）號(hào): CN103176837A
• 公開（公告）日: 2013-06-26
• 發(fā)明（設(shè)計(jì)）人: 周克利;唐杰;武港山
• 申請(qǐng)（專利權(quán)）人: 南京大學(xué)
• 主分類號(hào): G06F9/46
• 分類號(hào): G06F9/46
• 代理公司: 南京天翼專利代理有限責(zé)任公司 32112
• 代理人: 黃明哲

1.基于反轉(zhuǎn)單鏈表的鎖無關(guān)消息隊(duì)列實(shí)現(xiàn)方法，用于2線程服務(wù)器架構(gòu)，其特征包括：a)基于反轉(zhuǎn)單鏈表的鎖無關(guān)消息隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，b)基于所述數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的兩個(gè)鎖無關(guān)方法的操作函數(shù)：Push函數(shù)和Pop函數(shù)；2線程間通過所述鎖無關(guān)消息隊(duì)列，在所述鎖無關(guān)方法下進(jìn)行通訊，其中：

1）、反轉(zhuǎn)單鏈表的數(shù)據(jù)結(jié)構(gòu)為：

struct?LisElement{

?????????????struct?LisElement*prev；

???}；

反轉(zhuǎn)單鏈表中，每個(gè)鏈表元素只有一個(gè)指向其前一項(xiàng)鏈表元素的指針prev；

2）基于所述反轉(zhuǎn)單鏈表的鎖無關(guān)消息隊(duì)列的數(shù)據(jù)結(jié)構(gòu)為：

2a)設(shè)有一個(gè)指向反轉(zhuǎn)單鏈表的鏈表頭的head指針；

2b)設(shè)有一個(gè)指向反轉(zhuǎn)單鏈表的鏈表尾的tail指針；

2c)設(shè)有一個(gè)指向上次Pop出去元素項(xiàng)的last指針；

3）基于所述鎖無關(guān)消息隊(duì)列的Push函數(shù)，包括以下幾個(gè)要素：

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

3b)在Push第一個(gè)消息時(shí)，對(duì)tail的賦值要在Push函數(shù)返回之前最后一個(gè)執(zhí)行，使得Pop函數(shù)在Push函數(shù)結(jié)束前，總是返回NULL；

3c)每個(gè)新來的消息，都分配一個(gè)struct?ListElement數(shù)據(jù)結(jié)構(gòu)，即反轉(zhuǎn)單鏈表的數(shù)據(jù)結(jié)構(gòu)，并將其賦值；

3d)對(duì)于每一個(gè)消息項(xiàng)，Push函數(shù)在將其鏈入消息隊(duì)列之前對(duì)其執(zhí)行寫操作，當(dāng)其在消息隊(duì)列里以后，Push函數(shù)不對(duì)其進(jìn)行任何修改；

3e)只有Push函數(shù)永遠(yuǎn)不會(huì)被訪問的元素項(xiàng)，才能由Pop釋放內(nèi)存；

3f)剛剛Pop出去的元素項(xiàng)不會(huì)被立即釋放，而是存在last指針里，只有再次Pop出其他元素項(xiàng)時(shí)，last指針當(dāng)前指向的元素項(xiàng)才會(huì)被釋放；

4）基于所述鎖無關(guān)消息隊(duì)列的Pop函數(shù)，分為以下情況：

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

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

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

在2線程的服務(wù)器架構(gòu)下，其中一個(gè)線程A為收發(fā)網(wǎng)絡(luò)消息數(shù)據(jù)包的通訊線程，另一個(gè)線程B為處理服務(wù)器內(nèi)部邏輯的主線程，這2個(gè)線程間通過所述鎖無關(guān)消息隊(duì)列和操作函數(shù)進(jìn)行通訊：

a)定義一個(gè)基于反轉(zhuǎn)單鏈表的鎖無關(guān)消息隊(duì)列：MsgQueue；

b)線程A從網(wǎng)絡(luò)收到消息數(shù)據(jù)包Packet，執(zhí)行MsgQueue.Push(Packet)，即將收到的消息數(shù)據(jù)包通過Push函數(shù)添加進(jìn)鎖無關(guān)消息隊(duì)列里；

c)線程B每次要處理服務(wù)器內(nèi)部邏輯之前，都嘗試通過pop函數(shù)從鎖無關(guān)消息隊(duì)列MsgQueue中讀取新的消息：Packet=MsgQueue.Pop()。