引子
时间系统的工作需要软硬件以及操作系统的互相协作，在上一部分，我们已经看到大多数时间函数都依赖内核系统调用，GlibC 仅仅做了一次请求的转发。因此必须深入内核代码以便了解更多的细节。
内核自身的正常运行也依赖于时钟系统。Linux 是一个典型的分时系统，CPU 时间被分成多个时间片，这是多任务实现的基础。Linux 内核依赖 tick，即时钟中断来进行分时。
为了满足应用和内核自己的需求，内核时间系统必须提供以下三个基本功能：
提供系统 tick 中断（驱动调度器，实现分时）
维护系统时间
维护软件定时器
目前的 Linux 内核版本为 3.8，其时间系统比较复杂，复杂的原因来自几个方面：
首先 Linux 要支持不同的硬件体系结构和时钟电路，Linux 是一个通用操作系统，支持平台的多样性导致时间系统必须包含各种各样的硬件处理和驱动代码。
其次，早期 Linux 的时钟实现采用低精度时钟框架（ms 级别），随着硬件的发展和软件需求的发展，越来越多的呼声是提高时钟精度（ns 级别）；经过若干年的努力，人们发现无法在早期低精度时钟体系结构上优雅地扩展高精度时钟。最终，内核采用了两套独立的代码实现，分别对应于高精度和低精度时钟。这使得代码复杂度增加。
最后，来自电源管理的需求进一步增加了时间系统的复杂性。Linux 越来越多地被应用到嵌入式设备，对节电的要求增加了。当系统 idle 时，CPU 进入节电模式，此时一成不变的时钟中断将频繁地打断 CPU 的睡眠状态，新的时间系统必须改变以应对这种需求，在系统没有任务执行时，停止时钟中断，直到有任务需要执行时再恢复时钟。
以上几点，造成了内核时间系统的复杂性。不过 Linux 内核并不是从一开始就如此复杂，所以还是让我们从头说起吧。
早期的 Linux 时间系统
在 Linux 2.6.16 之前，内核只支持低精度时钟。内核围绕着 tick 时钟来实现所有的时间相关功能。Tick 是一个定期触发的中断，一般由 PIT (Programmable Interrupt Timer) 提供，大概 10ms 触发一次 (100HZ)，精度很低。在这个简单体系结构下，内核如何实现三个基本功能？
第一大功能：提供 tick 中断。
以 x86 为例，系统初始化时选择一个能够提供定时中断的设备 (比如 Programmable Interrupt Timer, PIT)，配置相应的中断处理 IRQ 和相应的处理例程。当硬件设备初始化完成后，便开始定期地产生中断，这便是 tick 了。非常简单明了，需要强调的是 tick 中断是由硬件直接产生的真实中断，这一点在当前的内核实现中会改变，我们在第四部分介绍。
第二大功能：维护系统时间。
RTC (Real Time Clock) 有独立的电池供电，始终保存着系统时间。Linux 系统初始化时，读取 RTC，得到当前时间值。
读取 RTC 是一个体系结构相关的操作，对于 x86 机器，定义在 arch\x86\kernel\time.c中。可以看到最终的实现函数为 mach_get_cmos_time，它直接读取 RTC 的 CMOS 芯片获得当前时间。如前所述，RTC 芯片一般都可以直接通过 IO 操作来读取年月日等时间信息。得到存储在 RTC 中的时间值之后，内核调用 mktime () 将 RTC 值转换为一个距离 Epoch（既 1970 年元旦）的时间值。此后直到下次重新启动，Linux 不会再读取硬件 RTC 了。
虽然内核也可以在每次需要的得到当前时间的时候读取 RTC，但这是一个 IO 调用，性能低下。实际上，在得到了当前时间后，Linux 系统会立即启动 tick 中断。此后，在每次的时钟中断处理函数内，Linux 更新当前的时间值，并保存在全局变量 xtime 内。比如时钟中断的周期为 10ms，那么每次中断产生，就将 xtime 加上 10ms。
当应用程序通过 time 系统调用需要获取当前时间时，内核只需要从内存中读取 xtime 并返回即可。就这样，Linux 内核提供了第二大功能，维护系统时间。
第三大功能：软件定时器
能够提供可编程定时中断的硬件电路都有一个缺点，即同时可以配置的定时器个数有限。但现代 Linux 系统中需要大量的定时器：内核自己需要使用 timer，比如内核驱动的某些操作需要等待一段给定的时间，或者 TCP 网络协议栈代码会需要大量 timer；内核还需要提供系统调用来支持 setitimer 和 POSIX timer。这意味着软件定时器的需求数量将大于硬件能够提供的 timer 个数，内核必须依靠软件 timer。
简单的软件 timer 可以通过 timer 链表来实现。需要添加新 timer 时，只需在一个全局的链表中添加一个新的 Timer 元素。每次 tick 中断来临时，遍历该链表，并触发所有到期的 Timer 即可。但这种做法缺乏可扩展性：当 Timer 的数量增加时，遍历链表的花销将线形增加。如果将链表排序，则 tick 中断中无须遍历列表，只需要查看链表头即可，时间为 O(1)，但这又导致创建新的 Timer 的时间复杂度变为 O(n)，因为将一个元素插入排序列表的时间复杂度为 O（N）。这些都是可行但扩展性有限的算法。在 Linux 尚未大量被应用到服务器时，系统中的 timer 个数不多，因此这种基于链表的实现还是可行的。
但随着 Linux 开始作为一种服务器操作系统，用来支持网络应用时，需要的 timer 个数剧增。一些 TCP 实现对于每个连接都需要 2 个 Timer，此外多媒体应用也需要 Timer，总之 timer 的个数达到了需要考虑扩展性的程度。
timer 的三个操作：添加 (add_timer)、删除 (del_timer) 以及到期处理（tick 中断）都对 timer 的精度和延迟有巨大影响，timer 的精度和延迟又对应用有巨大影响。例如，add_timer 的延迟太大，那么高速 TCP 网络协议就无法实现。为此，从 Linux2.4 开始，内核通过一种被称为时间轮的算法来保证 add_timer()、del_timer() 以及 expire 处理操作的时间复杂度都为 O(1)。
时间轮算法简述
时间轮算法是一种实现软件 timer 的算法，由计算机科学家 George Varghese 等提出，在 NetBSD(一种操作系统) 上实现并替代了早期内核中的 callout 定时器实现。
最原始的时间轮如下图所示。
图 1. 原始的时间轮
上图中的轮子有 8 个 bucket，每个 bucket 代表未来的一个时间点。我们可以定义每个 bucket 代表一秒，那么 bucket [1] 代表的时间点就是“1 秒钟以后”，bucket [8] 代表的时间点为“8 秒之后”。Bucket 存放着一个 timer 链表，链表中的所有 Timer 将在该 bucket 所代表的时间点触发。中间的指针被称为 cursor。这样的一个时间轮工作如下：