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

删除Timer：

Timer 本身有指向 bucket 的指针，因此删除 Timer 是 O(1) 的操作，比如删除我们之前添加的 15 分钟后到期的 Timer，只需要从该 Timer 的 bucket 指针读取到 MINUTE ARRAY Element 15 的指针，然后从该 List 中删除自己即可。

定时器处理：

每个时钟中断产生时（时钟间隔为 1 秒），将 SECOND ARRAY 的 cursor 加一，假如 SECOND ARRAY 当前 cursor 指向的 bucket 非空，则触发其中的所有 Timer。这个操作是 O(1) 的。

可以看到，添加，删除定时器处理的操作复杂度都很低。

难道 Hierarchy 时间轮完美了？可惜还不是。

为了处理 60 秒之外的那些保存在 MINUTES ARRAY 和 HOUR ARRAY 中的 Timer，时钟中断处理还需要做一些额外的工作：每当 SECOND ARRAY 处理完毕，即 cursor 又回到 0 时，我们应该将 MINUTE ARRAY 的当前 cursor 加一，并查看该 cursor 指向的 bucket 是否为空，如果非空，则需要将这些 Timer 移动到前一个 bucket 中。此外 MINUTE ARRAY 的 bucket[0] 的 Timer 这时候应该都移动到 SECOND ARRAY 中。同样，当 MINUTE ARRAY 的 cursor 重新回到 0 时，我们还需要对 HOUR ARRAY 做类似的处理。这个操作是 O(m) 的，其中 m 是 MINUTE ARRAY 或者 HOUR ARRAY 的 bucket 中时钟的个数。多数情况下 m 远远小于系统中所有 active 的 Timer 个数，但的确，这还是一个费时的操作。

Linux 内核采用的就是 Hierarchy 时间轮算法，Linux 内核中用 jiffies 表示时间而不是时分秒，因此 Linux 没有采用 Hour/Minutes/Second 来分层，而是将 32bit 的 jiffies 值分成了 5 个部分，用来索引五个不同的数组（Linux 术语叫做 Timer Vector，简称 TV），分别表示五个不同范围的未来 jiffies 值。

这个时间轮的精度为 1 个 jiffy，或者说一个 tick。每个时钟中断中，Linux 处理 TV1 的当前 bucket 中的 Timer。当 TV1 处理完（类似 SECOND ARRAY 处理完时），Linux 需要处理 TV2，TV3 等。这个过程叫做 cascades。TV2 当前 bucket 中的时钟需要从链表中读出，重新插入 TV2；TV2->bucket[0] 里面的 timer 都被插入 TV1。这个过程和前面描述的时分秒的时间轮时一样的。cascades 操作会引起不确定的延迟，对于高精度时钟来讲，这还是一个致命的缺点。

但时间轮还是所有 Timer 实现的基础，在它的基础上，Linux 提供了间隔 Timer 和 POSIX Timer 供应用程序使用。

动态 Timer、Interval Timer 和 POSIX Timer

早期 Linux 考虑两种定时器：内核自身需要的 timer，也叫做动态定时器；其次是来自用户态的需要, 即 setitimer 定时器，也叫做间隔定时器。2.5.63 开始支持 POSIX Timer。2.6.16 引入了高精度 hrtimer。本节介绍 hrtimer 出现之前 Linux 内核中动态 Timer，间隔 Timer 和 POSIX Timer 的概念，发展和实现原理。

动态 Timer

动态 timer 由内核自身使用，其实也是其他 Timer 的实现基础。使用动态 Timer 的接口函数有三个：

add_timer()

del_timer()

init_timer()

使用时，先调用 init_timer() 初始化一个定时器，指定到期时间和到期处理函数；初始化完成后，内核代码可以用 add_timer() 启动定时器，或者用 del_timer() 来取消一个已经启动的定时器。

add_timer 采用时间轮算法将定时器加入 per CUP 变量 tvec_bases 中，根据其 expire 时间，可能被加入 5 个 Timer Vector 之一。此后，tick 中断将根据时间轮算法处理。当本 timer 到期时，触发其处理函数。

动态 Timer 有两个方面的用途：一是内核自己使用，比如某些驱动程序需要定时服务的时候使用它；二是用来实现用户层 Timer。下面首先讲解间隔 Timer。

查看本栏目更多精彩内容：http://www.bianceng.cn/OS/Linux/

间隔 timer

间隔 timer 就是应用程序调用setitimer建立的定时器。

Linux 的间隔 Timer 实现经历了一个简单的发展过程。

Linux2.4 版本内核在进程描述符中有以下这些数据结构，用来实现间隔 timer:

struct timer_list real_timer;

unsigned long it_real_value, it_prof_value, it_virt_value;

unsigned long it_real_incr, it_prof_incr, it_virt_incr;

real_timer 是一个动态 timer，用于 ITIMER_REAL 时钟。其他的 unsigned long 类型的值分别用来维护各种时钟的到期时间和到期后的 interval 时间，用 jiffies 值表示。

（编辑：佛山站长网）

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