Linux系统内核定时器机制详解

Linux系统内核定时器机制详解（上）

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

7．6．1 Linux内核对定时器的描述

Linux在include/linux/timer.h头文件中定义了数据结构timer_list来描述一个内核定时器：

struct timer_list { 
struct list_head list; 
unsigned long expires; 
unsigned long data; 
void (*function)(unsigned long); 
};

各数据成员的含义如下：

（1）双向链表元素list：用来将多个定时器连接成一条双向循环队列。

（2）expires：指定定时器到期的时间，这个时间被表示成自系统启动以来的时钟滴答计数（也即时钟节拍数）。当一个定时器的expires值小于或等于jiffies变量时，我们就说这个定时器已经超时或到期了。在初始化一个定时器后，通常把它的expires域设置成当前expires变量的当前值加上某个时间间隔值（以时钟滴答次数计）。

（3）函数指针function：指向一个可执行函数。当定时器到期时，内核就执行function所指定的函数。而data域则被内核用作function函数的调用参数。

内核函数init_timer()用来初始化一个定时器。实际上，这个初始化函数仅仅将结构中的list成员初始化为空。如下所示（include/linux/timer.h）：

static inline void init_timer(struct timer_list * timer) 
{ 
timer->list.next = timer->list.prev = NULL; 
}

由于定时器通常被连接在一个双向循环队列中等待执行（此时我们说定时器处于pending状态）。因此函数time_pending()就可以用list成员是否为空来判断一个定时器是否处于pending状态。如下所示

（include/linux/timer.h）： 
static inline int timer_pending (const struct timer_list * timer) 
{ 
return timer->list.next != NULL; 
}

时间比较操作

在定时器应用中经常需要比较两个时间值，以确定timer是否超时，所以Linux内核在timer.h头文件中定义了4个时间关系比较操作宏。这里我们说时刻a在时刻b之后，就意味着时间值a≥b。Linux强烈推荐用户使用它所定义的下列4个时间比较操作宏（include/linux/timer.h）：

#define time_after(a,b) ((long)(b) - (long)(a) < 0) 
#define time_before(a,b) time_after(b,a) 

#define time_after_eq(a,b) ((long)(a) - (long)(b) >= 0) 
#define time_before_eq(a,b) time_after_eq(b,a)

 

7．6．2 动态内核定时器机制的原理

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）具有相同值的定时器都将被组织在同一个松散定时器向量中。因此，为组织所有满足条件0x100≤interval≤0x3fff的定时器，就需要26＝64个松散定时器向量。同样地，为方便起见，这64个松散定时器向量也放在一起形成数组，并作为数据结构timer_vec的一部分。基于数据结构timer_vec，Linux定义了全局变量tv2，来表示这64条松散定时器向量。如上述代码段所示。

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

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

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

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

7．6．3 内核动态定时器机制的实现

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

7．6．3．1 动态定时器机制的初始化

函数init_timervecs()实现对动态定时器机制的初始化。该函数仅被sched_init()初始化例程所调用。动态定时器机制初始化过程的主要任务就是将tv1、tv2、…、tv5这5个结构变量中的定时器向量指针数组vec［］初始化为NULL。如下所示（kernel/timer.c）：

void init_timervecs (void) 
{ 
int i; 

for (i = 0; i < TVN_SIZE; i++) { 
INIT_LIST_HEAD(tv5.vec + i); 
INIT_LIST_HEAD(tv4.vec + i); 
INIT_LIST_HEAD(tv3.vec + i); 
INIT_LIST_HEAD(tv2.vec + i); 
} 
for (i = 0; i < TVR_SIZE; i++) 
INIT_LIST_HEAD(tv1.vec + i); 
}

上述函数中的宏TVN_SIZE是指timer_vec结构类型中的定时器向量指针数组vec［］的大小，值为64。宏TVR_SIZE是指timer_vec_root结构类型中的定时器向量数组vec［］的大小，值为256。

7．6．3．2 动态定时器的时钟滴答基准timer_jiffies

由于动态定时器是在时钟中断的Bottom Half中被执行的，而从TIMER_BH向量被激活到其timer_bh()函数真正执行这段时间内可能会有几次时钟中断发生。因此内核必须记住上一次运行定时器机制是什么时候，也即内核必须保存上一次运行定时器机制时的jiffies值。为此，Linux在kernel/timer.c文件中定义了全局变量timer_jiffies来表示上一次运行定时器机制时的jiffies值。该变量的定义如下所示：

static unsigned long timer_jiffies;

7．6．3．3 对内核动态定时器链表的保护

由于内核动态定时器链表是一种系统全局共享资源，为了实现对它的互斥访问，Linux定义了专门的自旋锁timerlist_lock来保护。任何想要访问动态定时器链表的代码段都首先必须先持有该自旋锁，并且在访问结束后释放该自旋锁。其定义如下（kernel/timer.c）：

/* Initialize both explicitly - let's try to have them in the same cache line */ 
spinlock_t timerlist_lock = SPIN_LOCK_UNLOCKED;