时间轮的概念 

   关于定时器有很多种，有基于升序的定时器时间链表，但是这种链表存在效率的不足，就是当插入定时器的时候时间复杂度是O(n).今天，我们来认识一下高性能定时器时间轮。

   如上图所示，就是一个时间轮的基本轮廓。一个轮子上有很多槽slot,每一个槽指向一个定时器链表，这个链表是无序的。时间轮每转动一步就会指向下一个槽，其实也可以理解为一个滴答时间成为时间轮的槽间隔si (slot interval)。它实际上就是心跳时间。如果该时间轮有n个槽，因此它运转一周的时间是n*si.

   如果现在指针指向槽cs,我们此时要添加一个定时器时间为ti的定时器，则该定时器将被插入槽ts对应的链表

                                ts = (cs+ti/si)%N

   基于排序链表的定时器使用唯一的链表来管理所有定时器，所以插入定时器的数目越多，效率就会越低，而时间轮则是利用哈希表的思想，将定时器散列到不同的链表中，这样每条链表上的数据就会显著少于原来排序链表的数目。插入操作的效率基本不受定时器数目的影响(不需要排序，直接散列到一个链表上)。

显然要提高时间轮的精度，就要使si(slot interval)足够小，要提高其执行效率则要N要足够大。

时间轮

Distributor ID: Ubuntu
Description: Ubuntu 13.04
Release: 13.04
Codename: raring

#ifndef TIME_WHEEL_TIMER
#define TIME_WHEEL_TIMER
#include<time.h>
#include<netinet/in.h>
#define BUFFER_SIZE 64
class tw_timer;
struct client_data
{sockaddr_in address;int sockfd;char buf[BUFFER_SIZE];tw_timer* timer;} ;class tw_timer
{public:tw_timer(int rot,int ts):rotation(rot),time_slot(ts),next(NULL),prev(NULL){}public:int oldrotation;	int rotation;/*记录定时器在时间轮上转多少圈后生效*/int time_slot;/*记录定时器属于时间轮上的哪个槽*/void (*cb_func)(client_data*);/*定时器回调函数*/client_data* user_data;/*用户数据*/tw_timer* next;/*指向下一个定时器*/tw_timer* prev;/*指向前一个定时器*/time_t  expire;//定时时间time_t start_time;//设定定时器的时间};class time_wheel
{public:time_wheel():cur_slot(0){for(int i=0;i<N;i++){slots[i]=NULL;/*初始化每个槽的头结点*/}}~time_wheel(){for(int i=0;i<N;i++){tw_timer* tmp = slots[i];while(tmp){slots[i]=tmp->next;delete tmp;tmp = slots[i];}}}/*根据定时器的定时值timeout创建一个定时器，并把它插入合适的槽中*/tw_timer* add_timer(int put_timeout){if(put_timeout<0){return NULL;}int ticks =0;int  timeout = put_timeout-time(NULL);if(timeout<SI)ticks = 1;elseticks = timeout/SI;/*计算待插入的定时器在时间轮上转动多少圈后触发*/int  rotation = ticks/N;/*计算定时器应该被插入哪个槽中*/int ts = (cur_slot+ticks%N)%N;/*创建定时器，它在时间轮转动rotation圈之后被触发，且位于第ts个槽中*/ tw_timer* timer = new tw_timer(rotation,ts);timer->expire = put_timeout;timer->oldrotation = rotation;if(!slots[ts])slots[ts]=timer;else{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;if(timer == slots[ts]){slots[ts] = slots[ts]->next;if(slots[ts])slots[ts]->prev = NULL;delete timer;}else{timer ->prev->next = timer ->next;if(timer->next)timer ->next ->prev = timer ->prev;delete timer;}}void tick(){tw_timer* tmp = slots[cur_slot];while(tmp){//如果定时器要转的圈数仍大于零if(tmp->rotation>0){tmp ->rotation --;tmp= tmp->next;}else{time_t cur_time = time(NULL);if(cur_time<tmp->expire)tmp=tmp->next;else{tmp->cb_func(tmp->user_data);if(tmp ==slots[cur_slot]){slots[cur_slot] = tmp->next;delete 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;delete tmp;tmp = tmp2;//tmp 指向下一个定时器}}}}cur_slot=++cur_slot%N;}private:static const int N = 60;/*转动一周需要60时间单位*/static const int SI = 1;/*每隔1时间单位中，转动一次*/tw_timer* slots[N];/*时间轮的槽，其中每个月元素指向一个定时器链表，链表无序*/int cur_slot;/*时间轮当前槽*/};#endif

下面是time_wheel.main.cpp

#include<iostream>
#include<unistd.h>
#include<pthread.h>
#include<stdlib.h>
#include"time_wheel_timer.h"using namespace std;
static time_wheel client_timer; 
void myfunc(client_data*arg)
{cout<<"timeout-->"<<"oldrotation:"<<arg->timer->oldrotation<<" now need rotation:"<<arg->timer->rotation<<" sockfd:"<<arg->sockfd<<" timer_slot:"<<arg->timer->time_slot<<" start_time:"<<arg->timer->start_time<<" expire:"<<arg->timer->expire<<" now:"<<time(NULL)<<" duration_time:"<<arg->timer->expire-arg->timer->start_time<<endl;arg =NULL;	}
void* checktick(void*arg)
{while(1){client_timer.tick();usleep(100);//后续采用信号处理}}
int main(){client_data*users = new client_data[20];srand(time(NULL));for(int i =0;i<10;i++){users[i].sockfd = i;time_t cur_time = time(NULL);tw_timer* timer = client_timer.add_timer(cur_time+rand()%100+1);if(timer){timer->user_data = &users[i];timer->cb_func = myfunc;timer->start_time = cur_time;users[i].timer = timer;}}
pthread_t pid;
pthread_create(&pid,NULL,checktick,NULL);
void* retval;
pthread_join(pid,&retval);}

编译执行

       g++ time_wheel.main.cpp -lpthread -owheel

执行结果

ky@ky-S910-X31E:~/libz/72$ ./wheel 
timeout-->oldrotation:0 now need rotation:0 sockfd:9 timer_slot:24 start_time:1404385502 expire:1404385526 now:1404385526 duration_time:24
timeout-->oldrotation:0 now need rotation:0 sockfd:8 timer_slot:25 start_time:1404385502 expire:1404385527 now:1404385527 duration_time:25
timeout-->oldrotation:0 now need rotation:0 sockfd:0 timer_slot:25 start_time:1404385502 expire:1404385527 now:1404385527 duration_time:25
timeout-->oldrotation:0 now need rotation:0 sockfd:4 timer_slot:52 start_time:1404385502 expire:1404385554 now:1404385554 duration_time:52
timeout-->oldrotation:1 now need rotation:0 sockfd:1 timer_slot:2 start_time:1404385502 expire:1404385564 now:1404385564 duration_time:62
timeout-->oldrotation:1 now need rotation:0 sockfd:7 timer_slot:15 start_time:1404385502 expire:1404385577 now:1404385577 duration_time:75
timeout-->oldrotation:1 now need rotation:0 sockfd:3 timer_slot:16 start_time:1404385502 expire:1404385578 now:1404385578 duration_time:76
timeout-->oldrotation:1 now need rotation:0 sockfd:6 timer_slot:30 start_time:1404385502 expire:1404385592 now:1404385592 duration_time:90
timeout-->oldrotation:1 now need rotation:0 sockfd:2 timer_slot:32 start_time:1404385502 expire:1404385594 now:1404385594 duration_time:92
timeout-->oldrotation:1 now need rotation:0 sockfd:5 timer_slot:35 start_time:1404385502 expire:1404385597 now:1404385597 duration_time:95