介绍
时间轮顾名思义，就是将不同时间的定时任务放在一个轮子上，既然是轮子，肯定是会转动的，时间轮内指向槽的指针，以恒定的速度顺时针转动，每转动一步就指向下一个槽。，一次转动称为一次滴答(tick)。一个滴答的时间称为时间轮的槽间隔si，也就是心搏时间。一个时间轮若有N个槽，在它运转一周的时间是N * si。同一个槽上的定时器它们的定时时间相差N * si的整数倍。 对于时间轮来说，要提高精度，就要使si值足够小；要提高执行效率，则要求N值足够大。如图所示：
由图可知定时器在时间轮的槽上是以链表的形式存储的（双向链表），并且相同一条链（也就是同一个槽）上的定时器：它们的定时时间相差N*si的整数倍。时间轮就是利用这个关系将定时器散列到不同的链中。在插入槽中的时候采用的是头插的方法，这样可以减少不必要的遍历时间。但是正是因为一股脑的头插（无序），也造成了在我们每次转动的时候都不得不去遍历一遍链表。
对于时间轮来说，添加一个定时器的时间复杂度为O(1),删除一个定时器的时间复杂度也是O(1),执行一个定时器的时间复杂度为O(n)。但是由于时间轮将所有的定时器散列到了不同的链表上，因此其执行的时间复杂度是要小于O(n)的。此外我们可以通过增加槽的个数和减少每次心搏的间隔从而使得分配到一条链上的定时器的个数减少。从而减少每次遍历的时间，并且还提高了时间轮的定时精度。
代码分析
客户端信息类：
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 )
: next( NULL ), prev( NULL ), rotation( rot ), time_slot( ts ){}
public:
int rotation; //记录定时器在时间轮转动多少圈后生效
int time_slot; //该定时器所在时间槽的下标
void (*cb_func)( client_data* ); //定时回调函数
client_data* user_data; //保存该定时任务所对应的客户端信息
tw_timer* next; //指向下一个定时器
tw_timer* prev; //指向前一个定时器
};同一个时间槽上的多个定时器构成一条双向链表，因此该结构相当如双向链表中的一个节点。
时间轮类：
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];
}
}
}
tw_timer* add_timer( int timeout ) //根据相对时间在时间轮的一个槽上添加一个定时器，最后将指向定时器的指针返回，用以在后面为定时器设置回调函数，以及相应的客户端信息等
{
if( timeout < 0 )
{
return NULL;
}
int ticks = 0;
/*如果timeout小于一次滴答就将其向上折合为1
否则就向下折合为timeout除以SI*/
if( timeout < TI )
{
ticks = 1;
}
else
{
ticks = timeout / TI;
}
/*此处的rotation表示时间轮再转动多少圈生效，ts表示定时器所在槽的坐标。
同一个槽上的定时器它们的定时时间相差N * si的整数倍（si表示时间轮转动一
下的时间，N代表时间轮上槽的个数*/
int rotation = ticks / N;
int ts = ( cur_slot + ( ticks % N ) ) % N;
tw_timer* timer = new tw_timer( rotation, ts );
if( !slots[ts] ) //第ts个槽中没有定时器
{
printf( "add timer, rotation is %d, ts is %d, cur_slot is %d\n", rotation, ts, cur_slot );
slots[ts] = timer;
}
else
{
timer->next = slots[ts];
slots[ts]->prev = timer;
slots[ts] = timer;
}
return timer;
}
void adjust_timer( tw_timer* timer , int timeout )
{
if( !timer || timeout < 0)
{
return;
}
int ts = timer->time_slot;
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;
}
}
int ticks = 0;
if( timeout < TI )
{
ticks = 1;
}
else
{
ticks = timeout / TI;
}
int rotation = ticks / N;
ts = ( cur_slot + ( ticks % N ) ) % N;
timer->rotation = rotation;
timer->time_slot = ts;
if( !slots[ts] )
{
printf( "adjust timer, rotation is %d, ts is %d, cur_slot is %d\n", rotation, ts, cur_slot );
slots[ts] = timer;
}
else
{
timer->next = slots[ts];
slots[ts]->prev = timer;
slots[ts] = 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];
printf( "current slot is %d\n", cur_slot );
while( tmp ) //遍历链表执行到期的定时任务
{
printf( "tick the timer once\n" );
if( tmp->rotation > 0 )
{
tmp->rotation--;
tmp = tmp->next;
}
else
{
tmp->cb_func( tmp->user_data );
if( tmp == slots[cur_slot] )
{
printf( "delete header in cur_slot\n" );
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;
}
}
}
cur_slot = ++cur_slot % N;
}
private:
static const int N = 60; //槽的数目
static const int TI = 1; //每1s转动一次
tw_timer* slots[N]; //时间轮的槽
int cur_slot; //时间轮的当前槽
};关闭非活动连接
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <assert.h>
#include <stdio.h>
#include <signal.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <fcntl.h>
#include <stdlib.h>
#include <sys/epoll.h>
#include <pthread.h>
#include "tw_timer.h"
#define FD_LIMIT 65535
#define MAX_EVENT_NUMBER 1024
#define TIMESLOT 5
static int pipefd[2];
static time_wheel timer_w;
static int epollfd = 0;
int setnonblocking( int fd )
{
int old_option = fcntl( fd, F_GETFL );
int new_option = old_option | O_NONBLOCK;
fcntl( fd, F_SETFL, new_option );
return old_option;
}
void addfd( int epollfd, int fd )
{
epoll_event event;
event.data.fd = fd;
event.events = EPOLLIN | EPOLLET;
epoll_ctl( epollfd, EPOLL_CTL_ADD, fd, &event );
setnonblocking( fd );
}
void sig_handler( int sig )
{
int save_errno = errno;
int msg = sig;
send( pipefd[1], ( char* )&msg, 1, 0 );
errno = save_errno;
}
void addsig( int sig )
{
struct sigaction sa;
memset( &sa, '\0', sizeof( sa ) );
sa.sa_handler = sig_handler;
sa.sa_flags |= SA_RESTART;
sigfillset( &sa.sa_mask );
assert( sigaction( sig, &sa, NULL ) != -1 );
}
void timer_handler() //当获取到SIGALRM信号后会将timeout设置为true从而触发该函数
{
timer_w.tick(); //心搏函数，遍历链表
alarm( 1 );
}
void cb_func( client_data* user_data ) //回调函数，当定时器到期后会被触发
{
epoll_ctl( epollfd, EPOLL_CTL_DEL, user_data->sockfd, 0 );
assert( user_data );
close( user_data->sockfd );
printf( "close fd %d\n", user_data->sockfd );
}
int main( int argc, char* argv[] )
{
if( argc <= 2 )
{
printf( "usage: %s ip_address port_number\n", basename( argv[0] ) );
return 1;
}
const char* ip = argv[1];
int port = atoi( argv[2] );
int ret = 0;
struct sockaddr_in address;
bzero( &address, sizeof( address ) );
address.sin_family = AF_INET;
inet_pton( AF_INET, ip, &address.sin_addr );
address.sin_port = htons( port );
int listenfd = socket( PF_INET, SOCK_STREAM, 0 );
assert( listenfd >= 0 );
ret = bind( listenfd, ( struct sockaddr* )&address, sizeof( address ) );
assert( ret != -1 );
ret = listen( listenfd, 5 );
assert( ret != -1 );
epoll_event events[ MAX_EVENT_NUMBER ];
int epollfd = epoll_create( 5 );
assert( epollfd != -1 );
addfd( epollfd, listenfd );
ret = socketpair( PF_UNIX, SOCK_STREAM, 0, pipefd );
assert( ret != -1 );
setnonblocking( pipefd[1] );
addfd( epollfd, pipefd[0] );
// add all the interesting signals here
addsig( SIGALRM );
addsig( SIGTERM );
bool stop_server = false;
client_data* users = new client_data[FD_LIMIT];
bool timeout = false;
alarm( 1 );
while( !stop_server )
{
int number = epoll_wait( epollfd, events, MAX_EVENT_NUMBER, -1 );
if ( ( number < 0 ) && ( errno != EINTR ) )
{
printf( "epoll failure\n" );
break;
}
for ( int i = 0; i < number; i++ )
{
int sockfd = events[i].data.fd;
if( sockfd == listenfd )
{
struct sockaddr_in client_address;
socklen_t client_addrlength = sizeof( client_address );
int connfd = accept( listenfd, ( struct sockaddr* )&client_address, &client_addrlength );
printf("ip = %s port = %d\n", inet_ntoa(client_address.sin_addr), client_address.sin_port);
addfd( epollfd, connfd );
users[connfd].address = client_address;
users[connfd].sockfd = connfd;
tw_timer* timer = timer_w.add_timer( 3 * TIMESLOT );
timer->user_data = &users[connfd];
timer->cb_func = cb_func;
users[connfd].timer = timer;
}
else if( ( sockfd == pipefd[0] ) && ( events[i].events & EPOLLIN ) )
{
int sig;
char signals[1024];
ret = recv( pipefd[0], signals, sizeof( signals ), 0 );
if( ret == -1 )
{
// handle the error
continue;
}
else if( ret == 0 )
{
continue;
}
else
{
for( int i = 0; i < ret; ++i )
{
switch( signals[i] )
{
case SIGALRM:
{
timeout = true;
break;
}
case SIGTERM:
{
stop_server = true;
}
}
}
}
}
else if( events[i].events & EPOLLIN )
{
memset( users[sockfd].buf, '\0', BUFFER_SIZE );
ret = recv( sockfd, users[sockfd].buf, BUFFER_SIZE-1, 0 );
printf( "get %d bytes of client data %s from %d\n", ret, users[sockfd].buf, sockfd );
tw_timer* timer = users[sockfd].timer;
if( ret < 0 )
{
if( errno != EAGAIN )
{
cb_func( &users[sockfd] );
if( timer )
{
timer_w.del_timer( timer );
}
}
}
else if( ret == 0 )
{
cb_func( &users[sockfd] );
if( timer )
{
timer_w.del_timer( timer );
}
}
else
{
//send( sockfd, users[sockfd].buf, BUFFER_SIZE-1, 0 );
if( timer )
{
printf( "adjust timer once\n" );
timer_w.adjust_timer( timer, 3 * TIMESLOT );
}
}
}
else
{
// others
}
}
if( timeout )
{
timer_handler();
timeout = false;
}
}
close( listenfd );
close( pipefd[1] );
close( pipefd[0] );
delete [] users;
return 0;
}