Linux 時(shí)鐘管理

Linux 中的定時(shí)器

在 Linux 內核中主要有兩種類(lèi)型的定時(shí)器。一類(lèi)稱(chēng)為 timeout 類(lèi)型，另一類(lèi)稱(chēng)為 timer 類(lèi)型。timeout 類(lèi)型的定時(shí)器通常用于檢測各種錯誤條件，例如用于檢測網(wǎng)卡收發(fā)數據包是否會(huì )超時(shí)的定時(shí)器，IO 設備的讀寫(xiě)是否會(huì )超時(shí)的定時(shí)器等等。通常情況下這些錯誤很少發(fā)生，因此，使用 timeout 類(lèi)型的定時(shí)器一般在超時(shí)之前就會(huì )被移除，從而很少產(chǎn)生真正的函數調用和系統開(kāi)銷(xiāo)?？偟膩?lái)說(shuō)，使用 timeout 類(lèi)型的定時(shí)器產(chǎn)生的系統開(kāi)銷(xiāo)很小，它是下文提及的 timer wheel 通常使用的環(huán)境。此外，在使用 timeout 類(lèi)型定時(shí)器的地方往往并不關(guān)心超時(shí)處理，因此超時(shí)精確與否，早 0.01 秒或者晚 0.01 秒并不十分重要，這在下文論述 deferrable timers 時(shí)會(huì )進(jìn)一步介紹。timer 類(lèi)型的定時(shí)器與 timeout 類(lèi)型的定時(shí)器正相反，使用 timer 類(lèi)型的定時(shí)器往往要求在精確的時(shí)鐘條件下完成特定的事件，通常是周期性的并且依賴(lài)超時(shí)機制進(jìn)行處理。例如設備驅動(dòng)通常會(huì )定時(shí)讀寫(xiě)設備來(lái)進(jìn)行數據交互。如何高效的管理 timer 類(lèi)型的定時(shí)器對提高系統的處理效率十分重要，下文在介紹 hrtimer 時(shí)會(huì )有更加詳細的論述。

內核需要進(jìn)行時(shí)鐘管理，離不開(kāi)底層的硬件支持。在早期是通過(guò) 8253 芯片提供的 PIT（Programmable Interval Timer）來(lái)提供時(shí)鐘，但是 PIT 的頻率很低，只能提供最高 1ms 的時(shí)鐘精度，由于 PIT 觸發(fā)的中斷速度太慢，會(huì )導致很大的時(shí)延，對于像音視頻這類(lèi)對時(shí)間精度要求更高的應用并不足夠，會(huì )極大的影響用戶(hù)體驗。隨著(zhù)硬件平臺的不斷發(fā)展變化，陸續出現了 TSC（Time Stamp Counter），HPET（High Precision Event Timer），ACPI PM Timer（ACPI Power Management Timer），CPU Local APIC Timer 等精度更高的時(shí)鐘。這些時(shí)鐘陸續被 Linux 的時(shí)鐘子系統所采納，從而不斷的提高 Linux 時(shí)鐘子系統的性能和靈活性。這些不同的時(shí)鐘會(huì )在下文不同的章節中分別進(jìn)行介紹。

Timer wheel

在 Linux 2.6.16 之前，內核一直使用一種稱(chēng)為 timer wheel 的機制來(lái)管理時(shí)鐘。這就是熟知的 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 的邏輯結構

清單 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)))  (!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)) { void (*fn)(unsigned long); unsigned long data; timer = list_first_entry(head, struct timer_list,entry); fn = timer->function; data = timer->data; . . . . fn(data); . . . . } 

hrtimer (High-resolution Timer)

hrtimer 首先要實(shí)現的功能就是要克服 timer wheel 的缺點(diǎn)：低精度以及與內核其他模塊的高耦合性。在正式介紹 hrtimer 之前，有必要先介紹幾個(gè)常用的基本概念：

時(shí)鐘源設備（clock-source device）

系統中可以提供一定精度的計時(shí)設備都可以作為時(shí)鐘源設備。如 TSC，HPET，ACPI PM-Timer，PIT 等。但是不同的時(shí)鐘源提供的時(shí)鐘精度是不一樣的。像 TSC，HPET 等時(shí)鐘源既支持高精度模式（high-resolution mode）也支持低精度模式（low-resolution mode），而 PIT 只能支持低精度模式。此外，時(shí)鐘源的計時(shí)都是單調遞增的（monotonically），如果時(shí)鐘源的計時(shí)出現翻轉（即返回到 0 值），很容易造成計時(shí)錯誤， 內核的一個(gè) patch（commit id: ff69f2）就是處理這類(lèi)問(wèn)題的一個(gè)很好示例。時(shí)鐘源作為系統時(shí)鐘的提供者，在可靠并且可用的前提下精度越高越好。在 Linux 中不同的時(shí)鐘源有不同的 rating，具有更高 rating 的時(shí)鐘源會(huì )優(yōu)先被系統使用。如圖 2 所示：

表 1. 時(shí)鐘源中 rating 的定義

時(shí)鐘事件設備（clock-event device）

系統中可以觸發(fā) one-shot（單次）或者周期性中斷的設備都可以作為時(shí)鐘事件設備。如 HPET，CPU Local APIC Timer 等。HPET 比較特別，它既可以做時(shí)鐘源設備也可以做時(shí)鐘事件設備。時(shí)鐘事件設備的類(lèi)型分為全局和 per-CPU 兩種類(lèi)型。全局的時(shí)鐘事件設備雖然附屬于某一個(gè)特定的 CPU 上，但是完成的是系統相關(guān)的工作，例如完成系統的 tick 更新；per-CPU 的時(shí)鐘事件設備主要完成 Local CPU 上的一些功能，例如對在當前 CPU 上運行進(jìn)程的時(shí)間統計，profile，設置 Local CPU 上的下一次事件中斷等。和時(shí)鐘源設備的實(shí)現類(lèi)似，時(shí)鐘事件設備也通過(guò) rating 來(lái)區分優(yōu)先級關(guān)系。

tick device

Tick device 用來(lái)處理周期性的 tick event。Tick device 其實(shí)是時(shí)鐘事件設備的一個(gè) wrapper，因此 tick device 也有 one-shot 和周期性這兩種中斷觸發(fā)模式。每注冊一個(gè)時(shí)鐘事件設備，這個(gè)設備會(huì )自動(dòng)被注冊為一個(gè) tick device。全局的 tick device 用來(lái)更新諸如 jiffies 這樣的全局信息，per-CPU 的 tick device 則用來(lái)更新每個(gè) CPU 相關(guān)的特定信息。

broadcast

Timekeeping GTOD (Generic Time-of-Day)

Timekeeping（可以理解為時(shí)間測量或者計時(shí)）是內核時(shí)間管理的一個(gè)核心組成部分。沒(méi)有 Timekeeping，就無(wú)法更新系統時(shí)間，維持系統“心跳”。GTOD 是一個(gè)通用的框架，用來(lái)實(shí)現諸如設置系統時(shí)間 gettimeofday 或者修改系統時(shí)間 settimeofday 等工作。為了實(shí)現以上功能，Linux 實(shí)現了多種與時(shí)間相關(guān)但用于不同目的的數據結構。

struct timespec { __kernel_time_t    tv_sec;               /* seconds */ long                tv_nsec;               /* nanoseconds */ }; 

timespec 精度是納秒。它用來(lái)保存從 00:00:00 GMT, 1 January 1970 開(kāi)始經(jīng)過(guò)的時(shí)間。內核使用全局變量 xtime 來(lái)記錄這一信息，這就是通常所說(shuō)的“Wall Time”或者“Real Time”。與此對應的是“System Time”。System Time 是一個(gè)單調遞增的時(shí)間，每次系統啟動(dòng)時(shí)從 0 開(kāi)始計時(shí)。

struct timeval { __kernel_time_t          tv_sec;          /* seconds */ __kernel_suseconds_t    tv_usec;         /* microseconds */ }; 

timeval 精度是微秒。timeval 主要用來(lái)指定一段時(shí)間間隔。

union ktime { s64     tv64; #if BITS_PER_LONG != 64  !defined(CONFIG_KTIME_SCALAR) struct { # ifdef __BIG_ENDIAN s32     sec, nsec; # else s32     nsec, sec; # endif } tv; #endif }; 

ktime_t 是 hrtimer 主要使用的時(shí)間結構。無(wú)論使用哪種體系結構，ktime_t 始終保持 64bit 的精度，并且考慮了大小端的影響。

typedef u64 cycle_t; 

cycle_t 是從時(shí)鐘源設備中讀取的時(shí)鐘類(lèi)型。

為了管理這些不同的時(shí)間結構，Linux 實(shí)現了一系列輔助函數來(lái)完成相互間的轉換。

ktime_to_timespec，ktime_to_timeval，ktime_to_ns/ktime_to_us，反過(guò)來(lái)有諸如 ns_to_ktime 等類(lèi)似的函數。

timeval_to_ns，timespec_to_ns，反過(guò)來(lái)有諸如 ns_to_timeval 等類(lèi)似的函數。

timeval_to_jiffies，timespec_to_jiffies，msecs_to_jiffies, usecs_to_jiffies, clock_t_to_jiffies 反過(guò)來(lái)有諸如 ns_to_timeval 等類(lèi)似的函數。

clocksource_cyc2ns / cyclecounter_cyc2ns

有了以上的介紹，通過(guò)圖 3 可以更加清晰的看到這幾者之間的關(guān)聯(lián)。

圖 2. 內核時(shí)鐘子系統的結構關(guān)系

時(shí)鐘源設備和時(shí)鐘事件設備的引入，將原本放在各個(gè)體系結構中重復實(shí)現的冗余代碼封裝到各自的抽象層中，這樣做不但消除了原來(lái) timer wheel 與內核其他模塊的緊耦合性，更重要的是系統可以在運行狀態(tài)動(dòng)態(tài)更換時(shí)鐘源設備和時(shí)鐘事件設備而不影響系統正常使用，譬如當 CPU 由于睡眠要關(guān)閉當前使用的時(shí)鐘源設備或者時(shí)鐘事件設備時(shí)系統可以平滑的切換到其他仍處于工作狀態(tài)的設備上。Timekeeping/GTOD 在使用時(shí)鐘源設備的基礎上也采用類(lèi)似的封裝實(shí)現了體系結構的無(wú)關(guān)性和通用性。hrtimer 則可以通過(guò) timekeeping 提供的接口完成定時(shí)器的更新，通過(guò)時(shí)鐘事件設備提供的事件機制，完成對 timer 的管理。在圖 3 中還有一個(gè)重要的模塊就是 tick device 的抽象，尤其是 dynamic tick。Dynamic tick 的出現是為了能在系統空閑時(shí)通過(guò)停止 tick 的運行以達到降低 CPU 功耗的目的。使用 dynamic tick 的系統，只有在有實(shí)際工作時(shí)才會(huì )產(chǎn)生 tick，否則 tick 是處于停止狀態(tài)。下文會(huì )有專(zhuān)門(mén)的章節進(jìn)行論述。

hrtimer 的實(shí)現機制

hrtimer 是建立在 per-CPU 時(shí)鐘事件設備上的，對于一個(gè) SMP 系統，如果只有全局的時(shí)鐘事件設備，hrtimer 無(wú)法工作。因為如果沒(méi)有 per-CPU 時(shí)鐘事件設備，時(shí)鐘中斷發(fā)生時(shí)系統必須產(chǎn)生必要的 IPI 中斷來(lái)通知其他 CPU 完成相應的工作，而過(guò)多的 IPI 中斷會(huì )帶來(lái)很大的系統開(kāi)銷(xiāo)，這樣會(huì )令使用 hrtimer 的代價(jià)太大，不如不用。為了支持 hrtimer，內核需要配置 CONFIG_HIGH_RES_TIMERS=y。hrtimer 有兩種工作模式：低精度模式（low-resolution mode）與高精度模式（high-resolution mode）。雖然 hrtimer 子系統是為高精度的 timer 準備的，但是系統可能在運行過(guò)程中動(dòng)態(tài)切換到不同精度的時(shí)鐘源設備，因此，hrtimer 必須能夠在低精度模式與高精度模式下自由切換。由于低精度模式是建立在高精度模式之上的，因此即便系統只支持低精度模式，部分支持高精度模式的代碼仍然會(huì )編譯到內核當中。

在低精度模式下，hrtimer 的核心處理函數是 hrtimer_run_queues，每一次 tick 中斷都要執行一次。如清單 3 所示。這個(gè)函數的調用流程為：

update_process_times run_local_timers hrtimer_run_queuesraise_softirq(TIMER_SOFTIRQ) 

void hrtimer_run_queues(void) { struct rb_node *node; struct hrtimer_cpu_base *cpu_base = __get_cpu_var(hrtimer_bases); struct hrtimer_clock_base *base; int index, gettime = 1; if (hrtimer_hres_active()) return; for (index = 0; index  HRTIMER_MAX_CLOCK_BASES; index++) { base = cpu_base->clock_base[index]; if (!base->first) continue; if (gettime) { hrtimer_get_softirq_time(cpu_base); gettime = 0; } raw_spin_lock(cpu_base->lock); while ((node = base->first)) { struct hrtimer *timer; timer = rb_entry(node, struct hrtimer, node); if (base->softirq_time.tv64 = hrtimer_get_expires_tv64(timer)) break; __run_hrtimer(timer, base->softirq_time); } raw_spin_unlock(cpu_base->lock); } } 

hrtimer_bases 是實(shí)現 hrtimer 的核心數據結構，通過(guò) hrtimer_bases，hrtimer 可以管理掛在每一個(gè) CPU 上的所有 timer。每個(gè) CPU 上的 timer list 不再使用 timer wheel 中多級鏈表的實(shí)現方式，而是采用了紅黑樹(shù)（Red-Black Tree）來(lái)進(jìn)行管理。hrtimer_bases 的定義如清單 4 所示：

清單 4. hrtimer_bases 的定義

DEFINE_PER_CPU(struct hrtimer_cpu_base, hrtimer_bases) = { .clock_base = { { .index = CLOCK_REALTIME, .get_time = ktime_get_real, .resolution = KTIME_LOW_RES, }, { .index = CLOCK_MONOTONIC, .get_time = ktime_get, .resolution = KTIME_LOW_RES, }, } }; 

圖 4 展示了 hrtimer 如何通過(guò) hrtimer_bases 來(lái)管理 timer。

圖 3. hrtimer 的時(shí)鐘管理

每個(gè) hrtimer_bases 都包含兩個(gè) clock_base，一個(gè)是 CLOCK_REALTIME 類(lèi)型的，另一個(gè)是 CLOCK_MONOTONIC 類(lèi)型的。hrtimer 可以選擇其中之一來(lái)設置 timer 的 expire time, 可以是實(shí)際的時(shí)間 , 也可以是相對系統運行的時(shí)間。

在 hrtimer_run_queues 的處理中，首先要通過(guò) hrtimer_bases 找到正在執行當前中斷的 CPU 相關(guān)聯(lián)的 clock_base，然后逐個(gè)檢查每個(gè) clock_base 上掛的 timer 是否超時(shí)。由于 timer 在添加到 clock_base 上時(shí)使用了紅黑樹(shù)，最早超時(shí)的 timer 被放到樹(shù)的最左側，因此尋找超時(shí) timer 的過(guò)程非常迅速，找到的所有超時(shí) timer 會(huì )被逐一處理。超時(shí)的 timer 根據其類(lèi)型分為 softIRQ / per-CPU / unlocked 幾種。如果一個(gè) timer 是 softIRQ 類(lèi)型的，這個(gè)超時(shí)的 timer 需要被轉移到 hrtimer_bases 的 cb_pending 的 list 上，待 IRQ0 的軟中斷被激活后，通過(guò) run_hrtimer_pending 執行，另外兩類(lèi)則必須在 hardIRQ 中通過(guò) __run_hrtimer 直接執行。不過(guò)在較新的 kernel（> 2.6.29）中，cb_pending 被取消，這樣所有的超時(shí) timers 都必須在 hardIRQ 的 context 中執行。這樣修改的目的，一是為了簡(jiǎn)化代碼邏輯，二是為了減少 2 次 context 的切換：一次從 hardIRQ 到 softIRQ，另一次從 softIRQ 到被超時(shí) timer 喚醒的進(jìn)程。

在 update_process_times 中，除了處理處于低精度模式的 hrtimer 外，還要喚醒 IRQ0 的 softIRQ（TIMER_SOFTIRQ（run_timer_softirq））以便執行 timer wheel 的代碼。由于 hrtimer 子系統的加入，在 IRQ0 的 softIRQ 中，還需要通過(guò) hrtimer_run_pending 檢查是否可以將 hrtimer 切換到高精度模式，如清單 5 所示：

清單 5. hrtimer 進(jìn)行精度切換的處理函數

void hrtimer_run_pending(void) { if (hrtimer_hres_active()) return; /* * This _is_ ugly: We have to check in the softirq context, * whether we can switch to highres and / or nohz mode. The * clocksource switch happens in the timer interrupt with * xtime_lock held. Notification from there only sets the * check bit in the tick_oneshot code, otherwise we might * deadlock vs. xtime_lock. */ if (tick_check_oneshot_change(!hrtimer_is_hres_enabled())) hrtimer_switch_to_hres(); } 

正如這段代碼的作者注釋中所提到的，每一次觸發(fā) IRQ0 的 softIRQ 都需要檢查一次是否可以將 hrtimer 切換到高精度，顯然是十分低效的，希望將來(lái)有更好的方法不用每次都進(jìn)行檢查。

如果可以將 hrtimer 切換到高精度模式，則調用 hrtimer_switch_to_hres 函數進(jìn)行切換。如清單 6 所示：

清單 6. hrtimer 切換到高精度模式的核心函數

/* * Switch to high resolution mode */ static int hrtimer_switch_to_hres(void) { int cpu = smp_processor_id(); struct hrtimer_cpu_base *base = per_cpu(hrtimer_bases, cpu); unsigned long flags; if (base->hres_active) return 1; local_irq_save(flags); if (tick_init_highres()) { local_irq_restore(flags); printk(KERN_WARNING Could not switch to high resolution mode on CPU %dn, cpu); return 0; } base->hres_active = 1; base->clock_base[CLOCK_REALTIME].resolution = KTIME_HIGH_RES; base->clock_base[CLOCK_MONOTONIC].resolution = KTIME_HIGH_RES; tick_setup_sched_timer(); /* Retrigger the interrupt to get things going */ retrigger_next_event(NULL); local_irq_restore(flags); return 1; } 

在這個(gè)函數中，首先使用 tick_init_highres 更新與原來(lái)的 tick device 綁定的時(shí)鐘事件設備的 event handler，例如將在低精度模式下的工作函數 tick_handle_periodic / tick_handle_periodic_broadcast 換成 hrtimer_interrupt（它是 hrtimer 在高精度模式下的 timer 中斷處理函數），同時(shí)將 tick device 的觸發(fā)模式變?yōu)?one-shot，即單次觸發(fā)模式，這是使用 dynamic tick 或者 hrtimer 時(shí) tick device 的工作模式。由于 dynamic tick 可以隨時(shí)停止和開(kāi)始，以不規律的速度產(chǎn)生 tick，因此支持 one-shot 模式的時(shí)鐘事件設備是必須的；對于 hrtimer，由于 hrtimer 采用事件機制驅動(dòng) timer 前進(jìn)，因此使用 one-shot 的觸發(fā)模式也是順理成章的。不過(guò)這樣一來(lái)，原本 tick device 每次執行中斷時(shí)需要完成的周期性任務(wù)如更新 jiffies / wall time (do_timer) 以及更新 process 的使用時(shí)間（update_process_times）等工作在切換到高精度模式之后就沒(méi)有了，因此在執行完 tick_init_highres 之后緊接著(zhù)會(huì )調用 tick_setup_sched_timer 函數來(lái)完成這部分設置工作，如清單 7 所示：

清單 7. hrtimer 高精度模式下模擬周期運行的 tick device 的簡(jiǎn)化實(shí)現

void tick_setup_sched_timer(void) { struct tick_sched *ts = __get_cpu_var(tick_cpu_sched); ktime_t now = ktime_get(); u64 offset; /* * Emulate tick processing via per-CPU hrtimers: */ hrtimer_init(ts->sched_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS); ts->sched_timer.function = tick_sched_timer; . . . . for (;;) { hrtimer_forward(ts->sched_timer, now, tick_period); hrtimer_start_expires(ts->sched_timer, HRTIMER_MODE_ABS_PINNED); /* Check, if the timer was already in the past */ if (hrtimer_active(ts->sched_timer)) break; now = ktime_get(); } . . . . } 

這個(gè)函數使用 tick_cpu_sched 這個(gè) per-CPU 變量來(lái)模擬原來(lái) tick device 的功能。tick_cpu_sched 本身綁定了一個(gè) hrtimer，這個(gè) hrtimer 的超時(shí)值為下一個(gè) tick，回調函數為 tick_sched_timer。因此，每過(guò)一個(gè) tick，tick_sched_timer 就會(huì )被調用一次，在這個(gè)回調函數中首先完成原來(lái) tick device 的工作，然后設置下一次的超時(shí)值為再下一個(gè) tick，從而達到了模擬周期運行的 tick device 的功能。如果所有的 CPU 在同一時(shí)間點(diǎn)被喚醒，并發(fā)執行 tick 時(shí)可能會(huì )出現 lock 競爭以及 cache-line 沖突，為此 Linux 內核做了特別處理：如果假設 CPU 的個(gè)數為 N，則所有的 CPU 都在 tick_period 前 1/2 的時(shí)間內執行 tick 工作，并且每個(gè) CPU 的執行間隔是 tick_period / (2N)，見(jiàn)清單 8 所示：

清單 8. hrtimer 在高精度模式下 tick 執行周期的設置

void tick_setup_sched_timer(void) { . . . . /* Get the next period (per cpu) */ hrtimer_set_expires(ts->sched_timer, tick_init_jiffy_update()); offset = ktime_to_ns(tick_period) >> 1; do_div(offset, num_possible_cpus()); offset *= smp_processor_id(); hrtimer_add_expires_ns(ts->sched_timer, offset); . . . . } 

回到 hrtimer_switch_to_hres 函數中，在一切準備就緒后，調用 retrigger_next_event 激活下一次的 timer 就可以開(kāi)始正常的運作了。

隨著(zhù) hrtimer 子系統的發(fā)展，一些問(wèn)題也逐漸暴露了出來(lái)。一個(gè)比較典型的問(wèn)題就是 CPU 的功耗問(wèn)題?，F代 CPU 都實(shí)現了節能的特性，在沒(méi)有工作時(shí) CPU 會(huì )主動(dòng)降低頻率，關(guān)閉 CPU 內部一些非關(guān)鍵模塊以達到節能的目的。由于 hrtimer 的精度很高，觸發(fā)中斷的頻率也會(huì )很高，頻繁的中斷會(huì )極大的影響 CPU 的節能。在這方面 hrtimer 一直在不斷的進(jìn)行調整。以下幾個(gè)例子都是針對這一問(wèn)題所做的改進(jìn)。

schedule_hrtimeout 函數

/** * schedule_hrtimeout - sleep until timeout * @expires:    timeout value (ktime_t) * @mode:       timer mode, HRTIMER_MODE_ABS or HRTIMER_MODE_REL */ int __sched schedule_hrtimeout(ktime_t *expires, const enum hrtimer_mode mode) 

schedule_hrtimeout 用來(lái)產(chǎn)生一個(gè)高精度的調度超時(shí)，以 ns 為單位。這樣可以更加細粒度的使用內核的調度器。在 Arjan van de Ven 的最初實(shí)現中，這個(gè)函數有一個(gè)很大的問(wèn)題：由于其粒度很細，所以可能會(huì )更加頻繁的喚醒內核，導致消耗更多的能源。為了實(shí)現既能節省能源，又能確保精確的調度超時(shí)，Arjan van de Ven 的辦法是將一個(gè)超時(shí)點(diǎn)變成一個(gè)超時(shí)范圍。設置 hrtimer A 的超時(shí)值有一個(gè)上限，稱(chēng)為 hard expire，在 hard expire 這個(gè)時(shí)間點(diǎn)上設置 hrtimer A 的超時(shí)中斷；同時(shí)設置 hrtimer A 的超時(shí)值有一個(gè)下限，稱(chēng)為 soft expire。在 soft expire 到 hard expire 之間如果有一個(gè) hrtimer B 的中斷被觸發(fā)，在 hrtimer B 的中斷處理函數中，內核會(huì )檢查是否有其他 hrtimer 的 soft expire 超時(shí)了，譬如 hrtimer A 的 soft expire 超時(shí)了，即使 hrtimer A 的 hard expire 沒(méi)有到，也可以順帶被處理。換言之，將原來(lái)必須在 hard expire 超時(shí)才能執行的一個(gè)點(diǎn)變成一個(gè)范圍后，可以盡量把 hrtimer 中斷放在一起處理，這樣 CPU 被重復喚醒的幾率會(huì )變小，從而達到節能的效果，同時(shí)這個(gè) hrtimer 也可以保證其執行精度。

Deferrable timers round jiffies

在內核中使用的某些 legacy timer 對于精確的超時(shí)值并不敏感，早一點(diǎn)或者晚一點(diǎn)執行并不會(huì )產(chǎn)生多大的影響，因此，如果可以把這些對時(shí)間不敏感同時(shí)超時(shí)時(shí)間又比較接近的 timer 收集在一起執行，可以進(jìn)一步減少 CPU 被喚醒的次數，從而達到節能的目地。這正是引入 Deferrable timers 的目地。如果一個(gè) timer 可以被短暫延時(shí)，那么可以通過(guò)調用 init_timer_deferrable 設置 defer 標記，從而在執行時(shí)靈活選擇處理方式。不過(guò)，如果這些 timers 都被延時(shí)到同一個(gè)時(shí)間點(diǎn)上也不是最優(yōu)的選擇，這樣同樣會(huì )產(chǎn)生 lock 競爭以及 cache-line 的問(wèn)題。因此，即便將 defer timers 收集到一起，彼此之間也必須稍稍錯開(kāi)一些以防止上述問(wèn)題。這正是引入 round_jiffies 函數的原因。雖然這樣做會(huì )使得 CPU 被喚醒的次數稍多一些，但是由于間隔短，CPU 并不會(huì )進(jìn)入很深的睡眠，這個(gè)代價(jià)還是可以接受的。由于 round_jiffies 需要在每次更新 timer 的超時(shí)值（mod_timer）時(shí)被調用，顯得有些繁瑣，因此又出現了更為便捷的 round jiffies 機制，稱(chēng)為 timer slack。Timer slack 修改了 timer_list 的結構定義，將需要偏移的 jiffies 值保存在 timer_list 內部，通過(guò) apply_slack 在每次更新 timer 的過(guò)程中自動(dòng)更新超時(shí)值。apply_slack 的實(shí)現如清單 9 所示：

清單 9. apply_slack 的實(shí)現

/* * Decide where to put the timer while taking the slack into account * * Algorithm: *  1) calculate the maximum (absolute) time *  2) calculate the highest bit where the expires and new max are different *  3) use this bit to make a mask *  4) use the bitmask to round down the maximum time, so that all last *   bits are zeros */ static inline unsigned long apply_slack(struct timer_list *timer, unsigned long expires) { unsigned long expires_limit, mask; int bit; expires_limit = expires; if (timer->slack >= 0) { expires_limit = expires + timer->slack; } else { unsigned long now = jiffies; /* avoid reading jiffies twice */ /* if already expired, no slack; otherwise slack 0.4% */ if (time_after(expires, now)) expires_limit = expires + (expires - now)/256; } mask = expires ^ expires_limit; if (mask == 0) return expires; bit = find_last_bit(mask, BITS_PER_LONG); mask = (1  bit) - 1; expires_limit = expires_limit  ~(mask); return expires_limit; } 

隨著(zhù)現代計算機系統的發(fā)展，對節能的需求越來(lái)越高，尤其是在使用筆記本，手持設備等移動(dòng)環(huán)境是對節能要求更高。Linux 當然也會(huì )更加關(guān)注這方面的需求。hrtimer 子系統的優(yōu)化盡量確保在使用高精度的時(shí)鐘的同時(shí)節約能源，如果系統在空閑時(shí)也可以盡量的節能，則 Linux 系統的節能優(yōu)勢可以進(jìn)一步放大。這也是引入 dynamic tick 的根本原因。

Dynamic tick tickless

在 dynamic tick 引入之前，內核一直使用周期性的基于 HZ 的 tick。傳統的 tick 機制在系統進(jìn)入空閑狀態(tài)時(shí)仍然會(huì )產(chǎn)生周期性的中斷，這種頻繁的中斷迫使 CPU 無(wú)法進(jìn)入更深的睡眠。如果放開(kāi)這個(gè)限制，在系統進(jìn)入空閑時(shí)停止 tick，有工作時(shí)恢復 tick，實(shí)現完全自由的，根據需要產(chǎn)生 tick 的機制，可以使 CPU 獲得更多的睡眠機會(huì )以及更深的睡眠，從而進(jìn)一步節能。dynamic tick 的出現，就是為徹底替換掉周期性的 tick 機制而產(chǎn)生的。周期性運行的 tick 機制需要完成諸如進(jìn)程時(shí)間片的計算，更新 profile，協(xié)助 CPU 進(jìn)行負載均衡等諸多工作，這些工作 dynamic tick 都提供了相應的模擬機制來(lái)完成。由于 dynamic tick 的實(shí)現需要內核的很多模塊的配合，包括了很多實(shí)現細節，這里只介紹 dynamic tick 的核心工作機制，以及如何啟動(dòng)和停止 dynamic tick。

Dynamic tick 的核心處理流程

從上文中可知內核時(shí)鐘子系統支持低精度和高精度兩種模式，因此 dynamic tick 也必須有兩套對應的處理機制。從清單 5 中可以得知，如果系統支持 hrtimer 的高精度模式，hrtimer 可以在此從低精度模式切換到高精度模式。其實(shí)清單 5 還有另外一個(gè)重要功能：它也是低精度模式下從周期性 tick 到 dynamic tick 的切換點(diǎn)。如果當前系統不支持高精度模式，系統會(huì )嘗試切換到 NOHZ 模式，也就是使用 dynamic tick 的模式，當然前提是內核使能了 NOHZ 模式。其核心處理函數如清單 10 所示。這個(gè)函數的調用流程如下：

tick_check_oneshot_change tick_nohz_switch_to_nohz tick_switch_to_oneshot(tick_nohz_handler) 

static void tick_nohz_handler(struct clock_event_device *dev) { struct tick_sched *ts = __get_cpu_var(tick_cpu_sched); struct pt_regs *regs = get_irq_regs(); int cpu = smp_processor_id(); ktime_t now = ktime_get(); dev->next_event.tv64 = KTIME_MAX; if (unlikely(tick_do_timer_cpu == TICK_DO_TIMER_NONE)) tick_do_timer_cpu = cpu; /* Check, if the jiffies need an update */ if (tick_do_timer_cpu == cpu) tick_do_update_jiffies64(now); /* * When we are idle and the tick is stopped, we have to touch * the watchdog as we might not schedule for a really long * time. This happens on complete idle SMP systems while * waiting on the login prompt. We also increment the start * of idle jiffy stamp so the idle accounting adjustment we * do when we go busy again does not account too much ticks. */ if (ts->tick_stopped) { touch_softlockup_watchdog(); ts->idle_jiffies++; } update_process_times(user_mode(regs)); profile_tick(CPU_PROFILING); while (tick_nohz_reprogram(ts, now)) { now = ktime_get(); tick_do_update_jiffies64(now); } } 

在這個(gè)函數中，首先模擬周期性 tick device 完成類(lèi)似的工作：如果當前 CPU 負責全局 tick device 的工作，則更新 jiffies，同時(shí)完成對本地 CPU 的進(jìn)程時(shí)間統計等工作。如果當前 tick device 在此之前已經(jīng)處于停止狀態(tài)，為了防止 tick 停止時(shí)間過(guò)長(cháng)造成 watchdog 超時(shí)，從而引發(fā) soft-lockdep 的錯誤，需要通過(guò)調用 touch_softlockup_watchdog 復位軟件看門(mén)狗防止其溢出。正如代碼中注釋所描述的，這種情況有可能出現在啟動(dòng)完畢，完全空閑等待登錄的 SMP 系統上。最后需要設置下一次 tick 的超時(shí)時(shí)間。如果 tick_nohz_reprogram 執行時(shí)間超過(guò)了一個(gè) jiffy，會(huì )導致設置的下一次超時(shí)時(shí)間已經(jīng)過(guò)期，因此需要重新設置，相應的也需要再次更新 jiffies。這里雖然設置了下一次的超時(shí)事件，但是由于系統空閑時(shí)會(huì )停止 tick，因此下一次的超時(shí)事件可能發(fā)生，也可能不發(fā)生。這也正是 dynamic tick 根本特性。

從清單 7 中可以看到，在高精度模式下 tick_sched_timer 用來(lái)模擬周期性 tick device 的功能。dynamic tick 的實(shí)現也使用了這個(gè)函數。這是因為 hrtimer 在高精度模式時(shí)必須使用 one-shot 模式的 tick device，這也同時(shí)符合 dynamic tick 的要求。雖然使用同樣的函數，表面上都會(huì )觸發(fā)周期性的 tick 中斷，但是使用 dynamic tick 的系統在空閑時(shí)會(huì )停止 tick 工作，因此 tick 中斷不會(huì )是周期產(chǎn)生的。

Dynamic tick 的開(kāi)始和停止

當 CPU 進(jìn)入空閑時(shí)是最好的時(shí)機。此時(shí)可以啟動(dòng) dynamic tick 機制，停止 tick；反之在 CPU 從空閑中恢復到工作狀態(tài)時(shí)，則可以停止 dynamic tick。見(jiàn)清單 11 所示：

清單 11. CPU 在 idle 時(shí) dynamic tick 的啟動(dòng) / 停止設置

void cpu_idle(void) { . . . . while (1) { tick_nohz_stop_sched_tick(1); while (!need_resched()) { . . . . } tick_nohz_restart_sched_tick(); } . . . . } 

timer 子系統的初始化過(guò)程

在分別了解了內核時(shí)鐘子系統各個(gè)模塊后，現在可以系統的介紹內核時(shí)鐘子系統的初始化過(guò)程。系統剛上電時(shí)，需要注冊 IRQ0 時(shí)鐘中斷，完成時(shí)鐘源設備，時(shí)鐘事件設備，tick device 等初始化操作并選擇合適的工作模式。由于剛啟動(dòng)時(shí)沒(méi)有特別重要的任務(wù)要做，因此默認是進(jìn)入低精度 + 周期 tick 的工作模式，之后會(huì )根據硬件的配置（如硬件上是否支持 HPET 等高精度 timer）和軟件的配置（如是否通過(guò)命令行參數或者內核配置使能了高精度 timer 等特性）進(jìn)行切換。在一個(gè)支持 hrtimer 高精度模式并使能了 dynamic tick 的系統中，第一次發(fā)生 IRQ0 的軟中斷時(shí) hrtimer 就會(huì )進(jìn)行從低精度到高精度的切換，然后再進(jìn)一步切換到 NOHZ 模式。IRQ0 為系統的時(shí)鐘中斷，使用全局的時(shí)鐘事件設備（global_clock_event）來(lái)處理的，其定義如下：

static struct irqaction irq0  = { .handler = timer_interrupt, .flags = IRQF_DISABLED | IRQF_NOBALANCING | IRQF_IRQPOLL | IRQF_TIMER, .name = timer}; 

它的中斷處理函數 timer_interrupt 的簡(jiǎn)化實(shí)現如清單 12 所示：

清單 12. IRQ0 中斷處理函數的簡(jiǎn)化實(shí)現

static irqreturn_t timer_interrupt(int irq, void *dev_id) { . . . . global_clock_event->event_handler(global_clock_event);. . . . return IRQ_HANDLED; } 

在 global_clock_event->event_handler 的處理中，除了更新 local CPU 上運行進(jìn)程時(shí)間的統計，profile 等工作，更重要的是要完成更新 jiffies 等全局操作。這個(gè)全局的時(shí)鐘事件設備的 event_handler 根據使用環(huán)境的不同，在低精度模式下可能是 tick_handle_periodic / tick_handle_periodic_broadcast，在高精度模式下是 hrtimer_interrupt。目前只有 HPET 或者 PIT 可以作為 global_clock_event 使用。其初始化流程清單 13 所示：

清單 13. timer 子系統的初始化流程

void __init time_init(void) { late_time_init = x86_late_time_init; } static __init void x86_late_time_init(void) { x86_init.timers.timer_init(); tsc_init(); } /* x86_init.timers.timer_init 是指向 hpet_time_init 的回調指針 */ void __init hpet_time_init(void) { if (!hpet_enable()) setup_pit_timer(); setup_default_timer_irq(); } 

由清單 13 可以看到，系統優(yōu)先使用 HPET 作為 global_clock_event，只有在 HPET 沒(méi)有使能時(shí)，PIT 才有機會(huì )成為 global_clock_event。在使能 HPET 的過(guò)程中，HPET 會(huì )同時(shí)被注冊為時(shí)鐘源設備和時(shí)鐘事件設備。

hpet_enable hpet_clocksource_register hpet_legacy_clockevent_register clockevents_register_device(hpet_clockevent); 

clockevent_register_device 會(huì )觸發(fā) CLOCK_EVT_NOTIFY_ADD 事件，即創(chuàng )建對應的 tick device。然后在 tick_notify 這個(gè)事件處理函數中會(huì )添加新的 tick device。

clockevent_register_device trigger event CLOCK_EVT_NOTIFY_ADD tick_notify receives event CLOCK_EVT_NOTIFY_ADD tick_check_new_device tick_setup_device 

在 tick device 的設置過(guò)程中，會(huì )根據新加入的時(shí)鐘事件設備是否使用 broadcast 來(lái)分別設置 event_handler。對于 tick device 的處理函數，可見(jiàn)圖 5 所示：

表 2. tick device 在不同模式下的處理函數

另外，在系統運行的過(guò)程中，可以通過(guò)查看 /proc/timer_list 來(lái)顯示系統當前配置的所有時(shí)鐘的詳細情況，譬如當前系統活動(dòng)的時(shí)鐘源設備，時(shí)鐘事件設備，tick device 等。也可以通過(guò)查看 /proc/timer_stats 來(lái)查看當前系統中所有正在使用的 timer 的統計信息。包括所有正在使用 timer 的進(jìn)程，啟動(dòng) / 停止 timer 的函數，timer 使用的頻率等信息。內核需要配置 CONFIG_TIMER_STATS=y，而且在系統啟動(dòng)時(shí)這個(gè)功能是關(guān)閉的，需要通過(guò)如下命令激活echo 1 >/proc/timer_stats。/proc/timer_stats 的顯示格式如下所示：

count>, pid> command> start_func> (expire_func>)

總結

隨著(zhù)應用環(huán)境的改變，使用需求的多樣化，Linux 的時(shí)鐘子系統也在不斷的衍變。為了更好的支持音視頻等對時(shí)間精度高的應用，Linux 提出了 hrtimer 這一高精度的時(shí)鐘子系統，為了節約能源，Linux 改變了長(cháng)久以來(lái)一直使用的基于 HZ 的 tick 機制，采用了 tickless 系統。即使是在對硬件平臺的支持上，也是在不斷改進(jìn)。舉例來(lái)說(shuō)，由于 TSC 精度高，是首選的時(shí)鐘源設備。但是現代 CPU 會(huì )在系統空閑時(shí)降低頻率以節約能源，從而導致 TSC 的頻率也會(huì )跟隨發(fā)生改變。這樣會(huì )導致 TSC 無(wú)法作為穩定的時(shí)鐘源設備使用。隨著(zhù)新的 CPU 的出現，即使 CPU 的頻率發(fā)生變化，TSC 也可以一直維持在固定頻率上，從而確保其穩定性。在 Intel 的 Westmere 之前的 CPU 中，TSC 和 Local APIC Timer 類(lèi)似，都會(huì )在 C3+ 狀態(tài)時(shí)進(jìn)入睡眠，從而導致系統需要切換到其他較低精度的時(shí)鐘源設備上，但是在 Intel Westmere 之后的 CPU 中，TSC 可以一直保持運行狀態(tài)，即使 CPU 進(jìn)入了 C3+ 的睡眠狀態(tài)，從而避免了時(shí)鐘源設備的切換。在 SMP 的環(huán)境下，尤其是 16-COREs，32-COREs 這樣的多 CPU 系統中，每個(gè) CPU 之間的 TSC 很難保持同步，很容易出現“Out-of-Sync”。如果在這種環(huán)境下使用 TSC，會(huì )造成 CPU 之間的計時(shí)誤差，然而在 Intel 最新的 Nehalem-EX CPU 中，已經(jīng)可以確保 TSC 在多個(gè) CPU 之間保持同步，從而可以使用 TSC 作為首選的時(shí)鐘源設備。由此可見(jiàn)，無(wú)論是現在還是將來(lái)，只要有需要，內核的時(shí)鐘子系統就會(huì )一直向前發(fā)展。