Linux 時鐘處理機

在 Linux 操作系統中，很多活動都和時間有關，例如：進程調度和網路處理等等。所以說，了解 Linux 操作系統中的時鐘處理機制有助於更好地了解 Linux 操作系統的運作方式。本文分析了 Linux 2.6.25 內核的時鐘處理機制，首先介紹了在計算機系統中的一些硬體計時器，然後重點介紹了 Linux 操作系統中的硬體時鐘和軟體時鐘的處理過程以及軟體時鐘的應用。最後對全文進行了總結。

1 計算機系統中的計時器

在計算機系統中存在著許多硬體計時器，例如 Real Timer Clock （ RTC ）、Time Stamp Counter （ TSC ） 和 Programmable Interval Timer （ PIT ） 等等。

這部分內容不是本文的中點，這裡僅僅簡單介紹幾種，更多內容參見參考文獻：

• Real Timer Clock （ RTC ）：
  • 獨立於整個計算機系統（例如： CPU 和其他 chip ）
  • 內核利用其獲取系統當前時間和日期
• Time Stamp Counter （ TSC ）：
  • 從 Pentium 起，提供一個寄存器 TSC，用來累計每一次外部振蕩器產生的時鐘信號
  • 通過指令 rdtsc 訪問這個寄存器
  • 比起 PIT，TSC 可以提供更精確的時間測量
• Programmable Interval Timer （ PIT ）：
  • 時間測量設備
  • 內核使用的產生時鐘中斷的設備，產生的時鐘中斷依賴於硬體的體系結構，慢的為 10 ms 一次，快的為 1 ms 一次
• High Precision Event Timer （ HPET ）：
  • PIT 和 RTC 的替代者，和之前的計時器相比，HPET 提供了更高的時鐘頻率（至少10 MHz ）以及更寬的計數器寬度（64位）
  • 一個 HPET 包括了一個固定頻率的數值增加的計數器以及3到32個獨立的計時器，這每一個計時器有包涵了一個比較器和一個寄存器（保存一個數值，表示觸發中斷的時機）。每一個比較器都比較計數器中的數值和寄存器中的數值，當這兩個數值相等時，將產生一個中斷

2 硬體時鐘處理

這裡所說的硬體時鐘處理特指的是硬體計時器時鐘中斷的處理過程。

2.1 數據結構

和硬體計時器（本文又稱作硬體時鐘，區別於軟體時鐘）相關的數據結構主要有兩個：

• struct clocksource ：對硬體設備的抽象，描述時鐘源信息
• struct clock_event_device ：時鐘的事件信息，包括當硬體時鐘中斷髮生時要執行那些操作（實際上保存了相應函數的指針）。本文將該結構稱作為“時鐘事件設備”。

上述兩個結構內核源代碼中有較詳細的註解，分別位於文件 clocksource.h 和 clockchips.h 中。需要特別注意的是結構 clock_event_device 的成員 event_handler ，它指定了當硬體時鐘中斷髮生時，內核應該執行那些操作，也就是真正的時鐘中斷處理函數。 在2.3節“時鐘初始化”部分會介紹它真正指向哪個函數。

Linux 內核維護了兩個鏈表，分別存儲了系統中所有時鐘源的信息和時鐘事件設備的信息。這兩個鏈表的表頭在內核中分別是 clocksource_list 和 clockevent_devices 。圖2-1顯示了這兩個鏈表。

2.2 通知鏈技術（ notification chain ）

在時鐘處理這部分中，內核用到了所謂的“通知鏈（ notification chain ）”技術。所以在介紹時鐘處理過程之前先來了解下“通知鏈”技術。

在 Linux 內核中，各個子系統之間有很強的相互關係，一些被一個子系統生成或者被探測到的事件，很可能是另一個或者多個子系統感興趣的，也就是說這個事件的獲取者必須能夠通知所有對該事件感興趣的子系統，並且還需要這種通知機制具有一定的通用性。基於這些， Linux 內核引入了“通知鏈”技術。

2.2.1 數據結構：

通知鏈有四種類型，

1. 原子通知鏈（ Atomic notifier chains ）：通知鏈元素的回調函數（當事件發生時要執行的函數）只能在中斷上下文中運行，不允許阻塞
2. 可阻塞通知鏈（ Blocking notifier chains ）：通知鏈元素的回調函數在進程上下文中運行，允許阻塞
3. 原始通知鏈（ Raw notifier chains ）：對通知鏈元素的回調函數沒有任何限制，所有鎖和保護機制都由調用者維護
4. SRCU 通知鏈（ SRCU notifier chains ）：可阻塞通知鏈的一種變體

所以對應了四種通知鏈頭結構：

• struct atomic_notifier_head ：原子通知鏈的鏈頭
• struct blocking_notifier_head ：可阻塞通知鏈的鏈頭
• struct raw_notifier_head ：原始通知鏈的鏈頭
• struct srcu_notifier_head ： SRCU 通知鏈的鏈頭

通知鏈元素的類型：

• struct notifier_block ：通知鏈中的元素，記錄了當發出通知時，應該執行的操作（即回調函數）

鏈頭中保存著指向元素鏈表的指針。通知鏈元素結構則保存著回調函數的類型以及優先順序，參見 notifier.h 文件。

2.2.2 運作機制

通知鏈的運作機制包括兩個角色：

1. 被通知者：對某一事件感興趣一方。定義了當事件發生時，相應的處理函數，即回調函數。但需要事先將其註冊到通知鏈中（被通知者註冊的動作就是在通知鏈中增加一項）。
2. 通知者：事件的通知者。當檢測到某事件，或者本身產生事件時，通知所有對該事件感興趣的一方事件發生。他定義了一個通知鏈，其中保存了每一個被通知者對事件的處理函數（回調函數）。通知這個過程實際上就是遍歷通知鏈中的每一項，然後調用相應的事件處理函數。

包括以下過程：

1. 通知者定義通知鏈
2. 被通知者向通知鏈中註冊回調函數
3. 當事件發生時，通知者發出通知（執行通知鏈中所有元素的回調函數）

整個過程可以看作是“發布——訂閱”模型（參見參考資料）

被通知者調用 notifier_chain_register 函數註冊回調函數，該函數按照優先順序將回調函數加入到通知鏈中 。註銷回調函數則使用 notifier_chain_unregister 函數，即將回調函數從通知鏈中刪除。2.2.1節講述的4種通知鏈各有相應的註冊和註銷函數，但是他們最終都是調用上述兩個函數完成註冊和註銷功能的。有興趣的讀者可以自行查閱內核代碼。

通知者調用 notifier_call_chain 函數通知事件的到達，這個函數會遍歷通知鏈中所有的元素，然後依次調用每一個的回調函數（即完成通知動作）。2.2.1節講述的4種通知鏈也都有其對應的通知函數，這些函數也都是最終調用 notifier_call_chain 函數完成事件的通知。

更多關於通知鏈的內容，參見參考文獻。

由以上的敘述，“通知鏈”技術可以概括為：事件的被通知者將事件發生時應該執行的操作通過函數指針方式保存在鏈表（通知鏈）中，然後當事件發生時通知者依次執行鏈表中每一個元素的回調函數完成通知。

2.3 時鐘初始化

內核初始化部分（ start_kernel 函數）和時鐘相關的過程主要有以下幾個：

1. tick_init()
2. init_timers()
3. hrtimers_init()
4. time_init()

其中函數 hrtimers_init() 和高精度時鐘相關（本文暫不介紹這部分內容）。下面將詳細介紹剩下三個函數。

2.3.1 tick_init 函數

函數 tick_init() 很簡單，調用 clockevents_register_notifier 函數向 clockevents_chain 通知鏈註冊元素： tick_notifier。這個元素的回調函數指明了當時鐘事件設備信息發生變化（例如新加入一個時鐘事件設備等等）時，應該執行的操作，該回調函數為 tick_notify （參見2.4節）。

2.3.2 init_timers 函數

註：本文中所有代碼均來自於Linux2.6.25 源代碼

函數 init_timers() 的實現如清單2-1（省略了部分和

主要功能無關的內容，以後代碼同樣方式處理）

void __init init_timers(void)  {      int err = timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE,                                           (void *)(long)smp_processor_id());      ……      register_cpu_notifier(&timers_nb);      open_softirq(TIMER_SOFTIRQ,run_timer_softirq, NULL);  }  

代碼解釋：

• 初始化本 CPU 上的軟體時鐘相關的數據結構，參見3.2節
• 向 cpu_chain 通知鏈註冊元素 timers_nb ，該元素的回調函數用於初始化指定 CPU 上的軟體時鐘相關的數據結構
• 初始化時鐘的軟中斷處理函數

2.3.3 time_init 函數

函數 time_init 的實現如清單2-2

void __init time_init(void)  {      ……      init_tsc_clocksource();      late_time_init = choose_time_init();  }  

函數 init_tsc_clocksource 初始化 tsc 時鐘源。choose_time_init 實際是函數 hpet_time_init ，其代碼清單2-3

void __init hpet_time_init(void)  {      if (!hpet_enable())          setup_pit_timer();        setup_irq(0, &irq0);  }  

函數 hpet_enable 檢測系統是否可以使用 hpet 時鐘，如果可以則初始化 hpet 時鐘。否則初始化 pit 時鐘。最後設置硬體時鐘發生時的處理函數（參見2.4節）。

初始化硬體時鐘這個過程主要包括以下兩個過程（參見 hpet_enable 的實現）：

1. 初始化時鐘源信息（ struct clocksource 類型的變數），並將其添加到時鐘源鏈表中，即 clocksource_list 鏈表（參見圖2-1）。
2. 初始化時鐘事件設備信息（ struct clock_event_device 類型的變數），並向通知鏈 clockevents_chain 發布通知：一個時鐘事件設備要被添加到系統中。在通知（執行回調函數）結束后，該時鐘事件設備被添加到時鐘事件設備鏈表中，即 clockevent_devices 鏈表（參見圖2-1）。有關通知鏈的內容參見2.2節。

需要注意的是在初始化時鐘事件設備時，全局變數 global_clock_event 被賦予了相應的值。該變數保存著系統中當前正在使用的時鐘事件設備（保存了系統當前使用的硬體時鐘中斷髮生時，要執行的中斷處理函數的指針）。

2.4 硬體時鐘處理過程

由2.3.3可知硬體時鐘中斷的處理函數保存在靜態變數 irq0 中，其定義如清單2-4

static struct irqaction irq0 = {  	.handler	= timer_event_interrupt,  	.flags		= IRQF_DISABLED | IRQF_IRQPOLL | IRQF_NOBALANCING,  	.mask		= CPU_MASK_NONE,  	.name		= "timer"  };  

由定義可知：函數 timer_event_interrupt 為時鐘中斷處理函數，其定義如清單2-5

static irqreturn_t timer_event_interrupt(int irq, void *dev_id)  {      add_pda(irq0_irqs, 1);      global_clock_event->event_handler(global_clock_event);      return IRQ_HANDLED;  }  

從代碼中可以看出：函數 timer_event_interrupt 實際上調用的是 global_clock_event 變數的 event_handler 成員。那 event_handler 成員指向哪裡呢？

為了說明這個問題，不妨假設系統中使用的是 hpet 時鐘。由2.3.3節可知 global_clock_event 指向 hpet 時鐘事件設備（ hpet_clockevent ）。查看 hpet_enable 函數的代碼並沒有發現有對 event_handler 成員的賦值。所以繼續查看時鐘事件設備加入事件的處理函數 tick_notify ，該函數記錄了當時鐘事件設備發生變化（例如，新時鐘事件設備的加入）時，執行那些操作（參見2.3.1節），代碼如清單2-6

static int tick_notify(struct notifier_block *nb, unsigned long reason, void *dev)  {      switch (reason) {      case CLOCK_EVT_NOTIFY_ADD:          return tick_check_new_device(dev);      ……      return NOTIFY_OK;  }  

由代碼可知：對於新加入時鐘事件設備這個事件，將會調用函數 tick_check_new_device 。順著該函數的調用序列向下查找。tick_set_periodic_handler 函數將時鐘事件設備的 event_handler 成員賦值為 tick_handle_periodic 函數的地址。由此可知，函數 tick_handle_periodic 為硬體時鐘中斷髮生時，真正的運行函數。

函數 tick_handle_periodic 的處理過程分成了以下兩個部分：

1. 全局處理：整個系統中的信息處理
2. 局部處理：局部於本地 CPU 的處理

總結一下，一次時鐘中斷髮生后， OS 主要執行的操作（ tick_handle_periodic ）：

• 全局處理（僅在一個 CPU 上運行）：

1. 更新 jiffies_64
2. 更新 xtimer 和當前時鐘源信息等
3. 根據 tick 計算 avenrun 負載

• 局部處理（每個 CPU 都要運行）：
  1. 根據當前在用戶態還是核心態，統計當前進程的時間：用戶態時間還是核心態時間
  2. 喚醒 TIMER_SOFTIRQ 軟中斷
  3. 喚醒 RCU 軟中斷
  4. 調用 scheduler_tick （更新進程時間片等等操作，更多內容參見參考文獻）
  5. profile_tick 函數調用

以上就介紹完了硬體時鐘的處理過程，下面來看軟體時鐘。

3 軟體時鐘處理

這裡所說“軟體時鐘”指的是軟體定時器（ Software Timers ），是一個軟體上的概念，是建立在硬體時鐘基礎之上的。它記錄了未來某一時刻要執行的操作（函數），並使得當這一時刻真正到來時，這些操作（函數）能夠被按時執行。舉個例子說明：它就像生活中的鬧鈴，給鬧鈴設定振鈴時間（未來的某一時間）后，當時間（相當於硬體時鐘）更新到這個振鈴時間后，鬧鈴就會振鈴。這個振鈴時間好比軟體時鐘的到期時間，振鈴這個動作好比軟體時鐘到期后要執行的函數，而鬧鈴時間更新好比硬體時鐘的更新。

實現軟體時鐘原理也比較簡單：每一次硬體時鐘中斷到達時，內核更新的 jiffies ，然後將其和軟體時鐘的到期時間進行比較。如果 jiffies 等於或者大於軟體時鐘的到期時間，內核就執行軟體時鐘指定的函數。

接下來的幾節會詳細介紹 Linux2.6.25 是怎麼實現軟體時鐘的。

3.1 相關數據結構

• struct timer_list ：軟體時鐘，記錄了軟體時鐘的到期時間以及到期后要執行的操作。具體的成員以及含義見表3-1。
• struct tvec_base ：用於組織、管理軟體時鐘的結構。在 SMP 系統中，每個 CPU 有一個。具體的成員以及含義參見表3-2。

註：一個 tick 表示的時間長度為兩次硬體時鐘中斷髮生時的時間間隔

表3-2 struct tvec_base 類型的成員

域名	類型	描述
lock	spinlock_t	用於同步操作
running_timer	struct timer_list *	正在處理的軟體時鐘
timer_jiffies	unsigned long	當前正在處理的軟體時鐘到期時間
tv1	struct tvec_root	保存了到期時間從 timer_jiffies 到 timer_jiffies + 之間（包括邊緣值）的所有軟體時鐘
tv2	struct tvec	保存了到期時間從 timer_jiffies + 到 timer_jiffies +之間（包括邊緣值）的 所有軟體時鐘
tv3	struct tvec	保存了到期時間從 timer_jiffies +到 timer_jiffies +之間（包括邊緣值）的所有軟體時鐘
tv4	struct tvec	保存了到期時間從 timer_jiffies +到 timer_jiffies +之間（包括邊緣值）的所有軟體時鐘
tv5	struct tvec	保存了到期時間從 timer_jiffies +到 timer_jiffies +之間（包括邊緣值）的所有軟體時鐘

其中 tv1 的類型為 struct tvec_root ，tv 2~ tv 5的類型為 struct tvec ，清單3-1顯示它們的定義

struct tvec {  	struct list_head vec[TVN_SIZE];  };    struct tvec_root {  	struct list_head vec[TVR_SIZE];  };  

可見它們實際上就是類型為 struct list_head 的數組，其中 TVN_SIZE 和 TVR_SIZE 在系統沒有配置宏 CONFIG_BASE_SMALL 時分別被定義為64和256。

3.2 數據結構之間的關係

從圖中可以清楚地看出：軟體時鐘（ struct timer_list ，在圖中由 timer 表示）以雙向鏈表（ struct list_head ）的形式，按照它們的到期時間保存相應的桶（ tv1~tv5 ）中。tv1 中保存了相對於 timer_jiffies 下256個 tick 時間內到期的所有軟體時鐘； tv2 中保存了相對於 timer_jiffies 下256*64個 tick 時間內到期的所有軟體時鐘； tv3 中保存了相對於 timer_jiffies 下256*64*64個 tick 時間內到期的所有軟體時鐘； tv4 中保存了相對於 timer_jiffies 下256*64*64*64個 tick 時間內到期的所有軟體時鐘； tv5 中保存了相對於 timer_jiffies 下256*64*64*64*64個 tick 時間內到期的所有軟體時鐘。具體的說，從靜態的角度看，假設 timer_jiffies 為0，那麼 tv1[0] 保存著當前到期（到期時間等於 timer_jiffies ）的軟體時鐘（需要馬上被處理）， tv1[1] 保存著下一個 tick 到達時，到期的所有軟體時鐘， tv1[n] （0<= n <=255）保存著下 n 個 tick 到達時，到期的所有軟體時鐘。而 tv2[0] 則保存著下256到511個 tick 之間到期所有軟體時鐘， tv2[1] 保存著下512到767個 tick 之間到期的所有軟體時鐘， tv2[n] （0<= n <=63）保存著下256*(n+1)到256*(n+2)-1個 tick 之間到達的所有軟體時鐘。 tv3~tv5 依次類推。

註：一個tick的長度指的是兩次硬體時鐘中斷髮生之間的時間間隔

從上面的說明中可以看出：軟體時鐘是按照其到期時間相對於當前正在處理的軟體時鐘的到期時間（ timer_jiffies 的數值）保存在 struct tvec_base 變數中的。而且這個到期時間的最大相對值（到期時間 - timer_jiffies ）為 0xffffffffUL （ tv5 最後一個元素能夠表示的相對到期時間的最大值）。

還需要注意的是軟體時鐘的處理是局部於 CPU 的，所以在 SMP 系統中每一個 CPU 都保存一個類型為 struct tvec_base 的變數，用來組織、管理本 CPU 的軟體時鐘。從圖中也可以看出 struct tvec_base 變數是 per-CPU 的（關於 per-CPU 的變數原理和使用參見參考資料）。

由於以後的講解經常要提到每個 CPU 相關的 struct tvec_base 變數，所以為了方便，稱保存軟體時鐘的 struct tvec_base 變數為該軟體時鐘的 base ，或稱 CPU 的 base 。

3.3 添加或刪除軟體時鐘

在了解了軟體時鐘的數據組織關係之後，現在來看一下如何添加以及刪除一個軟體時鐘。

3.3.1 添加軟體時鐘

在 Linux 內核中要添加一個軟體時鐘，首先必須分配 struct timer_list 類型的變數，然後調用函數 add_timer() 將該軟體時鐘添加到相應調用 add_timer 函數的 CPU 的 base 中。 Add_timer 是對函數 __mod_timer() 的一層包裝。函數 __mod_timer() 的代碼如清單3-2：

int __mod_timer(struct timer_list *timer, unsigned long expires)  {      struct tvec_base *base, *new_base;      unsigned long flags;      int ret = 0;      ……      base = lock_timer_base(timer, &flags);      if (timer_pending(timer)) {          detach_timer(timer, 0);          ret = 1;      }      new_base = __get_cpu_var(tvec_bases);        if (base != new_base) {          if (likely(base->running_timer != timer)) {              /* See the comment in lock_timer_base() */              timer_set_base(timer, NULL);              spin_unlock(&base->lock);              base = new_base;              spin_lock(&base->lock);              timer_set_base(timer, base);          }      }      timer->expires = expires;      internal_add_timer(base, timer);      spin_unlock_irqrestore(&base->lock, flags);      return ret;  }  

代碼解釋：

註：卸載軟體時鐘的意思是指將軟體時鐘從軟體時鐘所在 base 中刪除，以後所說的卸載軟體時鐘也都是這個意思

1. 取得軟體時鐘所在 base 上的同步鎖（ struct tvec_base 變數中的自旋鎖），並返回該軟體時鐘的 base ，保存在 base 變數中
2. 如果該軟體時鐘處在 pending 狀態（在 base 中，準備執行），則卸載該軟體時鐘
3. 取得本 CPU 上的 base 指針（類型為 struct tvec_base* ），保存在 new_base 中
4. 如果 base 和 new_base 不一樣，也就是說軟體時鐘發生了遷移（從一個 CPU 中移到了另一個 CPU 上），那麼如果該軟體時鐘的處理函數當前沒有在遷移之前的那個 CPU 上運行，則先將軟體時鐘的 base 設置為 NULL ，然後再將該軟體時鐘的 base 設置為 new_base 。否則，跳到5。
5. 設置軟體時鐘的到期時間
6. 調用 internal_add_timer 函數將軟體時鐘添加到軟體時鐘的 base 中（本 CPU 的 base ）
7. 釋放鎖

這裡有必要詳細說明一下軟體時鐘如何被添加到軟體時鐘的 base 中的（添加到本 CPU base 的 tv1~tv5 裡面），因為這是軟體時鐘處理的基礎。來看函數 internal_add_timer 函數的實現，如清單3-3

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) {          vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);      } else {          int i;          if (idx > 0xffffffffUL) {              idx = 0xffffffffUL;              expires = idx + base->timer_jiffies;          }          i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;          vec = base->tv5.vec + i;      }      list_add_tail(&timer->entry, vec);  }  

代碼解釋：

• 計算該軟體時鐘的到期時間和 timer_jiffies （當前正在處理的軟體時鐘的到期時間）的差值，作為索引保存到 idx 變數中。
• 判斷 idx 所在的區間，在
  • [0, ]或者( , 0)（該軟體時鐘已經到期），則將要添加到 tv1 中
  • [, ]，則將要添加到 tv2 中
  • [, ]，則將要添加到 tv3 中
  • [, ]，則將要添加到 tv4 中
  • [, )，則將要添加到 tv5 中，但實際上最大值為 0xffffffffUL
• 計算所要加入的具體位置（哪個鏈表中，即 tv1~tv5 的哪個子鏈表，參考圖3-1）
• 最後將其添加到相應的鏈表中

從這個函數可以得知，內核中是按照軟體時鐘到期時間的相對值（相對於 timer_jiffies 的值）將軟體時鐘添加到軟體時鐘所在的 base 中的。

3.3.2 刪除軟體時鐘

內核可調用 del_timer 函數刪除軟體時鐘， del_timer 的代碼如清單3-4

int del_timer(struct timer_list *timer)  {      struct tvec_base *base;      unsigned long flags;      int ret = 0;      ……      if (timer_pending(timer)) {          base = lock_timer_base(timer, &flags);          if (timer_pending(timer)) {              detach_timer(timer, 1);              ret = 1;          }          spin_unlock_irqrestore(&base->lock, flags);      }      return ret;  }  

代碼解釋：

1. 檢測該軟體時鐘是否處在 pending 狀態（在 base 中，準備運行），如果不是則直接函數返回
2. 如果處於 pending 狀態，則獲得鎖
3. 再次檢測軟體時鐘是否處於 pending 狀態（該軟體時鐘可能被卸載了），不是則釋放鎖然後函數返回
4. 如果還是 pending 狀態，則將其卸載，之後釋放鎖，函數返回

如果在 SMP 系統中，則需使用 del_timer_sync 函數來刪除軟體時鐘。在講解 del_timer_sync 函數之前，先來看下 try_to_del_timer_sync 函數的實現（該函數被 del_timer_sync 函數使用），其代碼如清單3-5

int try_to_del_timer_sync(struct timer_list *timer)  {      struct tvec_base *base;      unsigned long flags;      int ret = -1;      base = lock_timer_base(timer, &flags);      if (base->running_timer == timer)          goto out;      ret = 0;      if (timer_pending(timer)) {          detach_timer(timer, 1);          ret = 1;      }  out:      spin_unlock_irqrestore(&base->lock, flags);      return ret;  }  

該函數檢測當前運行的軟體時鐘是不是該軟體時鐘，如果是，則函數返回-1，表明目前不能刪除該軟體時鐘；如果不是檢測該軟體時鐘是否處於 pending 狀態，如果不是，則函數返回0，表明軟體時鐘已經被卸載，如果處於 pending 狀態再把軟體時鐘卸載，函數返回1，表明成功卸載該軟體時鐘。

接下來，再來看看函數 del_timer_sync 定義，如清單3-6

int del_timer_sync(struct timer_list *timer)  {      for (;;) {          int ret = try_to_del_timer_sync(timer);          if (ret >= 0)              return ret;          cpu_relax();      }  }  

del_timer_sync 函數無限循環試圖卸載該軟體時鐘，直到該軟體時鐘能夠被成功卸載。從其實現中可以看出：如果一個軟體時鐘的處理函數正在執行時，對其的卸載操作將會失敗。一直等到軟體時鐘的處理函數運行結束后，卸載操作才會成功。這樣避免了在 SMP 系統中一個 CPU 正在執行軟體時鐘的處理函數，而另一個 CPU 則要將該軟體時鐘卸載所引發的問題。

3.3 時鐘的軟中斷處理

軟體時鐘的處理是在時鐘的軟中斷中進行的。

3.3.1 軟中斷初始化

軟中斷的一個重要的處理時機是在每個硬體中斷處理完成後（參見 irq_exit 函數），且由2.4節的內容可知：在硬體時鐘中斷處理中，會喚醒時鐘的軟中斷，所以每次硬體時鐘中斷處理函數執行完成後都要進行時鐘的軟中斷處理。和時鐘相關的軟中斷是 TIMER_SOFTIRQ ，其處理函數為 run_timer_softirq ，該函數用來處理所有的軟體時鐘。這部分初始化代碼在函數 init_timers 中進行，如清單3-7

void __init init_timers(void)  {      ……      open_softirq(TIMER_SOFTIRQ, run_timer_softirq, NULL);  }  

3.3.2 處理過程

函數 run_timer_softirq 所作的工作就是找出所有到期的軟體時鐘，然後依次執行其處理函數。其代碼如清單3-8

static void run_timer_softirq(struct softirq_action *h)  {      struct tvec_base *base = __get_cpu_var(tvec_bases);        hrtimer_run_pending();      if (time_after_eq(jiffies, base->timer_jiffies))          __run_timers(base);  }  

函數首先獲得到本地 CPU 的 base 。然後檢測如果 jiffies

註： hrtimer_run_pending() 函數是高精度時鐘的處理。本文暫沒有涉及高精度時鐘相關的內容。

大於等於 timer_jiffies ，說明可能已經有軟體時鐘到期了，此

時就要進行軟體時鐘的處理，調用函數 __run_timers 進行處

理。如果 jiffies 小於 timer_jiffies ，表明沒有軟體時鐘到期，

則不用對軟體時鐘進行處理。函數返回。

接下來看一下函數 __run_timers 都作了些什麼，如清單3-9

static inline void __run_timers(struct tvec_base *base)  {      ……      spin_lock_irq(&base->lock);      while (time_after_eq(jiffies, base->timer_jiffies)) {          ……          int index = base->timer_jiffies & TVR_MASK;          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)) {              ……              timer = list_first_entry(head, struct timer_list,entry);              fn = timer->function;              data = timer->data;              ……              set_running_timer(base, timer);              detach_timer(timer, 1);              spin_unlock_irq(&base->lock);              {                  int preempt_count = preempt_count();                  fn(data);                  ……              }  			spin_lock_irq(&base->lock);          }      }      set_running_timer(base, NULL);      spin_unlock_irq(&base->lock);  }  

代碼解釋：

1. 獲得 base 的同步鎖
2. 如果 jiffies 大於等於 timer_jiffies （當前正要處理的軟體時鐘的到期時間，說明可能有軟體時鐘到期了），就一直運行3~7，否則跳轉至8
3. 計算得到 tv1 的索引，該索引指明當前到期的軟體時鐘所在 tv1 中的鏈表（結構參見3.2節），代碼：

int index = base->timer_jiffies & TVR_MASK;  

1. 調用 cascade 函數對軟體時鐘進行必要的調整（稍後會介紹調整的過程）
2. 使得 timer_jiffies 的數值增加1
3. 取出相應的軟體時鐘鏈表
4. 遍歷該鏈表，對每個元素進行如下操作

• 設置當前軟體時鐘為 base 中正在運行的軟體時鐘（即保存當前軟體時鐘到 base-> running_timer 成員中）
• 將當前軟體時鐘從鏈表中刪除，即卸載該軟體時鐘
• 釋放鎖，執行軟體時鐘處理程序
• 再次獲得鎖

1. 設置當前 base 中不存在正在運行的軟體時鐘
2. 釋放鎖

3.3.3 軟體時鐘調整過程

函數 cascade 用於調整軟體時鐘（這個調整過程是指：將馬上就要到期的軟體時鐘從其所在的鏈表中刪除，重新計算到期時間的相對值（到期時間 - timer_jiffies ），然後根據該值重新插入到 base 中）。注意到在軟體時鐘處理過程中，每次都是從 tv1 中取出一個鏈表進行處理，而不是從 tv2~tv5 中取，所以對軟體時鐘就要進行必要的調整。

在講解 cascade 函數之前，再從直觀上理解下為什麼需要進行調整。所有軟體時鐘都是按照其到期時間的相對值（相對於 timer_jiffies ）被調加到 base 中的。但是 timer_jiffies 的數值都會在處理中增加1（如3.3.2節所示），也就是說這個相對值會隨著處理髮生變化，當這個相對值小於等於256時，就要將軟體時鐘從 tv2~tv5 中轉移到 tv1 中（ tv1 中保存著下256個 tick 內到期的所有軟體時鐘）。

函數 cascade 的實現如清單3-10

static int cascade(struct tvec_base *base, struct tvec *tv, int index)  {      struct timer_list *timer, *tmp;      struct list_head tv_list;      list_replace_init(tv->vec + index, &tv_list);      list_for_each_entry_safe(timer, tmp, &tv_list, entry) {          ……          internal_add_timer(base, timer);      }      return index;  }  

該函數根據索引，取出相應的 tv （ tv2~tv5 ）中的鏈表，然後遍歷鏈表每一個元素。按照其到期時間重新將軟體時鐘加入到軟體時鐘的 base 中。該函數返回 tv 中被調整的鏈表索引值（參見圖3-1）。

清單3-9中調整軟體時鐘的代碼如下：

int index = base->timer_jiffies & TVR_MASK;  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));  

這部分代碼表明：如果 index 有0再到0時（ index 是對 timer_jiffies 取模），說明時間已經過了256個 tick ，這時要把 tv2 中軟體時鐘轉移到 tv1 中。如果 index 和第一個 cascade 函數的返回值都從0再到到0時，說明時間已經過了256*64個 tick ，這時要把 tv3 中軟體時鐘轉移到 tv1 或者 tv2 中。之後的調整過程依次類推。

3.4 自我激活

軟體時鐘可分為兩種類型：

• 僅僅激活一次
• 激活多次或者周期性激活

多次激活的實現機制就是要在軟體時鐘處理函數中重新設置軟體時鐘的到期時間為將來的一個時間，這個過程通過調用 mod_timer 函數來實現。該函數的實現如清單3-11

int mod_timer(struct timer_list *timer, unsigned long expires)  {      ……      if (timer->expires == expires && timer_pending(timer))          return 1;        return __mod_timer(timer, expires);  }  

從代碼中可以看出，該函數實際上調用 __mod_timer 函數（參見3.3.1節）來調整軟體時鐘的到期時間。

3.5 軟體時鐘的應用

軟體時鐘的處理是在處理軟中斷時觸發的，而軟中斷的處理又會緊接著硬體中斷處理結束而進行，並且系統會周期地產生時鐘中斷（硬體中斷），這樣，軟體時鐘的處理至少會在系統每一次時鐘中斷處理完成後觸發（如果軟體時鐘的到期時間大於系統當前的 jiffies ，表明時間未到期，則不會調用保存在軟體時鐘中的函數，但此時的確提供了處理軟體時鐘的時機）。從這點上看，軟體時鐘會有較快的相應——一旦時間到期，保存在軟體時鐘中的函數會將快地被調用（在時鐘軟中斷中被調用，參見3.3.2節）。所以內核中凡是需要隔一段時間間隔後作指定操作的過程都通過軟體時鐘完成。例如大部分設備驅動程序使用軟體時鐘探測異常條件、軟盤驅動程序利用軟體時鐘關閉有一段時間沒有被訪問軟盤的設備馬達、進程的定時睡眠（ schedule_timeout 函數）和網路超時重傳等等。

本節主要通過介紹進程的定時睡眠（ schedule_timeout 函數）和網路超時重傳來說明軟體時鐘的應用。

3.5.1 進程的定時睡眠

函數 schedule_timeout 的代碼如清單3-12

signed long __sched schedule_timeout(signed long timeout)  {      struct timer_list timer;      unsigned long expire;        ……      expire = timeout + jiffies;        setup_timer(&timer, process_timeout, (unsigned long)current);      __mod_timer(&timer, expire);      schedule();      del_singleshot_timer_sync(&timer);        timeout = expire - jiffies;     out:      return timeout < 0 ? 0 : timeout;  }  

函數 schedule_timeout 定義了一個軟體時鐘變數 timer ，在計算到期時間后初始化這個軟體時鐘：設置軟體時鐘當時間到期時的處理函數為 process_timeout ，參數為當前進程描述符，設置軟體時鐘的到期時間為 expire 。之後調用 schedule() 函數。此時當前進程睡眠，交出執行權，內核調用其它進程運行。但內核在每一個時鐘中斷處理結束后都要檢測這個軟體時鐘是否到期。如果到期，將調用 process_timeout 函數，參數為睡眠的那個進程描述符。 process_timeout 函數的代碼如清單3-13。

static void process_timeout(unsigned long __data)  {      wake_up_process((struct task_struct *)__data);  }  

函數 process_timeout 直接調用 wake_up_process 將進程喚醒。當內核重新調用該進程執行時，該進程繼續執行 schedule_timeout 函數，執行流則從 schedule 函數中返回，之後調用 del_singleshot_timer_sync 函數將軟體時鐘卸載，然後函數 schedule_timeout 結束。函數 del_singleshot_timer_sync 是實際上就是函數 del_timer_sync （參見3.3.2節），如清單3-14

#define del_singleshot_timer_sync(t) del_timer_sync(t)  

以上就是進程定時睡眠的實現過程。接下來介紹的是軟體時鐘在網路超時重傳上的應用。

3.5.2 網路超時重傳

對於 TCP 協議而言，如果某次發送完數據包后，並超過一定的時間間隔還沒有收到這次發送數據包的 ACK 時， TCP 協議規定要重新發送這個數據包。

在 Linux2.6.25 的內核中，這種數據的重新發送使用軟體時鐘來完成。這個軟體時鐘保存在面向連接的套接字（對應內核中 inet_connection_sock 結構）中。對這個域的初始在函數 tcp_init_xmit_timers 中，如清單3-15

void tcp_init_xmit_timers(struct sock *sk)  {      inet_csk_init_xmit_timers(sk,                                      &tcp_write_timer, &tcp_delack_timer,                                     &tcp_keepalive_timer);  }    void inet_csk_init_xmit_timers(struct sock *sk,                                     void (*retransmit_handler)(unsigned long),                                     void (*delack_handler)(unsigned long),                                     void (*keepalive_handler)(unsigned long))  {      struct inet_connection_sock *icsk = inet_csk(sk);        setup_timer(&icsk->icsk_retransmit_timer, retransmit_handler,                      (unsigned long)sk);      ……  }    static inline void setup_timer(struct timer_list * timer,                                      void (*function)(unsigned long),                                      unsigned long data)  {      timer->function = function;      timer->data = data;      init_timer(timer);  }  

在函數 inet_csk_init_xmit_timers 中，變數 icsk 就是前面提到的面向連接的套接字，其成員 icsk_retransmit_timer 則為實現超時重傳的軟體時鐘。該函數調用 setup_timer 函數將函數 tcp_write_timer （參考函數 tcp_init_xmit_timers ）設置為軟體時鐘 icsk->icsk_retransmit_timer 當時間到期后的處理函數。初始化的時候並沒有設置該軟體時鐘的到期時間。

在 TCP 協議具體的一次數據包發送中，函數 tcp_write_xmit 用來將數據包從 TCP 層發送到網路層，如清單3-16。

static int tcp_write_xmit(struct sock *sk, unsigned int mss_now, int nonagle)  {      struct tcp_sock *tp = tcp_sk(sk);      struct sk_buff *skb;      ……      if (unlikely(tcp_transmit_skb(sk, skb, 1, GFP_ATOMIC)))          break;      tcp_event_new_data_sent(sk, skb);      ……      return !tp->packets_out && tcp_send_head(sk);  }  

注意該函數中加粗的函數，其中 tcp_transmit_skb 函數是真正將數據包由 TCP 層發送到網路層中的函數。數據發送后，將調用函數 tcp_event_new_data_sent ，而後者又會調用函數 inet_csk_reset_xmit_timer 來設置超時軟體時鐘的到期時間。

當函數 tcp_event_new_data_sent 結束之後，處理超時的軟體時鐘已經設置好了。內核會在每一次時鐘中斷處理完成後檢測該軟體時鐘是否到期。如果網路真的超時，沒有 ACK 返回，那麼當該軟體時鐘到期后內核就會執行函數 tcp_write_timer 。函數 tcp_write_timer 將進行數據包的重新發送，並重新設置超時重傳軟體時鐘的到期時間。

4 總結

本文介紹了 Linux 內核的時鐘處理機制。首先簡單介紹了系統的硬體計時器，然後重點介紹了硬體時鐘的處理過程和軟體時鐘的處理過程以及軟體時鐘的應用。（責任編輯：A6）