基于令牌漏桶法的數據記錄技術*

邢永昌

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

0 引言

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

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

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

1 基本原理

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

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

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

(3）發送一個包，流量調節器就從桶中刪除與包大小對應的令牌數;

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

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

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

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

(2）根據統計數據設置令牌發放頻率，構建循環隊列數據池的結構和設計令牌漏桶;

(3）根據設計的循環隊列數據池結構，打包緩存待處理數據，如果回放則設計回放循環隊列數據池中數據;

(4）根據系統運行情況和循環隊列數據池中待處理數據量適時產生令牌;

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

令牌漏桶法的網絡傳輸工作流程圖見圖1。基于令牌漏桶法的自適應數據記錄/回放技術工作流程圖見圖2。

圖1 令牌漏桶法的網絡傳輸工作流程圖

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

由于數據記錄過程中主要是讀寫外部存儲器影響系統的實時性，數據記錄過程中打開文件和關閉文件消耗的系統資源比重比較大，令牌漏桶法通過設置合適的漏桶容量、合適的數據緩沖區大小和適當的令牌產生頻率，使打開和關閉文件的次數大大地減少，從而有效地減少數據實時記錄對系統資源的消耗。

本文令牌的發放是通過創建較低優先級任務的方法實現的。該方法不但可以讓數據記錄任務放在當系統資源空閑狀態時才占用，而且可以實現當正在進行數據記錄時如果有較高優先級的系統任務到來時可以被較高優先級任務搶占回系統資源，從而達到只在系統資源空閑時才進行數據記錄而不影響系統的實時運行的目的。

2 算法實現

下面通過傳統算法和本文算法比較解釋本文設計的令牌漏桶法的實現。

2.1 傳統數據記錄算法分析

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

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

圖4 采用傳統方式記錄任務時CPU時間片分配圖

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

2.2 本文記錄算法分析

根據系統運行情況和當前循環隊列數據池中的待處理數據量確定令牌發放時機。

數據記錄任務的優先級要設計得比較低，這樣不但不影響系統的正常運行，而且可以在系統空閑時間內完成數據記錄。

2.2.1 構建循環隊列數據池

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

下面是一個循環隊列數據池的定義:

typedef struct DataSaveBuffer

{

DataStruct SaveDataBuffer［MAXSAVEDATANUM］;//循環隊列，數據緩存。

int nWritePtr;//寫指針

int nReadPtr;//讀指針

int nTrackCount;//待記錄航跡個數

int nTaskCount;//待記錄任務個數

};

2.2.2 適時產生令牌

在本文中產生令牌(創建數據記錄或回放任務）緩存入令牌隊列。

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

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

2.2.3 處理數據記錄任務釋放漏桶容量

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

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

3 試驗結果與分析

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

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

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

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

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

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

4 結束語

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

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

［2］嚴蔚敏，吳偉民.數據結構(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］孔祥營，柏桂枝.嵌入式實時操作系統VxWorks及其開發環境Tornado［M］.北京:中國電力出版社，2002.1.