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

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

　主要數(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；
　/*鏈表元素用來(lái)組織定時(shí)器向量Hash表*/
　structlist_headevent_list；
    /*鏈表元素用來(lái)組織定時(shí)事件Hash表*/
　TMR_PARA tmr_para；    /*定時(shí)器參數(shù)*/
　}TMR_Q；    /*定時(shí)器池?cái)?shù)據(jù)庫(kù)單元結(jié)構(gòu)*/
1.2 工作流程
1.2.1 主線程處理流程
　相對(duì)定時(shí)器池的主線程每隔100 ms被Linux系統(tǒng)定時(shí)器喚醒。此后，主線程檢查定時(shí)器列表以便找出超時(shí)定時(shí)器。當(dāng)有超時(shí)定時(shí)器被找出，線程將發(fā)送一個(gè)帶有已注冊(cè)事件eventID的超時(shí)通知消息給相應(yīng)用戶任務(wù)。當(dāng)用戶任務(wù)接收到這個(gè)消息，觸發(fā)相應(yīng)的處理方法來(lái)處理這個(gè)超時(shí)事件。主線程處理流程示意圖如圖2（a）所示。
1.2.2 定時(shí)器操作請(qǐng)求消息處理流程
　操作請(qǐng)求消息的處理線程是一個(gè)無(wú)限循環(huán)，它一直在等待接收用戶任務(wù)通過(guò)socket發(fā)送的定時(shí)器操作請(qǐng)求消息，當(dāng)接收到操作請(qǐng)求消息后進(jìn)行相應(yīng)的請(qǐng)求處理，請(qǐng)求消息處理流程圖如圖2（b）所示。請(qǐng)求處理模塊中有4個(gè)操作函數(shù)，函數(shù)定義如下：
　TMR_Q*FindTimer（TMR_PARA*target）；/*查找定時(shí)器*/
　u32 AddTimer（TMR_PARA*Timer_new）；/*添加定時(shí)器*/
　void ModifyTimer（TMR_Q*timer，TMR_PARA*Timer_new）；
　/*修改更新定時(shí)器*/
　void DeleteTimer（TMR_PARA*timer）；/*刪除定時(shí)器*/

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

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