定時(shí)器原理以及一般定時(shí)器實(shí)現(xiàn)的方式

定時(shí)器原理一般定時(shí)器實(shí)現(xiàn)的方式有以下幾種：

基于排序鏈表方式：

通過(guò)排序鏈表來(lái)保存定時(shí)器，由于鏈表是排序好的，所以獲取最?。ㄗ钤绲狡冢┑亩〞r(shí)器的時(shí)間復(fù)雜度為 O（1）。但插入需要遍歷整個(gè)鏈表，所以時(shí)間復(fù)雜度為 O（n）。如下圖：

基于最小堆方式：

通過(guò)最小堆來(lái)保存定時(shí)器，在最小堆中獲取最小定時(shí)器的時(shí)間復(fù)雜度為 O（1），但插入一個(gè)定時(shí)器的時(shí)間復(fù)雜度為 O（log n）。如下圖：

基于平衡二叉樹方式：

使用平衡二叉樹（如紅黑樹）保存定時(shí)器，在平衡二叉樹中獲取最小定時(shí)器的時(shí)間復(fù)雜度為 O（log n）（也可以通過(guò)緩存最小值的方法來(lái)達(dá)到 O（1）），而插入一個(gè)定時(shí)器的時(shí)間復(fù)雜度為 O（log n）。如下圖：

時(shí)間輪：

但對(duì)于Linux這種對(duì)定時(shí)器依賴性比較高（網(wǎng)絡(luò)子模塊的TCP協(xié)議使用了大量的定時(shí)器）的操作系統(tǒng)來(lái)說(shuō)，以上的數(shù)據(jù)結(jié)構(gòu)都是不能滿足要求的。所以Linux使用了效率更高的定時(shí)器算法：時(shí)間輪。

時(shí)間輪 類似于日常生活的時(shí)鐘。

日常生活的時(shí)鐘，每當(dāng)秒針轉(zhuǎn)一圈時(shí)，分針就會(huì)走一格，而分針走一圈時(shí)，時(shí)針就會(huì)走一格。而時(shí)間輪的實(shí)現(xiàn)方式與時(shí)鐘類似，就是把到期時(shí)間當(dāng)成一個(gè)輪，然后把定時(shí)器掛在這個(gè)輪子上面，每當(dāng)時(shí)間走一秒就移動(dòng)時(shí)針，并且執(zhí)行那個(gè)時(shí)針上的定時(shí)器。

一般的定時(shí)器范圍為一個(gè)32位整型的大小，也就是 0 ~ 4294967295，如果通過(guò)一個(gè)數(shù)組來(lái)存儲(chǔ)的話，就需要一個(gè)元素個(gè)數(shù)為4294967296的數(shù)組，非常浪費(fèi)內(nèi)存。這個(gè)時(shí)候就可以通過(guò)類似于時(shí)鐘的方式：通過(guò)多級(jí)數(shù)組來(lái)存儲(chǔ)。

時(shí)鐘通過(guò)時(shí)分秒來(lái)進(jìn)行分級(jí)，當(dāng)然我們也可以這樣，但對(duì)于計(jì)算機(jī)來(lái)說(shuō)，時(shí)分秒的分級(jí)不太友好，所以Linux內(nèi)核中，對(duì)32位整型分為5個(gè)級(jí)別，第一個(gè)等級(jí)存儲(chǔ)0 ~ 255秒 的定時(shí)器，第二個(gè)等級(jí)為 256秒 ~ 256*64秒，第三個(gè)等級(jí)為 256*64秒 ~ 256*64*64秒，第四個(gè)等級(jí)為 256*64*64秒 ~ 256*64*64*64秒，第五個(gè)等級(jí)為 256*64*64*64秒 ~ 256*64*64*64*64秒。

注意：第二級(jí)至第五級(jí)數(shù)組的第一個(gè)槽是不掛任何定時(shí)器的。

每級(jí)數(shù)組上面都有一個(gè)指針，指向當(dāng)前要執(zhí)行的定時(shí)器。每當(dāng)時(shí)間走一秒，Linux首先會(huì)移動(dòng)第一級(jí)的指針，然后執(zhí)行當(dāng)前位置上的定時(shí)器。當(dāng)指針變?yōu)?時(shí)，會(huì)移動(dòng)下一級(jí)的指針，并把該位置上的定時(shí)器重新計(jì)算一次并且插入到時(shí)間輪中，其他級(jí)如此類推。

當(dāng)要執(zhí)行到期的定時(shí)器只需要移動(dòng)第一級(jí)數(shù)組上的指針并且執(zhí)行該位置上的定時(shí)器列表即可，所以時(shí)間復(fù)雜度為 O（1），而插入一個(gè)定時(shí)器也很簡(jiǎn)單，先計(jì)算定時(shí)器的過(guò)期時(shí)間范圍在哪一級(jí)數(shù)組上，并且連接到該位置上的鏈表即可，時(shí)間復(fù)雜度也是 O（1）。

Linux時(shí)間輪的實(shí)現(xiàn)那么接下來(lái)我們看看Linux內(nèi)核是怎么實(shí)現(xiàn)時(shí)間輪算法的。

定義五個(gè)等級(jí)的數(shù)組

#define TVN_BITS 6#define TVR_BITS 8#define TVN_SIZE （1 《《 TVN_BITS） // 64#define TVR_SIZE （1 《《 TVR_BITS） // 256#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;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）;

}

上面的代碼定義第一級(jí)數(shù)組為 timer_vec_root 類型，其 index 成員是當(dāng)前要執(zhí)行的定時(shí)器指針（對(duì)應(yīng) vec 成員的下標(biāo)），而 vec 成員是一個(gè)鏈表數(shù)組，數(shù)組元素個(gè)數(shù)為256，每個(gè)元素上保存了該秒到期的定時(shí)器列表，其他等級(jí)的數(shù)組類似。

插入定時(shí)器

static inline void internal_add_timer（struct timer_list *timer）

{

/*

* must be cli-ed when calling this

*/

unsigned long expires = timer-》expires;

unsigned long idx = expires - timer_jiffies;

struct list_head * vec;

if （idx 《 TVR_SIZE） { // 0 ~ 255

int i = expires & TVR_MASK;

vec = tv1.vec + i;

} else if （idx 《 1 《《 （TVR_BITS + TVN_BITS）） { // 256 ~ 16191

int i = （expires 》》 TVR_BITS） & TVN_MASK;

vec = tv2.vec + i;

} else if （idx 《 1 《《 （TVR_BITS + 2 * TVN_BITS）） {

int i = （expires 》》 （TVR_BITS + TVN_BITS）） & TVN_MASK;

vec = tv3.vec + i;

} else if （idx 《 1 《《 （TVR_BITS + 3 * TVN_BITS）） {

int i = （expires 》》 （TVR_BITS + 2 * TVN_BITS）） & TVN_MASK;

vec = tv4.vec + i;

} else if （（signed long） idx 《 0） {

/* can happen if you add a timer with expires == jiffies，

* or you set a timer to go off in the past

*/

vec = tv1.vec + tv1.index;

} else if （idx 《= 0xffffffffUL） {

int i = （expires 》》 （TVR_BITS + 3 * TVN_BITS）） & TVN_MASK;

vec = tv5.vec + i;

} else {

/* Can only get here on architectures with 64-bit jiffies */

INIT_LIST_HEAD（&timer-》list）;

return;

}

/*

* 添加到鏈表中

*/

list_add（&timer-》list， vec-》prev）;

}

internal_add_timer（） 函數(shù)的主要工作是計(jì)算定時(shí)器到期時(shí)間所屬的等級(jí)范圍，然后把定時(shí)器添加到鏈表中。

執(zhí)行到期的定時(shí)器

static inline void cascade_timers（struct timer_vec *tv）

{

/* cascade all the timers from tv up one level */

struct list_head *head， *curr， *next;

head = tv-》vec + tv-》index;

curr = head-》next;

/*

* We are removing _all_ timers from the list， so we don‘t have to

* detach them individually， just clear the list afterwards.

*/

while （curr ！= head） {

struct timer_list *tmp;

tmp = list_entry（curr， struct timer_list， list）;

next = curr-》next;

list_del（curr）;

internal_add_timer（tmp）;

curr = next;

}

INIT_LIST_HEAD（head）;

tv-》index = （tv-》index + 1） & TVN_MASK;

}

static inline void run_timer_list（void）

{

spin_lock_irq（&timerlist_lock）;

while （（long）（jiffies - timer_jiffies） 》= 0） {

struct list_head *head， *curr;

if （！tv1.index） { // 完成了一個(gè)輪回， 移動(dòng)下一個(gè)單位的定時(shí)器

int n = 1;

do {

cascade_timers（tvecs［n］）;

} while （tvecs［n］-》index == 1 && ++n 《 NOOF_TVECS）;

}

repeat：

head = tv1.vec + tv1.index;

curr = head-》next;

if （curr ！= head） {

struct timer_list *timer;

void （*fn）（unsigned long）;

unsigned long data;

timer = list_entry（curr， struct timer_list， list）;

fn = timer-》function;

data= timer-》data;

detach_timer（timer）;

timer-》list.next = timer-》list.prev = NULL;

timer_enter（timer）;

spin_unlock_irq（&timerlist_lock）;

fn（data）;

spin_lock_irq（&timerlist_lock）;

timer_exit（）;

goto repeat;

}

++timer_jiffies;

tv1.index = （tv1.index + 1） & TVR_MASK;

}

spin_unlock_irq（&timerlist_lock）;

}

執(zhí)行到期的定時(shí)器主要通過(guò) run_timer_list（） 函數(shù)完成，該函數(shù)首先比較當(dāng)前時(shí)間與最后一次運(yùn)行 run_timer_list（） 函數(shù)時(shí)間的差值，然后循環(huán)這個(gè)差值的次數(shù)，并執(zhí)行當(dāng)前指針位置上的定時(shí)器。

每循環(huán)一次對(duì)第一級(jí)數(shù)組指針進(jìn)行加一操作，當(dāng)?shù)谝患?jí)數(shù)組指針變?yōu)?（即所有定時(shí)器都執(zhí)行完），那么就移動(dòng)下一個(gè)等級(jí)的指針，并把該位置上的定時(shí)器重新計(jì)算插入到時(shí)間輪中，重新計(jì)算定時(shí)器通過(guò) cascade_timers（） 函數(shù)實(shí)現(xiàn)。

編輯：jq