高性能定時器的設計與實現

劉啟銓

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

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

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

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

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

（4）支持較多的到期定時任務并發；

（5）可以根據到期待執行的定時任務負載情況自動進行處理能力的動態擴展和收縮。

1 高性能定時器架構

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

圖1 定時任務處理流圖

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

圖2 時間輪算法

圖3 軟時鐘的處理流程

圖4 定時任務的新增流程

1.1 定時器管理模塊

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

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

圖5 定時任務的刪除流程

圖6 到期任務的激活流程

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

（1）軟時鐘的維護；

（2）定時任務的新增；

（3）定時任務的刪除；

（4）到期任務的推送。

1.1.1 軟時鐘的維護

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

1.1.2 定時任務的新增

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

1.1.3 定時任務的刪除

首先外部調用定時器管理模塊的對外刪除定時任務的接口，定時器管理模塊內部判斷定時器任務節點池中是否存在該任務節點，如果存在該任務節點，則從相應的任務節點隊列中刪除該任務節點，并把該任務節點放入任務節點池中，并置為空閑狀態，最后返回結果。

1.1.4 到期任務的推送

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

1.2 定時器執行模塊

到期任務的執行：

圖7 到期任務的執行流程

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

2 到期任務處理能力自擴展和收縮

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

3 結束語

本文描述了采用分級時間輪的高性能定時器的設計及實現，該定時器能夠高性能實時并發處理大量的定時任務。首先我們基于定時任務的管理和到期任務的執行相分離的原則對系統進行了設計，定時任務的數據存儲采用雙向鏈表的方式，加快節點的插入和檢索。到期任務的數據存儲采用環形數組的方式，加快定時任務的插入和檢索。

考慮到需要較高的并發性，本架構采用到期任務處理能力自擴展和收縮，有專門的監控模塊實時監控到期任務的待處理隊列和處理到期任務的執行線程池的情況，并根據情況的變化進行處理能力的動態調整已達到在滿足實時性和并發性的情況下，盡可能下的占用系統資源，以減少對系統其他功能模塊的影響。