Linux 內(nèi)核通常會使用?定時器?來做一些延時的操作，比如常用的?sleep()?系統(tǒng)調(diào)用就是使用定時器來實(shí)現(xiàn)的。

在 Linux 內(nèi)核中，有兩種類型的定時器：高精度定時器?與?低精度定時器。低精度定時器基于硬件的時鐘中斷實(shí)現(xiàn)的，其定時周期的粒度為 1/HZ ms。例如，內(nèi)核 HZ 為 1000（也就是說 1 秒能夠產(chǎn)生 1000 次時鐘中斷），那么低精度定時器的最小定時間隔為1ms；而高精度定時器可以實(shí)現(xiàn)納秒級別的定時（實(shí)際的定時周期粒度與 CPU 的主頻有關(guān)）。

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

本文主要介紹 Linux 內(nèi)核中的低精度定時器的原理與實(shí)現(xiàn)。

時間輪

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

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

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

• 平衡二叉樹

• 最大堆/最小堆

• 跳躍表

• ...

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

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

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

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

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

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

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

1. 存儲定時器

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

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

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

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

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

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

• 第一級數(shù)組存放的是超時時間范圍為?[0, 256)?毫秒的定時器。

• 第二級數(shù)組存放的是超時時間范圍為?[256, 16384)?毫秒的定時器（16384 = 256 * 64）。

• 第三級數(shù)組存放的是超時時間范圍為?[16384, 1048576)?毫秒的定時器（1048576 = 256 * 64 * 64）。

• 第四級數(shù)組存放的是超時時間范圍為?[1048576, 67108864)?毫秒的定時器（67108864 = 256 * 64 * 64 * 64）。

• 第五級數(shù)組存放的是超時時間范圍為?[67108864, 4294967296)?毫秒的定時器（4294967296 = 256 * 64 * 64 * 64 * 64）。

2. 執(zhí)行定時器

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)? ?

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

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

1. 五個等級數(shù)組

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

上面代碼中，tv1、tv2、tv3、tv4、tv5?分別對應(yīng)第一級、二級、三級、四級和五級數(shù)組。

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

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

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

2. 定時器對象

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

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

• list：用于連接到期時候相同的定時器。

• expires：定時器的到期時間。

• data：傳給回調(diào)函數(shù)的數(shù)據(jù)。

• function：定時器到期后，將會調(diào)用的回調(diào)函數(shù)。

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

3. 添加定時器

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

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

internal_add_timer()?函數(shù)首先會計(jì)算定時器還有多少毫秒到期，然后按照到期的毫秒數(shù)來選擇對應(yīng)的級別數(shù)組：

• 如果到期時間小于256毫秒，那么將會添加到第一級數(shù)組中。

• 如果到期時間大于等于256毫秒，并且小于16384毫米，那么將會添加到第二級數(shù)組中。

• 其他等級如此類推。

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

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

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

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

1. 如果第一級數(shù)組已經(jīng)執(zhí)行完一輪（也就是說，到期指針變?yōu)?時），通過調(diào)用?cascade_timers()?函數(shù)來計(jì)算其他等級當(dāng)前到期指針指向的定時器列表（重新添加到內(nèi)核中）。

2. 遍歷第一級數(shù)組的到期指針指向的定時器列表。

3. 把定時器從鏈表中刪除。

4. 執(zhí)行定時器的回調(diào)函數(shù)。

5. 將到期指針移動一個位置。

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

總結(jié)

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

Linux內(nèi)核那些事