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