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-1 時鐘源鏈表和時鐘事件鏈表

　　2.2 通知鏈技術（ notification chain ）

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

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

　　2.2.1 數據結構：

　　通知鏈有四種類型,

　　原子通知鏈（ Atomic notifier chains ）：通知鏈元素的回調函數（當事件發生時要執行的函數）只能在中斷上下文中運行,不允許阻塞

　　可阻塞通知鏈（ Blocking notifier chains ）：通知鏈元素的回調函數在進程上下文中運行,允許阻塞

　　原始通知鏈（ Raw notifier chains ）：對通知鏈元素的回調函數沒有任何限制,所有鎖和保護機制都由調用者維護

　　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 運作機制

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

　　被通知者：對某一事件感興趣一方.定義了當事件發生時,相應的處理函數,即回調函數.但需要事先將其註冊到通知鏈中（被通知者註冊的動作就是在通知鏈中增加一項）.

　　通知者：事件的通知者.當檢測到某事件,或者本身產生事件時,通知所有對該事件感興趣的一方事件發生.他定義了一個通知鏈,其中保存了每一個被通知者對事件的處理函數（回調函數）.通知這個過程實際上就是遍歷通知鏈中的每一項,然後調用相應的事件處理函數.

　　包括以下過程：

　　通知者定義通知鏈

　　被通知者向通知鏈中註冊回調函數

　　當事件發生時,通知者發出通知（執行通知鏈中所有元素的回調函數）

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

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

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

　　更多關於通知鏈的內容,參見參考文獻.

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

　　2.3 時鐘初始化

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

　　tick_init()

　　init_timers()

　　hrtimers_init()

　　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（省略了部分和

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

　　清單2-1 init_timers 函數

　　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

　　清單2-2 time_init 函數

　　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

　　清單2-3 hpet_time_init 函數

　　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 的實現）：

　　初始化時鐘源信息（ struct clocksource 類型的變數）,並將其添加到時鐘源鏈表中,即 clocksource_list 鏈表（參見圖2-1）.

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

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

　　2.4 硬體時鐘處理過程

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

　　清單2-4 變數irq0定義

　　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

　　清單2-5 timer_event_interrupt 函數

　　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

　　清單2-6 tick_notify 函數

　　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 的處理過程分成了以下兩個部分：

　　全局處理：整個系統中的信息處理

　　局部處理：局部於本地 CPU 的處理

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

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

　　更新 jiffies_64

　　更新 xtimer 和當前時鐘源信息等

　　根據 tick 計算 avenrun 負載

　　局部處理（每個 CPU 都要運行）：

　　根據當前在用戶態還是核心態,統計當前進程的時間：用戶態時間還是核心態時間

　　喚醒 TIMER_SOFTIRQ 軟中斷

　　喚醒 RCU 軟中斷

　　調用 scheduler_tick （更新進程時間片等等操作,更多內容參見參考文獻）

　　profile_tick 函數調用

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

　　3 軟體時鐘處理

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

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

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

　　3.1 相關數據結構

　　struct timer_list ：軟體時鐘,記錄了軟體時鐘的到期時間以及到期后要執行的操作.具體的成員以及含義見表3-1.

　　struct tvec_base ：用於組織、管理軟體時鐘的結構.在 SMP 系統中,每個 CPU 有一個.具體的成員以及含義參見表3-2.

　　表3-1 struct timer_list 主要成員

　　域名 類型 描述

　　entry struct list_head 所在的鏈表

　　expires unsigned long 到期時間,以 tick 為單位

　　function void (*)(unsigned long) 回調函數,到期后執行的操作

　　data unsigned long 回調函數的參數

　　base struct tvec_base * 記錄該軟體時鐘所在的 struct tvec_base 變數

　　註：一個 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顯示它們的定義

　　清單3-1 struct tvec_root 和 struct tvec 的定義

　　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 數據結構之間的關係

　　圖3-1顯示了以上數據結構之間的關係：

　　從圖中可以清楚地看出：軟體時鐘（ 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 .

Tags: linux system 系統