3G Eden
RSS时间轮 (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. 简单时间轮
如果需要支持的定时器范围非常的大，上面的实现方式则不能满足这样的需求。因为这样将消耗非常可观的内存，假设需要表示的定时器范围为：0 – 2^3-1ticks，则简单时间轮需要 2^32 个元素空间，这对于内存空间的使用将非常的庞大。也许可以降低定时器的精度，使得每个 Tick 表示的时间更长一些，但这样的代价是定时器的精度将大打折扣。现在的问题是，度量定时器的粒度，只能使用唯一粒度吗？想想日常生活中常遇到的水表，如下图 4：
图 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：
图 5. Linux 时间轮
由上面的分析，可以看到各种定时器实现算法的复杂度：
表 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 在网络方面的发展。 |
