linux内核时钟与定时器的实现

一、概述
在计算机系统，CPU是以一个节拍一个节拍运行的（cpu cycle），这就是CPU的频率（HZ)。类似的，操作系统需要提供超时功能，显示时间（如PC机右下角的时钟），统计（CPU占有率计算）等功能，也需要有一个节拍（操作系统的频率HZ）触发操作系统做上述相关功能处理，内核在内部使用了一个全局变量记录了系统从启动后经过了多少个节拍，这就是tick值，通常由另外一个更形象的说法“嘀嗒”，在linux下用jiffies表示（该值为long型，为了防止32位系统下该值翻转，同时用了一个64位数jiffies_64来记录）。
那么谁来触发这个节拍呢，通常由时钟芯片来实现。由于内核需要运行在不同的硬件设备上，因此，内核抽象出了通用的时钟事件处理框架。其典型流程如下：
硬件<-->相关驱动代码<-->通用时钟处理代码<-->高分辨率定时器处理框架<-->高/低分辨率定时器处理<-->超时处理
上述流程从左到右为时钟触发处理流程，从右到左是设置配置流程。高分辨率定时器提供了比低分辨率定时器高很多的精度（通常前者为纳秒级，而后者为毫秒级），高精度定时器需要在编译内核时指定CONFIG_HIGH_RES_TIMERS才支持。


二、实现文件及入口函数说明：


clockchips.h/clockevents.c: 定义时钟事件设备struct clock_event_device，该结构抽象了时钟事件的通用处理代码，从结构体定义可以看出，主要为设置时钟芯片的触发模式（周期触发还是单触发），设置超时事件，已经超时事件的处理函数（时钟中断处理）等。
clocksource.h/clocksource.c: 定义了时钟源struct clocksource，该结构抽象了时钟源的处理，主要是使能时钟源，去使能时钟源，读取时钟源的cycle值，暂停和恢复时钟源等操作。
这4个文件为通用时钟处理代码，在它们的下一层，就是时钟芯片的驱动代码。如IA-32/AMD CPU的PIT(programmable interrupt timer,由时钟芯片8253实现，相关实现可参看I8253.h/I8253.c


tick.h: tick时钟头文件,定义了两个结构：
struct tick_device：经典tick时钟设备定义，低精度定时器。
struct tick_sched： 高精度定时器模拟tick时钟，或动态时钟（tickless）使用。
tick-common.c:经典tick时钟的实现。tick_handle_periodic为入口函数
tick_handle_periodic->do_timer（全局时钟）->jiffies_64更新
         update_wall_time
           calc_global_load 
           ->update_process_times->run_local_timers->hrtimer_run_queues/TIMER_SOFTIRQ->__run_timers(低分辨率定时器)
   rcu_check_callbacks
   scheduler_tick
   run_posix_cpu_timers
tick-internal.h：一些通用的支撑代码
tick-broadcast.c：广播模式的时钟处理。在一些系统，为了省电进入节能模式后，可能会停止某些时钟事件，这时候可以通过其他的设备广播一个时钟事件。
tick-oneshot.c：高精度定时器单触发方式的一些通用处理代码
tick-sched.c： 切换到动态时钟及动态时钟的实现

timer.c/h:低精度定时器的实现, 定时器节点管理上采用了级联方式。
hrtimer.c/h：高精度定时器的实现。hrtimer_interrupt为入口函数
hrtimer_interrupt->__run_hrtimer
与hrtimer_run_queues的区别？是通用框架的一部分，在每个硬件中断中触发。called by run_local_timers，没有高精度时钟系统才会运行。
timerqueue.c/h:高精度定时器节点队列,封装了rbtree的操作。
ktime_t为高精度定时器的定时时间


tick_setup_sched_timer：在切换到高精度模式时，启动一个高精度定时器模拟周期tick时钟。
struct hrtimer_sleeper ：任务定时操作是如此普遍，内核实现了此类公用接口，以方便使用。




三、硬件时钟设备
参见第二件时钟事件设备和时钟源的描述


四、一帘幽梦：低精度定时器的实现
前面的知识看起来似乎都很简单，现在问题来了，内核是如何管理定时器的？一个系统只要处理的数据上升一个数据量，其复杂程度与性能的挑战是非常大的。如果系统只有几十个定时器，那似乎没有什么，只需要一个for循环遍历是否超时即可，但如果定时器数量上升到了几千几万几十万呢？我们知道，硬件触发定时事件，定时事件的中断处理部分必须非常迅速，如果全部循环判断性能上是无法接受的。那linux内核是如何做到的呢？下面先看看低精度定时器的管理。
对于各个定时器来说，唯一的差异就是定时时间，而且我们知道，如果定时时间短的还没有超时，那么定时时间长的肯定也没有超市。那能不能根据定时时间把定时器分类散列开呢，每次定时中断到达后只判断定时时间最短的那些定时器？可以的，问题是怎么做？考虑一个32位的系统，那么定时时间就有1到约42亿个不同值，完全散列是不可能的（请你算下需要多少内存？）。


内核把定时时间散列成5组, 每组对应的时间间隔，分别如下：
tv1:  0 -> 255
tv2:  256 -> 2^14-1
tv3:  2^14 -> 2^20-1
tv4:  2^20 -> 2^26-1
tv5:  2^26 -> 2^32-1


参考struct tvec_base，
struct tvec_base {
spinlock_t lock;
struct timer_list *running_timer;
unsigned long timer_jiffies; -----当前时间轮上的jiffies，一般情况下比内核的jiffies相等或差1。可以看出，低精度定时器与系统jiffies是强相关的。
unsigned long next_timer;
struct tvec_root tv1;
struct tvec tv2;
struct tvec tv3;
struct tvec tv4;
struct tvec tv5;
} ____cacheline_aligned;
第一组有256个表项，对应着超时时间在下一个tick值到255个tick值。如果有多个定时器的超时值是相同的呢？相同的定时器通过链表串在一起。第二组有64个表项，这里的每个表项就不是对应着一个超时值了，而是一定超时间隔的都在同一个表项，相当于把把散列表压缩了。例如，第一项的链表里面的定时器的超时值就在范围256->511上。
第三组到第五组与第二组类似。
每个超时时间如何散列到各个组的，可以参考internal_add_timer的实现。

想象一下，有5个组，每个组下面挂着很多表项（256,64,64,64,64），每个表项下面又串着定时器，与一个帘子是很像的。


定时器是放到了合适的位置上了，那么超时时怎么处理。
由于定时器已经按照超时时间排好队了，那么就只需要判断第一组的第一个表项是否有定时器，如果有，则触发定时器；下一个超时时间到来，则判断第一组的第二个表项是否有定时器，依此。当到了256个定时器时间到来时，由于第一组的定时器都已经处理完毕，这时候该处理第二组的第一个表项了，前面说过，从第二组开始，是把散列表给压缩了，第二组的第一个表项下的定时器超时时间在256到511，因此，不能直接把这个表项下的所有定时器都触发，因此，必须把这里的定时器加压散开，系统就把这个表项下的定时器重新散列到第一组去，然后执行第一组的第一个表项的定时器链表。到了512个定时时间时，就把第二组的第二个表项下的定时器解压散列到第一组去。
依此往下，到了一定的时间间隔后，就把下一组的定时器往前移。
这就是定时器级联，或者说时间轮，与我们日常的时钟是很类似的，秒钟走了一圈后，分钟才动一下，分钟走完一圈后，时钟才动一下。
具体实现参考__run_timers函数：
int index = base->timer_jiffies & 255;


/*
* 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));






五、好大一棵树：高精度定时器的实现
在低精度下，级联方式管理的定时
器非常地高效，每一次时钟中断，只需要判断第一组下的表项（index = base->timer_jiffies & 255）是否有定时器即可。但到了高精度下，情况就不一样了，老革命遇到了新问题，高精度定时器的定时精度为纳级，而低精度下为毫秒级，
差了两个数量级，每秒钟就有1000000000个纳秒。如果还按级联方式来做的话，系统得有多少个表项啊，需要多少内存啊。而且原来的级联方式是根据jiffies和32位系统来做的，因此，最终系统采用了红黑树来管理定时器。更详细的描述可以参考源码树的hrtimes.txt文件。
由于系统jiffies为毫秒级，而高精度定时器为纳秒级，那么使用jiffies来表示已经不合适了，因此，系统引入了ktime_t来表示时间，ktime_t实际为一个64bit的值，如果系统为32位，则为两个32bit的联合体。并引入了一堆接口做时间换算。

下面看看高精度定时器的触发处理hrtimer_interrupt：
1，从红黑树取定时器节点（启动定时器时已经按照定时时间插入树中），判断是否超时，
2，处理定时器的回调，
3，所有超时定时器已经处理完毕，设置时钟芯片下一个定时时间。


高精度定时器可以基于两种时钟，一个是单调时钟，系统启动为0开始递增；一个是实际时间。
单调时钟是不会变化的，而实际时间是有可能变化的，比如调用了settimeofday接口，这时候定时器怎么处理？
系统计算当前时间与设置时间的差值，并从红黑树获取第一个定时器节点（最先超时），超时时间加上差值（可能为正也可能为负），以此结果重新设置时钟芯片的触发时间。时钟芯片触发时，需要对每一个定时器进行时间补偿。


六、tick时钟
没有启动动态时钟的情况下，系统内部有一个以固定周期触发的定时器，它就是tick时钟。
七、动态时钟(tickless)
第六节tick时钟介绍了系统的周期时钟是以固定的时间间隔触发，超时处理函数进行相应的处理。但实际上，在不是很繁忙的系统上（最直观的方法就是CPU占有率），大多数情况下，系统都是空闲的，由于该tick值较短（依赖于配置，常见的为10毫秒或者4毫秒），超时后发现没有事情需要处理，又接着运行IDLE任务或者CPU进入节能状态，这个超时处理是很浪费。考虑一个人，没有事情做的时候想打个盹，但又怕错过，不得不眼睛刚眯上，又得睁开问有没有事情做，还能睡好吗？那能不能在只有事情处理的时候才叫醒他呢？
在内核就实现了类似的机制，这就是动态时钟。所谓动态时钟，就是当系统空闲时，它不是采用周期性的tick超时，而是判断系统的下一个超时处理时间，如果超时处理时间大于1个tick值（小于则没有启动动态时钟的意义），则对时钟设备进行编程，让时钟设备以单触发的方式，在指定的超时时间触发。简单说，动态时钟就是在空闲态下，系统节拍不是固定周期触发的，是通过计算得出的，这就是动态的含义，可以认为是tick周期时钟的扩展。
当指定的超时时间到达之后或者被其他外部中断提前唤醒后，系统为下一个时钟信号编程，参见tick_nohz_restart_sched_tick->tick_nohz_restart
系统空闲时的相关处理函数参见cpu_idle->tick_nohz_stop_sched_tick。
相关数据结构参见struct tick_sched（该结构同时也是高精度定时器下的tick时钟的实现）。
特别的是，动态时钟机制是否支持是在编译时指定的，使能编译宏CONFIG_NO_HZ才会支持。