摘  要： 針對TD-LTE系統基站應用，提出一種Linux用戶空間下的相對定時器池的實現方法。結合哈希表、相對定時算法等技術，實現大數量定時器的高效管理，以Linux系統定時器單位為定時器粒度，定時器池滿足基站高層協議軟件大數量并發任務的應用需求。
關鍵詞： TD-LTE；協議定時器；哈希表；定時器池；相對定時器

　Linux系統提供這樣一種機制，預先設置一定時間長度并在設定的時間到期后執行預先設定的操作，這種機制即為定時器（timer）。Linux系統面向用戶提供多種用戶級的定時器接口，而基于這些用戶級定時器接口實現的應用于特定場合定時任務的定時器稱為相對定時器（relative timer）。TD-LTE（時分長期演進）系統基站控制面高層協議需要使用較大數量的百毫秒級、秒級甚至是分鐘級協議定時器，例如S1切換準備定時器的建議取值為3 000 ms，S1切換保護定時器的建議取值為5 000 ms，S1、X2再次切換間隔時間的建議取值為1 min。為滿足TD-LTE基站系統定時精度相對較低但定時器數量龐大的應用需求，本文實現了一種基于Linux系統定時器的相對定時器池，以守護進程（Daemon）的形式向基站控制面高層協議軟件內部各個任務提供定時服務并負責較大數量的定時器管理功能，定時粒度為100 ms，所實現的相對定時器池可穩定運行于TD-LTE系統基站設備。
1 工作流程及算法實現
1.1 定時器池架構
　相對定時器池模塊作為一個守護進程（Daemon）為高層協議軟件的其他任務提供服務。相對定時器池架構如圖1所示。定時器池后臺任務擁有兩個線程，主線程負責定時器池中超時定時器的檢測，另一個線程處理用戶任務對定時器池操作的請求消息。相對定時器池后臺程序每隔100 ms檢測一次定時器池鏈表，如果池內有超時定時器，將發送一個超時事件消息給注冊該定時器的擁有者，通常是高層協議軟件的一個任務（對于定時器池而言，即為用戶任務）；定時器操作請求處理線程通過socket接收定時器請求消息[1]，這些請求轉變為協議棧內部定義的消息，而且使用用戶任務的特定參數發送消息給定時器池。

　主要數據結構定義如下：
　structlist_head {structlist_head*next，*prev；}；
    //選用linux內核list.h中的雙向鏈表結構
　typedefstructtmr_q{structlist_headtime_vect_list；
　/*鏈表元素用來組織定時器向量Hash表*/
　structlist_headevent_list；
    /*鏈表元素用來組織定時事件Hash表*/
　TMR_PARA tmr_para；    /*定時器參數*/
　}TMR_Q；    /*定時器池數據庫單元結構*/
1.2 工作流程
1.2.1 主線程處理流程
　相對定時器池的主線程每隔100 ms被Linux系統定時器喚醒。此后，主線程檢查定時器列表以便找出超時定時器。當有超時定時器被找出，線程將發送一個帶有已注冊事件eventID的超時通知消息給相應用戶任務。當用戶任務接收到這個消息，觸發相應的處理方法來處理這個超時事件。主線程處理流程示意圖如圖2（a）所示。
1.2.2 定時器操作請求消息處理流程
　操作請求消息的處理線程是一個無限循環，它一直在等待接收用戶任務通過socket發送的定時器操作請求消息，當接收到操作請求消息后進行相應的請求處理，請求消息處理流程圖如圖2（b）所示。請求處理模塊中有4個操作函數，函數定義如下：
　TMR_Q*FindTimer（TMR_PARA*target）；/*查找定時器*/
　u32 AddTimer（TMR_PARA*Timer_new）；/*添加定時器*/
　void ModifyTimer（TMR_Q*timer，TMR_PARA*Timer_new）；
　/*修改更新定時器*/
　void DeleteTimer（TMR_PARA*timer）；/*刪除定時器*/

1.2.3 用戶接口的實現
　為了用戶任務使用定時器，定時器模塊提供了兩種操作接口，在用戶任務中啟動定時器和在任務中關閉定時器。如果一個任務要啟動多個定時器，每一個定時器將使用不同的事件eventID來進行標識區分，在定時器發送超時事件消息給用戶任務收到時，用戶任務通過事件eventID分開處理這些事件。超時時間的單位為100 ms，因此如果一個任務需要在5.3 s后觸發一個定時操作，超時時間應該被設置為53。因為資源限制等問題，定時器設置操作有可能失敗，本定時器池向用戶任務提供最多1 024個定時器。為簡化消息接口處理，關閉定時器的用戶請求消息只需要攜帶定時事件eventID參數即可完成定時器的刪除。
1.3 相對定時算法實現
　本定時器池中使用Linux內核list.h對定時器鏈表進行操作，相對定時算法圍繞兩個無符號長整型全局變量current_ticks和stored_ticks，作為鏈表的哈希函數的計算以及相對定時的計算參數，定時器池守護進程開啟后初始化這兩個變量為0，單位為10 ms。定義用于存儲定時器及定時事件的哈希表靜態數組變量如式　(1)，其中TIMER_VECTOR_SZ=8，TOTAL_EVENT_NUM=24。
static structlist_head    timer_vector[TIMER_VECTOR_SZ]，event_vector[TOTAL_EVENT_NUM]，（1）
free_timer_list；/*空閑定時器標記*/
　（1）添加定時器：整個定時器池數據庫中的定時器分為兩部分，已經被使用的定時器和空閑定時器。請求處理線程添加定時器newTimer時，首先計算相對定時時間（relativeTime=Timeout+stored_ticks），隨后計算定時器池哈希表的向量索引timerIndex=relativeTime&（TIMER_VECTOR_SZ-1），如果新添定時器的relativeTime小于stored_ticks，將relativeTime的值設置為stored_ticks，將其插入到索引位置對應的向量鏈表timer_vector[timerIndex]的頭部，保證該定時器在主線程輪詢第一輪循環中觸發；否則，從鏈表后面向前比較直到第一個relativeTime提前于新添定時器的位置，將定時器插入，同時綁定定時器到事件向量鏈表，采用除留余數法計算定時事件哈希表的向量索引eventIndex=eventID%TOTAL_EVENT_NUM。
　（2）輪詢定時器池：主線程經100 ms系統定時器喚醒后執行current_ticks加10操作，以stored_ticks++為步長，current_ticks-stored_ticks>=0為循環條件，對定時器向量哈希表進行輪詢查找超時定時器，遍歷timer_vector[TIMER_VECTOR_SZ]向量索引下的鏈表，比較定時器池中已使用的定時器的相對定時時間relativetime與current_ticks的大小，小于或等于current_ticks則已超時，立即發送超時響應消息，隨后在鏈表中刪除該定時器并在此位置重新放入空閑定時器標記。
　（3）刪除定時器：在添加定時器時返回定時器的定時事件eventID，刪除定時器時通過eventID在事件鏈表event_vector[TOTAL_EVENT_NUM]中查找。
2 性能測試及應用
　（1）測試環境：PowerPC MPC8548，1.33 GHz，Linux 2.6.35。
　（2）測試設計如下：為滿足TD-LTE系統基站設備的實際應用需求，根據基站協議棧實際運用的定時時間片長度分為三類精度級別，分別為500 ms，5 000 ms，60 s。對應每個定時時間片測試定時器池的定時器批量分別為10個、100個、1 024個定時器。測試開始前將定時器加入到定時器池中，完成初始化；然后開始工作，首先使用gettimeofday函數獲取當前時間t_Begin，主線程檢查超時定時向用戶任務發送超時通知消息前，再次獲取當前時間t_Now，記錄并保存t_Begin和t_Now兩個時間參數用于測試結果的統計，測試結果為定時器的絕對誤差比和相對誤差。定時器絕對誤差比代表定時器的定時性能，測試得到的定時絕對誤差與定時時間片的比值；相對誤差代表定時器池的穩定性[2]，即相同定時時間片大小的定時器在100次測試中的相對誤差。
　表1數據顯示，定時器個數相同情況下，定時時間片越長，絕對誤差比例越小。同時，在定時器滿負荷（1 024個定時器同時使用）也能保證良好的穩定性和定時性能。測試結果中的絕對誤差比和定時誤差均處于可忽略范圍內，定時器池的定時性能穩定。表1每種情況測試100次。

　本文設計并實現了一種基于哈希表定時器池算法，統一管理大量定時器，在滿足用戶任務定時需求、不影響定時器性能的前提下，提高了定時器池的容量及穩定性。通過測試驗證，本文實現的相對定時器池的穩定性、精確性能均滿足設計目標，穩定運行于基站設備。
參考文獻
[1] STEVENS W R．UNIX網路編程（第2卷）[M]．北京：人民郵電出版社，2010．
[2] 許健，于鴻洋.Linux下一種高性能定時器池的實現[J].電子技術應用，2012，38（12）：114-119.
[3] 趙紅武，之金瑜，劉云生.一種改進的定時器實現算法及其性能分析[J].微計算機應用，2006，27（3）：343-345.