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

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

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

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