时间轮 (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,可以在注册的回调函数中再次的注册自己。