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

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

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

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