一文讀懂 Linux 定時器實現

定時器原理

一般定時器實現的方式有以下幾種：

基於排序鏈表方式：

圖片

基於最小堆方式：

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

圖片

基於平衡二叉樹方式：

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

圖片

時間輪：

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

圖片

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

圖片

一般的定時器範圍爲一個 32 位整型的大小，也就是 0 ~ 4294967295，如果通過一個數組來存儲的話，就需要一個元素個數爲 4294967296 的數組，非常浪費內存。這個時候就可以通過類似於時鐘的方式：通過多級數組來存儲。時鐘通過時分秒來進行分級，當然我們也可以這樣，但對於計算機來說，時分秒的分級不太友好，所以 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秒。如下圖：

圖片

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

每級數組上面都有一個指針，指向當前要執行的定時器。每當時間走一秒，Linux 首先會移動第一級的指針，然後執行當前位置上的定時器。當指針變爲 0 時，會移動下一級的指針，並把該位置上的定時器重新計算一次並且插入到時間輪中，其他級如此類推。如下圖所示：

圖片

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

Linux 時間輪的實現

那麼接下來我們看看 Linux 內核是怎麼實現時間輪算法的。

定義五個等級的數組

#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);
}

上面的代碼定義第一級數組爲 timer_vec_root 類型，其 index 成員是當前要執行的定時器指針（對應 vec 成員的下標），而 vec 成員是一個鏈表數組，數組元素個數爲 256，每個元素上保存了該秒到期的定時器列表，其他等級的數組類似。

插入定時器

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() 函數的主要工作是計算定時器到期時間所屬的等級範圍，然後把定時器添加到鏈表中。

執行到期的定時器

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);
}

執行到期的定時器主要通過 run_timer_list() 函數完成，該函數首先比較當前時間與最後一次運行 run_timer_list() 函數時間的差值，然後循環這個差值的次數，並執行當前指針位置上的定時器。每循環一次對第一級數組指針進行加一操作，當第一級數組指針變爲 0（即所有定時器都執行完），那麼就移動下一個等級的指針，並把該位置上的定時器重新計算插入到時間輪中，重新計算定時器通過 cascade_timers() 函數實現。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/zdQY-I4KY5nuHrXySuAjlA