以下内容请参阅https://www.toutiao.com/I 6914186976950223367 /
Linux计时器分为低精度计时器和高精度计时器两种，内核实现了这一点。 本文介绍了APP应用程序开发中常见的低精度定时器。 作为常用的基础组件，定时器常用的几种实现方法是基于排序链接的实现、基于根堆的实现、基于红黑树的实现、基于时间轮的实现。 本文介绍了时间复杂度最好，linux内核采用的基于时间轮的实现方法。
通过有序链表实现的定时器，增加定时器的时间复杂度为o(n )； 使用由小根山或红黑树实现的计时器，追加计时器的时间复杂度为o(lgn )。 O(1)的复杂性是因为所有的定时器节点都挂在一个链表(或一棵树)上。 时间轮算法的核心思想是将定时器散列到多个链中，是典型的空间变时间策略。 以下将从各个时间轮开始介绍，并逐步扩展到linux实现计时器中使用的多级时间轮算法。
简单的单时间轮单时间轮只有一个通过bucket连接的轮子。 下图所示的时间轮有8个bucket，每个bucket下都链接了将来将过期的节点。 图中邻接的bucket的有效期限的间隔为slot=1s，从现在时刻0s开始计时，1s时有效期限到期的计时器节点在bucket[1]之下，2s时有效期限到期的计时器节点在bucket[2]之下tick的时间为110秒
bucket是一个数组，根据下标直接定位在特定的定时器节点链上，所以添加删除节点、执行定时器超时的时间复杂度都为o(1)。
但是，很明显，这个计时器的使用是有限制的。 添加的timer的有效期必须在8s以内。 这显然不能满足实际需要。 当然扩展也很简单，直接增加bucket的个数就可以了。 在Linux系统上，slot可以为单个Jiffy(1/Hz )设置计时器。 假设最大有效期限范围达到2^32个jiffies，如果采用上述单时间轮，则需要2^32个bucket，这将导致巨大的内存消耗，显然需要优化和改进。
【文章福利】需要C/C++ Linux服务器架构师学习资料加群812855908（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等）
改进的单时间轮改进的单时间轮其实是时间和空间折中的想法。 也就是说，虽然不像单时间轮那样具有o(1)的时间复杂度，但是不像单时间轮那样对bucket的个数有很大的需求。 原理也很简单，各bucket不仅可以连接有效期限expire=slot的计时器，还可以连接expire%N=slot的计时器(n为bucket的个数)。 这也正好适应了时间轮的轮回作用。 如图2所示，计时器的expire表示过期时间，rotation表示节点旋转了多少次后过期。 如果当前时间指针指向包含当前时间指针的bucket，则遍历链表中的节点一次，车轮转速为节点的rotation，而不是像在简单的时间轮中那样直接对bucket下的所有节点执行超时操作
因为在多个时间轮上叙述的时间轮是单枪匹马战斗的，所以无论在时间上还是空间上都很难得到理想的效果。 Linux实现的多时轮算法借鉴了日常生活中水表的测量方法，通过低刻度快速行驶的车轮带动更高刻度的车轮，达到了用较少的刻度显示大范围测量值的效果。
Linux计时器控制盘分为五个级别(tv1 ~ tv5 )，如图3所示。 各级车轮刻度值(slot )不同，规律是次级车轮的slot等于高级车轮的slot之和。 Linux定时器slot的单位为1jiffy，tv1轮分为256个刻度，各刻度的大小为1jiffy。 tv2车轮分为64个刻度，各刻度的大小为256个jiffy，是tv1车轮整体能够表现的范围。 只要相邻的车轮也满足该规律，就可以获得“低刻度车轮旋转一周，高刻度车轮前进一格”的效果。 因为tv3、tv4、tv5都分为64个刻度，所以很容易计算出最上面的车轮tv5能够表现的slot范围达到了25664646464=2^32 jiffies。
Linux时间轮定时器算法的关键是添加定时器操作和时间轮进位迁移链表操作。 首先添加计时器。 添加计时器的关键是知道每个时间轮上每个刻度表示的过期时间范围。 图4显示了每个时间轮可以测量的jiffies的大小。 如果在1000个jiffies之后有过期的计时器的话，很容易理解应该从图4到tv2轮。 tv2轮的每个刻度代表256个jiffies，应该乘以(1000/256 )=3，即第三个bucket。
Linux在计时器的有效期限检查中也得到了巧妙的安装。 如果curr_time=0x12345678，则下一次检查的时刻为0x12345679。 如果tv1.bucket[0x79]的链表不为空，则返回下一个检查时间tv1.bucke
t[0x79]上的定时器节点超时。如果curr_time到了0x12345700，低8位为空，说明有进位产生，这时移出8～13位对应的定时器链表(即正好对应着tv2轮)，重新加入定时器系统，这就完成了一次进位迁移操作。同样地，当curr_time的第8-13位为0时，这表明tv2轮对tv3轮有进位发生，将curr_time第14-19位的值作为下标，移出tv3中对应的定时器链表，然后将它们重新加入到定时器系统中来。tv4,tv5依次类推。之所以能够根据curr_time来检查超时链，是因为tv1~tv5轮的度量范围正好依次覆盖了整型的32位：tv1(1-8位)，tv2(9-14位)，tv3(15-20位)，tv4(21-26位)，tv5(27-32位)；而curr_time计数的递增中，低位向高位的进位正是低级时间轮转圈带动高级时间轮走动的过程。 对比最后比较一下多级时间轮和单个简单时间轮的时间复杂度及空间复杂度：linux使用了总计256+64+64+64+64=512个bucket，即可实现[0，2^32) jiffies的超时范围。相比简单的单时间轮，时间上仅仅多了1/256次(为约等于值，忽略了tv2以上产生的进位操作)的链表迁移操作耗时。可以认为其添加、删除定时器节点及到期check的操作时间复杂度均为O(1)。