时间轮 (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) 。在 [5] 中,给出了一个简单定时器轮实现的定时。下图 3 是一个简单的时间轮定时器:
图 3. 简单时间轮
![](http://image55.360doc.cn/DownloadImg/2012/09/1707/26878772_1.jpg)
如果需要支持的定时器范围非常的大,上面的实现方式则不能满足这样的需求。因为这样将消耗非常可观的内存,假设需要表示的定时器范围为:0 – 2^3-1ticks,则简单时间轮需要 2^32 个元素空间,这对于内存空间的使用将非常的庞大。也许可以降低定时器的精度,使得每个 Tick 表示的时间更长一些,但这样的代价是定时器的精度将大打折扣。现在的问题是,度量定时器的粒度,只能使用唯一粒度吗?想想日常生活中常遇到的水表,如下图 4:
图 4. 水表
![](http://image55.360doc.cn/DownloadImg/2012/09/1707/26878772_2.jpg)
在上面的水表中,为了表示度量范围,分成了不同的单位,比如 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:
图 5. Linux 时间轮
![](http://image55.360doc.cn/DownloadImg/2012/09/1707/26878772_3.jpg)
由上面的分析,可以看到各种定时器实现算法的复杂度:
表 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 [ 2 ]接口的定时器,只具有进程的语义,如果想在多线程环境下也 n 能使用,可以使用 Linux 提供的 timerfd_create(2) 接口。如果需要支持的定时器数量非常的大,可以考虑使用基于最小堆和时间轮的方式来实现。
描述 | 名字 | 大小 | 下载方法 |
---|---|---|---|
样例代码 | test-signal.c | 7KB | HTTP |
![]() | ||||
![]() | 关于下载方法的信息 | ![]() |
- George Varghese , Tony Lauck. Hashed and Hierarchical Timing Wheels: Efficient Data Structures for Implementing a Timer Facility ,这篇论文分析了各种定时器实现方法,并提出了时间轮的概念。如果你想很好的实现一个定时器,这篇论文你需要反复阅读。
- Open Group 对 POSIX timer 的描述 ,如果你对 UNIX 的标准有兴趣,推荐你在该网站下一份最新的 Specifications,并且,这份 Specifications 的描述相当容易读,linux 应用层的编程,它是我除了 Steven 的书之外的第一选择。
- http://www.pjsip.org/ 是一个 Open Source 的 VoIP 项目,如果你不关心 VoIP,该项目中提供的 pjlib 库也值得关注,它是一个在嵌入式环境下的通用基础库实现的典范。
- http://www.monkey.org/~provos/libevent/ 最出名的事件通知库之一,它的内部使用基于最小堆实现的优先级队列处理包括时间,信号等各种事件。
- Bo Berry 在文章“An embedded Single Timer Wheel” 中描述了一个简单时间轮算法实现的定时器。
- Linux 2.6.31-rc6 的源代码。
- http://lwn.net/Articles/156329/Ingo Molnar 对 linux 中的时间轮的实现做了最好的解释。
- Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein 著.算法导论 ( 第二版 ) .北京:机械工业出版社,2006:73-82 。
![]() | ||
| ![]() | 赵军,2005 年毕业于华中科技大学电气与电子工程学院,有 3 年基于 Linux 的 Router 开发经验,开发过基于 Linux 的高清 / 标清视频解码器,现在则开发基于 Linux 的图像处理平台,一直关注 Linux 在网络方面的发展。 |