7．5 時鐘中斷的Bottom Half
與時鐘中斷相關的Bottom Half向兩主要有兩個：TIMER_BH和TQUEUE_BH。與TIMER_BH相對應的BH函數是timer_bh()，與TQUEUE_BH對應的函數是tqueue_bh()。它們均實現在kernel/timer.c文件中。
7．5．1 TQUEUE_BH向量
TQUEUE_BH的作用是用來運行tq_timer這個任務隊列中的任務。因此do_timer()函數僅僅在tq_timer任務隊列不為空的情況才激活TQUEUE_BH向量。函數tqueue_bh()的實現非常簡單，它只是簡單地調用run_task_queue()函數來運行任務隊列tq_timer。如下所示：
void tqueue_bh(void)
{
run_task_queue(&tq_timer);
}
任務對列tq_timer也是定義在kernel/timer.c文件中，如下所示：
DECLARE_TASK_QUEUE(tq_timer);
7．5．2 TIMER_BH向量
TIMER_BH這個BottomHalf向量是Linux內核時鐘中斷驅動的一個重要輔助部分。內核在每一次對時鐘中斷的服務快要結束時，都會無條件地激活一個TIMER_BH向量，以使得內核在稍後一段延遲後執行相應的BH函數——timer_bh()。該任務的源碼如下：
void timer_bh(void)
{
update_times();
run_timer_list();
}
從上述源碼可以看出，內核在時鐘中斷驅動的底半部分主要有兩個任務：（1）調用update_times()函數來更新系統全局時間xtime；（2）調用run_timer_list()函數來執行定時器。關於定時器我們將在下一節討論。本節我們主要討論TIMER_BH的第一個任務——對內核時間xtime的更新。
我們都知道，內核局部時間xtime是用來供用戶程序通過時間syscall來檢索或設置當前系統時間的，而內核代碼在大多數情況下都引用jiffies變量，而很少使用xtime（偶爾也會有引用xtime的情況，比如更新inode的時間標記）。因此，對於時鐘中斷服務程序timer_interrupt（）而言，jiffies變量的更新是最緊迫的，而xtime的更新則可以延遲到中斷服務的底半部分來進行。
由於BottomHalf機制在執行時間具有某些不確定性，因此在timer_bh()函數得到真正執行之前，期間可能又會有幾次時鐘中斷發生。這樣就會造成時鐘滴答的丟失現象。為了處理這種情況，Linux內核使用了一個輔助全局變量wall_jiffies，來表示上一次更新xtime時的jiffies值。其定義如下（kernel/timer.c）：
/* jiffies at the most recent update of wall time */
unsigned long wall_jiffies;
而timer_bh()函數真正執行時的jiffies值與wall_jiffies的差就是在timer_bh()真正執行之前所發生的時鐘中斷次數。
函數update_times()的源碼如下（kernel/timer.c）：
static inline void update_times(void)
{
unsigned long ticks;
/*
* update_times() is run from the raw timer_bh handler so we
* just know that the irqs are locally enabled and so we don't
* need to save/restore the flags of the local CPU here. -arca
*/
write_lock_irq(&xtime_lock);
ticks = jiffies - wall_jiffies;
if (ticks) {
wall_jiffies += ticks;
update_wall_time(ticks);
}
write_unlock_irq(&xtime_lock);
calc_load(ticks);
}
（1）首先，根據jiffies和wall_jiffies的差值計算在此之前一共發生了幾次時鐘滴答，並將這個值保存到局部變量ticks中。並在ticks值大於0的情況下（ticks大於等於1，一般情況下為1）：①更新wall_jiffies為jiffies變量的當前值（wall_jiffies＋＝ticks等價於wall_jiffies＝jiffies）。②以參數ticks調用update_wall_time()函數去真正地更新全局時間xtime。
（2）調用calc_load()函數去計算系統負載情況。這裡我們不去深究它。
函數update_wall_time()函數根據參數ticks所指定的時鐘滴答次數相應地更新內核全局時間變量xtime。其源碼如下（kernel/timer.c）：
/*
* Using a loop looks inefficient, but "ticks" is
* usually just one (we shouldn't be losing ticks,
* we're doing this this way mainly for interrupt
* latency reasons, not because we think we'll
* have lots of lost timer ticks
*/
static void update_wall_time(unsigned long ticks)
{
do {
ticks--;
update_wall_time_one_tick();
} while (ticks);
if (xtime.tv_usec >= 1000000) {
xtime.tv_usec -= 1000000;
xtime.tv_sec++;
second_overflow();
}
}
對該函數的注釋如下：
（1）首先，用一個do{}循環來根據參數ticks的值一次一次調用update_wall_time_one_tick()函數來為一次時鐘滴答更新xtime中的tv_usec成員。
（2）根據需要調整xtime中的秒數成員tv_usec和微秒數成員tv_usec。如果微秒數成員tv_usec的值超過106，則說明已經過了一秒鐘。因此將tv_usec的值減去1000000，並將秒數成員tv_sec的值加1，然後調用second_overflow（）函數來處理微秒數成員溢出的情況。
函數update_wall_time_one_tick（）用來更新一次時鐘滴答對系統全局時間xtime的影響。由於tick全局變量表示了一次時鐘滴答的時間間隔長度（以us為單位），因此該函數的實現中最核心的代碼就是將xtime的tv_usec成員增加tick微秒。這裡我們不去關心函數實現中與NTP（Network TimeProtocol）和系統調用adjtimex（）的相關部分。其源碼如下（kernel/timer.c）：
/* in the NTP reference this is called "hardclock()" */
static void update_wall_time_one_tick(void)
{
if ( (time_adjust_step = time_adjust) != 0 ) {
/* We are doing an adjtime thing.
*
* Prepare time_adjust_step to be within bounds.
* Note that a positive time_adjust means we want the clock
* to run faster.
*
* Limit the amount of the step to be in the range
* -tickadj .. +tickadj
*/
if (time_adjust > tickadj)
time_adjust_step = tickadj;
else if (time_adjust < -tickadj)
time_adjust_step = -tickadj;
/* Reduce by this step the amount of time left */
time_adjust -= time_adjust_step;
}
xtime.tv_usec += tick + time_adjust_step;
/*
* Advance the phase, once it gets to one microsecond, then
* advance the tick more.
*/
time_phase += time_adj;
if (time_phase <= -FINEUSEC) {
long ltemp = -time_phase >> SHIFT_SCALE;
time_phase += ltemp << SHIFT_SCALE;
xtime.tv_usec -= ltemp;
}
else if (time_phase >= FINEUSEC) {
long ltemp = time_phase >> SHIFT_SCALE;
time_phase -= ltemp << SHIFT_SCALE;
xtime.tv_usec += ltemp;
}
}
7．6 內核定時器機制
Linux內核2.4版中去掉了老版本內核中的靜態定時器機制，而只留下動態定時器。相應地在timer_bh()函數中也不再通過run_old_timers()函數來運行老式的靜態定時器。動態定時器與靜態定時器這二個概念是相對於Linux內核定時器機制的可擴展功能而言的，動態定時器是指內核的定時器隊列是可以動態變化的，然而就定時器本身而言，二者並無本質的區別。考慮到靜態定時器機制的能力有限，因此Linux內核2.4版中完全去掉了以前的靜態定時器機制。
7．6．1 Linux內核對定時器的描述
Linux在include/linux/timer.h頭文件中定義了數據結構timer_list來描述一個內核定時器：
struct timer_list {
struct list_head list;
unsigned long expires;
unsigned long data;
void (*function)(unsigned long);
};
各數據成員的含義如下：
（1）雙向鏈表元素list：用來將多個定時器連接成一條雙向循環隊列。
（2）expires：指定定時器到期的時間，這個時間被表示成自系統啟動以來的時鐘滴答計數（也即時鐘節拍數）。當一個定時器的expires值小於或等於jiffies變量時，我們就說這個定時器已經超時或到期了。在初始化一個定時器後，通常把它的expires域設置成當前expires變量的當前值加上某個時間間隔值（以時鐘滴答次數計）。
（3）函數指針function：指向一個可執行函數。當定時器到期時，內核就執行function所指定的函數。而data域則被內核用作function函數的調用參數。
內核函數init_timer()用來初始化一個定時器。實際上，這個初始化函數僅僅將結構中的list成員初始化為空。如下所示（include/linux/timer.h）：
static inline void init_timer(struct timer_list * timer)
{
timer->list.next = timer->list.prev = NULL;
}
由於定時器通常被連接在一個雙向循環隊列中等待執行（此時我們說定時器處於pending狀態）。因此函數time_pending()就可以用list成員是否為空來判斷一個定時器是否處於pending狀態。如下所示（include/linux/timer.h）：
static inline int timer_pending (const struct timer_list * timer)
{
return timer->list.next != NULL;
}
l時間比較操作
在定時器應用中經常需要比較兩個時間值，以確定timer是否超時，所以Linux內核在timer.h頭文件中定義了4個時間關系比較操作宏。這裡我們說時刻a在時刻b之後，就意味著時間值a≥b。Linux強烈推薦用戶使用它所定義的下列4個時間比較操作宏（include/linux/timer.h）：
#define time_after(a,b)((long)(b) - (long)(a) < 0)
#define time_before(a,b)time_after(b,a)
#define time_after_eq(a,b)((long)(a) - (long)(b) >= 0)
#define time_before_eq(a,b)time_after_eq(b,a)
7．6．2 動態內核定時器機制的原理
Linux是怎樣為其內核定時器機制提供動態擴展能力的呢？其關鍵就在於“定時器向量”的概念。所謂“定時器向量”就是指這樣一條雙向循環定時器隊列（對列中的每一個元素都是一個timer_list結構）：對列中的所有定時器都在同一個時刻到期，也即對列中的每一個timer_list結構都具有相同的expires值。顯然，可以用一個timer_list結構類型的指針來表示一個定時器向量。
顯然，定時器expires成員的值與jiffies變量的差值決定了一個定時器將在多長時間後到期。在32位系統中，這個時間差值的最大值應該是0xffffffff。因此如果是基於“定時器向量”基本定義，內核將至少要維護0xffffffff個timer_list結構類型的指針，這顯然是不現實的。
另一方面，從內核本身這個角度看，它所關心的定時器顯然不是那些已經過期而被執行過的定時器（這些定時器完全可以被丟棄），也不是那些要經過很長時間才會到期的定時器，而是那些當前已經到期或者馬上就要到期的定時器（注意！時間間隔是以滴答次數為計數單位的）。
基於上述考慮，並假定一個定時器要經過interval個時鐘滴答後才到期（interval＝expires－jiffies），則Linux采用了下列思想來實現其動態內核定時器機制：對於那些0≤interval≤255的定時器，Linux嚴格按照定時器向量的基本語義來組織這些定時器，也即Linux內核最關心那些在接下來的255個時鐘節拍內就要到期的定時器，因此將它們按照各自不同的expires值組織成256個定時器向量。而對於那些256≤interval≤0xffffffff的定時器，由於他們離到期還有一段時間，因此內核並不關心他們，而是將它們以一種擴展的定時器向量語義（或稱為“松散的定時器向量語義”）進行組織。所謂“松散的定時器向量語義”就是指：各定時器的expires值可以互不相同的一個定時器隊列。
具體的組織方案可以分為兩大部分：
（1）對於內核最關心的、interval值在［0，255］之間的前256個定時器向量，內核是這樣組織它們的：這256個定時器向量被組織在一起組成一個定時器向量數組，並作為數據結構timer_vec_root的一部分，該數據結構定義在kernel/timer.c文件中，如下述代碼段所示：
/*
* Event timer code
*/
#define TVN_BITS 6
#define TVR_BITS 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 timer_vec {
int index;
struct list_head vec[TVN_SIZE];
};
struct timer_vec_root {
int index;
struct list_head vec[TVR_SIZE];
};
static struct timer_vec tv5;
static struct timer_vec tv4;
static struct timer_vec tv3;
static struct timer_vec tv2;
static struct timer_vec_root tv1;
static struct timer_vec * const tvecs[] = {
(struct timer_vec *)&tv1, &tv2, &tv3, &tv4, &tv5
};
#define NOOF_TVECS (sizeof(tvecs) / sizeof(tvecs[0]))
基於數據結構timer_vec_root，Linux定義了一個全局變量tv1，以表示內核所關心的前256個定時器向量。這樣內核在處理是否有到期定時器時，它就只從定時器向量數組tv1.vec［256］中的某個定時器向量內進行掃描。而tv1的index字段則指定當前正在掃描定時器向量數組tv1.vec［256］中的哪一個定時器向量，也即該數組的索引，其初值為0，最大值為255（以256為模）。每個時鐘節拍時index字段都會加1。顯然，index字段所指定的定時器向量tv1.vec［index］中包含了當前時鐘節拍內已經到期的所有動態定時器。而定時器向量tv1.vec［index＋k］則包含了接下來第k個時鐘節拍時刻將到期的所有動態定時器。當index值又重新變為0時，就意味著內核已經掃描了tv1變量中的所有256個定時器向量。在這種情況下就必須將那些以松散定時器向量語義來組織的定時器向量補充到tv1中來。
（2）而對於內核不關心的、interval值在［0xff，0xffffffff］之間的定時器，它們的到期緊迫程度也隨其interval值的不同而不同。顯然interval值越小，定時器緊迫程度也越高。因此在將它們以松散定時器向量進行組織時也應該區別對待。通常，定時器的interval值越小，它所處的定時器向量的松散度也就越低（也即向量中的各定時器的expires值相差越小）；而interval值越大，它所處的定時器向量的松散度也就越大（也即向量中的各定時器的expires值相差越大）。
內核規定，對於那些滿足條件：0x100≤interval≤0x3fff的定時器，只要表達式（interval>>8）具有相同值的定時器都將被組織在同一個松散定時器向量中。因此，為組織所有滿足條件0x100≤interval≤0x3fff的定時器，就需要26＝64個松散定時器向量。同樣地，為方便起見，這64個松散定時器向量也放在一起形成數組，並作為數據結構timer_vec的一部分。基於數據結構timer_vec，Linux定義了全局變量tv2，來表示這64條松散定時器向量。如上述代碼段所示。
對於那些滿足條件0x4000≤interval≤0xfffff的定時器，只要表達式（interval>>8＋6）的值相同的定時器都將被放在同一個松散定時器向量中。同樣，要組織所有滿足條件0x4000≤interval≤0xfffff的定時器，也需要26＝64個松散定時器向量。類似地，這64個松散定時器向量也可以用一個timer_vec結構來描述，相應地Linux定義了tv3全局變量來表示這64個松散定時器向量。
對於那些滿足條件0x100000≤interval≤0x3ffffff的定時器，只要表達式（interval>>8＋6＋6）的值相同的定時器都將被放在同一個松散定時器向量中。同樣，要組織所有滿足條件0x100000≤interval≤0x3ffffff的定時器，也需要26＝64個松散定時器向量。類似地，這64個松散定時器向量也可以用一個timer_vec結構來描述，相應地Linux定義了tv4全局變量來表示這64個松散定時器向量。
對於那些滿足條件0x4000000≤interval≤0xffffffff的定時器，只要表達式（interval>>8＋6＋6＋6）的值相同的定時器都將被放在同一個松散定時器向量中。同樣，要組織所有滿足條件0x4000000≤interval≤0xffffffff的定時器，也需要26＝64個松散定時器向量。類似地，這64個松散定時器向量也可以用一個timer_vec結構來描述，相應地Linux定義了tv5全局變量來表示這64個松散定時器向量。
最後，為了引用方便，Linux定義了一個指針數組tvecs［］，來分別指向tv1、tv2、…、tv5結構變量。如上述代碼所示。
整個內核定時器機制的總體結構如下圖7－8所示：
7．6．3 內核動態定時器機制的實現
在內核動態定時器機制的實現中，有三個操作時非常重要的：（1）將一個定時器插入到它應該所處的定時器向量中。（2）定時器的遷移，也即將一個定時器從它原來所處的定時器向量遷移到另一個定時器向量中。（3）掃描並執行當前已經到期的定時器。
7．6．3．1 動態定時器機制的初始化
函數init_timervecs()實現對動態定時器機制的初始化。該函數僅被sched_init()初始化例程所調用。動態定時器機制初始化過程的主要任務就是將tv1、tv2、…、tv5這5個結構變量中的定時器向量指針數組vec［］初始化為NULL。如下所示（kernel/timer.c）：
void init_timervecs (void)
{
int i;
for (i = 0; i < TVN_SIZE; i++) {
INIT_LIST_HEAD(tv5.vec + i);
INIT_LIST_HEAD(tv4.vec + i);
INIT_LIST_HEAD(tv3.vec + i);
INIT_LIST_HEAD(tv2.vec + i);
}
for (i = 0; i < TVR_SIZE; i++)
INIT_LIST_HEAD(tv1.vec + i);
}
上述函數中的宏TVN_SIZE是指timer_vec結構類型中的定時器向量指針數組vec［］的大小，值為64。宏TVR_SIZE是指timer_vec_root結構類型中的定時器向量數組vec［］的大小，值為256。
7．6．3．2 動態定時器的時鐘滴答基准timer_jiffies
由於動態定時器是在時鐘中斷的BottomHalf中被執行的，而從TIMER_BH向量被激活到其timer_bh()函數真正執行這段時間內可能會有幾次時鐘中斷發生。因此內核必須記住上一次運行定時器機制是什麼時候，也即內核必須保存上一次運行定時器機制時的jiffies值。為此，Linux在kernel/timer.c文件中定義了全局變量timer_jiffies來表示上一次運行定時器機制時的jiffies值。該變量的定義如下所示：
static unsigned long timer_jiffies;
7．6．3．3 對內核動態定時器鏈表的保護
由於內核動態定時器鏈表是一種系統全局共享資源，為了實現對它的互斥訪問，Linux定義了專門的自旋鎖timerlist_lock來保護。任何想要訪問動態定時器鏈表的代碼段都首先必須先持有該自旋鎖，並且在訪問結束後釋放該自旋鎖。其定義如下（kernel/timer.c）：
/* Initialize both explicitly - let's try to have them in the same cache line */
spinlock_t timerlist_lock = SPIN_LOCK_UNLOCKED;
7．6．3．4 將一個定時器插入到鏈表中
函數add_timer()用來將參數timer指針所指向的定時器插入到一個合適的定時器鏈表中。它首先調用timer_pending()函數判斷所指定的定時器是否已經位於在某個定時器向量中等待執行。如果是，則不進行任何操作，只是打印一條內核告警信息就返回了；如果不是，則調用internal_add_timer()函數完成實際的插入操作。其源碼如下（kernel/timer.c）：
void add_timer(struct timer_list *timer)
{
unsigned long flags;
spin_lock_irqsave(&timerlist_lock, flags);
if (timer_pending(timer))
goto bug;
internal_add_timer(timer);
spin_unlock_irqrestore(&timerlist_lock, flags);
return;
bug:
spin_unlock_irqrestore(&timerlist_lock, flags);
printk("bug: kernel timer added twice at %p.\n",
__builtin_return_address(0));
}
函數internal_add_timer()用於將一個不處於任何定時器向量中的定時器插入到它應該所處的定時器向量中去（根據定時器的expires值來決定）。如下所示（kernel/timer.c）：
static inline void internal_add_timer(struct timer_list *timer)
{
/*
* must be cli-ed when calling this
*/
unsigned long expires = timer->expires;
unsigned long idx = expires - timer_jiffies;
struct list_head * vec;
if (idx < TVR_SIZE) {
int i = expires & TVR_MASK;
vec = tv1.vec + i;
} else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
int i = (expires >> TVR_BITS) & TVN_MASK;
vec = tv2.vec + i;
} else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
vec = tv3.vec + i;
} else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {
int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
vec = tv4.vec + i;
} else if ((signed long) idx < 0) {
/* can happen if you add a timer with expires == jiffies,
* or you set a timer to go off in the past
*/
vec = tv1.vec + tv1.index;
} else if (idx <= 0xffffffffUL) {
int i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
vec = tv5.vec + i;
} else {
/* Can only get here on architectures with 64-bit jiffies */
INIT_LIST_HEAD(&timer->list);
return;
}
/*
* Timers are FIFO!
*/
list_add(&timer->list, vec->prev);
}
對該函數的注釋如下：
（1）首先，計算定時器的expires值與timer_jiffies的插值（注意！這裡應該使用動態定時器自己的時間基准），這個差值就表示這個定時器相對於上一次運行定時器機制的那個時刻還需要多長時間間隔才到期。局部變量idx保存這個差值。
（2）根據idx的值確定這個定時器應被插入到哪一個定時器向量中。其具體的確定方法我們在7.6.2節已經說過了，這裡不再詳述。最後，定時器向量的頭部指針vec表示這個定時器應該所處的定時器向量鏈表頭部。
（3）最後，調用list_add()函數將定時器插入到vec指針所指向的定時器隊列的尾部。
7．6．3．5 修改一個定時器的expires值
當一個定時器已經被插入到內核動態定時器鏈表中後，我們還可以修改該定時器的expires值。函數mod_timer()實現這一點。如下所示（kernel/timer.c）：
int mod_timer(struct timer_list *timer, unsigned long expires)
{
int ret;
unsigned long flags;
spin_lock_irqsave(&timerlist_lock, flags);
timer->expires = expires;
ret = detach_timer(timer);
internal_add_timer(timer);
spin_unlock_irqrestore(&timerlist_lock, flags);
return ret;
}
該函數首先根據參數expires值更新定時器的expires成員。然後調用detach_timer()函數將該定時器從它原來所屬的鏈表中刪除。最後調用internal_add_timer()函數將該定時器根據它新的expires值重新插入到相應的鏈表中。
函數detach_timer()首先調用timer_pending()來判斷指定的定時器是否已經處於某個鏈表中，如果定時器原來就不處於任何鏈表中，則detach_timer()函數什麼也不做，直接返回0值，表示失敗。否則，就調用list_del()函數將定時器從它原來所處的鏈表中摘除。如下所示（kernel/timer.c）：
static inline int detach_timer (struct timer_list *timer)
{
if (!timer_pending(timer))
return 0;
list_del(&timer->list);
return 1;
}
7．6．3．6 刪除一個定時器
函數del_timer()用來將一個定時器從相應的內核定時器隊列中刪除。該函數實際上是對detach_timer()函數的高層封裝。如下所示（kernel/timer.c）：
int del_timer(struct timer_list * timer)
{
int ret;
unsigned long flags;
spin_lock_irqsave(&timerlist_lock, flags);
ret = detach_timer(timer);
timer->list.next = timer->list.prev = NULL;
spin_unlock_irqrestore(&timerlist_lock, flags);
return ret;
}
7．6．3．7 定時器遷移操作
由於一個定時器的interval值會隨著時間的不斷流逝（即jiffies值的不斷增大）而不斷變小，因此那些原本到期緊迫程度較低的定時器會隨著jiffies值的不斷增大而成為既將馬上到期的定時器。比如定時器向量tv2.vec[0]中的定時器在經過256個時鐘滴答後會成為未來256個時鐘滴答內會到期的定時器。因此，定時器在內核動態定時器鏈表中的位置也應相應地隨著改變。改變的規則是：當tv1.index重新變為0時（意味著tv1中的256個定時器向量都已被內核掃描一遍了，從而使tv1中的256個定時器向量變為空），則用tv2.vec［index］定時器向量中的定時器去填充tv1，同時使tv2.index加1（它以64為模）。當tv2.index重新變為0（意味著tv2中的64個定時器向量都已經被全部填充到tv1中去了，從而使得tv2變為空），則用tv3.vec［index］定時器向量中的定時器去填充tv2。如此一直類推下去，直到tv5。
函數cascade_timers()完成這種定時器遷移操作，該函數只有一個timer_vec結構類型指針的參數tv。這個函數將把定時器向量tv->vec［tv->index］中的所有定時器重新填充到上一層定時器向量中去。如下所示（kernel/timer.c）：
static inline void cascade_timers(struct timer_vec *tv)
{
/* cascade all the timers from tv up one level */
struct list_head *head, *curr, *next;
head = tv->vec + tv->index;
curr = head->next;
/*
* We are removing _all_ timers from the list, so we don't have to
* detach them individually, just clear the list afterwards.
*/
while (curr != head) {
struct timer_list *tmp;
tmp = list_entry(curr, struct timer_list, list);
next = curr->next;
list_del(curr); // not needed
internal_add_timer(tmp);
curr = next;
}
INIT_LIST_HEAD(head);
tv->index = (tv->index + 1) & TVN_MASK;
}
對該函數的注釋如下：
（1）首先，用指針head指向定時器頭部向量頭部的list_head結構。指針curr指向定時器向量中的第一個定時器。
（2）然後，用一個while{}循環來遍歷定時器向量tv->vec［tv->index］。由於定時器向量是一個雙向循環隊列，因此循環的終止條件是curr=head。對於每一個被掃描的定時器，循環體都先調用list_del()函數將當前定時器從鏈表中摘除，然後調用internal_add_timer()函數重新確定該定時器應該被放到哪個定時器向量中去。
（3）當從while{}循環退出後，定時器向量tv->vec［tv->index］中所有的定時器都已被遷移到其它地方（到它們該呆的地方：－），因此它本身就成為一個空隊列。這裡我們顯示地調用INIT_LIST_HEAD()宏來將定時器向量的表頭結構初始化為空。
（4）最後，將tv->index值加1，當然它是以64為模。
7．6．4．8 掃描並執行當前已經到期的定時器
函數run_timer_list()完成這個功能。如前所述，該函數是被timer_bh()函數所調用的，因此內核定時器是在時鐘中斷的BottomHalf中被執行的。記住這一點非常重要。全局變量timer_jiffies表示了內核上一次執行run_timer_list()函數的時間，因此jiffies與timer_jiffies的差值就表示了自從上一次處理定時器以來，期間一共發生了多少次時鐘中斷，顯然run_timer_list()函數必須為期間所發生的每一次時鐘中斷補上定時器服務。該函數的源碼如下（kernel/timer.c）：
static inline void run_timer_list(void)
{
spin_lock_irq(&timerlist_lock);
while ((long)(jiffies - timer_jiffies) >= 0) {
struct list_head *head, *curr;
if (!tv1.index) {
int n = 1;
do {
cascade_timers(tvecs[n]);
} while (tvecs[n]->index == 1 && ++n < NOOF_TVECS);
}
repeat:
head = tv1.vec + tv1.index;
curr = head->next;
if (curr != head) {
struct timer_list *timer;
void (*fn)(unsigned long);
unsigned long data;
timer = list_entry(curr, struct timer_list, list);
fn = timer->function;
data= timer->data;
detach_timer(timer);
timer->list.next = timer->list.prev = NULL;
timer_enter(timer);
spin_unlock_irq(&timerlist_lock);
fn(data);
spin_lock_irq(&timerlist_lock);
timer_exit();
goto repeat;
}
++timer_jiffies;
tv1.index = (tv1.index + 1) & TVR_MASK;
}
spin_unlock_irq(&timerlist_lock);
}
函數run_timer_list()的執行過程主要就是用一個大while{}循環來為時鐘中斷執行定時器服務，每一次循環服務一次時鐘中斷。因此一共要執行（jiffies－timer_jiffies＋1）次循環。循環體所執行的服務步驟如下：
（1）首先，判斷tv1.index是否為0，如果為0則需要從tv2中補充定時器到tv1中來。但tv2也可能為空而需要從tv3中補充定時器，因此用一個do{}while循環來調用cascade_timer()函數來依次視需要從tv2中補充tv1，從tv3中補充tv2、…、從tv5中補充tv4。顯然如果tvi.index=0（2≤i≤5），則對於tvi執行cascade_timers()函數後，tvi.index肯定為1。反過來講，如果對tvi執行過cascade_timers()函數後tvi.index不等於1，那麼可以肯定在未對tvi執行cascade_timers()函數之前，tvi.index值肯定不為0，因此這時tvi不需要從tv(i+1)中補充定時器，這時就可以終止do{}while循環。
（2）接下來，就要執行定時器向量tv1.vec［tv1.index］中的所有到期定時器。因此這裡用一個gotorepeat循環從頭到尾依次掃描整個定時器對列。由於在執行定時器的關聯函數時並不需要關CPU中斷，所以在用detach_timer()函數將當前定時器從對列中摘除後，就可以調用spin_unlock_irq()函數進行解鎖和開中斷，然後在執行完當前定時器的關聯函數後重新用spin_lock_irq（）函數加鎖和關中斷。
（3）當執行完定時器向量tv1.vec[tv1.index]中的所有到期定時器後，tv1.vec［tv1.index］應該是個空隊列。至此這一次定時器服務也就宣告結束。
（4）最後，將timer_jiffies值加1，將tv1.index值加1，當然它的模是256。然後，回到while循環開始下一次定時器服務。
