高性能定時器的設(shè)計(jì)與實(shí)現(xiàn)

劉啟銓

（中興軟創(chuàng)科技股份有根公司，江蘇 南京 210012）

目前主要有幾種定時器處理方法，第一種方法是使用LINUX系統(tǒng)內(nèi)部的三個定時器（定時器在初始化時，被賦予一個初始值，隨時間遞減，遞減至0后發(fā)出信號，同時恢復(fù)初始值。在任務(wù)中，我們可以使用一種或者全部三種定時器，但同一時刻同一類型的定時器只能使用一個）；第二種是使用alarm定時發(fā)送一個信號。前者定時器個數(shù)很少、效率較低、準(zhǔn)確性較差；后者定時器個數(shù)少、效率低，準(zhǔn)確性差，共同的是無法同時并發(fā)，信號容易丟失，需要很小心的處理信號的問題。因此這些傳統(tǒng)的定時器距離我們的要求還存在著很大的差距，根本不可能符合計(jì)費(fèi)系統(tǒng)的要求，所以有必要重新設(shè)計(jì)一種高性能的定時器，該定時器重點(diǎn)具有以下一些特點(diǎn)：

（1）具有很高的實(shí)時性；

（2）具有較高的靈活性和擴(kuò)展性；

（3）可以安全的管理較多的定時任務(wù)；

（4）支持較多的到期定時任務(wù)并發(fā)；

（5）可以根據(jù)到期待執(zhí)行的定時任務(wù)負(fù)載情況自動進(jìn)行處理能力的動態(tài)擴(kuò)展和收縮。

1 高性能定時器架構(gòu)

從系統(tǒng)層面看，高性能定時器內(nèi)部由定時器管理模塊和定時器執(zhí)行模塊組成，兩個模塊分工明確、各司其職、互相配合，共同完成定時任務(wù)的新增、管理、到期推送、到期執(zhí)行和刪除的一整套功能。高性能定時器對外可以看成一個處理黑盒，外部不用關(guān)心其內(nèi)部的具體實(shí)現(xiàn)，只需要調(diào)用其暴露給外部的接口就可以了。

圖1 定時任務(wù)處理流圖

大量的定時任務(wù)通過定時器模塊暴露出的對外接口加入定時器管理池，由定時器管理模塊進(jìn)行管理和維護(hù)，定時器管理模塊同時也負(fù)責(zé)軟時鐘的維護(hù)，當(dāng)定時器管理池中的定時任務(wù)節(jié)點(diǎn)到達(dá)觸發(fā)時間點(diǎn)時，定時器管理模塊就把該節(jié)點(diǎn)定時任務(wù)取出來并放入定時器執(zhí)行池中即進(jìn)行推送，由定時器執(zhí)行模塊進(jìn)行搶占式執(zhí)行該到期定時任務(wù)。

圖2 時間輪算法

圖3 軟時鐘的處理流程

圖4 定時任務(wù)的新增流程

1.1 定時器管理模塊

定時器管理模塊采用分級別的時間輪算法 （Hierarchical Timing Wheel），即把整個時間輪按照不同的時間單位進(jìn)行分組，然后每組又由多個時間片組成，每個時間片下面又對應(yīng)一個鏈表，比如第一組1個時間片（序號為0）表示小于1秒，第二組9個時間片（序號為1-9）分別表示1-9秒，第三組9個時間片（序號為11-19）分別表示10秒-90秒，第四組9個時間片（序號為21-29）分別表示100秒-900秒。

例如一個定時任務(wù)要求在加入定時器管理池后15秒鐘執(zhí)行，那么定時器管理模塊會根據(jù)計(jì)算得出該定時任務(wù)首先插入第二組的序號為5號時間片的雙向鏈表，同時把任務(wù)節(jié)點(diǎn)的10s標(biāo)志置為序號11，當(dāng)該定時任務(wù)加入定時器管理池后，定時器管理模塊經(jīng)過5秒鐘后把該定時任務(wù)從5號時間片對應(yīng)的雙向鏈表中取出，然后放入11號時間片對應(yīng)的雙向鏈表中，然后再經(jīng)過10秒鐘后，定時器管理模塊就會再次把該定時任務(wù)從11號時間片對應(yīng)的雙向鏈表中取出，然后放入定時器執(zhí)行池，由定時器執(zhí)行模塊執(zhí)行該到期定時任務(wù)，至此就完成了該定時任務(wù)從新增到執(zhí)行的全過程。

圖5 定時任務(wù)的刪除流程

圖6 到期任務(wù)的激活流程

定時器管理模塊主要具有以下的功能：

（1）軟時鐘的維護(hù)；

（2）定時任務(wù)的新增；

（3）定時任務(wù)的刪除；

（4）到期任務(wù)的推送。

1.1.1 軟時鐘的維護(hù)

首先定時器管理模塊內(nèi)部取系統(tǒng)時間作為基準(zhǔn)時間，然后進(jìn)入循環(huán)，循環(huán)內(nèi)按照事先設(shè)定的休眠毫秒數(shù)值進(jìn)行預(yù)休眠，然后軟時鐘百毫秒數(shù)值+1，接著進(jìn)行定時器管理池的處理，如果有到期的定時任務(wù)，就把該任務(wù)的相關(guān)信息放入定時器執(zhí)行池，然后軟時鐘判斷是否到整秒鐘，如果到了整秒鐘，軟時鐘的緩存中的秒鐘數(shù)+1，然后判斷是否配置了需要進(jìn)行時間校正和軟時鐘時間是否已經(jīng)到校正的時間了，如果兩個條件都滿足就取系統(tǒng)時間做參照進(jìn)行軟時鐘的緩存中的秒鐘數(shù)的校正，最后取當(dāng)前系統(tǒng)時間和基準(zhǔn)系統(tǒng)時間進(jìn)行比較確定需要補(bǔ)休眠的毫秒數(shù)值并按此進(jìn)行補(bǔ)休眠。

1.1.2 定時任務(wù)的新增

首先外部調(diào)用定時器管理模塊的對外新增定時任務(wù)的接口，定時器管理模塊內(nèi)部判斷定時器任務(wù)節(jié)點(diǎn)池是否還存在空閑節(jié)點(diǎn)，如果存在空閑節(jié)點(diǎn)進(jìn)行互斥加鎖，根據(jù)該定時任務(wù)的具體信息進(jìn)行計(jì)算得到對應(yīng)的組，對應(yīng)的時間片等，然后把定時任務(wù)放入該組該時間片的鏈表中，同時把該節(jié)點(diǎn)的其他相應(yīng)組標(biāo)志位進(jìn)行賦值，然后互斥解鎖，返回結(jié)果。

1.1.3 定時任務(wù)的刪除

首先外部調(diào)用定時器管理模塊的對外刪除定時任務(wù)的接口，定時器管理模塊內(nèi)部判斷定時器任務(wù)節(jié)點(diǎn)池中是否存在該任務(wù)節(jié)點(diǎn)，如果存在該任務(wù)節(jié)點(diǎn)，則從相應(yīng)的任務(wù)節(jié)點(diǎn)隊(duì)列中刪除該任務(wù)節(jié)點(diǎn)，并把該任務(wù)節(jié)點(diǎn)放入任務(wù)節(jié)點(diǎn)池中，并置為空閑狀態(tài)，最后返回結(jié)果。

1.1.4 到期任務(wù)的推送

定時器管理模塊開始遍歷每個時間片，對于每個時間片首先判斷該時間片對應(yīng)的鏈表是否非空，如果非空就判斷該鏈表的頭節(jié)點(diǎn)的觸發(fā)時間是否已經(jīng)到達(dá)，如果到達(dá)就把該頭節(jié)點(diǎn)放入待執(zhí)行定時任務(wù)隊(duì)列，并從鏈表中刪除，如果該任務(wù)是循環(huán)任務(wù)的話，就把該任務(wù)重新加入鏈表尾部，同時判斷新的頭節(jié)點(diǎn)的觸發(fā)時間是否已經(jīng)到達(dá)，如果已經(jīng)到達(dá)就重復(fù)上面的操作，直至所有的時間片都遍歷結(jié)束。

1.2 定時器執(zhí)行模塊

到期任務(wù)的執(zhí)行：

圖7 到期任務(wù)的執(zhí)行流程

定時器執(zhí)行模塊首先進(jìn)行互斥加鎖，然后判斷任務(wù)執(zhí)行池中是否非空，如果有任務(wù)的話則從任務(wù)執(zhí)行池中取得任務(wù)，同時把任務(wù)執(zhí)行池中的讀取位置下移，待處理任務(wù)數(shù)-1，互斥解鎖，最后執(zhí)行該到期的定時任務(wù)。

2 到期任務(wù)處理能力自擴(kuò)展和收縮

傳統(tǒng)的定時器對于到期的任務(wù)只能串行的進(jìn)行處理，同一時刻只能執(zhí)行單個到期任務(wù)，如果此到期任務(wù)執(zhí)行比較耗時的話就會引起其他到期任務(wù)延遲執(zhí)行和到期任務(wù)大量積壓的嚴(yán)重的后果，對于計(jì)費(fèi)系統(tǒng)這種實(shí)時性要求很高的場合，這種影響是危害性很大的，所以高性能定時器采用專門的資源監(jiān)控模塊實(shí)時監(jiān)控待處理的到期定時任務(wù)隊(duì)列和任務(wù)執(zhí)行線程池，如果發(fā)現(xiàn)隊(duì)列堵塞且任務(wù)的處理線程池中的工作線程都很忙的情況下說明實(shí)時處理能力不夠就動態(tài)增加工作線程以提高任務(wù)的處理能力，如果發(fā)現(xiàn)待處理隊(duì)列較空且任務(wù)的處理線程池中的工作線程較空閑的情況下說明實(shí)時處理能力已經(jīng)滿足就動態(tài)減少工作線程以降低任務(wù)的處理能力，這樣就保證了定時任務(wù)的準(zhǔn)確性、實(shí)時性和高并發(fā)性，同時對系統(tǒng)資源的占用也較少，以平衡兩者之間的關(guān)系。

3 結(jié)束語

本文描述了采用分級時間輪的高性能定時器的設(shè)計(jì)及實(shí)現(xiàn)，該定時器能夠高性能實(shí)時并發(fā)處理大量的定時任務(wù)。首先我們基于定時任務(wù)的管理和到期任務(wù)的執(zhí)行相分離的原則對系統(tǒng)進(jìn)行了設(shè)計(jì)，定時任務(wù)的數(shù)據(jù)存儲采用雙向鏈表的方式，加快節(jié)點(diǎn)的插入和檢索。到期任務(wù)的數(shù)據(jù)存儲采用環(huán)形數(shù)組的方式，加快定時任務(wù)的插入和檢索。

考慮到需要較高的并發(fā)性，本架構(gòu)采用到期任務(wù)處理能力自擴(kuò)展和收縮，有專門的監(jiān)控模塊實(shí)時監(jiān)控到期任務(wù)的待處理隊(duì)列和處理到期任務(wù)的執(zhí)行線程池的情況，并根據(jù)情況的變化進(jìn)行處理能力的動態(tài)調(diào)整已達(dá)到在滿足實(shí)時性和并發(fā)性的情況下，盡可能下的占用系統(tǒng)資源，以減少對系統(tǒng)其他功能模塊的影響。