http://blog.csdn.net/droidphone/article/details/8051405
利用定時器，我們可以設定在未來的某一時刻，觸發一個特定的事件。所謂低分辨率定時器，是指這種定時器的計時單位基于jiffies值的計數，也就是說，它的精度只有1/HZ，假如你的內核配置的HZ是1000，那意味著系統中的低分辨率定時器的精度就是1ms。早期的內核版本中，內核并不支持高精度定時器，理所當然只能使用這種低分辨率定時器，我們有時候把這種基于HZ的定時器機制成為時間輪：time wheel。雖然后來出現了高分辨率定時器，但它只是內核的一個可選配置項，所以直到目前最新的內核版本，這種低分辨率定時器依然被大量地使用著。
在討論定時器的實現原理之前，我們先看看如何使用定時器。要在內核編程中使用定時器，首先我們要定義一個time_list結構，該結構在include/linux/timer.h中定義：
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 字段用于把一組定時器組成一個鏈表，至于內核如何對定時器進行分組，我們會在后面進行解釋。 expires 字段指出了該定時器的到期時刻，也就是期望定時器到期時刻的jiffies計數值。
base 每個cpu擁有一個自己的用于管理定時器的tvec_base結構，該字段指向該定時器所屬的cpu所對應tvec_base結構。
function 字段是一個函數指針，定時器到期時，系統將會調用該回調函數，用于響應該定時器的到期事件。
data 該字段用于上述回調函數的參數。
slack 對有些對到期時間精度不太敏感的定時器，到期時刻允許適當地延遲一小段時間，該字段用于計算每次延遲的HZ數。
要定義一個timer_list，我們可以使用靜態和動態兩種辦法，靜態方法使用DEFINE_TIMER宏：
#define DEFINE_TIMER(_name, _function, _expires, _data)該宏將得到一個名字為_name，并分別用_function,_expires,_data參數填充timer_list的相關字段。
如果要使用動態的方法，則可以自己聲明一個timer_list結構，然后手動初始化它的各個字段：
struct timer_list timer; ...... init_timer(&timer); timer.function = _function; timer.expires = _expires; timer.data = _data;要激活一個定時器，我們只要調用add_timer即可：
add_timer(&timer);要修改定時器的到期時間，我們只要調用mod_timer即可：
mod_timer(&timer, jiffies+50);要移除一個定時器，我們只要調用del_timer即可：
del_timer(&timer);定時器系統還提供了以下這些API供我們使用：
void add_timer_on(struct timer_list *timer, int cpu); // 在指定的cpu上添加定時器int mod_timer_pending(struct timer_list *timer, unsigned long expires); // 只有當timer已經處在激活狀態時，才修改timer的到期時刻int mod_timer_pinned(struct timer_list *timer, unsigned long expires); void set_timer_slack(struct timer_list *time, int slack_hz); // 設定timer允許的到期時刻的最大延遲，用于對精度不敏感的定時器int del_timer_sync(struct timer_list *timer); // 如果該timer正在被處理中，則等待timer處理完成才移除該timer低分辨率定時器是基于HZ來實現的，也就是說，每個tick周期，都有可能有定時器到期，關于tick如何產生，請參考：Linux時間子系統之四：定時器的引擎：clock_event_device。系統中有可能有成百上千個定時器，難道在每個tick中斷中遍歷一下所有的定時器，檢查它們是否到期？內核當然不會使用這么笨的辦法，它使用了一個更聰明的辦法：按定時器的到期時間對定時器進行分組。因為目前的多核處理器使用越來越廣泛，連智能手機的處理器動不動就是4核心，內核對多核處理器有較好的支持，低分辨率定時器在實現時也充分地考慮了多核處理器的支持和優化。為了較好地利用cache line，也為了避免cpu之間的互鎖，內核為多核處理器中的每個cpu單獨分配了管理定時器的相關數據結構和資源，每個cpu獨立地管理屬于自己的定時器。
首先，內核為每個cpu定義了一個tvec_base結構指針：
static DEFINE_PER_CPU(struct tvec_base *, tvec_bases) = &boot_tvec_bases;tvec_base結構的定義如下：
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 該字段指向當前cpu正在處理的定時器所對應的timer_list結構。 timer_jiffies 該字段表示當前cpu定時器所經歷過的jiffies數，大多數情況下，該值和jiffies計數值相等，當cpu的idle狀態連續持續了多個jiffies時間時，當退出idle狀態時，jiffies計數值就會大于該字段，在接下來的tick中斷后，定時器系統會讓該字段的值追趕上jiffies值。
next_timer 該字段指向該cpu下一個即將到期的定時器。
tv1–tv5 這5個字段用于對定時器進行分組，實際上，tv1–tv5都是一個鏈表數組，其中tv1的數組大小為TVR_SIZE， tv2 tv3 tv4 tv5的數組大小為TVN_SIZE，根據CONFIG_BASE_SMALL配置項的不同，它們有不同的大小：
#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]; };默認情況下，沒有使能CONFIG_BASE_SMALL，TVR_SIZE的大小是256，TVN_SIZE的大小則是64，當需要節省內存空間時，也可以使能CONFIG_BASE_SMALL，這時TVR_SIZE的大小是64，TVN_SIZE的大小則是16，以下的討論我都是基于沒有使能CONFIG_BASE_SMALL的情況。當有一個新的定時器要加入時，系統根據定時器到期的jiffies值和timer_jiffies字段的差值來決定該定時器被放入tv1至tv5中的哪一個數組中，最終，系統中所有的定時器的組織結構如下圖所示： 
要加入一個新的定時器，我們可以通過api函數add_timer或mod_timer來完成，最終的工作會交由internal_add_timer函數來處理。該函數按以下步驟進行處理：
計算定時器到期時間和所屬cpu的tvec_base結構中的timer_jiffies字段的差值，記為idx；根據idx的值，選擇該定時器應該被放到tv1–tv5中的哪一個鏈表數組中，可以認為tv1-tv5分別占據一個32位數的不同比特位，tv1占據最低的8位，tv2占據緊接著的6位，然后tv3再占位，以此類推，最高的6位分配給tv5。最終的選擇規則如下表所示：| 鏈表數組 | idx范圍 |
|---|---|
| tv1 | 0-255(2^8) |
| tv2 | 256–16383(2^14) |
| tv3 | 16384–1048575(2^20) |
| tv4 | 1048576–67108863(2^26) |
| tv5 | 67108864–4294967295(2^32) |
確定鏈表數組后，接著要確定把該定時器放入數組中的哪一個鏈表中，如果時間差idx小于256，按規則要放入tv1中，因為tv1包含了256個鏈表，所以可以簡單地使用timer_list.expires的低8位作為數組的索引下標，把定時器鏈接到tv1中相應的鏈表中即可。如果時間差idx的值在256–18383之間，則需要把定時器放入tv2中，同樣的，使用timer_list.expires的8–14位作為數組的索引下標，把定時器鏈接到tv2中相應的鏈表中,。定時器要加入tv3 tv4 tv5使用同樣的原理。經過這樣分組后的定時器，在后續的tick事件中，系統可以很方便地定位并取出相應的到期定時器進行處理。以上的討論都體現在internal_add_timer的代碼中：
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 < TVR_SIZE) { int i = expires & TVR_MASK; vec = base->tv1.vec + i; } else if (idx < 1 << (TVR_BITS + TVN_BITS)) { int i = (expires >> TVR_BITS) & TVN_MASK; vec = base->tv2.vec + i; } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) { int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK; vec = base->tv3.vec + i; } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) { int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK; vec = base->tv4.vec + i; } else if ((signed long) idx < 0) { ...... } else { ...... i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK; vec = base->tv5.vec + i; } list_add_tail(&timer->entry, vec); }經過2.1節的處理后，系統中的定時器按到期時間有規律地放置在tv1–tv5各個鏈表數組中，其中tv1中放置著在接下來的256個jiffies即將到期的定時器列表，需要注意的是，并不是tv1.vec[0]中放置著馬上到期的定時器列表，tv1.vec[1]中放置著將在jiffies+1到期的定時器列表。因為base.timer_jiffies的值一直在隨著系統的運行而動態地增加，原則上是每個tick事件會加1，base.timer_jiffies代表者該cpu定時器系統當前時刻，定時器也是動態地加入頭256個鏈表tv1中，按2.1節的討論，定時器加入tv1中使用的下標索引是定時器到期時間expires的低8位，所以假設當前的base.timer_jiffies值是0x34567826，則馬上到期的定時器是在tv1.vec[0x26]中，如果這時候系統加入一個在jiffies值0x34567828到期的定時器，他將會加入到tv1.vec[0x28]中，運行兩個tick后，base.timer_jiffies的值會變為0x34567828，很顯然，在每次tick事件中，定時器系統只要以base.timer_jiffies的低8位作為索引，取出tv1中相應的鏈表，里面正好包含了所有在該jiffies值到期的定時器列表。
那什么時候處理tv2–tv5中的定時器？每當base.timer_jiffies的低8位為0值時，這表明base.timer_jiffies的第8-13位有進位發生，這6位正好代表著tv2，這時只要按base.timer_jiffies的第8-13位的值作為下標，移出tv2中對應的定時器鏈表，然后用internal_add_timer把它們從新加入到定時器系統中來，因為這些定時器一定會在接下來的256個tick期間到期，所以它們肯定會被加入到tv1數組中，這樣就完成了tv2往tv1遷移的過程。同樣地，當base.timer_jiffies的第8-13位為0時，這表明base.timer_jiffies的第14-19位有進位發生，這6位正好代表著tv3，按base.timer_jiffies的第14-19位的值作為下標，移出tv3中對應的定時器鏈表，然后用internal_add_timer把它們從新加入到定時器系統中來，顯然它們會被加入到tv2中，從而完成tv3到tv2的遷移，tv4，tv5的處理可以以此作類推。具體遷移的代碼如下，參數index為事先計算好的高一級tv的需要遷移的數組索引：
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); // 重新加入到定時器系統中，實際上將會遷移到下一級的tv數組中 internal_add_timer(base, timer); } return index; }每個tick事件到來時，內核會在tick定時中斷處理期間激活定時器軟中斷：TIMER_SOFTIRQ，關于軟件中斷，請參考另一篇博文：Linux中斷（interrupt）子系統之五：軟件中斷（softIRQ。TIMER_SOFTIRQ的執行函數是__run_timers，它實現了本節討論的邏輯，取出tv1中到期的定時器，執行定時器的回調函數，由此可見，低分辨率定時器的回調函數是執行在軟件中斷上下文中的，這點在寫定時器的回調函數時需要注意。__run_timers的代碼如下：
static inline void __run_timers(struct tvec_base *base) { struct timer_list *timer; spin_lock_irq(&base->lock); /* 同步jiffies，在NO_HZ情況下，base->timer_jiffies可能落后不止一個tick */ while (time_after_eq(jiffies, base->timer_jiffies)) { struct list_head work_list; struct list_head *head = &work_list; /* 計算到期定時器鏈表在tv1中的索引 */ int index = base->timer_jiffies & TVR_MASK; /* * /* tv2--tv5定時器列表遷移處理 */ */ 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定時器系統運行時間遞增一個tick */ ++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; timer_stats_account_timer(timer); base->running_timer = timer; /* 標記正在處理的定時器 */ detach_timer(timer, 1); spin_unlock_irq(&base->lock); call_timer_fn(timer, fn, data); /* 調用定時器的回調函數 */ spin_lock_irq(&base->lock); } } base->running_timer = NULL; spin_unlock_irq(&base->lock); }通過上面的討論，我們可以發現，內核的低分辨率定時器的實現非常精妙，既實現了大量定時器的管理，又實現了快速的O(1)查找到期定時器的能力，利用巧妙的數組結構，使得只需在間隔256個tick時間才處理一次遷移操作，5個數組就好比是5個齒輪，它們隨著base->timer_jifffies的增長而不停地轉動，每次只需處理第一個齒輪的某一個齒節，低一級的齒輪轉動一圈，高一級的齒輪轉動一個齒，同時自動把即將到期的定時器遷移到上一個齒輪中，所以低分辨率定時器通常又被叫做時間輪：time wheel。事實上，它的實現是一個很好的空間換時間軟件算法。
系統初始化時，start_kernel會調用定時器系統的初始化函數init_timers：
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); /* 注冊cpu notify，以便在hotplug時在cpu之間進行定時器的遷移 */ open_softirq(TIMER_SOFTIRQ, run_timer_softirq); }可見，open_softirq把run_timer_softirq注冊為TIMER_SOFTIRQ的處理函數，另外，當cpu的每個tick事件到來時，在事件處理中斷中，update_process_times會被調用，該函數會進一步調用run_local_timers，run_local_timers會觸發TIMER_SOFTIRQ軟中斷：
void run_local_timers(void) { hrtimer_run_queues(); raise_softirq(TIMER_SOFTIRQ); }TIMER_SOFTIRQ的處理函數是run_timer_softirq：
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函數了，2.2節已經介紹過，正是這個函數完成了對到期定時器的處理工作，也完成了時間輪的不停轉動。
新聞熱點
疑難解答
