高性能定时器策略之时间轮定时器算法

　　时间轮定时器是有多个时间槽(slot )组成，每个时间槽代表时间的基本跨度。类似于一个时钟，时钟指针以恒定的速度每往下走一步，代表一个时间跨度。
　　时间槽的个数是固定的，用SN (Slot Num) 表示，每转动一次可称为一个滴答(tick),所以转动一周也就需要个SN 滴答。每一个滴答需要的槽间间隔为SI （Slot Interval ），则转一周也就共需要（SN * SI ）时间单位。
　　时间轮的每个槽都指向一个定时器链表，每个链表的定时器都有一个相同的特性：相差（SN * SI ）的整数倍，也即是一周的整数倍。正是由于时间轮有这样的特性，所以可以根据定时器的触发时间和时间轮的槽数，把定时器hash到对应的链表上。
　　一个简单的时间轮如下图：
　　比如我们要插入一个超时时间为TI 的定时器，那么计算器应该插入到槽对应的链表的方式如下：
　　TS = ( CS + （TI / SI) ) % SN
　　CS 代表当前的槽位，因为时间轮定时器不停的在走。
　　时间轮采用的是hash的思想，把各个定时器分散到不同槽的链表中，这个避免了单个链表的过长，提高了效率。
　　从上面的公式可以看出，对时间轮而言，当SI  越小的时候，定时器的精度就越高；当SN 槽数越多时，效率越高，因为定时器被分配到不同的链表中，链表的长度也就相对短了，提高了遍历效率。
　　下面实现一个简单的时间轮，代码如下：
　　#include  #include  #include  #include  #include  #include  #include  #include  #include  #include    #define BUFFER_SIZE  64 //缓冲区长度 #define SLOTS_NUM    60 //时间轮上槽的数目   //结构体声明 typedef struct tw_timer tw_timer; typedef struct client_date client_date;   /* EPOLL回调函数*/ typedef void (*epoll_ callback_ t)(int, int);    struct tw_timer{     int rotation; //记录定时器在时间轮上转多少圈后触发     int time_slot; //记录定时器属于时间轮上的槽位（对应的链表）     void (*cb_func)(client_date *); //定时器回调函数     client_date *user_date; //client数据     tw_timer *prev;  //指向前一个定时器     tw_timer *next ;  //指向下一个定时器 }; //用户数据  struct client_date{     int sockfd;      char buf[BUFFER_SIZE];     tw_timer *time;  };   //每1秒时间轮转动一次，也即是槽间隔为1秒 static const int SI = 1; //时间轮的槽， 其中每个元素指向一个定时器链表,链表无序 tw_timer *slots[SLOTS_NUM];    //事件的当前槽 int cur_slot = 0;   tw_timer * malloc_tw_timer(int rotation, int time_slot) {     tw_timer *timer = (tw timer *)malloc(sizeof(tw_timer));      memset(timer, 0, sizeof(tw_timer));     timer->rotation = rotation;     timer->time_slot = time_slot;     timer->prev = NULL ;     timer->next = NULL ;     timer->cb_func = NULL ;     timer->user_date = NULL;     return timer;   }   void* free_tw_timer(tw_timer *timer) {     if(NULL == timer)         return NULL;          if(NULL != timer->user_date)         free(timer->user_date);          free(timer); }    void time_wheel() {     int i = 0;     for(i = 0; i < SLOTS_NUM; i++)       slots[i] = NULL; }   //遍历每个槽，销毁定时器 void del_time_wheel() {     int i = 0;     for(i = 0; i < SLOTS_NUM; i++)     {     tw_timer *tmp = slots[i];     while(tmp)     {       slots[i] = tmp->next;       free_tw_timer(tmp);       tmp = slots[i];     }         } }    /*根据定时器timeout创建一 个定时器，并把它插入到一个合适的槽中*/  tw_timer * add_timer(int timeout) {     if(timeout < 0)         return NULL;       int ticks = 0;     /*待插入的超时时间小于时间轮的槽间隔SI，则将ticks向 上调整为1,       否则将ticks向下调整为 timeout/SI      */     if(timeout < SI)      {     ticks = 1;     }     else     {         ticks = timeout / SI;     }       //计算待插入的定时器在时间轮转动多少圈后被触发     int rotation = ticks / SLOTS_NUM;     //计算待插入的定时器应该被插入到哪个槽中     int ts = (cur_slot + (ticks % SLOTS_NUM)) % SLOTS_NUM;     //创建新的定时器，它在时间轮转动rotation圈后被触发     tw_timer *timer = malloc_tw_timer(rotation, ts);     /*若第ts个槽为空，则插入定时器，并将该定时器置为该槽的头结点*/     if(!slots[ts])     {         printf(＂add timer, rotation is %d, ts is %d, cur_ slot is %d ＂,                  rotation, ts, cur_slot);          slots[ts] = timer;     }     else //否则，将定时器插入其中     {         printf(＂slots[%d] is not null ＂, ts);      timer->next = slots[ts];         slots[ts]->prev = timer;         slots[ts] = timer;     }        return timer; }   void del_timer(tw_timer *timer) {     if(!timer)       return ;          int ts = timer->time_slot;       /*slots[ts]是目标定时器所在槽头结点，若目标定时器为头结点，则需要重置第ts个槽的头结点*/     if(timer == slots[ts])    {     slots[ts] = slots[ts]->next;         if(slots[ts])         {       slots[ts]->prev = NULL;       }      }     else     {     timer->prev->next = timer->next;     if(timer->next)     {         timer->next->prev = timer->prev;     }            }      free_tw_timer(timer);     }   //SI 时间到后，调用该函数， 时间轮向前滚动一个槽的间隔 void tick() {   tw_timer *tmp = slots[cur_slot];   //遍历该槽对应链表的所有定时器，查看是否触发   while(tmp)   {     if(tmp->rotation > 0)     {       tmp->rotation--;       tmp = tmp->next;     }     else //到期,执行任务     {       tmp->cb_func(tmp->user_date);       if(tmp == slots[cur_slot])       {         printf(＂delete head in cur_slot, cur_slot %d ＂, cur_slot);         slots[cur_slot] = tmp->next;         free_tw_timer(tmp);                  if(slots[cur_slot])           slots[cur_slot]->prev = NULL;                    tmp = slots[cur_slot];       }       else       {         tmp->prev->next = tmp->next;         if(tmp->next)         {           tmp->next->prev = tmp->prev;         }                tw_timer *tmp2 = tmp->next;         free_tw_timer(tmp);                 tmp = tmp2;       }          }   }     //更新时间轮的当前槽，以反映时间轮的转数   cur_slot = ++cur_slot % SLOTS_NUM; }
　　测试如下  int total = 0; //记录1s定时器触发次数   void test (client_date *cd) {    printf(＂total = %d ＂, total); }   void test_add_timer(int timeout, void (*cb_func)(client_date *)) {     tw_timer * timer;     timer = add_timer(timeout);      timer->cb_func = cb_func;   }     void test_crete_timer() {     //创建一一个2秒5秒10秒70秒， 85秒的定时器      test_add_timer(2, test);     test_add_timer(5, test);     test_add_timer(10, test);     test_add_timer(70, test);     test_add_timer(85, test);        time_t now ;     struct tm *tm_now ;     time(&now) ;     tm_now = localtime(&now) ;     printf(＂test_crete_timer datetime: %d-%d-%d %d:%d:%d ＂, tm_now->tm_year+1900,          tm_now->tm_mon+1, tm_now->tm_mday, tm_now->tm_hour, tm_now->tm_min, tm_now->tm_sec);    }   //保存触发定时器相应的fd和回调，在该回调中进行遍历时间轮 typedef struct epoll_callback_info {     int iFd;     epoll_callback_t pfEpollCallBack;  }epoll_callback_info;   //创建一个触发定时器 int createTimer(long lMSec, int epfd, epoll_callback_t pfEpollCallback) {   struct itimerspece stTimer;   struct epoll_event event;   int timerfd;   int iSec = (int)(lMSec/1000);   int ret = -1;     memset(&event, 0, sizeof(event));   event.events = EPOLLIN | EPOLLHUP | EPOLLERR;      memset(&stTimer, 0, sizeof(stTimer));   stTimer.it_value.tv_sec = iSec;   stTimer.it_value.tv_nsec = (lMSec%1000)*1000000;   stTimer.it_interval.tv_sec = iSec;   stTimer.it_interval.tv_nsec = (lMSec%1000)*1000000;      timerfd = timerfd_create(CLOCK_MONOTONIC, 0);   if(-1 != timerfd)   {     if(0 == timerfd_settime(timerfd, 0, &stTimer, NULL))     {       epoll_callback_info *p = malloc(sizeof(epoll_callback_info));       p->iFd = timerfd;       p->pfEpollCallback = pfEpollCallback;              event.data.ptr = p;       ret = epoll_ctl(epfd, EPOLL_CTL_ADD, timerfd, &event);     }     else     {       printf(＂timerfd_settime Failed＂);     }          /*定时器时间设定或添加epoll错误时，释放资源*/     if(0 != ret)     {       printf(＂add to epoll failed or set time failed＂);       close(timerfd);       timerfd = -1;     }   }   else   {     printf(＂create timerfd failed＂);   }     return timerfd; }   void timer_read_timerFd(int timerfd) {   uint64_t exp;   (void)read(timerfd, &exp, sizeof(uint64_t));      total++;   return; }   //epoll上定时器回调，每触发一次则调用一次tick() void commomTimerCB(int uiEvent, int iTimeFd) {   timer_read_timerFd(iTimeFd);   tick(); }     int main() {   struct epoll_event wait_event[100];   int epfd;   int timerfd;   epoll_callback_t pfEpllCallback;   int i = 0;   struct itimerspece stTimer;   long lMSec = 1000; //1s定时器时间   int count;      epfd = epoll_create(1);   if(-1 == epfd)   {     printf(＂epoll create error ＂);     return -1;   }      printf(＂create epoll fd: %d ＂, epfd);   time_wheel();   test_create_timer();      timerfd = createTimer(lMSec, epfd, (epoll_callback_t)commomTimerCB);   if(-1 == timerfd)   {     printf(＂failed to create timer＂);     return -1;   }      for(;;)   {     waitfds = epoll_wait(epfd, wait_event, 100, -1);     printf(＂count %d ＂, count++);          for(i = 0; i < waitfds; i++)     {       epoll_callback_info *t = (epoll_callback_info*)wait_event[i].data.ptr;       pfEpllCallback = (epoll_callback_t)(unsigned long)t->pfEpllCallback；       pfEpllCallback(wait_event[i].events, t->iFd);     }   }      return 0; }