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類似。