在linux操作系統(tǒng)中，定時(shí)器扮演著關(guān)鍵的角色，它們被用來執(zhí)行各種延遲任務(wù)，像是廣泛使用的系統(tǒng)調(diào)用sleep()。該調(diào)用的背后就是基于定時(shí)器的機(jī)制。

Linux內(nèi)部主要分為兩個(gè)類別的定時(shí)器：高精度定時(shí)器和低精度定時(shí)器。低精度定時(shí)器的工作原理是依托于硬件時(shí)鐘中斷，它的定時(shí)精度由HZ值決定，其表示每秒鐘時(shí)鐘中斷的次數(shù)。譬如，當(dāng)內(nèi)核的HZ設(shè)置為1000時(shí)，意味著每1毫秒會(huì)有一次時(shí)鐘中斷，這樣低精度定時(shí)器就能以1毫秒為最小的時(shí)間間隔來設(shè)定計(jì)時(shí)。相反，高精度定時(shí)器的精度更高，可以達(dá)到納秒級(jí)別，它的具體精度還和CPU的主頻緊密相關(guān)。

那么，為什么不全面采用高精度定時(shí)器呢？原因在于，盡管高精度定時(shí)器的時(shí)間精度更高，但其運(yùn)行成本同樣更高。因此，對(duì)于那些對(duì)時(shí)間精度要求不是特別高的場(chǎng)合，采用低精度定時(shí)器是更加經(jīng)濟(jì)且實(shí)用的選擇。

文章將著重講解Linux內(nèi)核中低精度定時(shí)器的工作原理和具體實(shí)現(xiàn)。

時(shí)間輪

低精度定時(shí)器是基于時(shí)鐘中斷實(shí)現(xiàn)的，而時(shí)鐘中斷的觸發(fā)頻率是可以配置的，Linux 內(nèi)核一般設(shè)置為每秒觸發(fā) 1000 次，也就是說每隔 1 毫秒就會(huì)觸發(fā)一次時(shí)鐘中斷。

一般來說，內(nèi)核中可能會(huì)存在成千上萬個(gè)定時(shí)器，那么內(nèi)核如何能夠快速找到將要到期的定時(shí)器呢？

在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程時(shí)，我們知道用于快速查找有序數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)有如何幾種：

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

由于這些數(shù)據(jù)結(jié)構(gòu)的時(shí)間復(fù)雜度都是 log(n)，對(duì)性能要求非常高的內(nèi)核來說是不能接受的，所以內(nèi)核使用了一種性能更高的數(shù)據(jù)結(jié)構(gòu)：時(shí)間輪。

時(shí)間輪能夠保證在時(shí)間復(fù)雜度為 log(1) 的情況下找到將要到期的定時(shí)器，下面我們將會(huì)介紹時(shí)間輪的原理。

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

如上圖所示的數(shù)組中，索引為 1 的槽位存放的是 1 毫秒后超時(shí)的定時(shí)器列表，索引為 2 的槽位存放的是 2 毫秒后超時(shí)的定時(shí)器列表，如此類推…

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

每當(dāng)時(shí)鐘中斷被觸發(fā)一次，指針向下移動(dòng)一位，這樣就能在時(shí)間復(fù)雜度為 log(1) 的情況下獲取到期的定時(shí)器。

這樣雖然能夠在時(shí)間復(fù)雜度為 log(1) 的情況下找到到期的定時(shí)器，但如果超時(shí)時(shí)間非常大的話，那么用于存儲(chǔ)定時(shí)器的數(shù)組也會(huì)非常巨大，如：定時(shí)器的超時(shí)時(shí)間為 4294967295 毫秒，那么將需要一個(gè)大小為 4294967296 的數(shù)組。

1. 存儲(chǔ)定時(shí)器

為了解決這個(gè)問題，內(nèi)核使用 層級(jí) 的概念來減少數(shù)組占用的內(nèi)存空間。其原理如下圖所示：

由于超時(shí)時(shí)間是一個(gè)整數(shù)（32 位整型），所以可以將其劃分為 5 個(gè)等級(jí)，每個(gè)級(jí)別使用一個(gè)數(shù)組來表示。例如第一級(jí)數(shù)組占用 8 個(gè)位，所以其大小為 256。而其他級(jí)別的數(shù)組都占用 6 個(gè)位，所以大小都為 64。

一個(gè)定時(shí)器被存放到哪個(gè)數(shù)組，是由其超時(shí)時(shí)間決定的，算法也非常簡(jiǎn)單：如果第五級(jí)的值不為零，那么將會(huì)被存放到第五級(jí)數(shù)組中，而存放的位置以第五級(jí)的值作為索引。

例如，一個(gè)定時(shí)器的超時(shí)時(shí)間其第五級(jí)的值為 32，那么此定時(shí)器將會(huì)被存放到第五級(jí)數(shù)組的第 32 個(gè)槽位上。如下圖所示：

如果第五級(jí)的值為零，而第四級(jí)的值不為零，那么定時(shí)器將會(huì)被存放在第四級(jí)數(shù)組中，存放的位置以第四級(jí)的值作為索引，如此類推。

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

• 第一級(jí)數(shù)組存放的是超時(shí)時(shí)間范圍為 [0, 256) 毫秒的定時(shí)器。
• 第二級(jí)數(shù)組存放的是超時(shí)時(shí)間范圍為 [256, 16384) 毫秒的定時(shí)器（16384 = 256 * 64）。
• 第三級(jí)數(shù)組存放的是超時(shí)時(shí)間范圍為 [16384, 1048576) 毫秒的定時(shí)器（1048576 = 256 * 64 * 64）。
• 第四級(jí)數(shù)組存放的是超時(shí)時(shí)間范圍為 [1048576, 67108864) 毫秒的定時(shí)器（67108864 = 256 * 64 * 64 * 64）。
• 第五級(jí)數(shù)組存放的是超時(shí)時(shí)間范圍為 [67108864, 4294967296) 毫秒的定時(shí)器（4294967296 = 256 * 64 * 64 * 64 * 64）。

2. 執(zhí)行定時(shí)器

接下來，我們將要分析內(nèi)核是如何選擇到期的定時(shí)器來執(zhí)行的。

如果所有定時(shí)器只存儲(chǔ)在一級(jí)數(shù)組中，那么選擇到期的定時(shí)器就非常簡(jiǎn)單：由于數(shù)組每個(gè)槽位的索引對(duì)應(yīng)著定時(shí)器的超時(shí)時(shí)間，所以只需要在時(shí)鐘中斷發(fā)生時(shí)，執(zhí)行到期指針指向的定時(shí)器列表。執(zhí)行完畢后，將到期指針移動(dòng)到下一個(gè)位置即可。如下圖所示：

但對(duì)于定時(shí)器存儲(chǔ)在多級(jí)數(shù)組的情況，算法就變得復(fù)雜很多。

從上面的分析可知，第一級(jí)數(shù)組存放的是 0 ～ 255 毫秒后到期的定時(shí)器列表，而數(shù)組的索引對(duì)應(yīng)的就是定時(shí)器的超時(shí)時(shí)間。如下圖所示：

而其他等級(jí)的數(shù)組，每個(gè)槽位存放的定時(shí)器其超時(shí)時(shí)間并不是一個(gè)固定的值，而是一個(gè)范圍，范圍與數(shù)組的等級(jí)和槽位的索引值有關(guān)，其計(jì)算方式為：

256?*?64^n?*?槽位索引?

在上面的公式中，n 的值等于 數(shù)組的等級(jí) 減去 2。所以對(duì)于第二級(jí)數(shù)組來說，其公式如下：

256?*?槽位索引?

第三級(jí)數(shù)組公式如下：

256?*?64?*?槽位索引?

第四和第五級(jí)數(shù)組如此類推。

由于內(nèi)核不會(huì)使用索引為 0 的槽位，所以第二、第三級(jí)數(shù)組的定時(shí)器如下圖所示：

內(nèi)核只會(huì)執(zhí)行第一級(jí)數(shù)組中的定時(shí)器，每當(dāng)時(shí)鐘中斷觸發(fā)時(shí)，會(huì)執(zhí)行第一級(jí)數(shù)組 到期指針 指向的定時(shí)器列表，執(zhí)行完畢后會(huì)將 到期指針 向下移動(dòng)一位。如下圖所示：

當(dāng)?shù)狡谥羔槇?zhí)行完最后一個(gè)槽位的定時(shí)器列表后，會(huì)重新移動(dòng)到第一個(gè)槽位。

那么其他級(jí)別數(shù)組的定時(shí)器在什么時(shí)候才會(huì)被執(zhí)行呢？其實(shí)對(duì)于其他級(jí)別的數(shù)組也有一個(gè) 到期指針，每當(dāng)前一級(jí)別的數(shù)組執(zhí)行完一輪后，當(dāng)前級(jí)別數(shù)組的 到期指針 將會(huì)移動(dòng)到下一個(gè)槽位，如：當(dāng)?shù)谝患?jí)數(shù)組執(zhí)行一輪后，第二級(jí)數(shù)組的 到期指針 將會(huì)移動(dòng)到下一個(gè)槽位。

其他級(jí)別的數(shù)組（非第一級(jí)數(shù)組）移動(dòng) 到期指針 時(shí)，會(huì)將指針指向的定時(shí)器列表從數(shù)組中刪除，并且重新添加到內(nèi)核中。如下圖所示：

如上圖所示，第一級(jí)數(shù)組執(zhí)行一輪后，內(nèi)核將會(huì)把第二級(jí)數(shù)組的到期指針指向的定時(shí)器列表刪除，并且重新添加到內(nèi)核中。然后，將會(huì)把到期指針移動(dòng)到下一個(gè)槽位。

第三級(jí)數(shù)組也會(huì)在第二級(jí)數(shù)組執(zhí)行一輪后，將其到期指針指向的定時(shí)器列表刪除，并且重新添加到內(nèi)核中。接著將到期指針移動(dòng)到下一個(gè)槽位，其他級(jí)別的數(shù)組如此類推。

源碼實(shí)現(xiàn)

接下來，我們將會(huì)分析 Linux 內(nèi)核是如何實(shí)現(xiàn)低精度定時(shí)器的。由于高版本的內(nèi)核其實(shí)現(xiàn)與上面介紹的原理有些區(qū)別，但基本原理是一致的，這里我們將使用 2.4.37 版本作為分析的對(duì)象。

1. 五個(gè)等級(jí)數(shù)組

如上面分析一致，在 Linux 內(nèi)核中定義了 5 個(gè)數(shù)組來存放系統(tǒng)中的定時(shí)器，如下代碼所示：

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 分別對(duì)應(yīng)第一級(jí)、二級(jí)、三級(jí)、四級(jí)和五級(jí)數(shù)組。

通過代碼可知，數(shù)組元素的類型為鏈表，用于存放不同到期時(shí)間的定時(shí)器。另外，除了第一級(jí)數(shù)組的元素個(gè)數(shù)是 256 個(gè)外，其他級(jí)別的數(shù)組的元素個(gè)數(shù)都是 64 個(gè)。每個(gè)級(jí)別的數(shù)組都有一個(gè)到期指針，用于指向當(dāng)前正在執(zhí)行的定時(shí)器列表。

我們接著來看看內(nèi)核怎么初始化這些數(shù)組的，內(nèi)核調(diào)用 init_timervecs() 函數(shù)來初始化各級(jí)數(shù)組。代碼如下：

void?init_timervecs(void) { ????int?i;  ????for?(i?=?0;?i?for?(i?=?0;?i?

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

2. 定時(shí)器對(duì)象

在內(nèi)核中，定時(shí)器使用 timer_list 對(duì)象來表示，其定義如下：

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

下面介紹一下 timer_list 對(duì)象各個(gè)字段的作用：

• list：用于連接到期時(shí)候相同的定時(shí)器。
• expires：定時(shí)器的到期時(shí)間。
• data：傳給回調(diào)函數(shù)的數(shù)據(jù)。
• function：定時(shí)器到期后，將會(huì)調(diào)用的回調(diào)函數(shù)。

我們要向內(nèi)核添加一個(gè)定時(shí)器時(shí)，需要先創(chuàng)建一個(gè) timer_list 對(duì)象，并且設(shè)置其到期時(shí)間和回調(diào)函數(shù)。

3. 添加定時(shí)器

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

void?add_timer(struct?timer_list?*timer) { ????unsigned?long?flags;  ????//?上鎖 ????spin_lock_irqsave(&timerlist_lock,?flags); ????... ????//?向內(nèi)核添加定時(shí)器 ????internal_add_timer(timer); ????//?解鎖 ????spin_unlock_irqrestore(&timerlist_lock,?flags); ????return; } 

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

static?inline?void?internal_add_timer(struct?timer_list?*timer) { ????unsigned?long?expires?=?timer->expires; ????unsigned?long?idx?=?expires?-?timer_jiffies;?//?多少毫秒數(shù)后到期 ????struct?list_head?*?vec;  ????if?(idx?else?if?(idx?>?TVR_BITS)?&?TVN_MASK; ????????vec?=?tv2.vec?+?i; ????}?else?if?(idx?>?(TVR_BITS?+?TVN_BITS))?&?TVN_MASK; ????????vec?=??tv3.vec?+?i; ????}?else?if?(idx?>?(TVR_BITS?+?2?*?TVN_BITS))?&?TVN_MASK; ????????vec?=?tv4.vec?+?i; ????}?else?if?((signed?long)?idx?else?if?(idx?>?(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() 函數(shù)首先會(huì)計(jì)算定時(shí)器還有多少毫秒到期，然后按照到期的毫秒數(shù)來選擇對(duì)應(yīng)的級(jí)別數(shù)組：

• 如果到期時(shí)間小于256毫秒，那么將會(huì)添加到第一級(jí)數(shù)組中。
• 如果到期時(shí)間大于等于256毫秒，并且小于16384毫米，那么將會(huì)添加到第二級(jí)數(shù)組中。
• 其他等級(jí)如此類推。

選擇到合適的數(shù)組后，內(nèi)核會(huì)調(diào)用 list_add() 函數(shù)將定時(shí)器添加到對(duì)應(yīng)槽位的鏈表中。

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

內(nèi)核會(huì)在時(shí)鐘中斷中通過調(diào)用 run_timer_list() 函數(shù)來執(zhí)行到期的定時(shí)器，其實(shí)現(xiàn)如下：

static?inline?void?run_timer_list(void) { ????... ????while?((long)(jiffies?-?timer_jiffies)?>=?0)?{ ????????struct?list_head?*head,?*curr;  ????????//?1.?如果第一級(jí)數(shù)組已經(jīng)執(zhí)行完一輪（到期指針變?yōu)?） ????????if?(!tv1.index)?{ ????????????int?n?=?1; ????????????do?{ ????????????????cascade_timers(tvecs[n]); ????????????}?while?(tvecs[n]->index?==?1?&&?++n?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.?把定時(shí)器從鏈表中刪除 ????????????detach_timer(timer); ????????????timer->list.next?=?timer->list.prev?=?NULL; ????????????timer_enter(timer);  ????????????spin_unlock_irq(&timerlist_lock); ????????????//?5.?執(zhí)行定時(shí)器的回調(diào)函數(shù) ????????????fn(data); ????????????spin_lock_irq(&timerlist_lock);  ????????????timer_exit(); ????????????goto?repeat; ????????} ????????++timer_jiffies; ????????//?6.?將到期指針移動(dòng)一個(gè)位置 ????????tv1.index?=?(tv1.index?+?1)?&?TVR_MASK; ????} ????... } 

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

1. 如果第一級(jí)數(shù)組已經(jīng)執(zhí)行完一輪（也就是說，到期指針變?yōu)?時(shí)），通過調(diào)用 cascade_timers() 函數(shù)來計(jì)算其他等級(jí)當(dāng)前到期指針指向的定時(shí)器列表（重新添加到內(nèi)核中）。
2. 遍歷第一級(jí)數(shù)組的到期指針指向的定時(shí)器列表。
3. 把定時(shí)器從鏈表中刪除。
4. 執(zhí)行定時(shí)器的回調(diào)函數(shù)。
5. 將到期指針移動(dòng)一個(gè)位置。

從時(shí)間輪的原理可知，每當(dāng)某一級(jí)數(shù)組執(zhí)行完一輪后，就會(huì)移動(dòng)下一級(jí)數(shù)組的到期指針，并且將指針指向的定時(shí)器列表重新添加到內(nèi)核中，這個(gè)過程由 cascade_timers() 函數(shù)完成。代碼如下所示：

static?inline?void?cascade_timers(struct?timer_vec?*tv) { ????struct?list_head?*head,?*curr,?*next;  ????head?=?tv->vec?+?tv->index; ????curr?=?head->next;  ????//?1.?遍歷定時(shí)器列表 ????while?(curr?!=?head)?{ ????????struct?timer_list?*tmp;  ????????tmp?=?list_entry(curr,?struct?timer_list,?list); ????????next?=?curr->next; ????????list_del(curr); ????????//?2.?將定時(shí)器重新添加到內(nèi)核中 ????????internal_add_timer(tmp); ????????curr?=?next; ????} ????INIT_LIST_HEAD(head); ????//?3.?將到期指針移動(dòng)到下一個(gè)位置 ????tv->index?=?(tv->index?+?1)?&?TVN_MASK; } 

總結(jié)

本文主要介紹低精度定時(shí)器的實(shí)現(xiàn)，低精度定時(shí)器是一種比較廉價(jià)（占用資源較低）的定時(shí)器，如果對(duì)定時(shí)器的到期時(shí)間精度不太高的情況下，可以優(yōu)先使用低精度定時(shí)。