时间轮 (Timing-Wheel) 算法类似于一以恒定速度旋转的左轮手枪，枪的撞针则撞击枪膛，如果枪膛中有子弹，则会被击发；与之相对应的是：对于 PerTickBookkeeping，其最本质的工作在于以 Tick 为单位增加时钟，如果发现有任何定时器到期，则调用相应的 ExpiryProcessing 。设定一个循环为 N 个 Tick 单元，当前时间是在 S 个循环之后指向元素 i (i>=0 and i<= N - 1)，则当前时间 (Current Time)Tc 可以表示为：Tc = S*N + i ；如果此时插入一个时间间隔 (Time Interval) 为 Ti 的定时器，设定它将会放入元素 n(Next) 中，则 n = （Tc + Ti）mod N = (S*N + i + Ti) mod N = (i + Ti) mod N 。如果我们的 N 足够的大，显然 StartTimer，StopTimer，PerTickBookkeeping 时，算法复杂度分别为 O(1)，O(1)，O(1) 。下图是一个简单的时间轮定时器：

如果需要支持的定时器范围非常的大，上面的实现方式则不能满足这样的需求。因为这样将消耗非常可观的内存，假设需要表示的定时器范围为：0 – 2^3-1ticks，则简单时间轮需要 2^32 个元素空间，这对于内存空间的使用将非常的庞大。也许可以降低定时器的精度，使得每个 Tick 表示的时间更长一些，但这样的代价是定时器的精度将大打折扣。现在的问题是，度量定时器的粒度，只能使用唯一粒度吗？想想日常生活中常遇到的水表，如下图 4：

在上面的水表中，为了表示度量范围，分成了不同的单位，比如 1000，100，10 等等，相似的，表示一个 32bits 的范围，也不需要 2^32 个元素的数组。实际上，Linux 的内核把定时器分为 5 组，每组的粒度分别表示为：1 jiffies，256 jiffies，256*64 jiffies，256*64*64 jiffies，256*64*64*64 jiffies，每组中桶的数量分别为：256，64，64，64，64，这样，在 256+64+64+64+64 = 512 个桶中，表示的范围为 2^32 。有了这样的实现，驱动内核定时器的机制也可以通过水表的例子来理解了，就像水表，每个粒度上都有一个指针指向当前时间，时间以固定 tick 递增，而当前时间指针则也依次递增，如果发现当前指针的位置可以确定为一个注册的定时器，就触发其注册的回调函数。 Linux 内核定时器本质上是 Single-Shot Timer，如果想成为 Repeating Timer，可以在注册的回调函数中再次的注册自己。内核定时器如下图 5：

由上面的分析，可以看到各种定时器实现算法的复杂度：

表 1. 定时器实现算法复杂度

实现方式 StartTimer StopTimer PerTickBookkeeping

基于链表 O(1) O(n) O(n)

基于排序链表 O(n) O(1) O(1)

基于最小堆 O(lgn) O(1) O(1)

基于时间轮 O(1) O(1) O(1)

如果需要能在线程环境中使用的定时器，对于基于链表的定时器，可能需要很小心的处理信号的问题；而 POSIX timer 接口的定时器，只具有进程的语义，如果想在多线程环境下也 n 能使用，可以使用 Linux 提供的 timerfd_create接口。如果需要支持的定时器数量非常的大，可以考虑使用基于最小堆和时间轮的方式来实现。

时间轮实现

用c++描述软件定时器设计如下：

class TimeoutHandler // 使用接口的方式而不是boost::function，一方面是出于效率考虑，另一方面是这样便于理解

{

public:

virtual ~TimeoutHandler(){}

virtual void onTimeout() = 0;

};

class TimerMonitor

{

int setTimer(int inteval, boost::shared_ptr<TimeoutHandler> handler); // 为何用智能指针？这种回调类的都很怕回调的时候对象被析构，智能指针是最简单解决办法

void stopTimer(int timer_id); // 删除，根据setTimer返回的timer_id进行删除，函数返回后保证不会再调用handler->onTimeout()

void run(int check_inteval); // 以设置好的检测周期开始监控线程

void stop(); // 停止监控线程

};

那具体如何实现TimerMonitor呢？

最简单低效的做法就是维持一个数组/非排序列表：定时器线程一直跑，检测超时时轮询所有设置的时间，如果超过了就执行相应回调函数。这种算法每次检测要遍历所有设置的时间，无疑是低效的0(n)。插入O(1)删除O(n)。

稍微高级的做法就是使用排序链表，最前面就是最近要到期的，检测超时时不需要轮询，只需要看看头几个结点即可(可视为O(1))。插入和删除O(n)。

之前我知道的比较好的方法是最小堆，检测超时时也是O(1)，插入0(lgn)，删除O(n)——注意如果不引入其他数据结构的情况下只能通过遍历找到timer_id对应结点。

今天刚知道的：Timing-Wheel时间轮算法，参考http://www.ibm.com/developerworks/cn/linux/l-cn-timers/。我感觉这个算法是很聪明的算法，水表的例子也非常好。我一开始看时间轮算法以为是类似TRIE的算法，后面又以为是多级Hash算法，但其实都似是而非。

Timing Wheels的本质有点像水表：高维度一单位等于低维度的一圈。

举个例子来说明吧，假设总共有两个维度，每个维度三个槽。

第一维：

slot 1-1 ：链表，放置在0间隔后过期的handler

slot 1-2 ：链表，放置在1间隔后过期的handler

slot 1-3 ：链表，放置在2间隔后过期的handler

第二维：

slot 2-1 ：链表，放置3-4-5间隔后过期的handler

slot 2-2 ：链表，放置6-7-8间隔后过期的handler

slot 2-3 ：链表，放置9-10-11间隔后过期的handler

注意slot1-1，slot2-1 并不是固定的，而是由这一维度的当前指向位置决定的，可以把每一个维度当做一个循环队列。步进的时候就是最低维+1，但这个+1可能会导致进位甚至连环进位。

假设有一个2*2*2的时间轮，步进时顺序是这样 0-0-0（初始) -> 1-0-0 -> 0-1-0（进位) -> 1-1-0 -> 0-0-1(连环进位))

发生进位的时候要把高纬度那个槽里的handler抓来处理，如果时间到了就触发，还没到就塞进低维度的槽中。还举3*3的例子，当触发slot2-1的时候，所有3的定时器触发，4的塞到slot1-2，5的就塞到slot1-3。

发布时间: 9年前【游戏相关】125人已围观【返回】【回到顶端】

转载：个人转载请注明文章出处 "www.itarticle.cc-IT技术类文章收集&分享"。

很赞哦！ (1)