邵延峰

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

邵延峰

（中國電子科技集團公司第五十四研究所，河北石家莊050081）

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

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

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

0 引言

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

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

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

1 總體設(shè)計

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

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

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

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

圖1　定時器資源管理

數(shù)組的大小決定了定時器的數(shù)量。在初始狀態(tài)，初始化數(shù)組值、定時器標識值和數(shù)組下標值相等，首尾指針都指向數(shù)組的基地址。當申請定時器時，首指針所指定時器標識被申請并且該指針前移一格。當釋放定時器時，定時器標識放入尾指針所指位置并且該指針同樣前移一格。圖1中示例為0和1號定時器先后被申請，然后1號定時器被先釋放。

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

1.2 風鈴式定時器架構(gòu)設(shè)計

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

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

圖2　風鈴式定時器架構(gòu)

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

啟動一個定時器，就是將定時器掛上相應(yīng)風鈴串的過程。首先計算要啟動的定時器需要多少個定時間隔，然后將定時器掛到當前串后相應(yīng)間隔的風鈴串的頭部上。

停止一個定時器，即將定時器從風鈴串上取下來的過程?；谑褂谜咛峁┑亩〞r器標識，可以索引到定時器的屬性。利用屬性中提供的雙向鏈表指針即可進行鏈表的節(jié)點刪除操作，也就完成了定時器的停止工作。

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

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

1.3.1 定時器數(shù)量及標識聲明

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

該數(shù)組用于存儲定時器標識。

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

1.3.2 定時間隔及風鈴串頭指針聲明

#define TIMING_PERIMETER10

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

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

1.3.3 定時器屬性聲明

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

2 定時器觸發(fā)源

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

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

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

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

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

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

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

3 軟件實現(xiàn)

3.1 定時器的初始化

定時器初始化主要包括定時器標識、定時器屬性和風鈴圈的初始化。

3.1.1 定時器標識初始化

3.1.2 定時器屬性初始化

3.1.3 風鈴圈初始化

上述操作讓每個風鈴串首尾指針首先指向自身。3.2 定時器的申請和釋放

定時器申請就是要從存儲定時器標識的數(shù)組中申請定時器。其主要操作如下：

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

3.3 定時器的啟動和停止

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

/*iActiveList記錄了當前位置，iTimingLen為定時時長，iTimingDelay記錄了當前位置之后的多少個定時間隔*/

iTimingDelay=（iActiveList+iTimingLen）%TIMING_ PERIMETER；

/*將申請的定時器對應(yīng)的定時器屬性掛接到對應(yīng)的風鈴串上*/

pTmpTimer=pHeadTimer+iTimerId；

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

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

/*基于定時器標識定位指針*/

pFreeTimer=pHeadTimer+iFreeTimerId；

/*從定時鏈表中刪除*/

DequeueElement（（Q_Struc_T*）pFreeTimer）；

3.4 定時器超時

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

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

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

圖3　時間校準

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

圖4　100 ms和1 s精度下10 s定時測試

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

圖5　100 ms和1 s精度下1 min定時測試

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

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

5 結(jié)束語

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

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

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

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

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

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

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

［6］ 孔祥營，柏桂枝.嵌入式實時操作系統(tǒng)VxWorks及其開發(fā)環(huán)境［M］.北京：中國電力出版社，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—），碩士，高級工程師。主要研究方向：通信網(wǎng)絡(luò)安全。