Linux 中的定時(shí)器
　　在 Linux 內(nèi)核中主要有兩種類型的定時(shí)器。一類稱為 timeout 類型，另一類稱為 timer 類型。timeout 類型的定時(shí)器通常用于檢測(cè)各種錯(cuò)誤條件，例如用于檢測(cè)網(wǎng)卡收發(fā)數(shù)據(jù)包是否會(huì)超時(shí)的定時(shí)器，IO 設(shè)備的讀寫是否會(huì)超時(shí)的定時(shí)器等等。通常情況下這些錯(cuò)誤很少發(fā)生，因此，使用 timeout 類型的定時(shí)器一般在超時(shí)之前就會(huì)被移除，從而很少產(chǎn)生真正的函數(shù)調(diào)用和系統(tǒng)開銷?？偟膩碚f，使用 timeout 類型的定時(shí)器產(chǎn)生的系統(tǒng)開銷很小，它是下文提及的 timer wheel 通常使用的環(huán)境。此外，在使用 timeout 類型定時(shí)器的地方往往并不關(guān)心超時(shí)處理，因此超時(shí)精確與否，早 0.01 秒或者晚 0.01 秒并不十分重要，這在下文論述 deferrable timers 時(shí)會(huì)進(jìn)一步介紹。timer 類型的定時(shí)器與 timeout 類型的定時(shí)器正相反，使用 timer 類型的定時(shí)器往往要求在精確的時(shí)鐘條件下完成特定的事件，通常是周期性的并且依賴超時(shí)機(jī)制進(jìn)行處理。例如設(shè)備驅(qū)動(dòng)通常會(huì)定時(shí)讀寫設(shè)備來進(jìn)行數(shù)據(jù)交互。如何高效的管理 timer 類型的定時(shí)器對(duì)提高系統(tǒng)的處理效率十分重要，下文在介紹 hrtimer 時(shí)會(huì)有更加詳細(xì)的論述。
　　內(nèi)核需要進(jìn)行時(shí)鐘管理，離不開底層的硬件支持。在早期是通過 8253 芯片提供的 PIT（Programmable Interval Timer）來提供時(shí)鐘，但是 PIT 的頻率很低，只能提供最高 1ms 的時(shí)鐘精度，由于 PIT 觸發(fā)的中斷速度太慢，會(huì)導(dǎo)致很大的時(shí)延，對(duì)于像音視頻這類對(duì)時(shí)間精度要求更高的應(yīng)用并不足夠，會(huì)極大的影響用戶體驗(yàn)。隨著硬件平臺(tái)的不斷發(fā)展變化，陸續(xù)出現(xiàn)了 TSC（Time Stamp Counter），HPET（High Precision Event Timer），ACPI PM Timer（ACPI Power Management Timer），CPU Local APIC Timer 等精度更高的時(shí)鐘。這些時(shí)鐘陸續(xù)被 Linux 的時(shí)鐘子系統(tǒng)所采納，從而不斷的提高 Linux 時(shí)鐘子系統(tǒng)的性能和靈活性。這些不同的時(shí)鐘會(huì)在下文不同的章節(jié)中分別進(jìn)行介紹。
　　Timer wheel
　　在 Linux 2.6.16 之前，內(nèi)核一直使用一種稱為 timer wheel 的機(jī)制來管理時(shí)鐘。這就是熟知的 kernel 一直采用的基于 HZ 的 timer 機(jī)制。Timer wheel 的核心數(shù)據(jù)結(jié)構(gòu)如清單 1 所示：
　　清單 1. Timer wheel 的核心數(shù)據(jù)結(jié)構(gòu)
　　#define TVN_BITS （CONFIG_BASE_SMALL ？ 4 ： 6）
　　#define TVR_BITS （CONFIG_BASE_SMALL ？ 6 ： 8）
　　#define TVN_SIZE （1 《《 TVN_BITS）
　　#define TVR_SIZE （1 《《 TVR_BITS）
　　#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］;
　　};
　　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;
　　以 CONFIG_BASE_SMALL 定義為 0 為例，TVR_SIZE ＝ 256，TVN_SIZE ＝ 64，這樣
　　可以得到如圖 1 所示的 timer wheel 的結(jié)構(gòu)。
　　
　　圖 1. Timer wheel 的邏輯結(jié)構(gòu)
　　在 timer wheel 的框架下，所有系統(tǒng)正在使用的 timer 并不是順序存放在一個(gè)平坦的鏈表中，因?yàn)檫@樣做會(huì)使得查找，插入，刪除等操作效率低下。Timer wheel 提供了 5 個(gè) timer 數(shù)組，數(shù)組之間存在著類似時(shí)分秒的進(jìn)位關(guān)系。TV1 為第一個(gè) timer 數(shù)組，其中存放著從 timer_jiffies（當(dāng)前到期的 jiffies）到 timer_jiffies + 255 共 256 個(gè) tick 對(duì)應(yīng)的 timer list。因?yàn)樵谝粋€(gè) tick 上可能同時(shí)有多個(gè) timer 等待超時(shí)處理，timer wheel 使用 list_head 將所有 timer 串成一個(gè)鏈表，以便在超時(shí)時(shí)順序處理。TV2 有 64 個(gè)單元，每個(gè)單元都對(duì)應(yīng)著 256 個(gè) tick，因此 TV2 所表示的超時(shí)時(shí)間范圍從 timer_jiffies + 256 到 timer_jiffies + 256 * 64 – 1。依次類推 TV3，TV4，TV5。以 HZ=1000 為例，每 1ms 產(chǎn)生一次中斷，TV1 就會(huì)被訪問一次，但是 TV2 要每 256ms 才會(huì)被訪問一次，TV3 要 16s，TV4 要 17 分鐘，TV5 甚至要 19 小時(shí)才有機(jī)會(huì)檢查一次。最終，timer wheel 可以管理的最大超時(shí)值為 2^32。一共使用了 512 個(gè) list_head（256+64+64+64+64）。如果 CONFIG_BASE_SMALL 定義為 1，則最終使用的 list_head 個(gè)數(shù)為 128 個(gè)（64+16+16+16+16），占用的內(nèi)存更少，更適合嵌入式系統(tǒng)使用。Timer wheel 的處理邏輯如清單 2 所示：
　　清單 2. timer wheel 的核心處理函數(shù)
　　static inline void __run_timers（struct tvec_base *base）
　　{
　　struct timer_list *timer;
　　spin_lock_irq（&base-》lock）;
　　while （time_after_eq（jiffies， base-》timer_jiffies）） {
　　struct list_head work_list;
　　struct list_head *head = &work_list;
　　int index = base-》timer_jiffies & TVR_MASK;
　　/*
　　* Cascade timers：
　　*/
　　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））;
　　++base-》timer_jiffies;
　　list_replace_init（base-》tv1.vec + index， &work_list）;
　　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;
　　。 . 。 .
　　fn（data）;
　　。 . 。 .
　　}
　　base-》timer_jiffies 用來記錄在 TV1 中最接近超時(shí)的 tick 的位置。index 是用來遍歷 TV1 的索引。每一次循環(huán) index 會(huì)定位一個(gè)當(dāng)前待處理的 tick，并處理這個(gè) tick 下所有超時(shí)的 timer。base-》timer_jiffies 會(huì)在每次循環(huán)后增加一個(gè) jiffy，index 也會(huì)隨之向前移動(dòng)。當(dāng) index 變?yōu)?0 時(shí)表示 TV1 完成了一次完整的遍歷，此時(shí)所有在 TV1 中的 timer 都被處理了，因此需要通過 cascade 將后面 TV2，TV3 等 timer list 中的 timer 向前移動(dòng)，類似于進(jìn)位。這種層疊的 timer list 實(shí)現(xiàn)機(jī)制可以大大降低每次檢查超時(shí) timer 的時(shí)間，每次中斷只需要針對(duì) TV1 進(jìn)行檢查，只有必要時(shí)才進(jìn)行 cascade。即便如此，timer wheel 的實(shí)現(xiàn)機(jī)制仍然存在很大弊端。一個(gè)弊端就是 cascade 開銷過大。在極端的條件下，同時(shí)會(huì)有多個(gè) TV 需要進(jìn)行 cascade 處理，會(huì)產(chǎn)生很大的時(shí)延。這也是為什么說 timeout 類型的定時(shí)器是 timer wheel 的主要應(yīng)用環(huán)境，或者說 timer wheel 是為 timeout 類型的定時(shí)器優(yōu)化的。因?yàn)?timeout 類型的定時(shí)器的應(yīng)用場(chǎng)景多是錯(cuò)誤條件的檢測(cè)，這類錯(cuò)誤發(fā)生的機(jī)率很小，通常不到超時(shí)就被刪除了，因此不會(huì)產(chǎn)生 cascade 的開銷。另一方面，由于 timer wheel 是建立在 HZ 的基礎(chǔ)上的，因此其計(jì)時(shí)精度無法進(jìn)一步提高。畢竟一味的通過提高 HZ 值來提高計(jì)時(shí)精度并無意義，結(jié)果只能是產(chǎn)生大量的定時(shí)中斷，增加額外的系統(tǒng)開銷。因此，有必要將高精度的 timer 與低精度的 timer 分開，這樣既可以確保低精度的 timeout 類型的定時(shí)器應(yīng)用，也便于高精度的 timer 類型定時(shí)器的應(yīng)用。還有一個(gè)重要的因素是 timer wheel 的實(shí)現(xiàn)與 jiffies 的耦合性太強(qiáng)，非常不便于擴(kuò)展。因此，自從 2.6.16 開始，一個(gè)新的 timer 子系統(tǒng) hrtimer 被加入到內(nèi)核中。