Linux 时钟管理

时间：06-13 来源：IBM 点击：

在 timer wheel 的框架下，所有系统正在使用的 timer 并不是顺序存放在一个平坦的链表中，因为这样做会使得查找，插入，删除等操作效率低下。Timer wheel 提供了 5 个 timer 数组，数组之间存在着类似时分秒的进位关系。TV1 为第一个 timer 数组，其中存放着从 timer_jiffies（当前到期的 jiffies）到 timer_jiffies + 255 共 256 个 tick 对应的 timer list。因为在一个 tick 上可能同时有多个 timer 等待超时处理，timer wheel 使用 list_head 将所有 timer 串成一个链表，以便在超时时顺序处理。TV2 有 64 个单元，每个单元都对应着 256 个 tick，因此 TV2 所表示的超时时间范围从 timer_jiffies + 256 到 timer_jiffies + 256 * 64 – 1。依次类推 TV3，TV4，TV5。以 HZ=1000 为例，每 1ms 产生一次中断，TV1 就会被访问一次，但是 TV2 要每 256ms 才会被访问一次，TV3 要 16s，TV4 要 17 分钟，TV5 甚至要 19 小时才有机会检查一次。最终，timer wheel 可以管理的最大超时值为 2^32。一共使用了 512 个 list_head（256+64+64+64+64）。如果 CONFIG_BASE_SMALL 定义为 1，则最终使用的 list_head 个数为 128 个（64+16+16+16+16），占用的内存更少，更适合嵌入式系统使用。Timer wheel 的处理逻辑如清单 2 所示：

清单 2. timer wheel 的核心处理函数

static inline void __run_timers(struct tvec_base *base) { struct timer_list *timer; spin_lock_irq(&base->lock); while (time_after_eq(jiffies, base->timer_jiffies)) { struct list_head work_list; struct list_head *head = &work_list; int index = base->timer_jiffies & TVR_MASK; /* * Cascade timers: */ if (!index && (!cascade(base, &base->tv2, INDEX(0))) && (!cascade(base, &base->tv3, INDEX(1))) && !cascade(base, &base->tv4, INDEX(2))) cascade(base, &base->tv5, INDEX(3)); ++base->timer_jiffies; list_replace_init(base->tv1.vec + index, &work_list); while (!list_empty(head)) { void (*fn)(unsigned long); unsigned long data; timer = list_first_entry(head, struct timer_list,entry); fn = timer->function; data = timer->data; . . . . fn(data); . . . . }
base->timer_jiffies 用来记录在 TV1 中最接近超时的 tick 的位置。index 是用来遍历 TV1 的索引。每一次循环 index 会定位一个当前待处理的 tick，并处理这个 tick 下所有超时的 timer。base->timer_jiffies 会在每次循环后增加一个 jiffy，index 也会随之向前移动。当 index 变为 0 时表示 TV1 完成了一次完整的遍历，此时所有在 TV1 中的 timer 都被处理了，因此需要通过 cascade 将后面 TV2，TV3 等 timer list 中的 timer 向前移动，类似于进位。这种层叠的 timer list 实现机制可以大大降低每次检查超时 timer 的时间，每次中断只需要针对 TV1 进行检查，只有必要时才进行 cascade。即便如此，timer wheel 的实现机制仍然存在很大弊端。一个弊端就是 cascade 开销过大。在极端的条件下，同时会有多个 TV 需要进行 cascade 处理，会产生很大的时延。这也是为什么说 timeout 类型的定时器是 timer wheel 的主要应用环境，或者说 timer wheel 是为 timeout 类型的定时器优化的。因为 timeout 类型的定时器的应用场景多是错误条件的检测，这类错误发生的机率很小，通常不到超时就被删除了，因此不会产生 cascade 的开销。另一方面，由于 timer wheel 是建立在 HZ 的基础上的，因此其计时精度无法进一步提高。毕竟一味的通过提高 HZ 值来提高计时精度并无意义，结果只能是产生大量的定时中断，增加额外的系统开销。因此，有必要将高精度的 timer 与低精度的 timer 分开，这样既可以确保低精度的 timeout 类型的定时器应用，也便于高精度的 timer 类型定时器的应用。还有一个重要的因素是 timer wheel 的实现与 jiffies 的耦合性太强，非常不便于扩展。因此，自从 2.6.16 开始，一个新的 timer 子系统 hrtimer 被加入到内核中。

hrtimer (High-resolution Timer)

hrtimer 首先要实现的功能就是要克服

上一页 1 2 3 4 5 6 7 8 9 10 下一页

上一篇：基于DSP Builder的脑电信号小波处理
下一篇：基于MSP430微处理器和GSM移动通信的血糖监护系统设计

TIMER Linux TSC 时钟管理相关文章：

栏目分类