Linux2.6定时器的时间轮算法分析

1.     Overview
常用的定时器实现算法有两种：红黑树和时间轮（timing wheel）。

在Linux2.6的代码中，kernel/timer.c文件实现了一个通用定时器机制，使用的是时间轮算法。

每一个CPU都有一个struct tvec_base结构，代表这个CPU使用的时间轮。

struct tvec_base

{

       spinlock_t lock;                                  // 同步锁

       struct timer_list * running_timer;         // 当前正在运行的定时器

       unsigned long timer_jiffies;                  // 当前运行到的jiffies

       struct tvec_root tv1;                          

       struct tvec tv2;

       struct tvec tv3;

       struct tvec tv4;

       struct tvec tv5;

} 

struct tvec_root与struct tvec都是数组，数组中的每一项都指定一个链表。struct tvec_root定义的数组大小是256(2的8次方)；struct tvec_root定义的数组大小是64（2的6次方）。所以，tv1~6定义的数组总大小是2的（8 + 4*6 = 32）次方，正好对应32位处理器中jiffies的定义（unsigned long）。

因为使用的是wheel算法，tv1~5就代表5个wheel。

tv1是转速最快的wheel，所有在256个jiffies内到期的定时器都会挂在tv1的某个链表头中。

tv2是转速第二快的wheel，里面挂的定时器超时jiffies在2^8 ~ 2^(8+6)之间。

tv3是转速第三快的wheel，超时jiffies在2^(8+6) ~ 2^(8+2*6)之间。

tv4、tv5类似。