浅析Linux中的时间编程和实现原理（三） Linux内核的工作

处理Timer的逻辑在时钟中断程序中，每次时钟中断产生时，cursor 增加一格，然后中断处理代码检查 cursor 所指向的 bucket，假如该 bucket 非空，则触发该 bucket 指向的 Timer 链表中的所有 Timer。这个操作也是 O(1) 的。

全都是 O(1) 操作？那这个算法岂不是完美的？可惜不是，我们的这个时间轮有一个限制：新 Timer 的到期时间必须在 8 秒之内。这显然不能满足实际需要，在 Linux 系统中，我们可以设置精度为 1 个 jiffy 的定时器，最大的到期时间范围可以达到 (2^32-1/2 ) 个 jiffies(一个很大的值)。如果采用上面这样的时间轮，我们需要很多个 bucket，需要巨大的内存消耗。这显然是不合理的。

为了减少 bucket 的数量，时间轮算法提供了一个扩展算法，即 Hierarchy 时间轮。图 1 里面的轮实际上也可以画成一个数组，

图 2. 时间轮的另一种表示

Hierarchy 时间轮将单一的 bucket 数组分成了几个不同的数组，每个数组表示不同的时间精度，下图是其基本思路：

图 3. Hierarchy 时间轮

这样的一个分层时间轮有三级，分别表示小时，分钟和秒。在 Hour 数组中，每个 bucket 代表一个小时。采用原始的时间轮，如果我们要表示一天，且 bucket 精度为 1 秒时，我们需要 24*60*60=86,400 个 bucket；而采用分层时间轮，我们只需要 24+60+60=144 个 bucket。

让我们简单分析下采用这样的数据结构，Timer 的添加/删除/处理操作的复杂度。

添加Timer

根据其到期值，Timer 被放到不同的 bucket 数组中。比如当前时间为 (hour:11, minute:0, second:0)，我们打算添加一个 15 分钟后到期的 Timer，就应添加到 MINUTE ARRAY 的第 15 个 bucket 中。这样的一个操作是 O(m) 的，m 在这里等于 3，即 Hierarchy 的层数。

图 4. 添加 15 分钟到期 Timer

（编辑：佛山站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!