文章目录

• 1、时间轮算法基本思想
• 2、定时器的添加
• 3、定时器到期处理

孙玄：毕业于浙江大学，现任转转公司首席架构师，技术委员会主席，大中后台技术负责人（交易平台、基础服务、智能客服、基础架构、智能运维、数据库、安全、IT 等方向）；前58集团技术委员会主席，高级系统架构师；前百度资深研发工程师；

1、时间轮算法基本思想

对于一个复杂的软件系统，定时器的对任务的管理和调度至关重要，通常定时器的管理已成为一个复杂系统的重要基础设施。

定时器有很多种（一文完全理解定时器实现技术），基于升序的定时器时间链表是一种最直接的实现方式：即按照定时器时间到的时间顺序依次存放在一个链表中进行管理。但是这种链表存在效率的不足，就是当插入定时器的时候时间复杂度是O(n). 因此需要一种更高效地管理定时器的数据结构和算法，这里结合Linux内核中基于时间轮的定时器管理器的具体实现，介绍一种基于时间轮的定时器管理算法。图1为时间轮的基本结构：

2、定时器的添加

要加入一个新的定时器，按以下步骤进行处理：

1）计算定时器到期时间和当前 cpu 定时器所经历过的毫秒数的差值，记为 idx

2）根据 idx 的值，选择该定时器应该被放到 tv1-tv5 中的哪一个链表数组中，可以认为 tv1-tv5 分别占据一个32 位数的不同比特位，tv1 占据最低的 8 位，tv2 占据紧接着的 6 位，然后 tv3 再占位，以此类推，最高的 6位分配给 tv5。最终的选择规则如下表所示：

确定链表数组后，接着要确定把该定时器放入数组中的哪一个链表中，如果时间差 idx 小于 256，按规则要放入 tv1 中，因为 tv1 包含了 256 个链表，所以可以简单地使定时器的 expires 的低 8 位作为数组的索引下标，把定时器链接到 tv1 中相应的链表中即可。如果时间差 idx 的值在 256-18383 之间，则需要把定时器放入 tv2中，同样的，使用定时器的 expires 的 8-14 位作为数组的索引下标，把定时器链接到 tv2 中相应的链表中,。定时器要加入 tv3 tv4 tv5使用同样的原理。经过这样分组后的定时器，在后续的 tick 事件中，系统可以很方便地定位并取出相应的到期定时器进行处理。代码如下：