Linux 时钟管理
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;
};
struct tvec_root {
struct list_head vec;
};
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 – 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 所示:
页:
[1]