[[416836]]

定時器原理

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

基于排序鏈表方式：

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

圖片

基于最小堆方式：

通過最小堆來保存定時器，在最小堆中獲取最小定時器的時間復雜度為 O(1)，但插入一個定時器的時間復雜度為 O(log n)。如下圖：

圖片

基于平衡二叉樹方式：

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

圖片

時間輪：

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

時間輪 類似于日常生活的時鐘，如下圖：

圖片

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

圖片

一般的定時器范圍為一個32位整型的大小，也就是 0 ~ 4294967295，如果通過一個數(shù)組來存儲的話，就需要一個元素個數(shù)為4294967296的數(shù)組，非常浪費內存。這個時候就可以通過類似于時鐘的方式：通過多級數(shù)組來存儲。時鐘通過時分秒來進行分級，當然我們也可以這樣，但對于計算機來說，時分秒的分級不太友好，所以Linux內核中，對32位整型分為5個級別，第一個等級存儲0 ~ 255秒 的定時器，第二個等級為 256秒 ~ 256*64秒，第三個等級為 256*64秒 ~ 256*64*64秒，第四個等級為 256*64*64秒 ~ 256*64*64*64秒，第五個等級為 256*64*64*64秒 ~ 256*64*64*64*64秒。如下圖：

圖片

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

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

圖片

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

Linux時間輪的實現(xiàn)

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

定義五個等級的數(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);  
} 

上面的代碼定義第一級數(shù)組為 timer_vec_root 類型，其 index 成員是當前要執(zhí)行的定時器指針（對應 vec 成員的下標），而 vec 成員是一個鏈表數(shù)組，數(shù)組元素個數(shù)為256，每個元素上保存了該秒到期的定時器列表，其他等級的數(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ù)的主要工作是計算定時器到期時間所屬的等級范圍，然后把定時器添加到鏈表中。

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

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) { // 完成了一個輪回, 移動下一個單位的定時器  
            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í)行到期的定時器主要通過 run_timer_list() 函數(shù)完成，該函數(shù)首先比較當前時間與最后一次運行 run_timer_list() 函數(shù)時間的差值，然后循環(huán)這個差值的次數(shù)，并執(zhí)行當前指針位置上的定時器。每循環(huán)一次對第一級數(shù)組指針進行加一操作，當?shù)谝患墧?shù)組指針變?yōu)?（即所有定時器都執(zhí)行完），那么就移動下一個等級的指針，并把該位置上的定時器重新計算插入到時間輪中，重新計算定時器通過 cascade_timers() 函數(shù)實現(xiàn)。