定时器用于处理周期性事件，其中比较重要的应用就是定期检测客户端是否还在连接，如果没有那么就需要关闭服务器与其的socket通信。因为Linux并不是实时操作系统，因此不可能保证定时器一定是按照某个周期运行，但我们需要想办法尽量提高定时器的精度。这里主要介绍3种定时器 - 基于链表的定时器，基于时间轮的定时器和基于最小堆的定时器。除了使用的容器不一样，这3种定时器的基本原理都是一样的，通过学习基于链表的定时器，我们就可以掌握其它两种定时器。
定时器的基本设计思路
这里定时器的实现是通过SIGALRM信号实现的。在一个进程中，我们定期接收SIGALRM信号；在SIGALRM的信号处理函数中，我们需要设置一个标记让主进程知道进程已经触发timeout了。等回到主进程时，主进程将根据这个标志对事件进行处理。处理定时事件的函数我们一般叫做心跳函数，也就是tick()函数。事件处理函数一般都放在主进程中，因为在运行事件处理函数时，内核将不能接收绝大多数相同的信号(信号不会被放入队列)，因此信号处理函数必须短(这个和嵌入式中ISR必须短一个道理)。
基于链表的定时器
这篇文章的所有代码来自《Linux高性能服务器编程》，这里我只做部分代码讲解，详细代码查看Linux高性能服务器编程源码。
定时器的实现
这里的定时器用于实现关闭已经断开连接的客户端(客户端的非正常关闭会导致服务器不知道其已经关闭)。定时器有三个结构体(类) - 客户数据、定时器和定时器链表：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| struct client_data
{
sockaddr_in address;
int sockfd;
char buf[ BUFFER_SIZE ];
util_timer* timer;
};
class util_timer
{
public:
util_timer() : prev( NULL ), next( NULL ){}
public:
time_t expire;
void (*cb_func)( client_data* );
client_data* user_data;
util_timer* prev;
util_timer* next;
};
class sort_timer_lst
{
...
};
|
client_data是客户数据，有socket描述符、地址信息、buffer和定时器指针；util_timer是定时器类，有过期时间(expire)，客户数据指针(user_data)，事件处理回调函数(cb_func)以及用于链表的prev和next指针。通过它们的定义我们可以看出，客户数据可以访问其定时器；定时器也可以访问其绑定的客户数据。所有的定时器都被添加到sort_timer_lst中，我们可以通过遍历链表找到我们需要的定时器。
sort_timer_lst有下面几个成员函数：
1
2
3
4
5
| void add_timer(util_timer* timer);
void adjust_timer(util_timer* timer);
void del_timer(util_timer* timer);
void tick();
void add_timer(util_timer* timer, util_timer* lst_head);
|
void add_timer(util_timer* timer)将定时器按照过期时间从小到大的顺序插入链表，对于插入位置不在头节点的定时器，需要调用void add_timer(util_timer* timer, util_timer* lst_head)，这个函数的时间复杂度是O(n)；void adjust_timer(util_timer* timer)用于调整定时器的过期时间，调整后需要用add_timer()将其重新添加到链表；void del_timer(util_timer* timer)用于删除定时器，定时器超时的时候会用到这个函数；tick()是心跳函数，其实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| void tick()
{
if( !head )
{
return;
}
printf( "timer tick\n" );
time_t cur = time( NULL );
util_timer* tmp = head;
while( tmp )
{
if( cur < tmp->expire )
{
break;
}
tmp->cb_func( tmp->user_data );
head = tmp->next;
if( head )
{
head->prev = NULL;
}
delete tmp;
tmp = head;
}
}
|
tick()函数通过判断当前时间和过期时间来确定定时器是否已经超时。对于超时的定时器，首先需要调用它的回调函数(断开连接等)，然后再将其从链表中删除。
定时器实例
下面这个例子简单地说明了如何使上面定义的定时器，我们这里简单地看看定时器是怎么处理到期的：
- 建立socket连接并调用
alarm()；
- 使用
epoll()进行多路复用，1）接收到新的连接；2）进程定时器到期；3）正常读就绪。
alarm()设置的时间到期，产生SIGALRM信号；信号处理函数使用本地管道发送信息给主进程，表示定时器到期了；- 多路复用的2）就绪，标记定时器到期了；
- 定时器的处理函数遍历链表，结束并删除已经超时的连接；
- 再次调用
alarm()来定时。
这个设计精度不高，因为1）即使收到了SIGALRM信号，还需要在epoll_wait()处等待，如果有新的连接来，还需要等待新的连接完成；2）链表操作效率低，每次添加/修改/查询都需要O(n)的时间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
| void sig_handler( int sig )
{
int save_errno = errno;
int msg = sig;
send( pipefd[1], ( char* )&msg, 1, 0 );
errno = save_errno;
}
void timer_handler()
{
timer_lst.tick();
alarm( TIMESLOT );
}
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[] )
{
addsig( SIGALRM );
addsig( SIGTERM );
bool stop_server = false;
client_data* users = new client_data[FD_LIMIT];
bool timeout = false;
alarm( TIMESLOT );
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 );
addfd( epollfd, connfd );
users[connfd].address = client_address;
users[connfd].sockfd = connfd;
util_timer* timer = new util_timer;
timer->user_data = &users[connfd];
timer->cb_func = cb_func;
time_t cur = time( NULL );
timer->expire = cur + 3 * TIMESLOT;
users[connfd].timer = timer;
timer_lst.add_timer( timer );
}
else if( ( sockfd == pipefd[0] ) && ( events[i].events & EPOLLIN ) )
{
int sig;
char signals[1024];
ret = recv( pipefd[0], signals, sizeof( signals ), 0 );
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 );
util_timer* timer = users[sockfd].timer;
else
{
if( timer )
{
time_t cur = time( NULL );
timer->expire = cur + 3 * TIMESLOT;
printf( "adjust timer once\n" );
timer_lst.adjust_timer( timer );
}
}
}
else
{
}
}
if( timeout )
{
timer_handler();
timeout = false;
}
}
}
|
基于时间轮和最小堆的定时器
链表实现的定时器，效率较低，我们可以使用更好的数据结构来优化定时器容器的操作。除了链表，最常见的就是时间轮和最小堆，也有用红黑树实现的。我这里就不贴时间轮和最小堆定时器的源代码了，只要搞懂了链表定时器怎么实现以及相应的数据结构，设计其他类型的定时器也就很容易了。
之后需要阅读相关开源库的代码，看看真正的项目中是如何设计、使用定时器的。
