Linux 时钟管理

admin

Linux 中的定时器
在 Linux 内核中主要有两种类型的定时器。一类称为 timeout 类型，另一类称为 timer 类型。timeout 类型的定时器通常用于检测各种错误条件，例如用于检测网卡收发数据包是否会超时的定时器，IO 设备的读写是否会超时的定时器等等。通常情况下这些错误很少发生，因此，使用 timeout 类型的定时器一般在超时之前就会被移除，从而很少产生真正的函数调用和系统开销。总的来说，使用 timeout 类型的定时器产生的系统开销很小，它是下文提及的 timer wheel 通常使用的环境。此外，在使用 timeout 类型定时器的地方往往并不关心超时处理，因此超时精确与否，早 0.01 秒或者晚 0.01 秒并不十分重要，这在下文论述 deferrable timers 时会进一步介绍。timer 类型的定时器与 timeout 类型的定时器正相反，使用 timer 类型的定时器往往要求在精确的时钟条件下完成特定的事件，通常是周期性的并且依赖超时机制进行处理。例如设备驱动通常会定时读写设备来进行数据交互。如何高效的管理 timer 类型的定时器对提高系统的处理效率十分重要，下文在介绍 hrtimer 时会有更加详细的论述。
内核需要进行时钟管理，离不开底层的硬件支持。在早期是通过 8253 芯片提供的 PIT（Programmable Interval Timer）来提供时钟，但是 PIT 的频率很低，只能提供最高 1ms 的时钟精度，由于 PIT 触发的中断速度太慢，会导致很大的时延，对于像音视频这类对时间精度要求更高的应用并不足够，会极大的影响用户体验。随着硬件平台的不断发展变化，陆续出现了 TSC（Time Stamp Counter），HPET（High Precision Event Timer），ACPI PM Timer（ACPI Power Management Timer），CPU Local APIC Timer 等精度更高的时钟。这些时钟陆续被 Linux 的时钟子系统所采纳，从而不断的提高 Linux 时钟子系统的性能和灵活性。这些不同的时钟会在下文不同的章节中分别进行介绍。
Timer wheel
在 Linux 2.6.16 之前，内核一直使用一种称为 timer wheel 的机制来管理时钟。这就是熟知的 kernel 一直采用的基于 HZ 的 timer 机制。Timer wheel 的核心数据结构如清单 1 所示：

清单 1. Timer wheel 的核心数据结构

#define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6) #define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8) #define TVN_SIZE (1 << TVN_BITS) #define TVR_SIZE (1 << TVR_BITS) #define TVN_MASK (TVN_SIZE - 1) #define TVR_MASK (TVR_SIZE - 1) struct tvec {         struct list_head vec[TVN_SIZE]; }; struct tvec_root {         struct list_head vec[TVR_SIZE]; }; struct tvec_base {         spinlock_t lock;         struct timer_list *running_timer;         unsigned long timer_jiffies;         unsigned long next_timer;         struct tvec_root tv1;         struct tvec tv2;         struct tvec tv3;         struct tvec tv4;         struct tvec tv5; } ____cacheline_aligned; 复制代码

以 CONFIG_BASE_SMALL 定义为 0 为例，TVR_SIZE ＝ 256，TVN_SIZE ＝ 64，这样
<p>可以得到如图 1 所示的 timer wheel 的结构。

图 1. Timer wheel 的逻辑结构

<div class="ibm-container-body">在 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 &ndash; 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 所示：