邵延峰

一種風(fēng)鈴式定時(shí)器算法研究與實(shí)現(xiàn)

邵延峰

（中國(guó)電子科技集團(tuán)公司第五十四研究所，河北石家莊050081）

基于軟件實(shí)現(xiàn)的定時(shí)器可以減少對(duì)硬件和系統(tǒng)資源的占用。風(fēng)鈴式軟件定時(shí)器算法采用首尾指針追趕機(jī)制，解決了定時(shí)器的資源管理問(wèn)題；借鑒風(fēng)鈴?fù)庑?，利用?lái)自硬件或系統(tǒng)的一個(gè)定時(shí)觸發(fā)和雙向鏈表操作，通過(guò)對(duì)風(fēng)鈴串間隔計(jì)算及風(fēng)鈴串上定時(shí)器的掛接和刪除，實(shí)現(xiàn)了定時(shí)器的啟動(dòng)、停止和超時(shí)等操作。性能測(cè)試結(jié)果表明，該算法的定時(shí)精度和誤差符合預(yù)期，而且該算法對(duì)外接口簡(jiǎn)單易操作，還可為系統(tǒng)中的其他軟件提供定制化服務(wù)。

定時(shí)器；雙向鏈表；資源管理；定時(shí)觸發(fā)

引用格式：邵延峰.一種風(fēng)鈴式定時(shí)器算法研究與實(shí)現(xiàn)［J］.無(wú)線電工程，2016，46（5）：90-94.

0 引言

在通信協(xié)議軟件中，定時(shí)器的使用無(wú)處不在。使用定時(shí)器可以進(jìn)行通信協(xié)議的狀態(tài)保護(hù)、定時(shí)監(jiān)控或事件維持等。為了防止程序無(wú)限制地運(yùn)行，造成死循環(huán)，還會(huì)設(shè)置看門狗以便在軟件故障時(shí)復(fù)位系統(tǒng)，其本質(zhì)也是定時(shí)器。

定時(shí)器的實(shí)現(xiàn)可以采用硬件和軟件2種方式實(shí)現(xiàn)。硬件方式是利用硬件計(jì)時(shí)并以中斷方式通知，其缺點(diǎn)是定時(shí)到時(shí)可反饋的信息比較少，并且難以支持同時(shí)實(shí)現(xiàn)數(shù)十個(gè)甚至上百個(gè)定時(shí)器。采用軟件方式可直接利用操作系統(tǒng)定義的定時(shí)器函數(shù)，但其占用系統(tǒng)資源較多，不斷涉及到系統(tǒng)的任務(wù)切換，在多個(gè)定時(shí)器同時(shí)使用時(shí)尤為明顯，所帶信息也多以函數(shù)參數(shù)形式實(shí)現(xiàn)，可反饋信息量有限。而降低大量定時(shí)器在系統(tǒng)內(nèi)的插入、刪除和超時(shí)等操作開銷，是關(guān)系系統(tǒng)性能高低的重要技術(shù)［1］。

本文基于雙向鏈表和定時(shí)觸發(fā)的思路實(shí)現(xiàn)了一個(gè)風(fēng)鈴式的軟件定時(shí)器［2-3］，可作為嵌入式實(shí)時(shí)操作系統(tǒng)的一個(gè)單獨(dú)任務(wù)執(zhí)行，達(dá)到代碼精簡(jiǎn)，算法優(yōu)化，占用硬件或系統(tǒng)資源少，對(duì)系統(tǒng)處理能力影響小的效果［4］。

1 總體設(shè)計(jì)

1.1 定時(shí)器資源管理設(shè)計(jì)

軟件系統(tǒng)中每一個(gè)定時(shí)器都會(huì)占用一部分內(nèi)存資源，定時(shí)器越多，其占用的內(nèi)存就會(huì)越多，所以定時(shí)器也是一種資源，要進(jìn)行管理以解決資源的占用和釋放。需要時(shí)申請(qǐng)，不需要時(shí)或超時(shí)后要釋放，避免內(nèi)存不斷泄露。

描述一個(gè)定時(shí)器主要由標(biāo)識(shí)和屬性組成，定時(shí)器標(biāo)識(shí)和定時(shí)器屬性一一對(duì)應(yīng)。標(biāo)識(shí)具有唯一性，一個(gè)標(biāo)識(shí)代表一個(gè)定時(shí)器。通常以連續(xù)的從0開始的阿拉伯?dāng)?shù)字作為每個(gè)定時(shí)器的唯一標(biāo)識(shí)，根據(jù)最大的阿拉伯?dāng)?shù)字即可知道定時(shí)器的數(shù)量（其數(shù)值+1）。定時(shí)器屬性主要由雙向指針、使用者標(biāo)識(shí)和一些自定義信息組成，其中雙向指針、使用者標(biāo)識(shí)為必選信息。雙向指針用于在雙向鏈表中的插入和刪除，使用者標(biāo)識(shí)用于定時(shí)器超時(shí)后通知，自定義信息可由使用者根據(jù)自己情況任意定義。

申請(qǐng)者申請(qǐng)定時(shí)器成功后，會(huì)獲得一個(gè)定時(shí)器標(biāo)識(shí)，該標(biāo)識(shí)具有隨機(jī)性。釋放時(shí)基于使用者提供的定時(shí)器標(biāo)識(shí)進(jìn)行定時(shí)器回收。為此主要利用一個(gè)數(shù)組和2個(gè)指針實(shí)現(xiàn)了定時(shí)器資源的管理，如圖1所示。

圖1　定時(shí)器資源管理

數(shù)組的大小決定了定時(shí)器的數(shù)量。在初始狀態(tài)，初始化數(shù)組值、定時(shí)器標(biāo)識(shí)值和數(shù)組下標(biāo)值相等，首尾指針都指向數(shù)組的基地址。當(dāng)申請(qǐng)定時(shí)器時(shí)，首指針?biāo)付〞r(shí)器標(biāo)識(shí)被申請(qǐng)并且該指針前移一格。當(dāng)釋放定時(shí)器時(shí)，定時(shí)器標(biāo)識(shí)放入尾指針?biāo)肝恢貌⑶以撝羔樛瑯忧耙埔桓?。圖1中示例為0和1號(hào)定時(shí)器先后被申請(qǐng)，然后1號(hào)定時(shí)器被先釋放。

任何一個(gè)指針指向數(shù)組尾部，都要重新指向數(shù)組基地址。首指針到尾指針之間的定時(shí)器記錄還未被申請(qǐng)的定時(shí)器。當(dāng)首指針追上尾指針時(shí)，表示定時(shí)器已申請(qǐng)耗盡。

1.2 風(fēng)鈴式定時(shí)器架構(gòu)設(shè)計(jì)

現(xiàn)實(shí)中的風(fēng)鈴由頂層的圓環(huán)和多個(gè)等間隔的多個(gè)風(fēng)鈴串組成，每個(gè)風(fēng)鈴串由于鈴鐺數(shù)量不同而長(zhǎng)短不一。風(fēng)鈴式定時(shí)器借鑒這種理念，將圓環(huán)上的串間隔等同于最小定時(shí)精度，串越多則間隔越多，一圈可代表的時(shí)間就越長(zhǎng)。假設(shè)1個(gè)串間隔為100 ms，間隔為100，則一圈即可定時(shí)長(zhǎng)度為10 s。

同時(shí)將風(fēng)鈴串上的風(fēng)鈴比喻為定時(shí)器，每個(gè)串上的定時(shí)器可通過(guò)雙向鏈表操作實(shí)現(xiàn)掛接和卸除，如圖2所示。

圖2　風(fēng)鈴式定時(shí)器架構(gòu)

每過(guò)一個(gè)定時(shí)精度，當(dāng)前串下的定時(shí)器就意味著超時(shí)了，需要停止定時(shí)并將超時(shí)消息發(fā)給使用者，同時(shí)，使用者在啟動(dòng)定時(shí)器時(shí)留存的各種自定義信息也可原樣返回給使用者。

啟動(dòng)一個(gè)定時(shí)器，就是將定時(shí)器掛上相應(yīng)風(fēng)鈴串的過(guò)程。首先計(jì)算要啟動(dòng)的定時(shí)器需要多少個(gè)定時(shí)間隔，然后將定時(shí)器掛到當(dāng)前串后相應(yīng)間隔的風(fēng)鈴串的頭部上。

停止一個(gè)定時(shí)器，即將定時(shí)器從風(fēng)鈴串上取下來(lái)的過(guò)程?；谑褂谜咛峁┑亩〞r(shí)器標(biāo)識(shí)，可以索引到定時(shí)器的屬性。利用屬性中提供的雙向鏈表指針即可進(jìn)行鏈表的節(jié)點(diǎn)刪除操作，也就完成了定時(shí)器的停止工作。

1.3 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

定時(shí)器的數(shù)據(jù)結(jié)構(gòu)主要包括定時(shí)器數(shù)量、定時(shí)精度、定時(shí)長(zhǎng)度、定時(shí)器及定時(shí)器屬性的數(shù)據(jù)設(shè)計(jì)。

1.3.1 定時(shí)器數(shù)量及標(biāo)識(shí)聲明

該值定義了定時(shí)器最大數(shù)量，通過(guò)更改該數(shù)值可以增加定時(shí)器數(shù)量。

該數(shù)組用于存儲(chǔ)定時(shí)器標(biāo)識(shí)。

該數(shù)據(jù)結(jié)構(gòu)用于定時(shí)器資源的管理。其首尾指針主要指向TimerIdIdxArray。

1.3.2 定時(shí)間隔及風(fēng)鈴串頭指針聲明

#define TIMING_PERIMETER10

定義了定時(shí)圓周間隔數(shù)量，通過(guò)更改該數(shù)值可以增加一圈的最大定時(shí)長(zhǎng)度。如果定時(shí)精度為100 ms，則風(fēng)鈴轉(zhuǎn)一圈為100 ms*10=1 s。

該結(jié)構(gòu)數(shù)組定義了每個(gè)風(fēng)鈴串的頭指針。

1.3.3 定時(shí)器屬性聲明

上述數(shù)據(jù)結(jié)構(gòu)描述了定時(shí)器屬性。正如前述，雙向指針、使用者標(biāo)識(shí)為必選信息。雙向指針用于風(fēng)鈴串上定時(shí)器的插入和刪除，使用者標(biāo)識(shí)用于定時(shí)器超時(shí)后通知，自定義信息可由使用者根據(jù)自己情況任意定義。新增的圈數(shù)為可選項(xiàng)，通過(guò)該值可增加定時(shí)長(zhǎng)度。風(fēng)鈴轉(zhuǎn)一圈后，該值-1，只有該值為0時(shí)，才可認(rèn)為定時(shí)器超時(shí)。

2 定時(shí)器觸發(fā)源

風(fēng)鈴式定時(shí)器能夠運(yùn)行，定時(shí)觸發(fā)是必不可少的。定時(shí)觸發(fā)源主要采用系統(tǒng)時(shí)鐘之外的一個(gè)定時(shí)中斷，是一種輔助時(shí)鐘［5］。常用的觸發(fā)源主要有以下幾種：

①硬件中斷。由硬件提供1個(gè)定時(shí)中斷，每次中斷產(chǎn)生就調(diào)用一次風(fēng)鈴，風(fēng)鈴就轉(zhuǎn)動(dòng)一個(gè)間隔。其缺點(diǎn)就是在中斷處理函數(shù)中需要進(jìn)行過(guò)多的軟件處理。

②硬件中斷結(jié)合信號(hào)量。同樣利用1個(gè)硬件的定時(shí)中斷，每次中斷發(fā)送一個(gè)信號(hào)量給定時(shí)任務(wù)。定時(shí)任務(wù)收到信號(hào)量后調(diào)用一次風(fēng)鈴，風(fēng)鈴就轉(zhuǎn)動(dòng)一個(gè)間隔。該方法簡(jiǎn)化了中斷處理函數(shù)的工作量。

③利用操作系統(tǒng)的任務(wù)延遲功能。一般情況下，嵌入式實(shí)時(shí)操作系統(tǒng)會(huì)提供任務(wù)延遲功能，通過(guò)調(diào)用該函數(shù)，相應(yīng)的軟件任務(wù)就會(huì)在規(guī)定tick數(shù)量后（一般情況下60 ticks=1 s）被執(zhí)行一次。

利用該功能，規(guī)定時(shí)間內(nèi)風(fēng)鈴也會(huì)被調(diào)用一次，即轉(zhuǎn)動(dòng)一個(gè)間隔。其前提需要確保系統(tǒng)時(shí)鐘非常準(zhǔn)確，即60 ticks時(shí)長(zhǎng)確實(shí)是現(xiàn)實(shí)中的1 s。

④利用操作系統(tǒng)的定時(shí)函數(shù)加信號(hào)量。在操作系統(tǒng)中申請(qǐng)一個(gè)系統(tǒng)定時(shí)器，啟動(dòng)操作系統(tǒng)定時(shí)器時(shí)需要指明一個(gè)函數(shù)作為參數(shù)，用于超時(shí)后被調(diào)用。該函數(shù)再重新啟動(dòng)定時(shí)器并發(fā)送信號(hào)量。通過(guò)這種無(wú)限迭代的方式實(shí)現(xiàn)了定時(shí)觸發(fā)源的獲取。與硬件中斷結(jié)合信號(hào)量不同之處是利用系統(tǒng)定時(shí)器產(chǎn)生軟件中斷，其前提仍然需要確保系統(tǒng)時(shí)鐘非常準(zhǔn)確。

上述4種方式可根據(jù)實(shí)際工程情況進(jìn)行選擇。常見的是②和③。觸發(fā)源②定時(shí)比較精準(zhǔn)，觸發(fā)源③實(shí)現(xiàn)比較簡(jiǎn)單。

3 軟件實(shí)現(xiàn)

3.1 定時(shí)器的初始化

定時(shí)器初始化主要包括定時(shí)器標(biāo)識(shí)、定時(shí)器屬性和風(fēng)鈴圈的初始化。

3.1.1 定時(shí)器標(biāo)識(shí)初始化

3.1.2 定時(shí)器屬性初始化

3.1.3 風(fēng)鈴圈初始化

上述操作讓每個(gè)風(fēng)鈴串首尾指針首先指向自身。3.2 定時(shí)器的申請(qǐng)和釋放

定時(shí)器申請(qǐng)就是要從存儲(chǔ)定時(shí)器標(biāo)識(shí)的數(shù)組中申請(qǐng)定時(shí)器。其主要操作如下：

定時(shí)器釋放就是將定時(shí)器標(biāo)識(shí)重新放入存儲(chǔ)定時(shí)器標(biāo)識(shí)的數(shù)組中，以備再次申請(qǐng)。其主要操作如下：

3.3 定時(shí)器的啟動(dòng)和停止

定時(shí)器啟動(dòng)和停止就是將定時(shí)器掛接到相應(yīng)風(fēng)鈴串的過(guò)程。為此需要計(jì)算定時(shí)時(shí)長(zhǎng)在當(dāng)前位置之后的多少個(gè)間隔，然后基于雙向鏈表操作將定時(shí)器掛接到相應(yīng)的風(fēng)鈴串上。其主要操作如下：

/*iActiveList記錄了當(dāng)前位置，iTimingLen為定時(shí)時(shí)長(zhǎng)，iTimingDelay記錄了當(dāng)前位置之后的多少個(gè)定時(shí)間隔*/

iTimingDelay=（iActiveList+iTimingLen）%TIMING_ PERIMETER；

/*將申請(qǐng)的定時(shí)器對(duì)應(yīng)的定時(shí)器屬性掛接到對(duì)應(yīng)的風(fēng)鈴串上*/

pTmpTimer=pHeadTimer+iTimerId；

InsertElement（（Q_Struc_T*）pTmpTimer，&Timing ListHead［iTimingDelay］）；

定時(shí)器停止就是將定時(shí)器從相應(yīng)風(fēng)鈴串刪除的過(guò)程。其主要操作就是基于定時(shí)器屬性的雙向指針將其從風(fēng)鈴串中刪除。

/*基于定時(shí)器標(biāo)識(shí)定位指針*/

pFreeTimer=pHeadTimer+iFreeTimerId；

/*從定時(shí)鏈表中刪除*/

DequeueElement（（Q_Struc_T*）pFreeTimer）；

3.4 定時(shí)器超時(shí)

每經(jīng)過(guò)一個(gè)定時(shí)觸發(fā)時(shí)間，后移一個(gè)定時(shí)間隔后對(duì)應(yīng)的風(fēng)鈴串就變?yōu)楫?dāng)前風(fēng)鈴串，其上的所有定時(shí)器（風(fēng)鈴）就被認(rèn)為超時(shí)。將定時(shí)器從當(dāng)前風(fēng)鈴串上逐一刪除，并可利用定時(shí)器屬性上的信息通知使用者。

4 性能測(cè)試和結(jié)果分析

在操作系統(tǒng)VxWorks 5.5和處理器PPC 860的測(cè)試環(huán)境下［6］，采用硬件的一個(gè)100 ms定時(shí)中斷做為觸發(fā)源。從圖3中調(diào)用系統(tǒng)函數(shù)sysClkRateGet可以看到，系統(tǒng)時(shí)鐘默認(rèn)1 s=60 ticks。為避免頻繁打印，軟件程序每隔1 s（10*100 ms）打印一次并輸出當(dāng)前的系統(tǒng)tick值。相鄰輸出的tick的差值正好是60 ticks。說(shuō)明觸發(fā)源和系統(tǒng)時(shí)間進(jìn)行了精確校準(zhǔn)，即100 ms=6 ticks。

圖3　時(shí)間校準(zhǔn)

調(diào)用函數(shù)StartTiming分別在100 ms和1 s精度下（函數(shù)的第5個(gè)參數(shù)為1表示100 ms精度，為2表示1 s精度，第6個(gè)參數(shù)是時(shí)長(zhǎng)），進(jìn)行了10 s的定時(shí)測(cè)試，如圖4所示。由圖4可以看到，申請(qǐng)和啟動(dòng)定時(shí)在1 tick時(shí)間內(nèi)即可完成。2次定時(shí)分別用時(shí)602 ticks和603 ticks，與理論用時(shí)600 ticks相差＜6 ticks，即誤差＜100 ms，符合預(yù)期。

圖4　100 ms和1 s精度下10 s定時(shí)測(cè)試

同樣調(diào)用函數(shù)StartTiming分別在100 ms和1 s精度下進(jìn)行了1 min的定時(shí)測(cè)試，如圖5所示。

圖5　100 ms和1 s精度下1 min定時(shí)測(cè)試

由圖5可以看到，申請(qǐng)和啟動(dòng)定時(shí)仍在1 tick時(shí)間內(nèi)完成。2次定時(shí)分別用時(shí) 3 605 ticks和3 602 ticks，與理論用時(shí)3 600 ticks相差＜6 ticks，即誤差同樣＜100 ms，符合預(yù)期。

通過(guò)性能測(cè)試，驗(yàn)證了定時(shí)器的申請(qǐng)、啟動(dòng)效率都沒有給定時(shí)精準(zhǔn)度造成影響。而且由于定時(shí)的基本觸發(fā)源為100 ms，無(wú)論采用100 ms還是1 s定時(shí)精度，定時(shí)誤差都不會(huì)超過(guò)100 ms（即6 ticks）。實(shí)際應(yīng)用中，考慮到可容忍誤差，該定時(shí)器多用于1 s以上到分鐘級(jí)的定時(shí)。

5 結(jié)束語(yǔ)

定時(shí)器作為一種資源有可能被多個(gè)軟件重復(fù)性地申請(qǐng)和釋放，從避免雙向鏈表中斷的角度考慮，建議在申請(qǐng)和釋放定時(shí)器操作時(shí)增加信號(hào)量互斥操作。此外，使用者只需根據(jù)自己實(shí)際情況修改宏定義的數(shù)值就可調(diào)整定時(shí)器數(shù)量和定時(shí)長(zhǎng)度，接口簡(jiǎn)單且易操作。

風(fēng)鈴式定時(shí)器由于其占用硬件及系統(tǒng)資源少，對(duì)外接口簡(jiǎn)單、獨(dú)立性強(qiáng)和軟件量少等特點(diǎn)，已被筆者多次應(yīng)用到通信協(xié)議棧和監(jiān)控項(xiàng)目的開發(fā)中，取得了良好的工程實(shí)踐效果。此外，使用首尾指針前后追趕實(shí)現(xiàn)定時(shí)器管理的方法，不僅效率高，還可被抽象出來(lái)應(yīng)用于具有唯一標(biāo)識(shí)的各種資源管理中去。

［1］ 竇志斌.基于C語(yǔ)言的高性能LTE RLC層設(shè)計(jì)與實(shí)現(xiàn)［J］.無(wú)線電工程，2014，44（12）：11-13.

［2］ 潘金貴，顧鐵成，李成法，等.算法導(dǎo)論［M］.北京：機(jī)械工業(yè)出版社，2012.

［3］ 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)＜C語(yǔ)言版＞［M］.北京：清華大學(xué)出版社，2000.

［4］ 李 光.大型有限狀態(tài)機(jī)系統(tǒng)中的定時(shí)器設(shè)計(jì)［J］.無(wú)線電工程，2005，35（6）：54-56.

［5］ 山 清.VxWorks下基于輔助時(shí)鐘的通用定時(shí)器設(shè)計(jì)［J］.電子科技，2014，27（3）：126-128.

［6］ 孔祥營(yíng)，柏桂枝.嵌入式實(shí)時(shí)操作系統(tǒng)VxWorks及其開發(fā)環(huán)境［M］.北京：中國(guó)電力出版社，2002.

Research and Implementation of a Wind Bell Timer Algorithm

SHAO Yan-feng
（The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China）

A timer based on software can reduce hardware and OS resource occupation.The algorithm of Wind Bell timer uses a head pointer and a tail pointer to solve the problem of resource management.The appearance of a wind bell is used for reference.The algorithm uses a period trigger and double-linked list.It realizes the operation of timer by calculating the interval of wind bell bunch and adding the timer to the wind bell bunch or deleting it.The performance test result shows that its timing precision and timing error meet the expectation.Moreover，the algorithm’s interface for user is simple and easy for operating.It can also provide customized service for other modules.

timer；double-linked list；resource management；period trigger

TP319

A

1003-3106（2016）05-0090-05

10.3969/j.issn.1003-3106.2016.05.23

2016-01-21

邵延峰 男，（1973—），碩士，高級(jí)工程師。主要研究方向：通信網(wǎng)絡(luò)安全。