圖解｜低精度定時器原理

Linux 內核通常會使用 定時器 來做一些延時的操作，比如常用的 sleep() 系統調用就是使用定時器來實現的。

在 Linux 內核中，有兩種類型的定時器：高精度定時器 與 低精度定時器。低精度定時器基於硬件的時鐘中斷實現的，其定時週期的粒度爲 1/HZ ms。例如，內核 HZ 爲 1000（也就是說 1 秒能夠產生 1000 次時鐘中斷），那麼低精度定時器的最小定時間隔爲 1ms；而高精度定時器可以實現納秒級別的定時（實際的定時週期粒度與 CPU 的主頻有關）。

可能有讀者會問，既然有了高精度定時器，那麼低精度定時器是否可以廢棄呢？答案是否定的，主要原因是使用高精度定時器的成本比低精度定時器要高。所以，如果對時間精度不是非常敏感的話，使用低精度定時器更合適。

本文主要介紹 Linux 內核中的低精度定時器的原理與實現。

時間輪

低精度定時器是基於時鐘中斷實現的，而時鐘中斷的觸發頻率是可以配置的，Linux 內核一般設置爲每秒觸發 1000 次，也就是說每隔 1 毫秒就會觸發一次時鐘中斷。

一般來說，內核中可能會存在成千上萬個定時器，那麼內核如何能夠快速找到將要到期的定時器呢？

在學習數據結構課程時，我們知道用於快速查找有序數據的數據結構有如何幾種：

平衡二叉樹
最大堆 / 最小堆
跳躍表
...

由於這些數據結構的時間複雜度都是 log(n)，對性能要求非常高的內核來說是不能接受的，所以內核使用了一種性能更高的數據結構：時間輪。

時間輪能夠保證在時間複雜度爲 log(1) 的情況下找到將要到期的定時器，下面我們將會介紹時間輪的原理。

時間輪的基本思想是通過數組來保存定時器，而數組的索引就是定時器的過期時間。如下圖所示：

如上圖所示的數組中，索引爲 1 的槽位存放的是 1 毫秒後超時的定時器列表，索引爲 2 的槽位存放的是 2 毫秒後超時的定時器列表，如此類推...

此時，我們可以使用一個指針來指向超時的定時器列表，如下圖所示：

每當時鐘中斷被觸發一次，指針向下移動一位，這樣就能在時間複雜度爲 log(1) 的情況下獲取到期的定時器。

這樣雖然能夠在時間複雜度爲 log(1) 的情況下找到到期的定時器，但如果超時時間非常大的話，那麼用於存儲定時器的數組也會非常巨大，如：定時器的超時時間爲 4294967295 毫秒，那麼將需要一個大小爲 4294967296 的數組。

1. 存儲定時器

爲了解決這個問題，內核使用 層級 的概念來減少數組佔用的內存空間。其原理如下圖所示：

由於超時時間是一個整數（32 位整型），所以可以將其劃分爲 5 個等級，每個級別使用一個數組來表示。例如第一級數組佔用 8 個位，所以其大小爲 256。而其他級別的數組都佔用 6 個位，所以大小都爲 64。

一個定時器被存放到哪個數組，是由其超時時間決定的，算法也非常簡單：如果第五級的值不爲零，那麼將會被存放到第五級數組中，而存放的位置以第五級的值作爲索引。

例如，一個定時器的超時時間其第五級的值爲 32，那麼此定時器將會被存放到第五級數組的第 32 個槽位上。如下圖所示：

如果第五級的值爲零，而第四級的值不爲零，那麼定時器將會被存放在第四級數組中，存放的位置以第四級的值作爲索引，如此類推。

從上面的分析可以看出，定時器的超時時間越小，其存放的數組層級就越小。所以：

第一級數組存放的是超時時間範圍爲 [0, 256) 毫秒的定時器。
第二級數組存放的是超時時間範圍爲 [256, 16384) 毫秒的定時器（16384 = 256 * 64）。
第三級數組存放的是超時時間範圍爲 [16384, 1048576) 毫秒的定時器（1048576 = 256 * 64 * 64）。
第四級數組存放的是超時時間範圍爲 [1048576, 67108864) 毫秒的定時器（67108864 = 256 * 64 * 64 * 64）。
第五級數組存放的是超時時間範圍爲 [67108864, 4294967296) 毫秒的定時器（4294967296 = 256 * 64 * 64 * 64 * 64）。

2. 執行定時器

接下來，我們將要分析內核是如何選擇到期的定時器來執行的。

如果所有定時器只存儲在一級數組中，那麼選擇到期的定時器就非常簡單：由於數組每個槽位的索引對應着定時器的超時時間，所以只需要在時鐘中斷髮生時，執行到期指針指向的定時器列表。執行完畢後，將到期指針移動到下一個位置即可。如下圖所示：

但對於定時器存儲在多級數組的情況，算法就變得複雜很多。

從上面的分析可知，第一級數組存放的是 0 ～ 255 毫秒後到期的定時器列表，而數組的索引對應的就是定時器的超時時間。如下圖所示：

而其他等級的數組，每個槽位存放的定時器其超時時間並不是一個固定的值，而是一個範圍，範圍與數組的等級和槽位的索引值有關，其計算方式爲：

256 * 64^n * 槽位索引 <= 超時時間 < 256 * 64^n * (槽位索引+1)

在上面的公式中，n 的值等於 數組的等級 減去 2。所以對於第二級數組來說，其公式如下：

256 * 槽位索引 <= 超時時間 < 256 * (槽位索引+1)

第三級數組公式如下：

256 * 64 * 槽位索引 <= 超時時間 < 256 * 64 * (槽位索引+1)

第四和第五級數組如此類推。

由於內核不會使用索引爲 0 的槽位，所以第二、第三級數組的定時器如下圖所示：

內核只會執行第一級數組中的定時器，每當時鐘中斷觸發時，會執行第一級數組 到期指針 指向的定時器列表，執行完畢後會將 到期指針 向下移動一位。如下圖所示：

當到期指針執行完最後一個槽位的定時器列表後，會重新移動到第一個槽位。

那麼其他級別數組的定時器在什麼時候纔會被執行呢？其實對於其他級別的數組也有一個 到期指針，每當前一級別的數組執行完一輪後，當前級別數組的 到期指針 將會移動到下一個槽位，如：當第一級數組執行一輪後，第二級數組的 到期指針 將會移動到下一個槽位。

其他級別的數組（非第一級數組）移動 到期指針 時，會將指針指向的定時器列表從數組中刪除，並且重新添加到內核中。如下圖所示：

如上圖所示，第一級數組執行一輪後，內核將會把第二級數組的到期指針指向的定時器列表刪除，並且重新添加到內核中。然後，將會把到期指針移動到下一個槽位。

第三級數組也會在第二級數組執行一輪後，將其到期指針指向的定時器列表刪除，並且重新添加到內核中。接着將到期指針移動到下一個槽位，其他級別的數組如此類推。

源碼實現

接下來，我們將會分析 Linux 內核是如何實現低精度定時器的。由於高版本的內核其實現與上面介紹的原理有些區別，但基本原理是一致的，這裏我們將使用 2.4.37 版本作爲分析的對象。

1. 五個等級數組

如上面分析一致，在 Linux 內核中定義了 5 個數組來存放系統中的定時器，如下代碼所示：

struct timer_vec {
 int index;     // 到期指針
 struct list_head vec[64];
};

struct timer_vec_root {
 int index;     // 到期指針
 struct list_head vec[256];
};

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;

上面代碼中，tv1、tv2、tv3、tv4、tv5 分別對應第一級、二級、三級、四級和五級數組。

通過代碼可知，數組元素的類型爲鏈表，用於存放不同到期時間的定時器。另外，除了第一級數組的元素個數是 256 個外，其他級別的數組的元素個數都是 64 個。每個級別的數組都有一個到期指針，用於指向當前正在執行的定時器列表。

我們接着來看看內核怎麼初始化這些數組的，內核調用 init_timervecs() 函數來初始化各級數組。代碼如下：

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

init_timervecs() 主要通過 INIT_LIST_HEAD 宏來初始化各級數組的元素。

2. 定時器對象

在內核中，定時器使用 timer_list 對象來表示，其定義如下：

struct timer_list {
    struct list_head list;
    unsigned long expires;
    unsigned long data;
    void (*function)(unsigned long);
};

下面介紹一下 timer_list 對象各個字段的作用：

list：用於連接到期時候相同的定時器。
expires：定時器的到期時間。
data：傳給回調函數的數據。
function：定時器到期後，將會調用的回調函數。

我們要向內核添加一個定時器時，需要先創建一個 timer_list 對象，並且設置其到期時間和回調函數。

3. 添加定時器

在內核中，可以使用 add_timer() 函數來添加一個定時器。其代碼如下所示：

void add_timer(struct timer_list *timer)
{
    unsigned long flags;

    // 上鎖
    spin_lock_irqsave(&timerlist_lock, flags);
    ...
    // 向內核添加定時器
    internal_add_timer(timer);
    // 解鎖
    spin_unlock_irqrestore(&timerlist_lock, flags);
    return;
}

從上面代碼可以看出，add_timer() 函數主要通過調用 internal_add_timer() 函數來添加定時器。我們繼續來分析 internal_add_timer() 函數的實現，代碼如下：

static inline void internal_add_timer(struct timer_list *timer)
{
    unsigned long expires = timer->expires;
    unsigned long idx = expires - timer_jiffies; // 多少毫秒數後到期
    struct list_head * vec;

    if (idx < TVR_SIZE) {
        int i = expires & TVR_MASK;
        vec = tv1.vec + i;
    } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
        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) {
        vec = tv1.vec + tv1.index;
    } else if (idx <= 0xffffffffUL) {
        int i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
        vec = tv5.vec + i;
    } else {
        INIT_LIST_HEAD(&timer->list);
        return;
    }

    list_add(&timer->list, vec->prev);
}

internal_add_timer() 函數首先會計算定時器還有多少毫秒到期，然後按照到期的毫秒數來選擇對應的級別數組：

如果到期時間小於 256 毫秒，那麼將會添加到第一級數組中。
如果到期時間大於等於 256 毫秒，並且小於 16384 毫米，那麼將會添加到第二級數組中。
其他等級如此類推。

選擇到合適的數組後，內核會調用 list_add() 函數將定時器添加到對應槽位的鏈表中。

4. 執行到期的定時器

內核會在時鐘中斷中通過調用 run_timer_list() 函數來執行到期的定時器，其實現如下：

static inline void run_timer_list(void)
{
    ...
    while ((long)(jiffies - timer_jiffies) >= 0) {
        struct list_head *head, *curr;

        // 1. 如果第一級數組已經執行完一輪（到期指針變爲0）
        if (!tv1.index) {
            int n = 1;
            do {
                cascade_timers(tvecs[n]);
            } while (tvecs[n]->index == 1 && ++n < NOOF_TVECS);
        }

repeat:
        // 2. 第一級數組當前到期指針指向的定時器列表
        head = tv1.vec + tv1.index;

        // 3. 遍歷到期的定時器列表
        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;

            // 4. 把定時器從鏈表中刪除
            detach_timer(timer);
            timer->list.next = timer->list.prev = NULL;
            timer_enter(timer);

            spin_unlock_irq(&timerlist_lock);
            // 5. 執行定時器的回調函數
            fn(data);
            spin_lock_irq(&timerlist_lock);

            timer_exit();
            goto repeat;
        }
        ++timer_jiffies;
        // 6. 將到期指針移動一個位置
        tv1.index = (tv1.index + 1) & TVR_MASK;
    }
    ...
}

run_timer_list() 函數主要按照以下步驟來執行到期的定時器：

如果第一級數組已經執行完一輪（也就是說，到期指針變爲 0 時），通過調用 cascade_timers() 函數來計算其他等級當前到期指針指向的定時器列表（重新添加到內核中）。
遍歷第一級數組的到期指針指向的定時器列表。
把定時器從鏈表中刪除。
執行定時器的回調函數。
將到期指針移動一個位置。

從時間輪的原理可知，每當某一級數組執行完一輪後，就會移動下一級數組的到期指針，並且將指針指向的定時器列表重新添加到內核中，這個過程由 cascade_timers() 函數完成。代碼如下所示：

static inline void cascade_timers(struct timer_vec *tv)
{
    struct list_head *head, *curr, *next;

    head = tv->vec + tv->index;
    curr = head->next;

    // 1. 遍歷定時器列表
    while (curr != head) {
        struct timer_list *tmp;

        tmp = list_entry(curr, struct timer_list, list);
        next = curr->next;
        list_del(curr);
        // 2. 將定時器重新添加到內核中
        internal_add_timer(tmp);
        curr = next;
    }
    INIT_LIST_HEAD(head);
    // 3. 將到期指針移動到下一個位置
    tv->index = (tv->index + 1) & TVN_MASK;
}

總結

本文主要介紹低精度定時器的實現，低精度定時器是一種比較廉價（佔用資源較低）的定時器，如果對定時器的到期時間精度不太高的情況下，可以優先使用低精度定時。

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

時間輪