基于令牌漏桶法的數(shù)據(jù)記錄技術(shù)*

邢永昌

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

0 引言

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

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

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

1 基本原理

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

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

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

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

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

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

本文設(shè)計(jì)的令牌漏桶原理如下:

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

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

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

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

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

令牌漏桶法的網(wǎng)絡(luò)傳輸工作流程圖見圖1。基于令牌漏桶法的自適應(yīng)數(shù)據(jù)記錄/回放技術(shù)工作流程圖見圖2。

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

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

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

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

2 算法實(shí)現(xiàn)

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

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

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

圖3 沒有記錄任務(wù)時(shí)CPU時(shí)間片分配圖

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

圖5 采用令牌漏桶時(shí)CPU時(shí)間片分配圖

2.2 本文記錄算法分析

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

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

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

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

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

typedef struct DataSaveBuffer

{

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

int nWritePtr;//寫指針

int nReadPtr;//讀指針

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

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

};

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

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

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

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

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

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

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

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

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

圖6、7 是使用傳統(tǒng)記錄方法和本文的令牌漏桶法處理記錄任務(wù)占用時(shí)間對(duì)照?qǐng)D。

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

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

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

圖7 采用本文的令牌漏桶法記錄航跡信息時(shí)記錄每條航跡占用的時(shí)間長(zhǎng)度

4 結(jié)束語

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

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

［2］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C 語言版）［M］.北京:清華大學(xué)出版社，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］孔祥營(yíng)，柏桂枝.嵌入式實(shí)時(shí)操作系統(tǒng)VxWorks及其開發(fā)環(huán)境Tornado［M］.北京:中國(guó)電力出版社，2002.1.