邢永昌

(中國船舶重工集團公司第七二四研究所，南京 210003)

0 引言

在試驗或軍事演習中，雷達產(chǎn)生的目標航跡數(shù)據(jù)具有很高的研究價值和訓練價值;如果能夠?qū)崟r采集當時的航跡，對雷達設計研究人員和指揮作戰(zhàn)人員與戰(zhàn)位操作人員具有很重要的價值。但是，由于雷達終端對實時性要求非常高，在終端上集成數(shù)據(jù)記錄功能會影響系統(tǒng)的實時性，從而影響整個作戰(zhàn)系統(tǒng)對目標處理的實時性。如果采用專門的數(shù)據(jù)采集回放設備，軟件硬件的代價昂貴，而且不能直觀地在原設備上面回放。

由于數(shù)據(jù)記錄任務占用的CPU 資源量很大，如果采用逐個航跡進行記錄，當航跡比較多時或目標分布不均勻時，會使實時系統(tǒng)失去實時性，甚至死機。

本文提出一種優(yōu)化的漏桶法，采用自適應記錄數(shù)據(jù)技術(shù)，可以大大減少數(shù)據(jù)記錄占用的CPU 資源，并且可以自適應選擇CPU 空閑時間執(zhí)行，從而有效避免數(shù)據(jù)記錄對系統(tǒng)的負面影響。

1 基本原理

令牌漏桶法是在英特爾網(wǎng)路由器上應用的一種網(wǎng)絡管制算法，其工作原理如下:

(1）令牌以一定的速率放入桶中;

(2）每個令牌允許源發(fā)送一定數(shù)量的比特;

(3）發(fā)送一個包，流量調(diào)節(jié)器就從桶中刪除與包大小對應的令牌數(shù);

(4）如果沒有足夠的令牌發(fā)送包，這個包就會等待直到有足夠的令牌或者包丟棄，也可能被標記更低的DSCP(在策略者的情況下）;

(5）桶有特定的容量，如果桶已經(jīng)滿了，新加入的令牌就會被丟棄。因此，在任何時候，源發(fā)送到網(wǎng)絡上的最大突發(fā)數(shù)據(jù)量與桶的大小成正比。令牌桶允許突發(fā)，但是不能超出限制。

本文設計的令牌漏桶原理如下:

(1）通過WDB 繪出當前實時系統(tǒng)資源占用圖表，統(tǒng)計系統(tǒng)資源的占用率、空閑時間段情況等數(shù)據(jù);

(2）根據(jù)統(tǒng)計數(shù)據(jù)設置令牌發(fā)放頻率，構(gòu)建循環(huán)隊列數(shù)據(jù)池的結(jié)構(gòu)和設計令牌漏桶;

(3）根據(jù)設計的循環(huán)隊列數(shù)據(jù)池結(jié)構(gòu)，打包緩存待處理數(shù)據(jù)，如果回放則設計回放循環(huán)隊列數(shù)據(jù)池中數(shù)據(jù);

(4）根據(jù)系統(tǒng)運行情況和循環(huán)隊列數(shù)據(jù)池中待處理數(shù)據(jù)量適時產(chǎn)生令牌;

(5）接收到令牌的任務，根據(jù)當前CPU的空閑情況自適應選擇執(zhí)行時機，根據(jù)當前循環(huán)隊列數(shù)據(jù)池中待處理數(shù)據(jù)量自適應選擇處理數(shù)據(jù)量。

令牌漏桶法的網(wǎng)絡傳輸工作流程圖見圖1?；诹钆坡┩胺ǖ淖赃m應數(shù)據(jù)記錄/回放技術(shù)工作流程圖見圖2。

圖1 令牌漏桶法的網(wǎng)絡傳輸工作流程圖

圖2 基于令牌漏桶法的自適應數(shù)據(jù)記錄/回放技術(shù)工作流程圖

由于數(shù)據(jù)記錄過程中主要是讀寫外部存儲器影響系統(tǒng)的實時性，數(shù)據(jù)記錄過程中打開文件和關(guān)閉文件消耗的系統(tǒng)資源比重比較大，令牌漏桶法通過設置合適的漏桶容量、合適的數(shù)據(jù)緩沖區(qū)大小和適當?shù)牧钆飘a(chǎn)生頻率，使打開和關(guān)閉文件的次數(shù)大大地減少，從而有效地減少數(shù)據(jù)實時記錄對系統(tǒng)資源的消耗。

本文令牌的發(fā)放是通過創(chuàng)建較低優(yōu)先級任務的方法實現(xiàn)的。該方法不但可以讓數(shù)據(jù)記錄任務放在當系統(tǒng)資源空閑狀態(tài)時才占用，而且可以實現(xiàn)當正在進行數(shù)據(jù)記錄時如果有較高優(yōu)先級的系統(tǒng)任務到來時可以被較高優(yōu)先級任務搶占回系統(tǒng)資源，從而達到只在系統(tǒng)資源空閑時才進行數(shù)據(jù)記錄而不影響系統(tǒng)的實時運行的目的。

2 算法實現(xiàn)

下面通過傳統(tǒng)算法和本文算法比較解釋本文設計的令牌漏桶法的實現(xiàn)。

2.1 傳統(tǒng)數(shù)據(jù)記錄算法分析

按照傳統(tǒng)的數(shù)據(jù)記錄方法，當需要記錄數(shù)據(jù)單元產(chǎn)生后，即按照設計的數(shù)據(jù)格式處理數(shù)據(jù)并打開對應文件記錄數(shù)據(jù)，然后關(guān)閉文件。圖3～5分別是系統(tǒng)正常運行時傳統(tǒng)方式數(shù)據(jù)記錄時和采用令牌漏桶法數(shù)據(jù)記錄時系統(tǒng)資源占用情況。由于數(shù)據(jù)記錄與數(shù)據(jù)處理串行處理，當數(shù)據(jù)產(chǎn)生頻率較高時，在t1、t2、t3時刻就容易產(chǎn)生系統(tǒng)癱瘓甚至死機。

圖3 沒有記錄任務時CPU時間片分配圖

圖4 采用傳統(tǒng)方式記錄任務時CPU時間片分配圖

圖5 采用令牌漏桶時CPU時間片分配圖

2.2 本文記錄算法分析

根據(jù)系統(tǒng)運行情況和當前循環(huán)隊列數(shù)據(jù)池中的待處理數(shù)據(jù)量確定令牌發(fā)放時機。

數(shù)據(jù)記錄任務的優(yōu)先級要設計得比較低，這樣不但不影響系統(tǒng)的正常運行，而且可以在系統(tǒng)空閑時間內(nèi)完成數(shù)據(jù)記錄。

2.2.1 構(gòu)建循環(huán)隊列數(shù)據(jù)池

建立合適的數(shù)據(jù)緩沖區(qū)對該算法的實現(xiàn)至關(guān)重要，它決定著本算法的成功與失敗。數(shù)據(jù)池的容量應該大于漏桶中最多令牌創(chuàng)對應的數(shù)據(jù)量。數(shù)據(jù)池設計成循環(huán)隊列，以實現(xiàn)在最小的緩沖空間中實現(xiàn)數(shù)據(jù)的緩沖，等待和處理可以同時且互不干擾地進行。通過對線程的并行處理提供實現(xiàn)的基礎(chǔ)框架和對于軟件模塊間松耦處理，該設計提高了軟件的模塊化、可重用性和穩(wěn)定性。

下面是一個循環(huán)隊列數(shù)據(jù)池的定義:

typedef struct DataSaveBuffer

{

DataStruct SaveDataBuffer［MAXSAVEDATANUM］;//循環(huán)隊列，數(shù)據(jù)緩存。

int nWritePtr;//寫指針

int nReadPtr;//讀指針

int nTrackCount;//待記錄航跡個數(shù)

int nTaskCount;//待記錄任務個數(shù)

};

2.2.2 適時產(chǎn)生令牌

在本文中產(chǎn)生令牌(創(chuàng)建數(shù)據(jù)記錄或回放任務）緩存入令牌隊列。

如果按照固定時間間隔產(chǎn)生令牌，在需要記錄數(shù)據(jù)分布比較均勻或在數(shù)據(jù)產(chǎn)生頻率非常低的情況下，基本可以達到本文要求的效果。但是，如果需要記錄數(shù)據(jù)源產(chǎn)生頻率不均勻或數(shù)據(jù)量比較大時，數(shù)據(jù)記錄回放功能將會影響系統(tǒng)的實時性。

在這里提出定時產(chǎn)生與循環(huán)隊列數(shù)據(jù)池中待處理數(shù)據(jù)量相結(jié)合的思想，即不僅要滿足一定的時間間隔而且要滿足緩存夠一定的數(shù)據(jù)容量才會釋放數(shù)據(jù)記錄令牌。當取消該類數(shù)據(jù)記錄或收到要關(guān)機命令時，只要緩存中還有待記錄數(shù)據(jù)則釋放令牌創(chuàng)建任務進行處理。

2.2.3 處理數(shù)據(jù)記錄任務釋放漏桶容量

每個數(shù)據(jù)記錄任務對應漏桶中的一個令牌，每處理完一個任務漏桶中令牌即減少一個，同時漏桶中可以多增加一個令牌。

在打開記錄文件過程中需要鎖定其他任務，以免在打開文件的過程中由于任務優(yōu)先級被搶占而破壞文件。記錄過程中對不同的文件分別打開、記錄、關(guān)閉，而不可打開多個再記錄。完成一個記錄任務，釋放循環(huán)隊列數(shù)據(jù)池一個存儲數(shù)據(jù)空間。

3 試驗結(jié)果與分析

試驗環(huán)境要求:Intel Core Duo 1.66Hz中央處理器，2GB 內(nèi)存，VxWorks5.5 操作系統(tǒng)，周期為2s，66 批目標，實時記錄航跡信息，航跡信息需要記錄成3個文件，分別用于回放、數(shù)據(jù)分析和記錄航跡個數(shù)。令牌產(chǎn)生時間間隔為2 s。

圖6、7 是使用傳統(tǒng)記錄方法和本文的令牌漏桶法處理記錄任務占用時間對照圖。

圖6 采用傳統(tǒng)方法記錄航跡信息時記錄每條航跡占用的時間長度

對比圖6、7 可以發(fā)現(xiàn)，當沒有較高優(yōu)先級任務搶占記錄任務時本文的令牌漏桶法記錄每條航跡大約需要1～2 ms，傳統(tǒng)算法需要30～50ms;當有較高優(yōu)先級任務搶占記錄任務時本文的令牌漏桶法記錄每條航跡大約需要時間3～9 ms，傳統(tǒng)方法記錄每條航跡大約需要230～260 ms。

從現(xiàn)象上看，采用傳統(tǒng)算法，當航跡個數(shù)超過12批時即會出現(xiàn)數(shù)據(jù)處理滯后現(xiàn)象，運行幾分鐘后行軟件即處于嚴重癱瘓狀態(tài)，操作命令不能執(zhí)行，只有光標還可以移動。如果采用本文的令牌漏桶法，當航跡數(shù)達到90 批以上時，持續(xù)運行4 h，通過系統(tǒng)測試沒有出現(xiàn)延時，同時也沒有其他異?，F(xiàn)象。

圖7 采用本文的令牌漏桶法記錄航跡信息時記錄每條航跡占用的時間長度

4 結(jié)束語

通過以上試驗驗證，在不影響系統(tǒng)的正常運行情況下，本文算法不僅能實現(xiàn)數(shù)據(jù)的實時記錄，而且可以顯著降低數(shù)據(jù)實時記錄占用的系統(tǒng)資源，解決了數(shù)據(jù)的實時記錄引起系統(tǒng)癱瘓的問題。該方法應用于通信數(shù)據(jù)的實時接收與處理功能上同樣可以得到很好的效果。

［1］謝希仁.計算機網(wǎng)絡(第5 版）［M］.北京:電子工業(yè)出版社，2008.1.

［2］嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C 語言版）［M］.北京:清華大學出版社，1997.4.

［3］Bruno R Preiss.Data Structures and Algorithms with Object-Oriented Design Pattern in C++.Press John Wiley ＆ Sons，Inc.1999.8.

［4］孔祥營，柏桂枝.嵌入式實時操作系統(tǒng)VxWorks及其開發(fā)環(huán)境Tornado［M］.北京:中國電力出版社，2002.1.