linux HZ Tick Jiffies

linux HZ

Linux核心几个重要跟时间有关的名词或变数，底下将介绍HZ、tick与jiffies。

HZ

Linux核心每隔固定周期会发出timer interrupt (IRQ 0)，HZ是用来定义每一秒有几次timer interrupts。举例来说，HZ为1000，代表每秒有1000次timer interrupts。 HZ可在编译核心时设定，如下所示(以核心版本2.6.20-15为例)：

     adrian@adrian-desktop:~$ cd /usr/src/linux
     adrian@adrian-desktop:/usr/src/linux$ make menuconfig
     Processor type and features ---> Timer frequency (250 HZ) --->


其 中HZ可设定100、250、300或1000。以小弟的核心版本预设值为250。

小实验
观察/proc/interrupt的 timer中断次数，并于一秒后再次观察其值。理论上，两者应该相差250左右。

     adrian@adrian-desktop:~$ cat /proc/interrupts | grep timer && sleep 1 && cat /proc/interrupts | grep timer
     0: 9309306 IO-APIC-edge timer
     0: 9309562 IO-APIC-edge timer


上 面四个栏位分别为中断号码、CPU中断次数、PIC与装置名称。

要检查系统上HZ的值是什么，就执行命令

     cat /boot/config-`uname -r` | grep '^CONFIG_HZ='

还可以直接更改文件
os/linux/include/asm-cris/param.h?

Tick

Tick是HZ的倒数，意即timer interrupt每发生一次中断的时间。如HZ为250时，tick为4毫秒(millisecond)。

Jiffies

Jiffies为Linux核心变数(32位元变数，unsigned long)，它被用来纪录系统自开几以来，已经过多少的tick。每发生一次timer interrupt，Jiffies变数会被加一。值得注意的是，Jiffies于系统开机时，并非初始化成零，而是被设为-300*HZ (arch/i386/kernel/time.c)，即代表系统于开机五分钟后，jiffies便会溢位。那溢位怎么办?事实上，Linux核心定义几 个macro(timer_after、time_after_eq、time_before与time_before_eq)，即便是溢位，也能藉由这 几个macro正确地取得jiffies的内容。

另外，80x86架构定义一个与jiffies相关的变数jiffies_64 ，此变数64位元，要等到此变数溢位可能要好几百万年。因此要等到溢位这刻发生应该很难吧。那如何经由jiffies_64取得jiffies资讯呢?事 实上，jiffies被对应至jiffies_64最低的32位元。因此，经由jiffies_64可以完全不理会溢位的问题便能取得jiffies。

HZ的设定：
#make menuconfig
processor type and features--->Timer frequency (250 HZ)--->

HZ的不同值会影响timer （节拍）中断的频率

2.2 jiffies及其溢出 
全局变量jiffies取值为自操作系统启动以来的时钟滴答的数目，在头文 件中定义，数据类型为unsigned long volatile (32位无符号长整型)。关于 jiffies为什么要采用volatile来限定，可参考《关于volatile和jiffies.txt》。 
jiffies转换为秒可采用 公式：(jiffies/HZ)计算，将秒转换为jiffies可采用公式：(seconds*HZ)计算。 
当时钟中断发生时，jiffies 值就加1。因此连续累加一年又四个多月后就会溢出(假定HZ=100，1个jiffies等于1/100秒，jiffies可记录的最大秒数为 (2^32 -1)/100=42949672.95秒，约合497天或1.38年)，即当取值到达最大值时继续加1，就变为了0。 
在 Vxworks操作系统中，定义HZ的值为60，因此连续累加两年又三个多月后也将溢出（jiffies可记录的最大秒数为约合2.27年）。如果在 Vxworks操作系统上的应用程序对jiffies的溢出没有加以充分考虑，那么在连续运行两年又三个多月后，这些应用程序还能够稳定运行吗？ 
下 面我们来考虑jiffies的溢出，我们将从以下几个方面来阐述： 
. 无符号整型溢出的具体过程 
. jiffies溢出造成程序逻辑 出错 
. Linux内核如何来防止jiffies溢出 
. time_after等比较时间先/后的宏背后的原理 
. 代码中 使用time_after等比较时间先/后的宏 

3. 无符号整型溢出的具体过程 
我们首先来看看无符号长整型（unsigned long）溢出的具体过程。实际上，无符号整型的溢出过 程都很类似。为了更具体地描述无符号长整型溢出的过程，我们以8位无符号整型为例来加以说明。 
8位无符号整型从0开始持续增长，当增长到最大值 255时，继续加1将变为0，然后该过程周而复始： 
0, 1, 2, ..., 253, 254, 255, 
0, 1, 2, ..., 253, 254, 255, 
... 

4. jiffies溢出造成程序逻辑出错 
下面，通过一个例子来看jiffies的溢出。 
例4-1：jiffies溢出造成程 序逻辑出错 
unsigned long timeout = jiffies + HZ/2; /* timeout in 0.5s */ 

/* do some work ... */ 
do_somework(); 

/* then see whether we took too long */ 
if (timeout > jiffies) { 
/* we did not time out, call no_timeout_handler() ... */ 
no_timeout_handler(); 

} else { 
/* we timed out, call timeout_handler() ... */ 
timeout_handler(); 
} 
本 例的目的是从当前时间起，如果在0.5秒内执行完do_somework()，则调用no_timeout_handler()。如果在0.5秒后执行完 do_somework()，则调用timeout_handler()。 
我们来看看本例中一种可能的溢出情况，即在设置timeout并执行 do_somework()后，jiffies值溢出，取值为0。设在设置timeout后，timeout的值临近无符号长整型的最大值，即小于 2^32-1。设执行do_somework()花费了1秒，那么代码应当调用timeout_handler()。但是当jiffies值溢出取值为0 后，条件timeout > jiffies成立，jiffies值（等于0）小于timeout（临近但小于2^32-1），尽管从逻辑上讲 jiffies值要比timeout大。但最终代码调用的是no_timeout_handler()，而不是timeout_handler()。 

5. Linux内核如何来防止jiffies溢出 
Linux内核中提供了以下四个宏，可有效地解决由于jiffies溢出而造成程序逻 辑出错的情况。下面是从Linux Kernel 2.6.7版本中摘取出来的代码： 
/* 
* These inlines deal with timer wrapping correctly. You are 
* strongly encouraged to use them 
* 1. Because people otherwise forget 
* 2. Because if the timer wrap changes in future you won't have to 
* alter your driver code. 
* 
* time_after(a,b) returns true if the time a is after time b. 
* 
* Do this with "<0" and ">=0" to only test the sign of the result. A 
* good compiler would generate better code (and a really good compiler 
* wouldn't care). Gcc is currently neither. 
*/ 
#define time_after(a,b) \ 
(typecheck(unsigned long, a) && \ 
typecheck(unsigned long, b) && \ 
((long)(b) - (long)(a) < 0)) 
#define time_before(a,b) time_after(b,a) 

#define time_after_eq(a,b) \ 
(typecheck(unsigned long, a) && \ 
typecheck(unsigned long, b) && \ 
((long)(a) - (long)(b) >= 0)) 
#define time_before_eq(a,b) time_after_eq(b,a) 

在宏time_after中，首先确保两个输入参数a和b的数据类型为unsigned long，然后才执行实际的比较。这是以后编码中应当注意 的地方。 

6. time_after等比较时间先后的宏背后的原理 
那么，上述time_after等比较时间先/后的宏为什么能够解决 jiffies溢出造成的错误情况呢？ 
我们仍然以8位无符号整型(unsigned char)为例来加以说明。仿照上面的 time_after宏，我们可以给出简化的8位无符号整型对应的after宏： 
#define uc_after(a, b) ((char)(b) - (char)(a) < 0) 

设a和b的数据类型为unsigned char，b为临近8位无符号整型最大值附近的一个固定值254，下面给出随着a（设其初始值为254）变 化而得到的计算值： 
a b (char)(b) - (char)(a) 
254 254 0 
255 - 1 
0 - 2 
1 - 3 
... 
124 -126 
125 -127 
126 -128 
127 127 
128 126 
... 
252 2 
253 1 

从上面的计算可以看出，设定b不变，随着a（设其初始值为254）不断增长1，a的取值变化为： 
254, 255, (一次产生溢出) 
0, 1, ..., 124, 125, 126, 127, 126, ..., 253, 254, 255, (二 次产生溢出) 
0, 1, ... 
... 

而(char)(b) - (char)(a)的变化为： 
0, -1, 
-2, -3, ..., -126, -127, -128, 127, 126, ..., 1, 0, -1, 
-2, -3, ... 
... 

从上面的详细过程可以看出，当a取值为254，255, 接着在（一次产生溢出）之后变为0，然后增长到127之前，uc_after(a,b)的 结果都显示a是在b之后，这也与我们的预期相符。但在a取值为127之后，uc_after(a,b)的结果却显示a是在b之前。 
从上面的运算 过程可以得出以下结论： 
使用uc_after(a,b)宏来计算两个8位无符号整型a和b之间的大小（或先/后，before/after）， 那么a和b的取值应当满足以下限定条件： 
. 两个值之间相差从逻辑值来讲应小于有符号整型的最大值。 
. 对于8位无符号整型，两个值 之间相差从逻辑值来讲应小于128。 
从上面可以类推出以下结论： 
对于time_after等比较jiffies先/后的宏，两个值的 取值应当满足以下限定条件： 
两个值之间相差从逻辑值来讲应小于有符号整型的最大值。 
对于32位无符号整型，两个值之间相差从逻辑值来 讲应小于2147483647。 
对于HZ=100，那么两个时间值之间相差不应当超过2147483647/100秒 = 0.69 年 = 248.5天。对于HZ=60，那么两个时间值之间相差不应当超过2147483647/60秒 = 1.135年。在实际代码应用中，需要比较 先/后的两个时间值之间一般都相差很小，范围大致在1秒~1天左右，所以以上time_after等比较时间先/后的宏完全可以放心地用于实际的代码 中。 

7. 代码中使用time_after等比较时间先/后的宏 
下面代码是针对例4-1修改后的正确代码： 
例7-1：在例4-1基 础上使用time_before宏后的正确代码 
unsigned long timeout = jiffies + HZ/2; /* timeout in 0.5s */ 

/* do some work ... */ 
do_somework(); 

/* then see whether we took too long */ 
if (time_before(jiffies, timeout)) { 
/* we did not time out, call no_timeout_handler() ... */ 
no_timeout_handler(); 

} else { 
/* we timed out, call timeout_handler() ... */ 
timeout_handler(); 
} 

8. 结论 
系统中采用jiffies来计算时间，但由于jiffies溢出可能造成时间比较的错误，因而强烈建议在编码中使用 time_after等宏来比较时间先后关系，这些宏可以放心使用。

内核时钟：

内核使用硬件提供的不同时钟来提供依赖于时间的服务，如busy-waiting（浪费CPU周期）和sleep-waiting（放弃CPU）

HZ and Jiffies

      系统时钟以可编程的频率中断处理器，这个频率即每秒滴答数，记录在HZ,选择合适的HZ值是个重要问题，而且HZ值是架构相关的，可以在配置菜单中修改。 【2.6.21核提供了对tickless kernel(CONFIG_NO_HZ)的支持，它会根据系统负载动态触发时钟中断】。

      jiffies记录了系统启动后的滴答数，常用的函数：time_before()、 time_after()、time_after_eq()、time_before_eq()。因为jiffies随时钟滴答变化，不能 用编译器优化它，应取volatile值。

      32位jiffies变量会在50天后溢出，太小，因此内核提供变量jiffies_64来hold 64位jiffies。该64位的低32位即为jiffies，在32位机上需要两天指令来赋值64位数据，不是原子的，因此内核提供函数 get_jiffies_64()。

Long Delays

      busy-wait：timebefore(),使CPU忙等待；sleep-wait：shedule_timeout(截至时间)；无论在内核空间还 是用户空间，都没有比HZ更精确的控制了，因为时间片都是根据滴答更新的，而且即使定义了您的进程在超过指定时间后运行，调度器也可能根据优先级选择其他 进程执行。

      sleep-wait()：wait_event_timeout()用于在满足某个条件或超时后重新执行，msleep()睡眠指定的ms后重新进入就 绪队列，这些长延迟仅适用于进程上下文，在中断上下文中不能睡眠也不能长时间busy-waiting。

内核提供了timer API来在一定时间后执行某个函数：

#include

struct timer_list my_timer;

init_timer(&my_timer);            /* Also see setup_timer() */
my_timer.expire = jiffies + n*HZ; /* n is the timeout in number
                                     of seconds */
my_timer.function = timer_func;   /* Function to execute
                                     after n seconds */
my_timer.data = func_parameter;   /* Parameter to be passed
                                     to timer_func */
add_timer(&my_timer);             /* Start the timer */

如果您想周期性执行上述代码，那么把它们加入timer_func()函数。您使用mod_timer()来改变my_timer的 超时值，del_timer()来删掉my_timer， 用timer_pending()查看是否my_timer处于挂起状态。

      用户空间函数clock_settime()和clock_gettime()用 于获取内核时钟服务。用户应用程序使用setitimer()和getitimer()来控制alarm信号的传递当指定超时发生后。

Short Delays

前面讨论的sleep-wait不适用，只能用busy-wait方法。内核用于short delay的有mdelay()、udelay()、ndelay()。

      Busy-waiting对于short durations的实现是通过衡量处理器执行一条指令和必要数量的反复loop来实现的，根据loops_per_jiffy实现。

Pentium Time Stamp Counter

      Time Stamp Counter(TSC)是一个64位寄存器，仅出现在奔腾兼容机上，记录了自启动后处理器消耗的clock cycles数目。TSC是以processor cycle速率增长的，使用rdtsc()读 取，提供微秒级的精确度。TSC ticks可以通过除以CPU时钟速率来转换成秒数，这可以从cpu_khz读 取。

unsigned long low_tsc_ticks0, high_tsc_ticks0;
unsigned long low_tsc_ticks1, high_tsc_ticks1;
unsigned long exec_time;
rdtsc(low_tsc_ticks0, high_tsc_ticks0); /* Timestamp
                                           before */
printk("Hello World\n");                /* Code to be
                                           profiled */
rdtsc(low_tsc_ticks1, high_tsc_ticks1); /* Timestamp after */
exec_time = low_tsc_ticks1 - low_tsc_ticks0;

从核2.6.21已经提供high-resolution timers(CONFIG_HIGH_RES_TIMERS)， 它利用硬件相关高速时钟来提供高精确度的功能函数如nanosleep()。奔腾机上使用 TSC实现该功能。

Real Time Clock

      RTC时钟track绝对时间，记录在非易失性存储器中。RTC电池常超过computer生存期。可以用RTC完成以下功能：（1）、读或设置绝对时 钟，并在clock updates时产生中断；（2）以2HZ到8192HZ来产生周期性中断；（3）设置alarms。

      jiffies仅是相对于系统启动的相对时间，如果想获取absolute time或wall time，则需要使用RTC，内核用变量xtime来记录，当系统启动时，读取RTC并记录 在xtime中，当系统halt时，则将wall time写回RTC，函数do_gettimeofday()来读取wall time。

#include
static struct timeval curr_time;
do_gettimeofday(&curr_time);
my_timestamp = cpu_to_le32(curr_time.tv_sec); /* Record timestamp */

      用户空间获取wall time的函数：time()返回calendar time或从00：00：00 on January 1，1970的秒数；（2）localtime()：返回calendar time in broken-down format；（3）mktime()：与 localtime()相反；（4）gettimeofday()以microsecond 精确度返回calendar时间（需硬件支持）

      另外一个获取RTC的方法是通过字符设备/dev/rtc，一个时刻仅允许一个处理器访问它。

时钟和定时器对Linux内核来说十分重要。首先内核要管理系统的运行时间(uptime)和当前墙上时间(wall time)， 即当前实际时间。其次，内核中大量的活动由时间驱动(time driven)。其中一些活动是周期性的，比如调度调度器(scheduler)中的运行队列(runqueue)或者刷新屏幕这样的活动，它们以固有的 频率定时发生；同时，内核要非周期性地调度某些函数在未来某个时间发生，比如推迟执行的磁盘I/O操作等。


实时时钟
---------------------------------------------------------
    内核必须借助硬件来实现时间管理。实时时钟(real time clock)是用来持久存放系统时间的设备，它与CMOS集成在一起，并通过主板电池供电，所以即便在关闭计算机系统之后，实时时钟仍然能继续工作。
    系统启动时，内核读取实时时钟，将所读的时间存放在变量xtime中作为墙上时间(wall time)，xtime保存着从1970年1月1日0:00到当前时刻所经历的秒数。虽然在Intel x86机器上，内核会周期性地将当前时间存回实时时钟中，但应该明确，实时时钟的主要作用就是在启动时初始化墙上时间xtime。



系统定时器与动态定时器
---------------------------------------------------------
    周期性发生的事件都是由系统定时器(system timer)驱动。在X86体系结构上，系统定时器通常是一种可编程硬件芯片(如8254 CMOS芯片)，又称可编程间隔定时器(PIT， Programmable Interval Timer)，其产生的中断就是时钟中断(timer interrupt)。时钟中断对应的处理程序负责更新系统时间和执行周期性运行的任务。系统定时器的频率称为节拍率(tick rate)，在内核中表示为HZ。
    以X86为例，在2.4之前的内核中其大小为100； 从内核2.6开始，HZ = 1000， 也就是说每秒时钟中断发生1000次。这一变化使得系统定时器的精度(resolution)由10ms提高到1ms，这大大提高了系统对于时间驱动事件 调度的精确性。过于频繁的时钟中断不可避免地增加了系统开销(overhead)，但是总的来说，在现在计算机系统上，HZ = 1000不会导致难以接受的系统开销。
    与系统定时器相对的是动态定时器(dynamic timer)，它是调度事件(执行调度程序)在未来某个时刻发生的时机。内核可以动态地创建或销毁动态定时器。
    系统定时器及其中断处理程序是内核管理机制的中枢，下面是一些利用系统定时器周期执行的工作(中断处理程序所做的工作):
    (1) 更新系统运行时间(uptime)
    (2) 更新当前墙上时间(wall time)
    (3) 在对称多处理器系统(SMP)上，均衡调度各处理器上的运行队列
    (4) 检查当前进程是否用完了时间片(time slice)，如果用尽，则进行重新调度
    (5) 运行超时的动态定时器
    (6) 更新资源耗尽和处理器时间的统计值

    内核动态定时器依赖于系统时钟中断，因为只有在系统时钟中断发生后内核才会去检查当前是否有超时的动态定时器。

   
    X86体系结构中时钟资源还包括CPU本地APIC(local Advanced Programmable Interrupt Controller)中的定时器和时间戳计时器TSC(Time Stamp Counter)。高精度定时器将使用CPU本地APIC作为高精度定时中断源。



高精度定时器的设计与实现
---------------------------------------------------------
    X86体系结构中，内核2.6.X的HZ = 1000， 即系统时钟中断执行粒度为1ms，这意味着系统中周期事情最快为1ms执行一次，而不可能有更高的精度。动态定时器随时都可能超时，但由于只有在系统时钟 中断到来时内核才会检查执行超时的动态定时器，所以动态定时器的平均误差大约为半个系统时钟周期(即0.5ms).
    对于实时要求较高的电信应用来说，普通Linux在实时性方面与电信平台的要求之间还存在一定的差距。CGL为了增强Linux的软实时能力，在以下方面 对内核进行了改进:提供高精度的动态定时器；提供可抢占式内核(preemption kernel)等。下面主要介绍高精度实时器的设计思想及实现，该实现遵循PISIX 1003.1b中时钟和定时器相关API标准，方便应用程序开发人员的使用。
    高精度定时器的基本设计思想为:用 (jiffies+sub_jiffie)表示动态定时器的超时时间，PIT仍然按频率HZ = 1000产生系统时钟中断。如果在一个时钟中断tick与下一个时钟中断(tick+1)之间，即[jiffies, jiffies+1)之间，有高精度动态定时器等待处理(超时时间表示为(jiffies+sub_jiffie), sub_jiffie < 1)， 那么用最近的动态定时器超时值sub_jiffie对硬件定时器(PIT或local APIC)进行设定，使其在时刻(jiffies+sub_jiffie)产生中断，通知内核对该高精度定时器进行处理。而不必总是等到系统时钟中断到来 后才检查执行所有超时的定时器，从而达到提高动态定时器精度的目的。



高精度定时器的中断源
---------------------------------------------------------
    高精度定时器在内核中，仍然使用可编程间隔定时器PIC产生每秒HZ次的系统时钟中断，对于采用哪种硬件定时器产生高精度定时器中断则取决于CPU上是否 有本地APIC。若CPU上没有本地APIC，那么仍可使用PIT产生高精度定时中断，虽然这种然PIT即产生系统时钟中断又产生高精度定时器中断的做法 效率不高。


获取高精度定时器的发生时间
---------------------------------------------------------
    高精度定时器发生在连续两个jiffies之间(即时刻(jiffies+sub_jiffie))，要确定其产生时间，就必须确定sub_jiffie 的大小。通过函数get_arch_cycles(ref_jiffies)可获取sub_jiffie的值，sub_jiffe以CPU时钟周期为最小 计时单位。函数具体实现思想是，通过访问计数器TSC，计算从上一个jiffies到当前时刻ref_jiffies之间的TSC差值，最终确定 sub_jiffies的大小。


The high-resolution timer API
---------------------------------------------------------
    Last September, this page featured an article on the ktimers patch by Thomas Gleixner. The new timer abstraction was designed to enable the provision of high-resolution timers in the kernel and to address some of the inefficiencies encountered when the current timer code is used in this mode. Since then, there has been a large amount of discussion, and the code has seen significant work. The end product of that work, now called "hrtimers," was merged for the 2.6.16 release.

    At its core, the hrtimer mechanism remains the same. Rather than using the "timer wheel" data structure, hrtimers live on a time-sorted linked list, with the next timer to expire being at the head of the list. A separate red/black tree is also used to enable the insertion and removal of timer events without scanning through the list. But while the core remains the same, just about everything else has changed, at least superficially.


struct ktime_t
-----------------------------
    There is a new type, ktime_t, which is used to store a time value in nanoseconds. This type, found in , is meant to be used as an opaque structure. And, interestingly, its definition changes depending on the underlying architecture. On 64-bit systems, a ktime_t is really just a 64-bit integer value in nanoseconds. On 32-bit machines, however, it is a two-field structure: one 32-bit value holds the number of seconds, and the other holds nanoseconds. The order of the two fields depends on whether the host architecture is big-endian or not; they are always arranged so that the two values can, when needed, be treated as a single, 64-bit value. Doing things this way complicates the header files, but it provides for efficient time value manipulation on all architectures.

struct--ktime_t
typedef union {
On 64-bit systems
|----------------------|
|   s64 tv64;          |
|----------------------|

On 32-bit machines
|----------------------|
|    struct {          |
|       s32 sec, nsec; |
|       s32 nsec, sec; |
|   } tv;              |
|----------------------|
} ktime_t;




初始化ktime_t
-----------------------------
    A whole set of functions and macros has been provided for working with ktime_t values, starting with the traditional two ways to declare and initialize them(ktime_t values):
    (1) Initialize to zero
           DEFINE_KTIME(name);  

       (2) ktime_t kt;
           kt = ktime_set(long secs, long nanosecs);



初始化高精度时钟hrtimer
-----------------------------
    The interface for hrtimers can be found in . A timer is represented by struct hrtimer, which must be initialized with:

    void hrtimer_init(struct hrtimer *timer, clockid_t which_clock);



System clocks
-----------------------------
    Every hrtimer is bound to a specific clock. The system currently supports two clocks, being:

    * CLOCK_MONOTONIC: a clock which is guaranteed always to move forward in time, but which does not reflect "wall clock time" in any specific way. In the current implementation, CLOCK_MONOTONIC resembles the jiffies tick count in that it starts at zero when the system boots and increases monotonically from there.

    * CLOCK_REALTIME which matches the current real-world time.

    The difference between the two clocks can be seen when the system time is adjusted, perhaps as a result of administrator action, tweaking by the network time protocol code, or suspending and resuming the system. In any of these situations, CLOCK_MONOTONIC will tick forward as if nothing had happened, while CLOCK_REALTIME may see discontinuous changes. Which clock should be used will depend mainly on whether the timer needs to be tied to time as the rest of the world sees it or not. The call to hrtimer_init() will tie an hrtimer to a specific clock, but that clock can be changed with:

    void hrtimer_rebase(struct hrtimer *timer, clockid_t new_clock);



hrtimer_start()
-----------------------------
    Actually setting a timer is accomplished with:

    int hrtimer_start(struct hrtimer    *timer,
                      ktime_t           time,
                      enum hrtimer_mode mode);

    The mode parameter describes how the time parameter should be interpreted. A mode of HRTIMER_ABS indicates that time is an absolute value, while HRTIMER_REL indicates that time should be interpreted relative to the current time.