linux内核定时器使用及原理

linux内核定时器使用及原理

内核定时器使用

       内核定时器是内核用来控制在未来某个时间点（基于jiffies）调度执行某个函数的一种机制，其实现位于  和 kernel/timer.c 文件中。

被调度的函数肯定是异步执行的，它类似于一种“软件中断”，而且是处于非进程的上下文中，所以调度函数必须遵守以下规则：

1) 没有 current 指针、不允许访问用户空间。因为没有进程上下文，相关代码和被中断的进程没有任何联系。

2) 不能执行休眠（或可能引起休眠的函数）和调度。

3) 任何被访问的数据结构都应该针对并发访问进行保护，以防止竞争条件。

内核定时器的调度函数运行过一次后就不会再被运行了（相当于自动注销），但可以通过在被调度的函数中重新调度自己来周期运行。

在SMP系统中，调度函数总是在注册它的同一CPU上运行，以尽可能获得缓存的局域性。

内核定时器的数据结构

struct timer_list {

    struct list_head entry;

    unsigned long expires;

    void (*function)(unsigned long);

    unsigned long data;

    struct tvec_base *base;

    /* ... */

};

其中 expires 字段表示期望定时器执行的 jiffies 值，到达该 jiffies 值时，将调用 function 函数，并传递 data 作为参数。当一个定时器被注册到内核之后，entry 字段用来连接该定时器到一个内核链表中。base 字段是内核内部实现所用的。

需要注意的是 expires 的值是32位的，因为内核定时器并不适用于长的未来时间点。

初始化

在使用 struct timer_list 之前，需要初始化该数据结构，确保所有的字段都被正确地设置。初始化有两种方法。

方法一：

DEFINE_TIMER(timer_name, function_name, expires_value, data);

该宏会定义一个名叫 timer_name 内核定时器，并初始化其 function, expires, name 和 base 字段。

方法二：

struct timer_list mytimer;

setup_timer(&mytimer, (*function)(unsigned long), unsigned long data);

mytimer.expires = jiffies + 5*HZ;

注意，无论用哪种方法初始化，其本质都只是给字段赋值，所以只要在运行 add_timer() 之前，expires, function 和 data 字段都可以直接再修改。

关于上面这些宏和函数的定义，参见 include/linux/timer.h。

 

注册

定时器要生效，还必须被连接到内核专门的链表中，这可以通过 add_timer(struct timer_list *timer) 来实现。

重新注册

要修改一个定时器的调度时间，可以通过调用 mod_timer(struct timer_list *timer, unsigned long expires)。mod_timer() 会重新注册定时器到内核，而不管定时器函数是否被运行过。

注销

注销一个定时器，可以通过 del_timer(struct timer_list *timer) 或 del_timer_sync(struct timer_list *timer)。其中 del_timer_sync 是用在 SMP 系统上的（在非SMP系统上，它等于del_timer），当要被注销的定时器函数正在另一个 cpu 上运行时，del_timer_sync() 会等待其运行完，所以这个函数会休眠。另外还应避免它和被调度的函数争用同一个锁。对于一个已经被运行过且没有重新注册自己的定时器而言，注销函数其实也没什么事可做。

int timer_pending(const struct timer_list *timer)

这个函数用来判断一个定时器是否被添加到了内核链表中以等待被调度运行。注意，当一个定时器函数即将要被运行前，内核会把相应的定时器从内核链表中删除（相当于注销）

 

 

动态内核定时器机制的原理

 

       Linux内核2.4版中去掉了老版本内核中的静态定时器机制，而只留下动态定时器。相应地在timer_bh()函数中也不再通过run_old_timers()函数来运行老式的静态定时器。动态定时器与静态定时器这二个概念是相对于Linux内核定时器机制的可扩展功能而言的，动态定时器是指内核的定时器队列是可以动态变化的，然而就定时器本身而言，二者并无本质的区别。考虑到静态定时器机制的能力有限，因此Linux内核2.4版中完全去掉了以前的静态定时器机制。 

     

       Linux是怎样为其内核定时器机制提供动态扩展能力的呢？其关键就在于“定时器向量”的概念。所谓“定时器向量”就是指这样一条双向循环定时器队列（对列中的每一个元素都是一个timer_list结构）：对列中的所有定时器都在同一个时刻到期，也即对列中的每一个timer_list结构都具有相同的expires值。显然，可以用一个timer_list结构类型的指针来表示一个定时器向量。 

      显然，定时器expires成员的值与jiffies变量的差值决定了一个定时器将在多长时间后到期。在32位系统中，这个时间差值的最大值应该是0xffffffff。因此如果是基于“定时器向量”基本定义，内核将至少要维护0xffffffff个timer_list结构类型的指针，这显然是不现实的。 

      另一方面，从内核本身这个角度看，它所关心的定时器显然不是那些已经过期而被执行过的定时器（这些定时器完全可以被丢弃），也不是那些要经过很长时间才会到期的定时器，而是那些当前已经到期或者马上就要到期的定时器（注意！时间间隔是以滴答次数为计数单位的）。 

     基于上述考虑，并假定一个定时器要经过interval个时钟滴答后才到期（interval＝expires－jiffies），则Linux采用了下列思想来实现其动态内核定时器机制：对于那些0≤interval≤255的定时器，Linux严格按照定时器向量的基本语义来组织这些定时器，也即Linux内核最关心那些在接下来的255个时钟节拍内就要到期的定时器，因此将它们按照各自不同的expires值组织成256个定时器向量。而对于那些256≤interval≤0xffffffff的定时器，由于他们离到期还有一段时间，因此内核并不关心他们，而是将它们以一种扩展的定时器向量语义（或称为“松散的定时器向量语义”）进行组织。所谓“松散的定时器向量语义”就是指：各定时器的expires值可以互不相同的一个定时器队列。 

具体的组织方案可以分为两大部分： 

（1）对于内核最关心的、interval值在［0，255］之间的前256个定时器向量，内核是这样组织它们的：这256个定时器向量被组织在一起组成一个定时器向量数组，并作为数据结构timer_vec_root的一部分，该数据结构定义在kernel/timer.c文件中，如下述代码段所示： 


/* 
* Event timer code 
*/ 
#define TVN_BITS 6 
#define TVR_BITS 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 timer_vec { 
int index; 
struct list_head vec[TVN_SIZE]; 
}; 

struct timer_vec_root { 
int index; 
struct list_head vec[TVR_SIZE]; 
}; 

static struct timer_vec tv5; 
static struct timer_vec tv4; 
static struct timer_vec tv3; 
static struct timer_vec tv2; 
static struct timer_vec_root tv1; 

static struct timer_vec * const tvecs[] = { 
(struct timer_vec *)&tv1, &tv2, &tv3, &tv4, &tv5 
}; 
#define NOOF_TVECS (sizeof(tvecs) / sizeof(tvecs[0]))
 
基于数据结构timer_vec_root，Linux定义了一个全局变量tv1，以表示内核所关心的前256个定时器向量。这样内核在处理是否有到期定时器时，它就只从定时器向量数组tv1.vec［256］中的某个定时器向量内进行扫描。而tv1的index字段则指定当前正在扫描定时器向量数组tv1.vec［256］中的哪一个定时器向量，也即该数组的索引，其初值为0，最大值为255（以256为模）。每个时钟节拍时index字段都会加1。显然，index字段所指定的定时器向量tv1.vec［index］中包含了当前时钟节拍内已经到期的所有动态定时器。而定时器向量tv1.vec［index＋k］则包含了接下来第k个时钟节拍时刻将到期的所有动态定时器。当index值又重新变为0时，就意味着内核已经扫描了tv1变量中的所有256个定时器向量。在这种情况下就必须将那些以松散定时器向量语义来组织的定时器向量补充到tv1中来。 

（2）而对于内核不关心的、interval值在［0xff，0xffffffff］之间的定时器，它们的到期紧迫程度也随其interval值的不同而不同。显然interval值越小，定时器紧迫程度也越高。因此在将它们以松散定时器向量进行组织时也应该区别对待。通常，定时器的interval值越小，它所处的定时器向量的松散度也就越低（也即向量中的各定时器的expires值相差越小）；而interval值越大，它所处的定时器向量的松散度也就越大（也即向量中的各定时器的expires值相差越大）。 

       内核规定，对于那些满足条件：0x100≤interval≤0x3fff的定时器，只要表达式（interval>>8）具有相同值(1~64)的定时器都将被组织在同一个松散定时器向量中。因此，为组织所有满足条件0x100≤interval≤0x3fff的定时器，就需要2^6＝64个松散定时器向量。同样地，为方便起见，这64个松散定时器向量也放在一起形成数组，并作为数据结构timer_vec的一部分。基于数据结构timer_vec，Linux定义了全局变量tv2，来表示这64条松散定时器向量。如上述代码段所示。 

       对于那些满足条件0x4000≤interval≤0xfffff的定时器，只要表达式（interval>>8＋6）的值相同的定时器都将被放在同一个松散定时器向量中。同样，要组织所有满足条件0x4000≤interval≤0xfffff的定时器，也需要2^6＝64个松散定时器向量。类似地，这64个松散定时器向量也可以用一个timer_vec结构来描述，相应地Linux定义了tv3全局变量来表示这64个松散定时器向量。 

       对于那些满足条件0x100000≤interval≤0x3ffffff的定时器，只要表达式（interval>>8＋6＋6）的值相同的定时器都将被放在同一个松散定时器向量中。同样，要组织所有满足条件0x100000≤interval≤0x3ffffff的定时器，也需要2^6＝64个松散定时器向量。类似地，这64个松散定时器向量也可以用一个timer_vec结构来描述，相应地Linux定义了tv4全局变量来表示这64个松散定时器向量。 

      对于那些满足条件0x4000000≤interval≤0xffffffff的定时器，只要表达式（interval>>8＋6＋6＋6）的值相同的定时器都将被放在同一个松散定时器向量中。同样，要组织所有满足条件0x4000000≤interval≤0xffffffff的定时器，也需要2^6＝64个松散定时器向量。类似地，这64个松散定时器向量也可以用一个timer_vec结构来描述，相应地Linux定义了tv5全局变量来表示这64个松散定时器向量。 

     最后，为了引用方便，Linux定义了一个指针数组tvecs［］，来分别指向tv1、tv2、…、tv5结构变量。如上述代码所示。 

内核动态定时器机制的实现

     在内核动态定时器机制的实现中，有三个操作是非常重要的：（1）将一个定时器插入到它应该所处的定时器向量中。（2）定时器的迁移，也即将一个定时器从它原来所处的定时器向量迁移到另一个定时器向量中。（3）扫描并执行当前已经到期的定时器。

   代码位置：kernel/kernel/timer.c