内容


浅析 Linux 中的时间编程和实现原理,第 4 部分

Linux 内核的工作

Comments

系列内容:

此内容是该系列 # 部分中的第 # 部分: 浅析 Linux 中的时间编程和实现原理,第 4 部分

敬请期待该系列的后续内容。

此内容是该系列的一部分:浅析 Linux 中的时间编程和实现原理,第 4 部分

敬请期待该系列的后续内容。

回顾

近年来,随着 Linux 的广泛使用,对时间编程提出了更高的要求。实时应用、多媒体软件对时钟和定时器的精度要求不断提高,在早期 Linux 内核中,定时器所能支持的最高精度是一个 tick。为了提高时钟精度,人们只能提高内核的 HZ 值 (一个内核参数,代表内核时钟中断的频率)。更高的 HZ 值,意味着时钟中断更加频繁,内核要花更多的时间进行时钟处理。而内核的任何工作对于应用来说纯粹是无益的开销。当 HZ 值提高到 1000 之后,如果继续提高,Linux 的可用性将下降。

另外一方面,我们已看到,类似 HPET(High Precision Event Timer) 等系统硬件已经能够提供纳秒级别的时钟中断,如何利用这些高精度时钟硬件来提供更高精度的定时服务是这一部分的主要话题。

2.6.16 以来的新变化

在 2.6.16 之前,Linux 开发人员花了很多的努力试图在原有代码体系结构下实现高精度时钟,但这种努力被证明是徒劳的。

因此从 2.6.16 开始,RedHat 公司的 Ingo Molar 和 Thomas Gleixner 对时间系统进行了比较大的重构。引入了以下几个新的模块:

Generic Timer Framework

早期 Linux 内核也需要支持众多不同的时钟硬件设备,但内核本身对这些设备的使用相对简单。内核将硬件的不同操作封装在 Arch 层里面。比如 x86 体系结构下,设置 PIT(Programmable Interrupt Timer) 是在 8259 芯片初始化时完成的,调用的 API 名字叫做 setup_pit_timer(),而在其他体系结构中,没有 8259,其初始化 time_init()中的具体实现又有所不同,会采用不同的 API 命名和不同的表示 Timer 硬件的数据结构。因为早期 Linux 上只需要做一次时钟初始化,操作具体硬件的次数有限,因此这种不同体系结构用不同实现细节的做法没有什么问题。

新的内核能够支持 tickless 模式,即当内核空闲时为了省电而关闭时钟中断。为此,内核需要频繁操作 Timer 硬件,在这种情况下,采用统一的抽象层有助于代码的维护。这便是 Generic Timer Frame,它将各种不同硬件抽象为三个统一的数据结构:

  • Clock Source,由 struct clocksource 表示。这个数据结构主要用来抽象那些能够提供计时功能的系统硬件,比如 RTC(Real Time Clock)、TSC(Time Stamp Counter) 等。
  • Clock Event Device,由 struct clock_event_device 表示。这个数据结构主要用来封装和抽象那些能提供定时中断能力的系统硬件,比如 HPET 等。
  • Tick Device,由 struct tick_device 表示。这个数据结构建立在 clock event device 之上,专门用来表示产生 tick 的设备。tick 是一个定时中断。因此归根结底需要一个 Clock Event Device 来完成,但 Clock Event Device 不仅可以用来提供 tick,在高精度 Timer 模式下,还用来提供其他功能。

Generic Timer Frame 把各种不同时间硬件的区别同上层软件隔离开来,使得时间系统能够方便地支持新的时钟硬件,而无需大量修改硬件无关代码。

高精度定时器 hrtimer(High Resolution Timer)

高精度时钟不能建立在已有的时间轮算法上,虽然时间轮是一种有效的管理数据结构,但其 cascades 操作有不可预料的延迟。它更适于被称为"timeout”类型的低精度定时器,即不等触发便被取消的 Timer。这种情况下,cascades 可能造成的时钟到期延误不会有任何不利影响,因为根本等不到 cascades,换句话说,多数 Timer 都不会触发 cascades 操作。而高精度定时器的用户往往是需要等待其精确地被触发,执行对时间敏感的任务。因此 cascades 操作带来的延迟是无法接受的。所以内核开发人员不得不放弃时间轮算法,转而寻求其他的高精度时钟算法。最终,开发人员选择了内核中最常用的高性能查找算法红:黑树来实现 hrtimer。

在描述 hrtimer 的实现之前,先了解其使用方法是必要的。

hrtimer 的编程接口和方法

使用 hrtimer 之需要了解三个 API:

hrtimer_init() 初始化一个 Timer 对象,用 hrtimer_start() 设定到期时间和到期操作,并添加启动该 Timer。remove_hrtimer() 删除一个 Timer。

Hrtimer 的实现

高精度定时器和低精度定时器的实现有以下两个主要的不同点:

  • 高精度定时器由红黑树管理,而非时间轮。
  • Hrtimer 与系统时钟 tick 无关,不使用 jiffies,用纳秒作为计时单位。

所有的 hrtimer 实例都被保存在红黑树中,添加 Timer 就是在红黑树中添加新的节点;删除 Timer 就是删除树节点。红黑树的键值为到期时间。

Timer 的触发和设置管理不在定期的 tick 中断中进行,而是动态调整:当前 Timer 触发后,在中断处理的时候,将高精度时钟硬件的下次中断触发时间设置为红黑树中最早到期的 Timer 的时间。时钟到期后从红黑树中得到下一个 Timer 的到期时间,并设置硬件,如此循环反复。

图 1 显示了内核中用来管理 hrtimer 的数据结构及他们之间的关系。

图 1. 数据结构
数据结构
数据结构

每一个具体的高精度定时器用 structhrtimer 表示,并且是红黑树的一个节点。

在多处理器系统中,每个 CPU 都保存和维护自己的高精度定时器,为了同步和通知的需要处理器间的消息通信将引入不可忍受的延迟。要知道,hrtimer 的精度要求是纳秒级别的。在每个 CPU 上,hrtimer 还分为两大类:

  • Monotonic:与系统时间无关的自然流失的时间,不可以被人修改。
  • Real time:实时时间即系统时间,可以被人修改。

因此每个 CPU 都需要两个 clock_base 数据结构:一个指向所有 monotonic hrtimer;另一个指向所有的 realtime hrtimer。

clock_base 数据结构中,active 指向一个红黑树,每个 hrtimer 都是该红黑树的一个节点,用到期时间作为 key。这样所有的定时器便按照到期时间的先后被顺序加入这棵平衡树。first 指向最近到期的 hrtimer, 即红黑树最左边的叶子节点。

这种数据结构组织是很清晰和简单的,理解了这些数据结构,描述 hrtimer 的具体操作便十分容易了。

添加 Timer,即在相应的 clock_base 指向的红黑树中增加一个新的节点,红黑树的 key 由 hrtimer 的到期时间表示,因此越早到期的 hrtimer 在树上越靠左。

删除 Timer,即从红黑树上删除该 hrtimer。

hrtimer 是如何触发的

我们所描述过的低精度定时器都是依赖系统定期产生的 tick 中断的。而高精度时钟模式下,定时器直接由高精度定时器硬件产生的中断触发。比如目前系统中有 3 个 hrtimer,其到期时间分别为 10ns、100ns 和 1000ns。添加第一个 hrtimer 时,系统通过当前默认的 clock_event_device 操作时钟硬件将其下一次中断触发时间设置为 10ns 之后;当 10ns 过去时,中断产生,通过系统的中断处理机制,最终会调用到 hrtimer_interrrupt() 函数,该函数从红黑树中得到所有到期的 Timer,并负责调用 hrtimer 数据结构中维护的用户处理函数(或者通过软中断执行用户指定操作);hrtimer_interrupt 还从红黑树中读取下一个到期的 hrtimer,并且通过 clock_event_device 操作时钟硬件将下一次中断到期时间设置为 90ns 之后。如此反复操作。

这样就突破了 tick 的精度限制,用户操作可以精确到 ns 级别,当然中断依然存在延迟,这种延迟在几百个纳秒级别,还是比较高的精度。

Tick 时钟模拟

在高精度时钟模式下,内核系统依然需要一个定时触发的 tick 中断,以便驱动任务切换等重要操作。可是我们在上一节看到,高精度时钟模式下,系统产生时间中断的间隔是不确定的,假如系统中没有创建任何 hrtimer,就不会有时钟中断产生了。但 Linux 内核必须要一个严格定时触发的 tick 中断。

因此系统必须创建一个模拟 tick 时钟的特殊 hrtimer,并且该时钟按照 tick 的间隔时间(比如 10ms)定期启动自己,从而模拟出 tick 时钟,不过在 tickless 情况下,会跳过一些 tick。关于 tickless,和本文主旨无关,不再赘述。

内核时间系统的总体运行情况

至此,我们可以用下面这张图来总结高精度模式下,内核时间系统的总体运行情况。

图 2. 内核时间系统概览
内核时间系统概览
内核时间系统概览

Linux 用 Generic Timer Framework 层来屏蔽底层硬件的细节,对上抽象出 Clock Sources 和 Clock Event 两个数据结构,分别用来表示计时的硬件和定时的硬件。

用基于红黑树的 hrtimer 系统维护高精度时钟,并用一个特殊的 hrtimer 模拟系统时钟 tick,产生定期的系统时钟中断。

模拟的系统时钟 tick 将驱动传统的低精度定时器系统(基于时间轮)和内核进程调度。

用户层 Timer 的支持和改变

高精度时钟主要应用于实时系统。在用户层,实时时钟的编程接口就是我们在第一部分介绍的 POSIX Timer。本文的第三部分介绍了基于 2.6.16 之前内核的 POSIX Timer 实现细节。

hrtimer 加入内核之后,POSIX Timer 的实现细节有一些改变,其中 per process 和 per thread 定时器的实现基本没有变化。但针对 CLOCK_REALTIME 和 CLOCK_MONOTONIC 两个时钟源的基本实现有所改变。以前它们依赖内核中的动态定时器实现,现在这类 Timer 都采用了新的 hrtimer。换句话说,每个时钟源为 CLOCK_REALTIME/CLOCK_MONOTONIC 的 POSIX Timer 都由一个内核 hrtimer 实现。

传统的间隔 Timer 虽然不属于实时应用,也没有很高的时钟精度要求,但在新的内核中,间隔 Timer 也使用了 hrtimer,而非传统的动态 Timer。因此 setitimer 在内核中也不再由时间轮管理了。

总体来说,用户请求的 Timer,无论是精度较低的间隔 Timer 还是精度高的 POSIX Timer,内核都采用 hrtimer 来支持。而由时间轮算法维护的内核动态 Timer 则仅仅在内核内部使用,比如一些驱动程序中还依旧使用 add_timer() 等动态 Timer 接口实现定时需求。

时区问题

结束之前,我们探讨一个尚未展开的话题,即时区问题。这是非常容易让人迷惑的一个话题。因此放在文章的结尾处讨论会好些。

首先介绍两个缩写: UTC 和 LCT。

UTC 就是 Coordinated Universal Time,是全世界通用的时间标准。它是格林威治时间 (GMT) 的后继者,在计算机领域,GMT 术语不再广泛使用,因为它的精度不够高。UTC 是 1963 年标准化的,采用了高精度的原子钟。因此在科学领域,包括计算机科学,都采用 UTC 而不再使用 GMT 这个术语。我们可以认为 UTC 就是时区 0 的标准时间。LCT(Local Civil Time) 即当地时间,比如北京时间。

假如您耐心读到了这里,应该已经了解了系统时间 (system time) 和硬件时间 (RTC time) 的区别。硬件时间存放在 RTC(Real Time Clock) 硬件中。Linux 系统启动时,会读取 RTC 时间,并该时间来初始化系统时间;正常运行时,系统时间在每次 tick 中断中加以更新和维护;当系统关闭时,Linux 用系统时间来更新硬件时间。

Linux 系统时间总是 UTC 时间。那么硬件 RTC 中保存的是 UTC 还是 LCT 呢?

微软的 Windows 系统认定该时间为 LCT,即当地时间。我在上海的家里打开电脑,RTC 的时间是 2013-01-25 10:00:00,当系统启动后,会发现屏幕最右下角显示的当前时间就是 2013 年 1 月 25 日上午 10 点。

而在 Linux 系统中,RTC 的时间究竟是 LCT 还是 UTC 是由一个配置文件决定。RedHat 发行版中,该配置文件叫做/etc/sysconfig/clock。当该文件中有”UTC=true”这一行设定时,Linux 系统会将 RTC 时间解读为 UTC 时间,否则就解读为 LCT。(Debian 发行版依赖/etc/default/rcS 的设定来决定从 RTC 读入的是 UTC 还是 LCT)假设 RTC 中的时间还是 2013-01-25 10:00:00,并且/etc/sysconfig/clock 中有一行”UTC=true”,那么系统启动后就会将系统时间设置为 2013-01-25 10:00:00。如果/etc/sysconfig/clock 中没有这一行,系统 init 进程会将 RTC 中的时间解释为 LCT,并根据当前的时区配置计算出 UTC 时间,再用该时间设置系统时间 (hwclock 命令)。RTC 时间不变,现在的系统时间就变成了 2013-01-25 02:00:00,因为我的电脑在上海,系统计算出 UTC 为 8 小时之前。我们用 time()、gettimeofday() 等获得的时间值都是系统时间,即 UTC 时间。

可是桌面程序显示时间时,最好显示当地时间,您恐怕也不愿意每次看时间都需要在脑海中把格林威治时间转成当地时间吧。因此桌面应用通常会显示本地时间,我们常用的 date 命令也缺省显示 LCT。这是怎么做到的呢?

查看 date 的源代码,可以发现它用 localtime() 将调用 gettimeofday() 得到的 UTC 时间转换为 LCT 时间再进行输出。

那么 localtime() 是如何转换 LCT 的呢?感谢 POSIX 在这里有一个标准,Linux 系统将时区信息写入/etc/localtime 文件。该文件一般是/usr/share/zone 中某个文件的拷贝或者软链接。LibC 的 localtime 函数会读取/etc/localtime 获取本机的时区设置,然后进行复杂的时区转换,将给定 time_t 表示的 UTC 时间转换为 LCT。此外,在读取/etc/localtime 之前,localtime() 会先读取环境变量 TZ,因此用户也可以通过设置该环境变量来临时改变时区设置。/etc/localtime 文件中还包含了 Day Light Saving,即夏令时的信息。在实行夏令时的地区,/etc/localtime 文件中包含了如何计算夏令时的必要信息,因此 LibC 函数 localtime 才能够正确地将 UTC 转换为 LCT。

结束语

至此本文终于告一段落,用了 4 篇文章走马观花地试图指出时间系统的完整图景,不足之处甚至错误一定很多。希望读者包涵并和我交流。

关于 Linux 内核时间系统的更多细节,读者可参考继续 IBM deeveloperWorks 的文章 Linux 下定时器的实现方式分析以及 Linux 时钟管理。它们都有更加精彩而详细的解说。


相关主题


评论

添加或订阅评论,请先登录注册

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Linux
ArticleID=940439
ArticleTitle=浅析 Linux 中的时间编程和实现原理,第 4 部分: Linux 内核的工作
publish-date=08122013