白正 張宏宇 王萍

1中國電子科技集團第二十八研究所 江蘇 210007

2海軍指揮所 北京 100841

3北航指揮所 山東 266000

0 引言

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

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

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

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

1 模型描述及性能指標

1.1 流水線模型

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

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

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

1.2 生產者/消費者隊列

在流水線模型中，報文隊列是流水段之間的共享數據結構。這是一個典型的生產者/消費者(producer/consumer)隊列結構。整個生產/消費模型信息流程關系如圖2所示。

圖2 報文分發(fā)軟件生產/消費信息關系

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

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

2 無鎖隊列算法

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

2.1 相關算法分析

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

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

2.2 無鎖隊列算法

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

圖3 無鎖隊列算法實現

3 模擬試驗

3.1 試驗環(huán)境

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

3.2 試驗結果與分析

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

圖4 報文分發(fā)軟件性能測試結果

4 結論

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

[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.