邢永昌
(中國(guó)船舶重工集團(tuán)公司第七二四研究所,南京 210003)
在試驗(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ù)面影響。
令牌漏桶法是在英特爾網(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)行的目的。
下面通過傳統(tǒng)算法和本文算法比較解釋本文設(shè)計(jì)的令牌漏桶法的實(shí)現(xiàn)。
按照傳統(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í)間片分配圖
根據(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ù)空間。
試驗(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)度
通過以上試驗(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.