利用定時(shí)器，我們可以設(shè)定在未來(lái)的某一時(shí)刻，觸發(fā)一個(gè)特定的事件。所謂低分辨率定時(shí)器，是指這種定時(shí)器的計(jì)時(shí)單位基于jiffies值的計(jì)數(shù)，也就是說(shuō)，它的精度只有1/HZ，假如你的內(nèi)核配置的HZ是1000，那意味著系統(tǒng)中的低分辨率定時(shí)器的精度就是1ms。早期的內(nèi)核版本中，內(nèi)核并不支持高精度定時(shí)器，理所當(dāng)然只能使用這種低分辨率定時(shí)器，我們有時(shí)候把這種基于HZ的定時(shí)器機(jī)制成為時(shí)間輪：time wheel。雖然后來(lái)出現(xiàn)了高分辨率定時(shí)器，但它只是內(nèi)核的一個(gè)可選配置項(xiàng)，所以直到目前最新的內(nèi)核版本，這種低分辨率定時(shí)器依然被大量地使用著。

1. ?定時(shí)器的使用方法

在討論定時(shí)器的實(shí)現(xiàn)原理之前，我們先看看如何使用定時(shí)器。要在內(nèi)核編程中使用定時(shí)器，首先我們要定義一個(gè)time_list結(jié)構(gòu)，該結(jié)構(gòu)在include/linux/timer.h中定義：

[cpp]?view plain?copy

struct?timer_list?{??

/*?

*?All?fields?that?change?during?normal?runtime?grouped?to?the?

*?same?cacheline?

*/??

struct?list_head?entry;??

unsigned?long?expires;??

struct?tvec_base?*base;??

void?(*function)(unsigned?long);??

unsigned?long?data;??

int?slack;??

......??

};??

entry ?字段用于把一組定時(shí)器組成一個(gè)鏈表，至于內(nèi)核如何對(duì)定時(shí)器進(jìn)行分組，我們會(huì)在后面進(jìn)行解釋。

expires??字段指出了該定時(shí)器的到期時(shí)刻，也就是期望定時(shí)器到期時(shí)刻的jiffies計(jì)數(shù)值。

base??每個(gè)cpu擁有一個(gè)自己的用于管理定時(shí)器的tvec_base結(jié)構(gòu)，該字段指向該定時(shí)器所屬的cpu所對(duì)應(yīng)tvec_base結(jié)構(gòu)。

function??字段是一個(gè)函數(shù)指針，定時(shí)器到期時(shí)，系統(tǒng)將會(huì)調(diào)用該回調(diào)函數(shù)，用于響應(yīng)該定時(shí)器的到期事件。

data??該字段用于上述回調(diào)函數(shù)的參數(shù)。

slack??對(duì)有些對(duì)到期時(shí)間精度不太敏感的定時(shí)器，到期時(shí)刻允許適當(dāng)?shù)匮舆t一小段時(shí)間，該字段用于計(jì)算每次延遲的HZ數(shù)。

要定義一個(gè)timer_list，我們可以使用靜態(tài)和動(dòng)態(tài)兩種辦法，靜態(tài)方法使用DEFINE_TIMER宏：

#define DEFINE_TIMER(_name, _function, _expires, _data)

該宏將得到一個(gè)名字為_(kāi)name，并分別用_function,_expires,_data參數(shù)填充timer_list的相關(guān)字段。

如果要使用動(dòng)態(tài)的方法，則可以自己聲明一個(gè)timer_list結(jié)構(gòu)，然后手動(dòng)初始化它的各個(gè)字段：

[cpp]?view plain?copy

struct?timer_list?timer;??

......??

init_timer(&timer);??

timer.function?=?_function;??

timer.expires?=?_expires;??

timer.data?=?_data;??

要激活一個(gè)定時(shí)器，我們只要調(diào)用add_timer即可：

[cpp]?view plain?copy

add_timer(&timer);??

要修改定時(shí)器的到期時(shí)間，我們只要調(diào)用mod_timer即可：

[cpp]?view plain?copy

mod_timer(&timer,?jiffies+50);??

要移除一個(gè)定時(shí)器，我們只要調(diào)用del_timer即可：

[cpp]?view plain?copy

del_timer(&timer);??

定時(shí)器系統(tǒng)還提供了以下這些API供我們使用：

void add_timer_on(struct timer_list *timer, int cpu); ?// 在指定的cpu上添加定時(shí)器

int mod_timer_pending(struct timer_list *timer, unsigned long expires); ?// ?只有當(dāng)timer已經(jīng)處在激活狀態(tài)時(shí)，才修改timer的到期時(shí)刻

int mod_timer_pinned(struct timer_list *timer, unsigned long expires); ?// ?當(dāng)

void set_timer_slack(struct timer_list *time, int slack_hz); ?// ?設(shè)定timer允許的到期時(shí)刻的最大延遲，用于對(duì)精度不敏感的定時(shí)器

int del_timer_sync(struct timer_list *timer); ?// ?如果該timer正在被處理中，則等待timer處理完成才移除該timer

2. ?定時(shí)器的軟件架構(gòu)

低分辨率定時(shí)器是基于HZ來(lái)實(shí)現(xiàn)的，也就是說(shuō)，每個(gè)tick周期，都有可能有定時(shí)器到期，關(guān)于tick如何產(chǎn)生，請(qǐng)參考：Linux時(shí)間子系統(tǒng)之四：定時(shí)器的引擎：clock_event_device。系統(tǒng)中有可能有成百上千個(gè)定時(shí)器，難道在每個(gè)tick中斷中遍歷一下所有的定時(shí)器，檢查它們是否到期？?jī)?nèi)核當(dāng)然不會(huì)使用這么笨的辦法，它使用了一個(gè)更聰明的辦法：按定時(shí)器的到期時(shí)間對(duì)定時(shí)器進(jìn)行分組。因?yàn)槟壳暗亩嗪?a target="_blank">處理器使用越來(lái)越廣泛，連智能手機(jī)的處理器動(dòng)不動(dòng)就是4核心，內(nèi)核對(duì)多核處理器有較好的支持，低分辨率定時(shí)器在實(shí)現(xiàn)時(shí)也充分地考慮了多核處理器的支持和優(yōu)化。為了較好地利用cache line，也為了避免cpu之間的互鎖，內(nèi)核為多核處理器中的每個(gè)cpu單獨(dú)分配了管理定時(shí)器的相關(guān)數(shù)據(jù)結(jié)構(gòu)和資源，每個(gè)cpu獨(dú)立地管理屬于自己的定時(shí)器。

2.1 ?定時(shí)器的分組

首先，內(nèi)核為每個(gè)cpu定義了一個(gè)tvec_base結(jié)構(gòu)指針：

[cpp]?view plain?copy

static?DEFINE_PER_CPU(struct?tvec_base?*,?tvec_bases)?=?&boot_tvec_bases;??

tvec_base結(jié)構(gòu)的定義如下：

[cpp]?view plain?copy

struct?tvec_base?{??

spinlock_t?lock;??

struct?timer_list?*running_timer;??

unsigned?long?timer_jiffies;??

unsigned?long?next_timer;??

struct?tvec_root?tv1;??

struct?tvec?tv2;??

struct?tvec?tv3;??

struct?tvec?tv4;??

struct?tvec?tv5;??

}?____cacheline_aligned;??

running_timer? 該字段指向當(dāng)前cpu正在處理的定時(shí)器所對(duì)應(yīng)的timer_list結(jié)構(gòu)。

timer_jiffies? 該字段表示當(dāng)前cpu定時(shí)器所經(jīng)歷過(guò)的jiffies數(shù)，大多數(shù)情況下，該值和jiffies計(jì)數(shù)值相等，當(dāng)cpu的idle狀態(tài)連續(xù)持續(xù)了多個(gè)jiffies時(shí)間時(shí)，當(dāng)退出idle狀態(tài)時(shí)，jiffies計(jì)數(shù)值就會(huì)大于該字段，在接下來(lái)的tick中斷后，定時(shí)器系統(tǒng)會(huì)讓該字段的值追趕上jiffies值。

next_timer? 該字段指向該cpu下一個(gè)即將到期的定時(shí)器。

tv1--tv5??這5個(gè)字段用于對(duì)定時(shí)器進(jìn)行分組，實(shí)際上，tv1--tv5都是一個(gè)鏈表數(shù)組，其中tv1的數(shù)組大小為TVR_SIZE， tv2 tv3 tv4 tv5的數(shù)組大小為TVN_SIZE，根據(jù)CONFIG_BASE_SMALL配置項(xiàng)的不同，它們有不同的大小：

[cpp]?view plain?copy

#define?TVN_BITS?(CONFIG_BASE_SMALL???4?:?6)??

#define?TVR_BITS?(CONFIG_BASE_SMALL???6?:?8)??

#define?TVN_SIZE?(1?<

#define?TVR_SIZE?(1?<

#define?TVN_MASK?(TVN_SIZE?-?1)??

#define?TVR_MASK?(TVR_SIZE?-?1)??

struct?tvec?{??

struct?list_head?vec[TVN_SIZE];??

};??

struct?tvec_root?{??

struct?list_head?vec[TVR_SIZE];??

};??

默認(rèn)情況下，沒(méi)有使能CONFIG_BASE_SMALL，TVR_SIZE的大小是256，TVN_SIZE的大小則是64，當(dāng)需要節(jié)省內(nèi)存空間時(shí)，也可以使能CONFIG_BASE_SMALL，這時(shí)TVR_SIZE的大小是64，TVN_SIZE的大小則是16，以下的討論我都是基于沒(méi)有使能CONFIG_BASE_SMALL的情況。當(dāng)有一個(gè)新的定時(shí)器要加入時(shí)，系統(tǒng)根據(jù)定時(shí)器到期的jiffies值和timer_jiffies字段的差值來(lái)決定該定時(shí)器被放入tv1至tv5中的哪一個(gè)數(shù)組中，最終，系統(tǒng)中所有的定時(shí)器的組織結(jié)構(gòu)如下圖所示：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??圖 2.1.1 ?定時(shí)器在系統(tǒng)中的組織結(jié)構(gòu)

2.2 ?定時(shí)器的添加

要加入一個(gè)新的定時(shí)器，我們可以通過(guò)api函數(shù)add_timer或mod_timer來(lái)完成，最終的工作會(huì)交由internal_add_timer函數(shù)來(lái)處理。該函數(shù)按以下步驟進(jìn)行處理：

計(jì)算定時(shí)器到期時(shí)間和所屬cpu的tvec_base結(jié)構(gòu)中的timer_jiffies字段的差值，記為idx；

根據(jù)idx的值，選擇該定時(shí)器應(yīng)該被放到tv1--tv5中的哪一個(gè)鏈表數(shù)組中，可以認(rèn)為tv1-tv5分別占據(jù)一個(gè)32位數(shù)的不同比特位，tv1占據(jù)最低的8位，tv2占據(jù)緊接著的6位，然后tv3再占位，以此類推，最高的6位分配給tv5。最終的選擇規(guī)則如下表所示：

鏈表數(shù)組idx范圍tv10-255(2^8)tv2256--16383(2^14)tv316384--1048575(2^20)tv41048576--67108863(2^26)tv567108864--4294967295(2^32)

確定鏈表數(shù)組后，接著要確定把該定時(shí)器放入數(shù)組中的哪一個(gè)鏈表中，如果時(shí)間差idx小于256，按規(guī)則要放入tv1中，因?yàn)閠v1包含了256個(gè)鏈表，所以可以簡(jiǎn)單地使用timer_list.expires的低8位作為數(shù)組的索引下標(biāo)，把定時(shí)器鏈接到tv1中相應(yīng)的鏈表中即可。如果時(shí)間差idx的值在256--18383之間，則需要把定時(shí)器放入tv2中，同樣的，使用timer_list.expires的8--14位作為數(shù)組的索引下標(biāo)，把定時(shí)器鏈接到tv2中相應(yīng)的鏈表中,。定時(shí)器要加入tv3 tv4 tv5使用同樣的原理。經(jīng)過(guò)這樣分組后的定時(shí)器，在后續(xù)的tick事件中，系統(tǒng)可以很方便地定位并取出相應(yīng)的到期定時(shí)器進(jìn)行處理。以上的討論都體現(xiàn)在internal_add_timer的代碼中：

[cpp]?view plain?copy

static?void?internal_add_timer(struct?tvec_base?*base,?struct?timer_list?*timer)??

{??

unsigned?long?expires?=?timer->expires;??

unsigned?long?idx?=?expires?-?base->timer_jiffies;??

struct?list_head?*vec;??

if?(idx?

int?i?=?expires?&?TVR_MASK;??

vec?=?base->tv1.vec?+?i;??

}?else?if?(idx?

int?i?=?(expires?>>?TVR_BITS)?&?TVN_MASK;??

vec?=?base->tv2.vec?+?i;??

}?else?if?(idx?

int?i?=?(expires?>>?(TVR_BITS?+?TVN_BITS))?&?TVN_MASK;??

vec?=?base->tv3.vec?+?i;??

}?else?if?(idx?

int?i?=?(expires?>>?(TVR_BITS?+?2?*?TVN_BITS))?&?TVN_MASK;??

vec?=?base->tv4.vec?+?i;??

}?else?if?((signed?long)?idx?

......??

}?else?{??

......??

i?=?(expires?>>?(TVR_BITS?+?3?*?TVN_BITS))?&?TVN_MASK;??

vec?=?base->tv5.vec?+?i;??

}??

list_add_tail(&timer->entry,?vec);??

}??

2.2 ?定時(shí)器的到期處理

經(jīng)過(guò)2.1節(jié)的處理后，系統(tǒng)中的定時(shí)器按到期時(shí)間有規(guī)律地放置在tv1--tv5各個(gè)鏈表數(shù)組中，其中tv1中放置著在接下來(lái)的256個(gè)jiffies即將到期的定時(shí)器列表，需要注意的是，并不是tv1.vec[0]中放置著馬上到期的定時(shí)器列表，tv1.vec[1]中放置著將在jiffies+1到期的定時(shí)器列表。因?yàn)閎ase.timer_jiffies的值一直在隨著系統(tǒng)的運(yùn)行而動(dòng)態(tài)地增加，原則上是每個(gè)tick事件會(huì)加1，base.timer_jiffies代表者該cpu定時(shí)器系統(tǒng)當(dāng)前時(shí)刻，定時(shí)器也是動(dòng)態(tài)地加入頭256個(gè)鏈表tv1中，按2.1節(jié)的討論，定時(shí)器加入tv1中使用的下標(biāo)索引是定時(shí)器到期時(shí)間expires的低8位，所以假設(shè)當(dāng)前的base.timer_jiffies值是0x34567826，則馬上到期的定時(shí)器是在tv1.vec[0x26]中，如果這時(shí)候系統(tǒng)加入一個(gè)在jiffies值0x34567828到期的定時(shí)器，他將會(huì)加入到tv1.vec[0x28]中，運(yùn)行兩個(gè)tick后，base.timer_jiffies的值會(huì)變?yōu)?x34567828，很顯然，在每次tick事件中，定時(shí)器系統(tǒng)只要以base.timer_jiffies的低8位作為索引，取出tv1中相應(yīng)的鏈表，里面正好包含了所有在該jiffies值到期的定時(shí)器列表。

那什么時(shí)候處理tv2--tv5中的定時(shí)器？每當(dāng)base.timer_jiffies的低8位為0值時(shí)，這表明base.timer_jiffies的第8-13位有進(jìn)位發(fā)生，這6位正好代表著tv2，這時(shí)只要按base.timer_jiffies的第8-13位的值作為下標(biāo)，移出tv2中對(duì)應(yīng)的定時(shí)器鏈表，然后用internal_add_timer把它們從新加入到定時(shí)器系統(tǒng)中來(lái)，因?yàn)檫@些定時(shí)器一定會(huì)在接下來(lái)的256個(gè)tick期間到期，所以它們肯定會(huì)被加入到tv1數(shù)組中，這樣就完成了tv2往tv1遷移的過(guò)程。同樣地，當(dāng)base.timer_jiffies的第8-13位為0時(shí)，這表明base.timer_jiffies的第14-19位有進(jìn)位發(fā)生，這6位正好代表著tv3，按base.timer_jiffies的第14-19位的值作為下標(biāo)，移出tv3中對(duì)應(yīng)的定時(shí)器鏈表，然后用internal_add_timer把它們從新加入到定時(shí)器系統(tǒng)中來(lái)，顯然它們會(huì)被加入到tv2中，從而完成tv3到tv2的遷移，tv4，tv5的處理可以以此作類推。具體遷移的代碼如下，參數(shù)index為事先計(jì)算好的高一級(jí)tv的需要遷移的數(shù)組索引：

[cpp]?view plain?copy

static?int?cascade(struct?tvec_base?*base,?struct?tvec?*tv,?int?index)??

{??

/*?cascade?all?the?timers?from?tv?up?one?level?*/??

struct?timer_list?*timer,?*tmp;??

struct?list_head?tv_list;??

list_replace_init(tv->vec?+?index,?&tv_list);??//??移除需要遷移的鏈表??

/*?

*?We?are?removing?_all_?timers?from?the?list,?so?we?

*?don't?have?to?detach?them?individually.?

*/??

list_for_each_entry_safe(timer,?tmp,?&tv_list,?entry)?{??

BUG_ON(tbase_get_base(timer->base)?!=?base);??

//??重新加入到定時(shí)器系統(tǒng)中，實(shí)際上將會(huì)遷移到下一級(jí)的tv數(shù)組中??

internal_add_timer(base,?timer);????

}??

return?index;??

}??

每個(gè)tick事件到來(lái)時(shí)，內(nèi)核會(huì)在tick定時(shí)中斷處理期間激活定時(shí)器軟中斷：TIMER_SOFTIRQ，關(guān)于軟件中斷，請(qǐng)參考另一篇博文：Linux中斷（interrupt）子系統(tǒng)之五：軟件中斷（softIRQ。TIMER_SOFTIRQ的執(zhí)行函數(shù)是__run_timers，它實(shí)現(xiàn)了本節(jié)討論的邏輯，取出tv1中到期的定時(shí)器，執(zhí)行定時(shí)器的回調(diào)函數(shù)，由此可見(jiàn)，低分辨率定時(shí)器的回調(diào)函數(shù)是執(zhí)行在軟件中斷上下文中的，這點(diǎn)在寫(xiě)定時(shí)器的回調(diào)函數(shù)時(shí)需要注意。__run_timers的代碼如下：

[cpp]?view plain?copy

static?inline?void?__run_timers(struct?tvec_base?*base)??

{??

struct?timer_list?*timer;??

spin_lock_irq(&base->lock);??

/*?同步j(luò)iffies，在NO_HZ情況下，base->timer_jiffies可能落后不止一個(gè)tick??*/??

while?(time_after_eq(jiffies,?base->timer_jiffies))?{????

struct?list_head?work_list;??

struct?list_head?*head?=?&work_list;??

/*??計(jì)算到期定時(shí)器鏈表在tv1中的索引??*/??

int?index?=?base->timer_jiffies?&?TVR_MASK;????

/*?

*?/*??tv2--tv5定時(shí)器列表遷移處理??*/??

*/??

if?(!index?&&??

(!cascade(base,?&base->tv2,?INDEX(0)))?&&????????????????

(!cascade(base,?&base->tv3,?INDEX(1)))?&&????????

!cascade(base,?&base->tv4,?INDEX(2)))????

cascade(base,?&base->tv5,?INDEX(3));????

/*??該cpu定時(shí)器系統(tǒng)運(yùn)行時(shí)間遞增一個(gè)tick??*/???????????????????

++base->timer_jiffies;????

/*??取出到期的定時(shí)器鏈表??*/?????????????????????????????????????????

list_replace_init(base->tv1.vec?+?index,?&work_list);??

/*??遍歷所有的到期定時(shí)器??*/????????????

while?(!list_empty(head))?{??????????????????????????????????????

void?(*fn)(unsigned?long);??

unsigned?long?data;??

timer?=?list_first_entry(head,?struct?timer_list,entry);??

fn?=?timer->function;??

data?=?timer->data;??

timer_stats_account_timer(timer);??

base->running_timer?=?timer;????/*??標(biāo)記正在處理的定時(shí)器??*/??

detach_timer(timer,?1);??

spin_unlock_irq(&base->lock);??

call_timer_fn(timer,?fn,?data);??/*??調(diào)用定時(shí)器的回調(diào)函數(shù)??*/??

spin_lock_irq(&base->lock);??

}??

}??

base->running_timer?=?NULL;??

spin_unlock_irq(&base->lock);??

}??

通過(guò)上面的討論，我們可以發(fā)現(xiàn)，內(nèi)核的低分辨率定時(shí)器的實(shí)現(xiàn)非常精妙，既實(shí)現(xiàn)了大量定時(shí)器的管理，又實(shí)現(xiàn)了快速的O(1)查找到期定時(shí)器的能力，利用巧妙的數(shù)組結(jié)構(gòu)，使得只需在間隔256個(gè)tick時(shí)間才處理一次遷移操作，5個(gè)數(shù)組就好比是5個(gè)齒輪，它們隨著base->timer_jifffies的增長(zhǎng)而不停地轉(zhuǎn)動(dòng)，每次只需處理第一個(gè)齒輪的某一個(gè)齒節(jié)，低一級(jí)的齒輪轉(zhuǎn)動(dòng)一圈，高一級(jí)的齒輪轉(zhuǎn)動(dòng)一個(gè)齒，同時(shí)自動(dòng)把即將到期的定時(shí)器遷移到上一個(gè)齒輪中，所以低分辨率定時(shí)器通常又被叫做時(shí)間輪：time wheel。事實(shí)上，它的實(shí)現(xiàn)是一個(gè)很好的空間換時(shí)間軟件算法。

3. ?定時(shí)器軟件中斷

系統(tǒng)初始化時(shí)，start_kernel會(huì)調(diào)用定時(shí)器系統(tǒng)的初始化函數(shù)init_timers：

[cpp]?view plain?copy

void?__init?init_timers(void)??

{????????

int?err?=?timer_cpu_notify(&timers_nb,?(unsigned?long)CPU_UP_PREPARE,???

(void?*)(long)smp_processor_id());??

init_timer_stats();??

BUG_ON(err?!=?NOTIFY_OK);??

register_cpu_notifier(&timers_nb);??/*?注冊(cè)cpu?notify，以便在hotplug時(shí)在cpu之間進(jìn)行定時(shí)器的遷移?*/??

open_softirq(TIMER_SOFTIRQ,?run_timer_softirq);??

}??

可見(jiàn)，open_softirq把run_timer_softirq注冊(cè)為TIMER_SOFTIRQ的處理函數(shù)，另外，當(dāng)cpu的每個(gè)tick事件到來(lái)時(shí)，在事件處理中斷中，update_process_times會(huì)被調(diào)用，該函數(shù)會(huì)進(jìn)一步調(diào)用run_local_timers，run_local_timers會(huì)觸發(fā)TIMER_SOFTIRQ軟中斷：

[cpp]?view plain?copy

void?run_local_timers(void)??

{??

hrtimer_run_queues();??

raise_softirq(TIMER_SOFTIRQ);??

}??

TIMER_SOFTIRQ的處理函數(shù)是run_timer_softirq：

[cpp]?view plain?copy

static?void?run_timer_softirq(struct?softirq_action?*h)??

{??

struct?tvec_base?*base?=?__this_cpu_read(tvec_bases);??

hrtimer_run_pending();??

if?(time_after_eq(jiffies,?base->timer_jiffies))??

__run_timers(base);??

}??

好啦，終于看到__run_timers函數(shù)了，2.2節(jié)已經(jīng)介紹過(guò)，正是這個(gè)函數(shù)完成了對(duì)到期定時(shí)器的處理工作，也完成了時(shí)間輪的不停轉(zhuǎn)動(dòng)。

?