定時器詳解引出定時器是一個比較常見的數據結構，或者說框架，以一個最簡單的例子引出，在游戲中，冷卻時間使用的就是定時器；所以說定時器是**等待時間過期執行對應時間事件處理( 回調函數 )**的一個框架；補充：下文中可能會出現定時任務，它和時間事件基本上是一個東西那麼現在有一個就有一個問題，該 ...

定時器詳解

引出

定時器是一個比較常見的數據結構，或者說框架，以一個最簡單的例子引出，在游戲中，冷卻時間使用的就是定時器；

所以說定時器是等待時間過期執行對應時間事件處理( 回調函數 )的一個框架；

補充：下文中可能會出現定時任務，它和時間事件基本上是一個東西

那麼現在有一個就有一個問題，該如何實現定時器這一功能？

首先進行兩種分類：隨著網路事件處理定時事件；不隨著網路事件處理時間事件；

定時器概述

對於一個伺服器來說，需要許多客戶端進行通信，必然會有網路IO相關的事件( 網路IO事件 )；

除此之外，伺服器內部對於一個或N個客戶端傳輸過來的數據進行延時相關的處理，針對不同送達時間，必然會有排序和時間事件；

對於不同的框架，針對網路事件和時間會有不同的實現：

第一種，網路事件和定時事件在同一個線程中使用；
第二種：網路事件和定時事件在不同的線程中使用；

第一種形式-網路事件和定時事件在同一個線程中使用

int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);
int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, 
           struct timeval *timeout);
timeout > 0：表示等待指定的時間，單位為毫秒;
timeout == 0：表示立即返回，不管是否有事件發生;
timeout == -1：表示一直等待，直到有事件發生。

這一模式中，利用的是IO多路復用中的timeout參數；使用其大於0與等於0的情況，以一下代碼舉例。

// ... 其他代碼
while(!quit){
    
	int timeout=get_nearest_timer()-now_time();// get_nearest_timer為得到最近的時間事件
	if(timeout<0)
		timeout=-1;
	int event_count=epoll_wait(epfd,ev,ev_num,timeout);
	for(int i=0;i<event_count;i++){
        
		// ... 處理網路事件
	}
    
	update_timer();// 處理時間事件
	// ... 其他代碼
}
// ... 其他代碼

說明：get_nearest_timer()、update_timer()，為定時器提供

從上述中可知其流程：

最近定時任務需要的時間->epoll_wait阻塞一會兒->處理網路事件->處理時間事件;

update_timer()函數可以只是用作確定時間事件的回調函數，可以把事件處理拋給線程池，而update_timer()會直接進行返回，不會阻塞主流程，這是一種事件的非同步形式。

總結

針對於上述流程，最關鍵的一步就是使用epoll_wait進行阻塞，使得可以同步地進行網路IO處理和定時任務處理，讓其處於一個流程中

當然這種必然也是有缺點的，比如定時任務或者網路IO數量太多，導致處理時間太長，不過這可以使用 reactor模型( 或者使用協程)+時間事件非同步處理的形式解決。多數情況下還是針對少量定時任務使用第一種。

再有就是多線程環境下，如果網路IO的事件處理和時間任務處理需要有一種同步的關係，大概還得進行加鎖的複雜處理

擴展

其實reactor模型也是非同步事件處理，從而讓IO處理時同步的

第二種：網路事件和定時事件在不同的線程中使用

概況：時間事件使用一個單獨的線程進行檢測，一旦檢測到進行回調、或者再拋給任務隊列，由線程池進行處理；

void* thread_timer(void * thread_param) {
    init_timer();// 初始化定時器
    while (!quit) {
        update_timer(); // 檢測定時器中的定時任務
        sleep(t); // 這⾥的 t 要⼩於 時間精度
    }
    clear_timer();
    return NULL;
}
pthread_create(&pid, NULL, thread_timer, &thread_param);

說明：

定時器內部會維護大量的定時任務，update_timer()是用於檢測定時器中所有需要被處理的定時任務，檢測到後進行處理並刪除該定時任務，處理時可以直接調用回調，也可以做成非同步的事件處理。

使用sleep()/usleep()函數，減少進入update_timer()函數的次數，不過一定要讓t小於時間精度（最小運行單元），否則t大於時間精度會讓定時器不會及時的被檢測到，會出現延時的狀況。

總結

在不同線程處理網路事件和時間事件時，可以進行大量的定時任務的維護和處理，讓網路IO處理和定時任務解耦。

定時器設計

既然要使用定時器，必然離不開定時器的設計，那麼如何設計定時器，成為接下來需要解決的問題。

介面設計

首先是介面的設計

基本介面：

初始化定時器：void init_timer();

添加定時任務：Node *add_timer(int expire,callback cb);

刪除定時任務：bool delete_timer(Node* node);一般在檢測定時器的時候使用，可以不對外提供該介面；

找到最近的需要被觸發的定時任務：Node* find_nearest_timer();這種介面一般應用於網路事件和定時事件在一個線程中處理的觸發方式。

檢測更新所有定時任務：void update_timer();

清除所有定時任務 :void clear_timer();

內部數據結構選擇

對外提供的介面解決了，那麼接下來該思考定時器內部該用什麼樣的數據結構維護定時任務會讓效率達到最佳；

該數據結構需要滿足一些條件，比如查詢最小節點的時間複雜度比如得小，比如增加刪除節點不會影響原有的數據結構。

因此選擇出來了，紅黑樹、最小堆都是最佳的選擇。

紅黑樹

紅黑樹的中序遍歷，讓數據可以有序排序，而且是絕對排序（從小到大排序）。具體數據結構，可以去查找網上其他資料。

增刪查的時間複雜度均為O(logN);

最小的節點為紅黑樹最左側的節點，時間複雜度O(logN);

如果幾乎同時來個兩個時間相等的任務，但是key值比較時會出現相等的情況，你可以把後來的任務放到其右節點位置。

最小堆

最小堆是一個完全二叉樹，且父節點一定比子節點小，這樣得到的結果就是根節點一定是這棵樹的最小值；具體數據結構，可以去查找網上其他資料。

增查的時間複雜度O(logN);

刪除操作需要查找是否包含這個節點，刪除的時間複雜度O(n);

最小節點的時間複雜度為O(1);

時間輪

以上兩種實現方法需要時時刻刻都要進行檢測，對於定時任務密集類型的自然可以，如果是定時任務之間的間隔時間過長怎麼辦？時時刻刻檢測會增加很多無效檢測，降低cpu的使用效率。

使用時間輪是一種解決上述問題的方法；

時間輪需要保證自己的時間精度足夠小，否則會出現不能插入定時任務的情況

單層級時間輪

首先先談一談單層級時間輪，單層級時間輪就是使用數組模擬一個環形隊列，數組的每一個元素是一個定時任務鏈表。通過一個指針不斷遍歷這個數組，遇到某個元素的任務鏈表不為空就執行相應的任務。

對於單層級時間輪需要數組的大小足夠大，否則插入的定時任務超出數組可關註時間（比如時間精度1ms，數組大小為20，可關註的時間就是20ms）的N多倍，會導致定時任務執行順序出錯。（不確定在定時任務的結構體增加一個圈數可不可以）;

多層級時間輪

那麼多層級時間輪就是解決上述問題一個好的解決辦法。類似於進位進位一樣，一旦超過該層級的可關註時間，就會進入下一層級，直到有位置可以插入；如果某個定時任務即將執行，也會不斷返回上一層級，直至掛載到第一層級（也是被執行層級）。

如果使用時間輪也是直接使用多層級時間輪的，它有以下這些優點：

相比於單層級時間輪，它的空間占用大大減少；因為多層級針對任務的時間儲存是乘的關係，而單層級是加的關係
對於多層級，除去第一層的任務需要時時刻刻關註，其他層的元素每增加一次重新映射一次即可。

數據結構

struct timer_event {
	uint32_t handle;
	int session;
};
// 定時任務
struct timer_node {
	struct timer_node *next;
	uint32_t expire;
};
// 任務鏈表
struct link_list {
	struct timer_node head;
	struct timer_node *tail;
};
struct timer {
	struct link_list near[TIME_NEAR];
	struct link_list t[4][TIME_LEVEL];
	struct spinlock lock;	// 自旋鎖，多線程操作需要，時間複雜度O(1)
	uint32_t time;			//時間指針，範圍是2^32*10ms
	uint32_t starttime;
	uint64_t current;
	uint64_t current_point;
};

因此針對時間輪設計，需要確定幾點：

確定時間範圍。每一層級允許的添加任務的時間範圍
確定時間精度。每一次tick(指針增加一次)的時間
確定時間層級。第一層組織最近關註的延時任務，是實際執行的層級；其他層級只負責向上一層級重新映射。
實現添加任務介面。
實現刪除任務的介面。對於刪除任務，一般不採取直接從鏈表刪除的方式，因為時間指針一直再增加，定時任務可能會被重新映射，節點位置發生改變。因此，可以通過添加一個標記欄位cancel，當cancel=true時不執行具體任務。
實現重新映射，每一次時間指針移動都需要判斷是否可重新映射。

時間輪總結

時間輪顧名思義，是仿照時鐘規律而發明出來的。使用時間輪就是使用多層級時間輪。

時間輪通過多個層級存放定時任務，第一層組織最近關註的延時任務，是實際執行的層級；其他層級只負責向上一層級重新映射。

對於相同時間觸發的定時任務，時間輪採用一個鏈表將它們存放在同一個時間槽，時間到達時一起執行。

多線程下，定時器只管檢測，檢測到了定時任務，將其拋給線程池執行，定時器本身線程不執行定時任務的業務邏輯。

時間輪刪除節點很不方便，一般不採用刪除方式，因為時間指針一直在移動，定時任務可能會被重新映射，節點位置發生改變；因此，可以通過添加一個標記欄位cancel，當cancel=true時不執行具體任務。

內部數據結構選擇總結

多線程環境下，使用最小堆和紅黑樹的定時器，在進行添加任務、刪除任務的時候需要把整個樹進行加鎖，使用互斥鎖；如果是時間輪，由於其時間複雜度為O(1)，對於添加任務、刪除任務使用自旋鎖即可。

如果定時任務比較少，可以選擇紅黑樹或者最小堆；如果定時任務比較多，選擇時間輪。

說明

寫這篇文章的目的，是捋清定時器會有哪些問題，從巨集觀的一個角度去看待定時器，如果內容有哪些地方不夠細節，可以利用谷歌、必應進行搜索，深度瞭解其原理、或者實現代碼。比如紅黑樹的數據結構是什麼樣的、最小堆的數據結構是什麼樣的等這些問題我相信有很多大牛會比我講的更好，或者說有著更深刻的理解。

此外，本人目前只是一名大學生，對於編程自認為沒有達到很高的水平，而且很多地方也有一些借鑒的成分，如果文章中有任何不對的地方，歡迎指正，本人會虛心接受的。