基于無(wú)鎖隊(duì)列算法的報(bào)文分發(fā)流水線模型

白正 張宏宇 王萍

1中國(guó)電子科技集團(tuán)第二十八研究所 江蘇 210007

2海軍指揮所 北京 100841

3北航指揮所 山東 266000

0 引言

隨著網(wǎng)絡(luò)速度的不斷提升和計(jì)算機(jī)處理性能的不斷提高，對(duì)計(jì)算機(jī)網(wǎng)絡(luò)報(bào)文的處理能力也迅速增加，傳統(tǒng)的基于順序報(bào)文處理機(jī)制已經(jīng)不能滿足應(yīng)用對(duì)網(wǎng)絡(luò)的需求。為了適應(yīng)這樣的變化趨勢(shì)，網(wǎng)絡(luò)報(bào)文接收分發(fā)在設(shè)計(jì)和實(shí)現(xiàn)上必須具備更快的處理速度和分發(fā)的性能。

基于多核處理器和多處理器系統(tǒng)的并行處理架構(gòu)成為報(bào)文分發(fā)處理的必然選擇。在各種并行處理模型中，流水線模型在處理網(wǎng)絡(luò)報(bào)文分發(fā)中是一種高效的模型。

在流水線處理模型中，各個(gè)處理階段間需要通過(guò)設(shè)置適當(dāng)?shù)木彌_數(shù)據(jù)區(qū)，這些處理階段之間的緩沖就構(gòu)成了流水線。緩沖數(shù)據(jù)區(qū)的讀寫效率在很大程度上影響整個(gè)流水線系統(tǒng)的吞吐率。

本文采用了生產(chǎn)者/消費(fèi)者隊(duì)列模型來(lái)描述流水線各處理階段之間的緩沖數(shù)據(jù)區(qū)讀寫問(wèn)題，采用無(wú)鎖隊(duì)列操作算法提高系統(tǒng)的效率，滿足數(shù)據(jù)線性化要求和非阻塞屬性。

1 模型描述及性能指標(biāo)

1.1 流水線模型

報(bào)文分發(fā)軟件對(duì)于每個(gè)數(shù)據(jù)報(bào)文的處理過(guò)程可以分為網(wǎng)絡(luò)報(bào)文接收、套接字異步消息、數(shù)據(jù)報(bào)文分發(fā)和業(yè)務(wù)報(bào)文通告四個(gè)階段。網(wǎng)絡(luò)報(bào)文的接收由Socket套接字完成；套接字異步消息通過(guò)設(shè)置Socket套接字異步事件或者異步IO信號(hào)；數(shù)據(jù)報(bào)文的分發(fā)主要是根據(jù)應(yīng)用層協(xié)議區(qū)分各類報(bào)文的類型分發(fā)至各業(yè)務(wù)程序；業(yè)務(wù)報(bào)文通告是通知業(yè)務(wù)程序數(shù)據(jù)已經(jīng)準(zhǔn)備完畢，可以獲取數(shù)據(jù)進(jìn)行相應(yīng)處理。因此可以將此流水線分成四級(jí)流水線模型(如圖1所示)。

圖1 報(bào)文分發(fā)軟件流水線模型

根據(jù)流水線模型相對(duì)順序模型的加速比公式 Speedup=kn/(k+n-1)(其中n為連續(xù)處理n條報(bào)文，k為流水線級(jí)數(shù))可知，加速比主要由流水線級(jí)數(shù)決定。

1.2 生產(chǎn)者/消費(fèi)者隊(duì)列

在流水線模型中，報(bào)文隊(duì)列是流水段之間的共享數(shù)據(jù)結(jié)構(gòu)。這是一個(gè)典型的生產(chǎn)者/消費(fèi)者(producer/consumer)隊(duì)列結(jié)構(gòu)。整個(gè)生產(chǎn)/消費(fèi)模型信息流程關(guān)系如圖2所示。

圖2 報(bào)文分發(fā)軟件生產(chǎn)/消費(fèi)信息關(guān)系

定義?代表整個(gè)生產(chǎn)者/消費(fèi)者系統(tǒng)，?由5個(gè)元素構(gòu)成：?：{P,C,Q,consume,produce}，其中：P為生產(chǎn)者集合，|P|為生產(chǎn)者個(gè)數(shù)，P={pi|i∈[1,|P|]}，集合中的每個(gè)元素 pi代表一個(gè)獨(dú)立運(yùn)行的生產(chǎn)者線程，整個(gè)系統(tǒng)中要求至少包含一個(gè)生產(chǎn)者線程，即：|P|≥1；C為消費(fèi)者集合，|C|為消費(fèi)者個(gè)數(shù)，C={ci|i∈[1,|C|]}，集合中的每個(gè)元素 ci代表一個(gè)獨(dú)立運(yùn)行的消費(fèi)者線程，整個(gè)系統(tǒng)中要求至少包含一個(gè)消費(fèi)者線程，即：|C|≥1；Q 為共享數(shù)據(jù)隊(duì)列集合，|Q|為隊(duì)列個(gè)數(shù)，Q={qi|i∈[1,|Q|]}，集合中每個(gè)元素qi表示為一個(gè)獨(dú)立的隊(duì)列對(duì)象；produce為生產(chǎn)操作，生產(chǎn)者線程pi向數(shù)據(jù)隊(duì)列對(duì)象qj中放置新的數(shù)據(jù)元素 x 的操作記為：＜qj.produce(x),pi＞；consume為消費(fèi)操作，消費(fèi)者線程ci從數(shù)據(jù)隊(duì)列對(duì)象qj中獲取數(shù)據(jù)元素y所執(zhí)行的操作記為：＜qj.consume(y),ci＞。

對(duì)于給定的流水線系統(tǒng)，上述生產(chǎn)者/消費(fèi)者模型中的P、C、Q 是確定的，需求解的問(wèn)題為：通過(guò)優(yōu)化設(shè)計(jì) produce和consume兩個(gè)操作算法使其滿足在并行執(zhí)行環(huán)境中的評(píng)價(jià)指標(biāo)，即正確性(correctness property)、活躍性(liveness property)、效率性(productiveness property)。

2 無(wú)鎖隊(duì)列算法

根據(jù)圖2所示的報(bào)文分發(fā)軟件流水線信息關(guān)系模型，整個(gè)流水線存在兩種共享數(shù)據(jù)區(qū)：一種是Socket緩沖區(qū)，是操作系統(tǒng)創(chuàng)建和維護(hù)的緩沖區(qū)，是Socket套接字自身支持的；另一種是報(bào)文分發(fā)程序與業(yè)務(wù)處理軟件之間的緩沖區(qū)，是本文介紹設(shè)計(jì)的重點(diǎn)。該緩沖區(qū)僅存在一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者，因此可以將問(wèn)題簡(jiǎn)化為針對(duì)單生產(chǎn)者/單消費(fèi)者(SP/SC)隊(duì)列的操作算法設(shè)計(jì)。

2.1 相關(guān)算法分析

針對(duì)SP/SC隊(duì)列的并發(fā)操作已經(jīng)有很多經(jīng)典算法，最直接的算法基于互斥鎖的算法，生產(chǎn)者和消費(fèi)者在操作隊(duì)列之前獲得鎖，在操作完成之后釋放鎖，但是這種鎖操作的效率不高，而且算法是阻塞的，操作不當(dāng)易產(chǎn)生死鎖等問(wèn)題。由于SP/SC系統(tǒng)的特殊性(只有一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者)，只需要對(duì)算法實(shí)現(xiàn)進(jìn)行簡(jiǎn)單改進(jìn)即可實(shí)現(xiàn)非阻塞操作算法(記為L(zhǎng)amport算法)。Giacomoni 等人在PPoPP08會(huì)議上發(fā)表了針對(duì)Lamport算法的優(yōu)化算法——Fast Forward算法，通過(guò)對(duì)Lamport算法的改進(jìn)，消除了生產(chǎn)操作中對(duì)隊(duì)列HEAD指針的讀寫和消費(fèi)操作中對(duì)隊(duì)列TAIL 指針的讀寫，使得算法在多處理器環(huán)境中執(zhí)行時(shí)不會(huì)產(chǎn)生處理器緩存頻繁同步的問(wèn)題，執(zhí)行效率有了進(jìn)一步的提升。

Lamport算法和FastForward算法是關(guān)于SP/SC隊(duì)列操作的非阻塞的經(jīng)典算法，可以在并行系統(tǒng)中高效執(zhí)行。但是，都是采用靜態(tài)循環(huán)數(shù)組結(jié)構(gòu)來(lái)組織隊(duì)列元素，對(duì)突發(fā)流量的時(shí)間段很容易產(chǎn)生丟包，因此動(dòng)態(tài)鏈表的結(jié)構(gòu)形式更適合報(bào)文分發(fā)流水線模型。

2.2 無(wú)鎖隊(duì)列算法

針對(duì)SP/SC隊(duì)列的特點(diǎn)，借鑒Lamport和Fast Forward兩個(gè)算法的設(shè)計(jì)思想，提出面向動(dòng)態(tài)鏈表結(jié)構(gòu)的無(wú)鎖隊(duì)列算法，算法實(shí)現(xiàn)見(jiàn)圖3。無(wú)鎖隊(duì)列算法中，借鑒了Fast Forward算法的思想，在報(bào)文隊(duì)列中始終保留一個(gè)數(shù)據(jù)元素，在produce操作中只讀寫隊(duì)列的TAIL指針，在consume操作中只讀寫隊(duì)列的HEAD指針，從而消除了由于生產(chǎn)者線程和消費(fèi)者線程訪問(wèn)共享數(shù)據(jù)變量引起的頻繁緩存同步開(kāi)銷，提升算法執(zhí)行效率。

圖3 無(wú)鎖隊(duì)列算法實(shí)現(xiàn)

3 模擬試驗(yàn)

3.1 試驗(yàn)環(huán)境

通過(guò)模擬試驗(yàn)獲得算法的性能衡量指標(biāo)，試驗(yàn)中選取SPARC64VII2.4GHz處理器作為硬件平臺(tái)，采用Solaris10構(gòu)建軟件環(huán)境。

3.2 試驗(yàn)結(jié)果與分析

在測(cè)試環(huán)境下對(duì)Lock-based、Fast Forward和本文介紹的無(wú)鎖隊(duì)列算法進(jìn)行性能測(cè)試，測(cè)試中生產(chǎn)者和消費(fèi)者各自連續(xù)執(zhí)行100萬(wàn)次生產(chǎn)操作和消費(fèi)操作，然后計(jì)算平均操作時(shí)間。測(cè)試結(jié)果如圖4。

圖4 報(bào)文分發(fā)軟件性能測(cè)試結(jié)果

4 結(jié)論

本文針對(duì)報(bào)文分發(fā)軟件的流水線處理模型，提出了一種無(wú)鎖隊(duì)列算法，該算法采用了動(dòng)態(tài)鏈表結(jié)構(gòu)，消除了存儲(chǔ)空間限制和內(nèi)存浪費(fèi)問(wèn)題；同時(shí)該鏈表通過(guò)無(wú)鎖算法實(shí)現(xiàn)更為簡(jiǎn)潔，效率更高，通過(guò)證明試驗(yàn)，在多核多處理器的環(huán)境下具有較好的性能指標(biāo)。

[1] Guo Danhua,Liao Guangdeng,Bhuyan L N,et al.A Scalable Multithreaded L7-filter Design for Multi-Core Servers [C] ∥ANCS’08 , San Jose.California,USA ：ACM.2008.

[2]Schuff D L,Choe Y R,Pai V S.Conservative vs.Optimistic Parallelization of Stateful Network Intrusion Detec2tion[C]∥PPoPP’07,San Jose.California,USA：IEEE .2007.

[3]Wu Qiang , Wolf Tilman.On Runtime Management in Multi-Core Packet Processing Systems [C] ∥ANCS’08 ,San Jose.California , USA ： ACM .2008.

[4]LamportL.Specifying Concurrent Program Modules[J]ACM Transactions on Programming Languages and Systems.1983.

[5]Giacomoni J,Moseley T,Vachharajani M.Fast Forwardfor Efficient Pipeline Parallelism： A Cache2Optimized Concurrent Lock2Free Queue[C]∥PPoPP’08,Salt LakeCity,USA：ACM.2008.