深入剖析Linux内核定时器实现机制

Sailor_forever  sailing_9806@163.com 转载请注明

http://blog.csdn.net/sailor_8318/archive/2008/07/09/2627136.aspx

 

【摘要】本文详解了Linux内核的定时器实现机制。具体分析了定时器的分级组织结构，以及在此基础之上的插入、更新、扫描执行等过程。其动态刷新维护的机制值得借鉴。然后介绍了内核定时器相关的API。

【关键字】内核定时器，分级结构，定时器迁移刷新，DEFINE_TIMER，init_timer，setup_timer，add_timer，mod_timer，del_timer

 

1       内核定时器概述

Linux内核2.4版中去掉了老版本内核中的静态定时器机制，而只留下动态定时器。动态定时器与静态定时器这二个概念是相对于Linux内核定时器机制的可扩展功能而言的，动态定时器是指内核的定时器队列是可以动态变化的，然而就定时器本身而言，二者并无本质的区别。考虑到静态定时器机制的能力有限，因此Linux内核2.4版中完全去掉了以前的静态定时器机制。2.6内核为了支持SMP及CPU热插拔，对定时器相关结构又做了改动。本文所有代码基于2.6.19内核http://lxr.linux.no/linux+v2.6.19。

Linux

  11        struct list_head entry;

  12        unsigned long expires;

  13

  14        void (*function)(unsigned long);

  15        unsigned long data;

  16

  17        struct tvec_t_base_s *base;

  18};
各数据成员的含义如下： 

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

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

²      函数指针function：指向一个可执行函数。当定时器到期时，内核就执行function所指定的函数。

²      data域：被内核用作function函数的调用参数。 

²      base：当前timer所属的base。由于考虑了SMP的情况，每个CPU都含有一个base。

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值可以互不相同的一个定时器队列。 

各定时器向量数据结构定义在kernel/timer.c文件中，如下述代码段所示： 

/////////////////////////////////////////////// 2.4.19内核  ///////////////////////////////////////////////

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

};

 

static struct list_head * run_timer_list_running;

static unsigned long timer_jiffies;

/* Initialize both explicitly - let's try to have them in the same cache line */

spinlock_t timerlist_lock = SPIN_LOCK_UNLOCKED;

volatile struct timer_list * volatile running_timer;

/////////////////////////////////////////////// 2.4.19内核  ///////////////////////////////////////////////

 

/////////////////////////////////////////////// 2.6.19内核  ///////////////////////////////////////////////
  51#define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6)

  52#define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8)

  53#define TVN_SIZE (1 << TVN_BITS)

  54#define TVR_SIZE (1 << TVR_BITS)

  55#define TVN_MASK (TVN_SIZE - 1)

  56#define TVR_MASK (TVR_SIZE - 1)

  58typedef struct tvec_s {

  59        struct list_head vec[TVN_SIZE];

  60} tvec_t;

  61

  62typedef struct tvec_root_s {

  63        struct list_head vec[TVR_SIZE];

  64} tvec_root_t;

  65

  66struct tvec_t_base_s {

  67        spinlock_t lock;

  68        struct timer_list *running_timer;

  69        unsigned long timer_jiffies;

  70        tvec_root_t tv1;

  71        tvec_t tv2;

  72        tvec_t tv3;

  73        tvec_t tv4;

  74        tvec_t tv5;

  75} ____cacheline_aligned_in_smp;

  76

  77typedef struct tvec_t_base_s tvec_base_t;

  78

  79tvec_base_t boot_tvec_bases;

  80EXPORT_SYMBOL(boot_tvec_bases);

 

²      lock：由于内核动态定时器链表是一种系统全局共享资源，为了实现对它的互斥访问，Linux定义了专门的自旋锁