一種風鈴式定時器算法研究與實現

邵延峰

一種風鈴式定時器算法研究與實現

邵延峰

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

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

定時器；雙向鏈表；資源管理；定時觸發

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

0 引言

在通信協議軟件中，定時器的使用無處不在。使用定時器可以進行通信協議的狀態保護、定時監控或事件維持等。為了防止程序無限制地運行，造成死循環，還會設置看門狗以便在軟件故障時復位系統，其本質也是定時器。

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

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

1 總體設計

1.1 定時器資源管理設計

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

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

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

圖1　定時器資源管理

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

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

1.2 風鈴式定時器架構設計

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

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

圖2　風鈴式定時器架構

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

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

停止一個定時器，即將定時器從風鈴串上取下來的過程。基于使用者提供的定時器標識，可以索引到定時器的屬性。利用屬性中提供的雙向鏈表指針即可進行鏈表的節點刪除操作，也就完成了定時器的停止工作。

1.3 數據結構設計

定時器的數據結構主要包括定時器數量、定時精度、定時長度、定時器及定時器屬性的數據設計。

1.3.1 定時器數量及標識聲明

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

該數組用于存儲定時器標識。

該數據結構用于定時器資源的管理。其首尾指針主要指向TimerIdIdxArray。

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

#define TIMING_PERIMETER10

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

該結構數組定義了每個風鈴串的頭指針。

1.3.3 定時器屬性聲明

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

2 定時器觸發源

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

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

②硬件中斷結合信號量。同樣利用1個硬件的定時中斷，每次中斷發送一個信號量給定時任務。定時任務收到信號量后調用一次風鈴，風鈴就轉動一個間隔。該方法簡化了中斷處理函數的工作量。

③利用操作系統的任務延遲功能。一般情況下，嵌入式實時操作系統會提供任務延遲功能，通過調用該函數，相應的軟件任務就會在規定tick數量后（一般情況下60 ticks=1 s）被執行一次。

利用該功能，規定時間內風鈴也會被調用一次，即轉動一個間隔。其前提需要確保系統時鐘非常準確，即60 ticks時長確實是現實中的1 s。

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

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

3 軟件實現

3.1 定時器的初始化

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

3.1.1 定時器標識初始化

3.1.2 定時器屬性初始化

3.1.3 風鈴圈初始化

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

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

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

3.3 定時器的啟動和停止

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

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

iTimingDelay=（iActiveList+iTimingLen）%TIMING_ PERIMETER；

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

pTmpTimer=pHeadTimer+iTimerId；

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

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

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

pFreeTimer=pHeadTimer+iFreeTimerId；

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

DequeueElement（（Q_Struc_T*）pFreeTimer）；

3.4 定時器超時

每經過一個定時觸發時間，后移一個定時間隔后對應的風鈴串就變為當前風鈴串，其上的所有定時器（風鈴）就被認為超時。將定時器從當前風鈴串上逐一刪除，并可利用定時器屬性上的信息通知使用者。

4 性能測試和結果分析

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

圖3　時間校準

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

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

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

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

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

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

5 結束語

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

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

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

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

［3］ 嚴蔚敏，吳偉民.數據結構＜C語言版＞［M］.北京：清華大學出版社，2000.

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

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

［6］ 孔祥營，柏桂枝.嵌入式實時操作系統VxWorks及其開發環境［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—），碩士，高級工程師。主要研究方向：通信網絡安全。