時間輪

---

簡述

顧名思義，時間輪就像一個輪子，在轉動的時候外界會指向輪子不同的區域，該區域就可以被使用。因此只要將不同時間的定時器按照一定的方法散列到時間輪的不同槽（即時間輪劃分的區域）之中，就可以實現在運轉到某個槽時，進行判斷該定時器是否已經到達運行時間（需要判斷是由于有的定時器并非在這一圈就需要運行，可能需要后面幾圈才會運行。

從圖中也可以看出，每個槽中的定時器是以（雙向）鏈表形式存儲的，每次添加的時候直接插入到鏈表的開始（頭插法）。值得注意的是，由于使用頭插法，因此在運行到某個槽時，需要遍歷一遍鏈表，已檢查是否有到達時間的計時器，有的話就運行，并刪除結點。

至于在每轉到一個槽時都要檢查是否到達運行時間，可以這樣理解：時間輪進行散列的方法就是取余運算，假設每個槽的間隔為1s，共有n個槽，當前轉到了第cur個槽，那么一個定時在 t s以后運行的定時器就要放在第（ cur + t % n ） % n個槽，并在運行t / n圈后到達該槽時才會運行。因此一個槽中的定時器運行的時間是相差i（i >= 0）個周期的。

所以時間輪簡單來說就是散列 + 鏈表，這樣與使用升序鏈表相比，散列可以直接定位要插入的槽所在位置，可以提高添加定時器的效率，由O(N)到了O(1)。

對實現時間輪來說，最主要的還是鏈表的操作是否熟練，當然也主要是雙向鏈表的添加與刪除。

---

代碼分析

• 記錄定時器的時間信息，從而獲取在時間輪中槽的位置，以及在多少圈之后被觸發。在定時時間不足槽之間切換的時間時，要將t/n記為1，否則記錄t/n的整除結果。

// timeout為定時時間，SI為槽之間切換的時間int ticks;if( timeout < SI ) {ticks = 1;} else {ticks = timeout / SI;}int rotation = ticks / N; // 被觸發的圈數int ts = ( cur_slot + ticks % N ) % N; // 被插入的槽

• 為提高定時器的添加效率，使用頭插法，將定時器添加在槽的開始位置。
• 使用雙向鏈表，需要注意將后面的結點的pre指向前一個結點。
• 刪除鏈表時要注意結點是否是第一個結點

---

代碼實現（含注釋）

#ifndef _TIMEWHEEL_H_ #define _TIMEWHEEL_H_#include <time.h> #include <netinet/in.h>const int BUFFER_SIZE = 64;class TwTimer;// 用戶數據，綁定socket和定時器 struct client_data {sockaddr_in address;int sock_fd;char buf[BUFFER_SIZE];TwTimer* timer; };// 定時器類，時間輪采用雙向鏈表 class TwTimer { public:int rotation; // 定時器轉多少圈后生效int time_slot; // 記錄定時器屬于時間輪的哪個時間槽client_data* user_data; // 客戶數據TwTimer* next; // 指向下一個定時器TwTimer* pre; // 指向上一個定時器 public:TwTimer( int rot, int ts ) : rotation(rot), time_slot(ts), next(NULL), pre(NULL) {}void (*cb_func)( client_data * ); // 回調函數 };class TimeWheel { private: static const int N = 60; // 槽的數目static const int SI = 1; // 定時器槽之間時間間隔TwTimer* slot[ N ]; // 時間輪的槽，指向一個定時器鏈表，鏈表無序int cur_slot; // 當前槽 public:TimeWheel() : cur_slot(0) {for( int i = 0; i < N; i++ ) {slot[i] = NULL;}}~TimeWheel() {for( int i = 0; i < N; i++ ) {TwTimer* tmp;while( tmp = slot[i], tmp ) {slot[i] = tmp->next;delete tmp;}}}TwTimer* add_timer( int timeout ); // 根據定時值創建定時器，并插入槽中void del_timer( TwTimer* timer );void tick(); };TwTimer* TimeWheel::add_timer( int timeout ) {if( timeout < 0 ) {return NULL;}// 記錄多少個tick后被觸發，不足最小單位SI的記為1，其余為timeout/SIint ticks = 0;if( timeout < SI ) {ticks = 1;} else {ticks = timeout / SI;}int rotation = ticks / N; // 被觸發的圈數int ts = ( cur_slot + ticks % N ) % N; // 被插入的槽TwTimer* timer = new TwTimer( rotation, ts );// 如果鏈表為空，則放到頭，否則插入到第一個位置if( !slot[ts] ) {slot[ts] = timer;} else {timer->next = slot[ts];slot[ts]->pre = timer;slot[ts] = timer;}return timer; }// 刪除定時器 void TimeWheel::del_timer( TwTimer* timer ) {if( !timer ) {return;}// 注意鏈表為雙向的int ts = timer->time_slot;if( timer == slot[ts] ) {slot[ts] = slot[ts]->next;if( slot[ts] ) {slot[ts]->pre = NULL;}} else {timer->pre->next = timer->next;if( timer->next ) {timer->next->pre = timer->pre;}}delete timer; }// SI時間到后，條用該函數，時間輪向前滾動一個槽的間隔 void TimeWheel::tick() {TwTimer* tmp = slot[cur_slot];while( tmp ) {if( tmp->rotation > 0 ) { // 定時時間未到tmp->rotation--;tmp = tmp->next;} else { // 定時時間已到tmp->cb_func( tmp->user_data );if( tmp == slot[cur_slot] ) { // tmp位于鏈表首slot[cur_slot] = tmp->next;if( slot[cur_slot] ) {slot[cur_slot]->pre = NULL;}delete tmp;tmp = slot[cur_slot];} else { // tmp位于鏈表中tmp->pre->next = tmp->next;if( tmp->next ) {tmp->next->pre = tmp->pre;}TwTimer* tmp2 = tmp->next;delete tmp;tmp = tmp2;}}}cur_slot = ( cur_slot + 1 ) % N; }#endif

總結

以上是生活随笔為你收集整理的【高性能定时器】 时间轮的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。