在后台开发中，定时器是我们基本上避不开的一个概念，无论是用什么语言，都会遇到需要自行定时任务的情形。在 Python 中，在我的博客中已经多次介绍过了 Celery，他可以帮助我们快速方便得基于消息队列实现定时任务，但是，毕竟还是有外部依赖的。假设我们需要开发一个中偏小型应用的时候，使用定时任务，那么上这么组件有点显得杀鸡用牛刀的感觉，所以，我就参考了一些资料，对在 Linux 下实现定时器进行了一些总结，和大家分享一下。

概述

总的来说，在 Linux 要实现定时器，虽然实现方式可能有所不同，但是很多在原理上都是一致的，可以当成一种，这样一来，可以笼统得归纳成三类，分别是：

1. 精确度比较高的 IO 复用系统调用
2. 比较常见的 SIGALRM 信号
3. 针对网络的 socket 选项 SO_RCVTIMEO 和 SO_SNDTIMEO

对于第一种和第三种可发挥的空间可能没有那么大，毕竟相对来说他们较多用于 IO 方面，而我们定时的操作需要复合各种场景，所以，在这篇文章中，我着重在 SIGALRM 信号上发挥，讨论一下定时的几种实现。

基于 SIGALRM 信号呢，具体实现起来方法也很多，这里我主要讨论一下以下几种方式：

1. 基于链表
2. 基于排序链表
3. 基于时间轮
4. 基于最小堆

这里为了简便说明，我们的定时器的功能很简单，就假设有5 个定时任务，分别是 a～e，然后分别隔：2/3/5/7/9 秒执行一次。其实这是高度抽象后的结果，因为即时是我们在 Linux 中的 crontab 的 分 时 日 月 周 我们也可以将它转换为这种形式，而且，也是这么做的。

基于链表的定时器实现

在开始链表之前，我们先来熟悉以下 alarm 和 timer 的使用，在 Linux 中，其实这两个东西共享的是同一个 timer，所以使用谁都一样，所以我就任选一个了，下面直接先上代码：

这是一份简略版的代码，先看下核心代码 Line 41，这里设置了一个每秒钟一次的 tick，然后在 Line 39 设置了信号回调函数：

所以，可以清楚 sig_func 这个函数每秒钟都会被调用一次。然后看下里面的内容，可以发现，其实就是遍历链表里面的一个个定时任务，看他们时候需要执行，不需要执行就刷新一下 tick 数；需要执行就调用一下回调函数。

这就是基于链表的定时器实现，通过这个实例，我们可以发现一些问题：

1. 每秒钟都需要遍历一次链表，数量多了怎么办？
2. 定时时间只能是 tick 的倍数，这里 tick 是 1 秒好处理，如果 tick 是 5 秒就坑了
3. 删除一个定时任务也需要遍历一次链表，不是很高效

基于有序链表的定时器实现

在上面基于链表的实现中，我们发现了一些问题，那么如果能够改进一下，不就是一个更好的方案么？从这点出发，我们思考一下这些缺点中哪些是可以很快速的解决的？

1. 对于缺点一，这个问题可以抽象成顺序查找的性能低，如果链表是有序的，那么可以优化！
2. 这个 tick 和数据结构没有关系，是 alarm 机制决定的，比较难解决。
3. 在一个链表中删除一个指定元素，无论是有序无序还是单向双向链表都比较难优化。

那么，我们就可以将这个链表转换成有序的链表，排序的键可以设置为：node->interval - node->elapse，这样我们就更进一步了，现在这个多了一个优点：

1. 执行一个任务的时间是 O(1)

但是，考虑到我们一般都是添加任务少，执行任务多的情况，那么这种转换是值得的！

基于时间轮的定时器实现

单层时间轮实现

前面基于有序／无序的链表的定时器实现问题相对来说比较多，添加复杂度高，执行复杂度相对高。所以，为了更加高效得解决问题，我们考虑再优化一下效果，所以引入了所谓的时间轮的概念。

在时间轮中，我们不用一个链表来保存定时任务了，而是用很多链表，但是，这些链表不是瞎划分的，他们是按照一定的规则来划分的，下面就先来一段代码：

这里核心框架还是没变：

• main 函数绑定 ALARM 的处理函数，并且设置每秒钟的定时器
• addTimer：将任务添加进时间轮中
• timeCb：就是定时被执行的任务了

这里着重讲的有两个：如何将任务添加进时间轮／如果选择要执行的任务

如何将任务添加进时间轮

从这段代码中我们可以看到，关键行在于 8 行，这里根据任务的周期然后计算应该在时间轮转了几圈之后才执行这个任务，而且需要注意的一点就是基于时间轮的 timer 类中不存在 elapse 时间片累加器了，反而是用 周期变量 rotation 代替。

如何选择要执行的任务

这里我们可以看到，选择任务的时候上来就是找到当前时间轮上的 slot，然后对这个 slot 的任务 简单判断轮数 rotation 是否已经到期即可判断是否需要执行。

还有一点很重要的是，在执行完一个任务之后还需要对这个任务进行位置调整，这些操作速度都很快，虽然理论上是 O(n)，但是，实践中可能会趋向于 O(1)。

小结

对比一下基于时间轮的实现和链表的实现，我们可以发现：

1. 查找一个任务的时间变少了
2. 添加／删除一个任务的时间也变少了
3. 内存占用空间变多了，数据结构稍微变复杂了
4. 对于长周期任务，这个时间轮实现会出现多余的判断，所以可以增加不同的轮周期时间轮来提升效率， 就像：

多级时间轮定时器

TODO

基于时间堆的定时器实现

前边介绍了三种实现定时器的方式，讲来讲去都是使用的链表，有可能都让同学们怀疑了，一定要用链表吗？用数组不行？诚然，有序的数组查找效率不错，但是插入性能不行啊；如果不排序，那和链表的查询效率有什么区别？而且链表的插入速度是 O(1)，数组还有可能需要重新分配内存。

但是，凡事都不能只从一面看，有序数组又不一定就是个 array，还可以是 complete binary tree 啊，相对于 array 来说，完全二叉查找树的查找性能好，插入性能稳定，基于这个考虑，所以可以考虑用最小堆来实现，排序的键就用 next_time_to_run，来一个实现：

这里做了几点的小改动：

保留时间的量

• 基于链表的使用的是执行的周期以及定时器经历过的周期
• 基于时间轮的使用的是执行的周期以及下一次执行的剩余轮数
• 这里基于堆的使用的是执行的周期以及下一次执行的 tick 数

这里稍作解释，假如一个任务是在 tick = 3 的时候加进来，周期是 5 个 tick 执行一次，那么三种情况分别对应于：

• interval = 5, elapse = 0
• interval = 5, slot = 8, rotation = 0 【( 3 + 5) % TOTAL_SLOT】
• interval = 5, timeout = 8 【 3 + 5 】

将任务添加进堆中

1. 计算任务下一次执行的 tick，其实就是 timeout = currTick + interval
2. 按照 timeout 排序将任务加入到最小堆中

选择要执行的任务

1. 不断获取堆顶的元素，直到堆顶元素不需要执行
2. 执行任务
3. 更新任务的 timeout，放回到堆中

总结

在本文中，我基于个人的理解小结了一下在 Linux 中实现定时器的几种方式，并且对于每种方式都给出一个完整的代码示例，代码放在 github 上，点击查看。需要说明的是，本文提及的代码都是以验证理论为原则，实现方式较为不严谨，请勿用于工业需要。

Reference

1. settimer
2. cpp stl forwarl list
3. Linux 下定时器的实现方式分析
4. libevent源码学习（三）信号evsignal
5. 本文中的代码示例下载