Linux 网络编程学习笔记——十一、定时器

BeZer0 SpaceLinux 网络编程学习笔记 | BeZer0 Space
Linux 网络编程学习笔记 | BeZer0 Space
Linux 网络编程学习笔记
BeZer0 Space

网络程序需要处理的第三类事件是定时事件，比如定期检测一个客户连接的活动状态。服务器程序通常管理着众多定时事件，因此有效地组织这些定时事件，使之能在预期的时间点被触发且不影响服务器的主要逻辑，对于服务器的性能有着至关重要的影响。为此，要将每个定时事件分别封装成定时器，并使用某种容器类数据结构，比如链表、排序链表和时间轮，将所有定时器串联起来，以实现对定时事件的统一管理。本章主要讨论的就是两种高效的管理定时器的容器：时间轮和时间堆。

不过，在讨论如何组织定时器之前，我们先要介绍定时的方法。定时是指在一段时间之后触发某段代码的机制，我们可以在这段代码中依次处理所有到期的定时器。换言之，定时机制是定时器得以被处理的原动力。Linux 提供了三种定时方法，它们是：

socket 选项 SO_RCVTIMEO 和 SO_SNDTIMEO；

SIGALRM 信号；

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

一、socket 选项 SO_RCVTIMEO 和 SO_SNDTIMEO

socket 选项 SO_RCVTIMEO 和 SO_SNDTIMEO 分别用来设置 socket 接收数据超时时间和发送数据超时时间。因此，这两个选项仅对与数据接收和发送相关的 socket 专用系统调用（socket API）有效，这些系统调用包括 send 、sendmsg 、recv 、recvmsg 、 accept 和 connect 。我们将选项 SO_RCVTIMEO 和 SO_SNDTIMEO 对这些系统调用的影响总结如下：

系统调用	有效选项	系统调用超时后的行为
send	SO_SNDTIMEO	返回 -1 ，设置 errno 为 EGAIN 或 EWOULDBLOCK
sendmsg	SO_SNDTIMEO	返回 -1 ，设置 errno 为 EGAIN 或 EWOULDBLOCK
recv	SO_RCVTIMEO	返回 -1 ，设置 errno 为 EGAIN 或 EWOULDBLOCK
recvmsg	SO_RCVTIMEO	返回 -1 ，设置 errno 为 EGAIN 或 EWOULDBLOCK
accept	SO_RCVTIMEO	返回 -1 ，设置 errno 为 EGAIN 或 EWOULDBLOCK
connect	SO_SNDTIMEO	返回 -1 ，设置 errno 为 EINPROGRESS

因此在程序中可以根据系统调用的返回值以及 errno 来判断超时时间是否已到，进而决定是否开始处理定时任务：

二、SIGALRM 信号

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

本节中通过实例：处理非活动连接，来介绍如何使用 SIGALRM 信号定时。不过需要先给出一种简单的定时器实现：基于升序链表的定时器，并把它应用到处理非活动连接这个实例中。这样才能观察到 SIGALRM 信号处理函数是如何处理定时器并执行定时任务的。此外这种定时器也是为了和后面要讨论的高效定时器：时间轮和时间堆做对比。

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

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

为了便于阅读，我们将实现包含在头文件中。sort_timer_lst 是一个升序链表。其核心函数 tick 相当于一个心搏函数，它每隔一段固定的时间就执行一次，以检测并处理到期的任务。判断定时任务到期的依据是定时器的 expire 值小于当前的系统时间。从执行效率来看，添加定时器的时间复杂度是，删除定时器的时间复杂度是，执行定时任务的时间复杂度是。

2. 处理非活动连接

现在我们考虑上述升序定时器链表的实际应用：处理非活动连接。服务器程序通常要定期处理非活动连接：给客户端发一个重连请求，或者关闭该连接，或者其他。Linux 在内核中提供了对连接是否处于活动状态的定期检查机制，我们可以通过 socket 选项 KEEPALIVE 来激活它。不过使用这种方式将使得应用程序对连接的管理变得复杂。因此，可以考虑在应用层实现类似于 KEEPALIVE 的机制，以管理所有长时间处于非活动状态的连接。比如，下述代码利用 alarm 函数周期性地触发 SIGALRM 信号，该信号的信号处理函数利用管道通知主循环执行定时器链表上的定时任务：关闭非活动的连接：

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

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

四、高性能定时器

1. 时间轮

前文提到，基于排序链表的定时器存在一个问题：添加定时器的效率偏低。为解决这个问题，一种简单的时间轮如下：

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

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

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

上图描述的是一种简单的时间轮，因为它只有一个轮子。而复杂的时间轮可能有多个轮子，不同的轮子拥有不同的粒度。相邻的两个轮子，精度高的转一圈，精度低的仅往前移动一槽，就像水表一样。代码如下所示：

可见，对时间轮而言，添加一个定时器的时间复杂度是，删除一个定时器的时间复杂度也是，执行一个定时器的时间复杂度是。但实际上执行一个定时器任务的效率要比好得多，因为时间轮将所有的定时器散列到了不同的链表上。时间轮的槽越多，等价于散列表的入口（entry）越多，从而每条链表上的定时器数量越少。此外代码仅使用了一个时间轮。当使用多个轮子来实现时间轮时，执行一个定时器任务的时间复杂度将接近。

2. 时间堆

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

最小堆很适合处理这种定时方案。最小堆是指每个节点的值都小于或等于其子节点的值的完全二叉树。使用最小堆实现定时器的代码如下：

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

BeZer0 SpaceLinux 网络编程学习笔记 | BeZer0 Space
Linux 网络编程学习笔记 | BeZer0 Space
Linux 网络编程学习笔记
BeZer0 Space

一、socket 选项 SO_RCVTIMEO 和 SO_SNDTIMEO