劉啟銓

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

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

（1）具有很高的實時性；

（2）具有較高的靈活性和擴展性；

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

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

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

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

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

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

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

圖2 時間輪算法

圖3 軟時鐘的處理流程

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

1.1 定時器管理模塊

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

例如一個定時任務(wù)要求在加入定時器管理池后15秒鐘執(zhí)行，那么定時器管理模塊會根據(jù)計算得出該定時任務(wù)首先插入第二組的序號為5號時間片的雙向鏈表，同時把任務(wù)節(jié)點的10s標志置為序號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）軟時鐘的維護；

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

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

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

1.1.1 軟時鐘的維護

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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

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