定时器

网络程序需要处理的一类事件是定时事件，比如定期检测一个客户连接的活动状态。服务器程序通常管理众多定时事件，因此有效地组织这些事件，使之能在预期的时间点被触发且不影响服务器的主要逻辑，对于服务器的性能有着至关重要的影响。

定时指在一段时间之后触发某段代码的机制，我们可以在这段代码中依次处理所有到期的定时器。换言之，定时机制是定时器得以被处理的原动力。Linux提供了三种定时方法：

• socket 选项SO_RCVTIMEO、SO_SNDTIMEO

• SIGALRM信号

• I/O复用系统调用的超时参数

1. socket选项SO_RCVTIMEO和SO_SNDTIMEO

socket选项SO_RCVTIMEO和SO_SNDTIMEO，他们分别用来设置socket接收数据超时事件和发送数据超时时间。因此，这两个选项仅对与数据接收和发送相关的socket专用系统调用有效（send、sendmsg、recv、recvmsg、accept和connect）。

在程序中，可以根据系统调用(send、recv、...)的返回值以及errno来判断超时时间是否已到，进而决定是否开始处理定时任务。

示例代码

2. SIGALRM信号

由alarm和setitimer函数设置的实时⏰一旦超时，将触发SIGALRM信号。因此，我们可以利用该信号的信号处理函数来处理定时任务。

但是要处理多个任务，就需要不断地触发SIGALRM信号，并在其信号处理函数中执行到期的任务。一般而言，SIGALRM信号按照固定的频率生成，即由alarm或setitimer函数设置的定时周期T保持不变。如果某个定时任务的超时时间不是T的整数倍，那么它实际被执行的时间和预期的时间将略有偏差。因此定时周期T反映了定时的精度。

2.1. 基于升序链表的定时器

定时器至少要包含两个成员：一个超时时间（相对或绝对）和一个任务回调函数。有时候还可能包含回调函数被执行时需要传入的参数，以及是否重启定时器等信息。如果使用链表作为容器来串联所有的定时器，则每个定时器还要包含指向下一个定时器的指针。

示例代码

代码中，sort_timer_lst是一个升序链表，其核心函数tick相当于一个心搏函数，每隔一段固定的时间就执行一次，以检测并处理到期的任务。判断定时任务到期的依据是定时器的expire值小于当前的系统时间。

从执行效率来看，添加一个定时器的时间复杂度是O(n)，删除定时器的时间复杂度是O(1)，执行定时任务的时间复杂度是O(1)。

2.2. 处理非活动连接

考虑使用上一节的升序定时器链表来处理非活动连接。服务器程序通常要定期处理非活动连接：给客户端发送一个重连请求，或者关闭该连接，或者其它。Linux在内核提供了对连接是否处于活动状态的定期检查机制，我们可以通过socket选项KEEPALIVE来激活它。不过使用这种方式将使得应用程序对连接的管理变得复杂。因此，我们可以考虑在应用层实现类似与KEEPALIVE机制，以管理所有长时间处于非活动状态的连接。

下面示例代码利用 alarm 函数周期性的触发SIGALRM信号，该信号的信号处理函数利用管道通知主循环执行定时器链表上的定时任务---关闭非活动连接。

示例代码

可以将上述代码运行并监听 127.0.0.1 某个端口，并多开几个终端去 telnet 该地址，发送数据查看。

3. I/O复用系统调用的超时参数

Linux下的3组I/O复用系统调用都带有超时参数，因此它们不仅能统一处理信号和I/O事件，也能统一处理定时事件。但是由于I/O复用系统调用可能在超时时间到期之前就返回（有I/O事件发生），所以如果我们要利用它们来定时，就需要不断更新定时参数以反映剩余的事件。

如下代码，可能需要配合前两节代码来理解。

#define TIMEOUT 5000

int timeout = TIMEOUT;
time_t start = time (NULL);
time_t end = time (NULL);

while (1) {
    printf ("the timeout is now %d mil-seconds\n", timeout);
    start = time (NULL);
    int number = epoll_wait (epollfd, events, MAX_EVENT_NUMBER, timeout);
    if ((number < 0>) && (errno != EINTR)) {
        printf ("epoll failure\n");
        break;
    }
    // 如果 epoll_wait 成功返回0,则说明超时时间到，
    // 此时便可以处理定时任务，并重置定时时间
    if (number == 0) {
        timeout = TIMEOUT;
        continue;
    }
    end = time(NULL);
    /*如果epoll_wati的返回值大于0,则本次epoll_wait调用持续时间是
    (end-start)*100ms，我们需要将定时时间timeout减去这段时间，
    以获得下次epoll_wait调用的超时参数*/
    timeout -= (end - start) * 1000;
    /*重新计算之后的timeout值就有可能等于0,说明本次epoll_wait调用返回时，
    不仅有文件描述符就绪，而且其超时时间也刚好到达，此时我们也要处理定时任务，
    并重置定时时间。*/
    if (timeout <= 0) {
        timeout = TIMEOUT;
    }
    // handle connections
}

4. 高性能定时器

4.1. 时间轮

基于排序链表的定时器存在一个问题，添加定时器的效率偏低。时间轮方法解决了这个问题，简单的时间轮如图所示。

指针（实线）指向轮子上的一个槽(slot)，它以恒定的速度顺时间转动，每转动一步就指向下一个槽（虚线指针指向的槽），每次转动称为一个滴答(tick)。一个滴答的时间称为时间轮的槽间隔 si (slot interval)，它实际上就是心搏时间。该时间轮共有N个槽，因此它运转一周需要的时间是N*si。每个槽指向一条定时器链表，每条链表上的定时器具有相同的特征：它们的定时时间相差 N*si 的整数倍。时间轮正是利用这个关系将定时器散列到不同的链表中。假如现在指针指向槽 cs，我们要添加一个定时时间为 ti 的定时器，则该定时器被插入到槽 ts (timer slot) 对应的链表中：

$ts = (cs + (ti/si)) \% N$

基于排序链表的定时器使用唯一的一条链表来管理所有定时器，所以插入操作的效率随着定时器数目的增多而降低。而时间轮使用哈希表的思想，将定时器散列到不同的链表上。这样每条链表上的定时器数目都将明显小于原来的排序链表上的定时器数目，插入操作的效率基本不受定时器数目的影响。

很显然，对时间轮而言，要提高定时精确，就要使si足够小：要提高执行效率，则要求N值足够大。

复杂的时间轮可能有多个轮子，不同的轮子拥有不同的粒度。相邻的两个轮子，精确度高的转一圈，精度低的仅往前移动一槽，就像水表一样。

对简单时间轮而言，添加一个定时器的时间复杂度是O(1)，删除一个定时器的时间复杂度也是O(1)，执行一个定时器的时间复杂度是O(n)。但实际执行一个定时器任务的效率比O(n)好得多，因为时间轮将所有的定时器散列到了不同的链表上。时间轮的槽月多，等价于散列表的入口越多，从而每条链表上的定时器数量越少。当使用多个轮子来实现时间轮时，执行一个定时器任务的时间复杂度将接近O(1)。

4.2. 时间堆

前面说的都是以固定频率调用心搏函数tick，并在其中依次检测到期的定时器，然后执行期定时器上的回调函数。设计定时器的另外一种思路是：将所有定时器中超时时间最小的定时器的超时值作为心搏间隔。这样，一旦心搏函数tick被调用，超时时间最小的定时器必然到期，我们就可以在tick函数中处理该定时器。然后，再次从剩余的定时器中找到超时时间最小的一个，并将这段时间最小设置为下一次心搏间隔。如此反复，就实现了较为精确的定时。

最小堆很适合处理这种方案。最小堆是指每个节点的值都小于或等于其子结点的值的完全二叉树。

由于最小堆是一种完全二叉树，所以可以采用数组来组织其中的元素。与用链表来表示堆相比，用数组表示堆不仅节省空间，而且更容易实现堆的插入、删除等操作。

假设我们已经有一个包含 N 个元素的数组，现在要把它初始化为一个最小堆。可以初始化一个空堆，然后将数组的每个元素插入，不过这样效率偏低。实际上，只需要对数组的第[(N-1)/2]~0个元素执行下滤操作，即可确保该数组构成一个堆。这是因为对包含 N 个元素的完全二叉树而言，它具有[(N-1)/2]个非叶子节点，这些非叶子节点正是该完全二叉树的第0~[(N-1)/2]个节点。我们只要保证这些非叶子节点构成的子树都具有堆序性质，整个树就具有堆序性质。

对于时间堆而言，添加一个定时器的时间复杂度是O(lgn)，删除一个定时器的时间复杂度O(1)，执行一个定时器的时间复杂度是O(1)。因此，时间堆效率是很高的。