回顧
近年來,隨著 Linux 的廣泛使用,對時間編程提出了更高的要求。實時應用、多媒體軟件對時鐘和定時器的精度要求不斷提高,在早期 Linux 內核中,定時器所能支持的最高精度是一個 tick。為了提高時鐘精度,人們只能提高內核的 HZ 值 (一個內核參數,代表內核時鐘中斷的頻率)。更高的 HZ 值,意味著時鐘中斷更加頻繁,內核要花更多的時間進行時鐘處理。而內核的任何工作對於應用來說純粹是無益的開銷。當 HZ 值提高到 1000 之後,如果繼續提高,Linux 的可用性將下降。
另外一方面,我們已看到,類似 HPET(High Precision Event Timer) 等系統硬件已經能夠提供納秒級別的時鐘中斷,如何利用這些高精度時鐘硬件來提供更高精度的定時服務是這一部分的主要話題。
2.6.16 以來的新變化
在 2.6.16 之前,Linux 開發人員花了很多的努力試圖在原有代碼體系結構下實現高精度時鐘,但這種努力被證明是徒勞的。
因此從 2.6.16 開始,RedHat 公司的 Ingo Molar 和 Thomas Gleixner 對時間系統進行了比較大的重構。引入了以下幾個新的模塊:
Generic Timer Framework
早期 Linux 內核也需要支持眾多不同的時鐘硬件設備,但內核本身對這些設備的使用相對簡單。內核將硬件的不同操作封裝在 Arch 層裡面。比如 x86 體系結構下,設置 PIT(Programmable Interrupt Timer) 是在 8259 芯片初始化時完成的,調用的 API 名字叫做 setup_pit_timer(),而在其他體系結構中,沒有 8259,其初始化 time_init()中的具體實現又有所不同,會采用不同的 API 命名和不同的表示 Timer 硬件的數據結構。因為早期 Linux 上只需要做一次時鐘初始化,操作具體硬件的次數有限,因此這種不同體系結構用不同實現細節的做法沒有什麼問題。
新的內核能夠支持 tickless 模式,即當內核空閒時為了省電而關閉時鐘中斷。為此,內核需要頻繁操作 Timer 硬件,在這種情況下,采用統一的抽象層有助於代碼的維護。這便是 Generic Timer Frame,它將各種不同硬件抽象為三個統一的數據結構:
Clock Source,由 struct clocksource 表示。這個數據結構主要用來抽象那些能夠提供計時功能的系統硬件,比如 RTC(Real Time Clock)、TSC(Time Stamp Counter) 等。
Clock Event Device,由 struct clock_event_device 表示。這個數據結構主要用來封裝和抽象那些能提供定時中斷能力的系統硬件,比如 HPET 等。
Tick Device,由 struct tick_device 表示。這個數據結構建立在 clock event device 之上,專門用來表示產生 tick 的設備。tick 是一個定時中斷。因此歸根結底需要一個 Clock Event Device 來完成,但 Clock Event Device 不僅可以用來提供 tick,在高精度 Timer 模式下,還用來提供其他功能。
Generic Timer Frame 把各種不同時間硬件的區別同上層軟件隔離開來,使得時間系統能夠方便地支持新的時鐘硬件,而無需大量修改硬件無關代碼。
高精度定時器 hrtimer(High Resolution Timer)
高精度時鐘不能建立在已有的時間輪算法上,雖然時間輪是一種有效的管理數據結構,但其 cascades 操作有不可預料的延遲。它更適於被稱為"timeout”類型的低精度定時器,即不等觸發便被取消的 Timer。這種情況下,cascades 可能造成的時鐘到期延誤不會有任何不利影響,因為根本等不到 cascades,換句話說,多數 Timer 都不會觸發 cascades 操作。而高精度定時器的用戶往往是需要等待其精確地被觸發,執行對時間敏感的任務。因此 cascades 操作帶來的延遲是無法接受的。所以內核開發人員不得不放棄時間輪算法,轉而尋求其他的高精度時鐘算法。最終,開發人員選擇了內核中最常用的高性能查找算法紅:黑樹來實現 hrtimer。
在描述 hrtimer 的實現之前,先了解其使用方法是必要的。
hrtimer 的編程接口和方法
使用 hrtimer 之需要了解三個 API:
用 hrtimer_init() 初始化一個 Timer 對象,用 hrtimer_start() 設定到期時間和到期操作,並添加啟動該 Timer。remove_hrtimer() 刪除一個 Timer。
Hrtimer 的實現
高精度定時器和低精度定時器的實現有以下兩個主要的不同點:
高精度定時器由紅黑樹管理,而非時間輪。
Hrtimer 與系統時鐘 tick 無關,不使用 jiffies,用納秒作為計時單位。
所有的 hrtimer 實例都被保存在紅黑樹中,添加 Timer 就是在紅黑樹中添加新的節點;刪除 Timer 就是刪除樹節點。紅黑樹的鍵值為到期時間。
Timer 的觸發和設置管理不在定期的 tick 中斷中進行,而是動態調整:當前 Timer 觸發後,在中斷處理的時候,將高精度時鐘硬件的下次中斷觸發時間設置為紅黑樹中最早到期的 Timer 的時間。時鐘到期後從紅黑樹中得到下一個 Timer 的到期時間,並設置硬件,如此循環反復。
圖 1 顯示了內核中用來管理 hrtimer 的數據結構及他們之間的關系。
圖 1. 數據結構
每一個具體的高精度定時器用 structhrtimer 表示,並且是紅黑樹的一個節點。
在多處理器系統中,每個 CPU 都保存和維護自己的高精度定時器,為了同步和通知的需要處理器間的消息通信將引入不可忍受的延遲。要知道,hrtimer 的精度要求是納秒級別的。在每個 CPU 上,hrtimer 還分為兩大類:
Monotonic:與系統時間無關的自然流失的時間,不可以被人修改。
Real time:實時時間即系統時間,可以被人修改。
因此每個 CPU 都需要兩個 clock_base 數據結構:一個指向所有 monotonic hrtimer;另一個指向所有的 realtime hrtimer。
clock_base 數據結構中,active 指向一個紅黑樹,每個 hrtimer 都是該紅黑樹的一個節點,用到期時間作為 key。這樣所有的定時器便按照到期時間的先後被順序加入這棵平衡樹。first 指向最近到期的 hrtimer, 即紅黑樹最左邊的葉子節點。
這種數據結構組織是很清晰和簡單的,理解了這些數據結構,描述 hrtimer 的具體操作便十分容易了。
添加 Timer,即在相應的 clock_base 指向的紅黑樹中增加一個新的節點,紅黑樹的 key 由 hrtimer 的到期時間表示,因此越早到期的 hrtimer 在樹上越靠左。
刪除 Timer,即從紅黑樹上刪除該 hrtimer。
hrtimer 是如何觸發的
我們所描述過的低精度定時器都是依賴系統定期產生的 tick 中斷的。而高精度時鐘模式下,定時器直接由高精度定時器硬件產生的中斷觸發。比如目前系統中有 3 個 hrtimer,其到期時間分別為 10ns、100ns 和 1000ns。添加第一個 hrtimer 時,系統通過當前默認的 clock_event_device 操作時鐘硬件將其下一次中斷觸發時間設置為 10ns 之後;當 10ns 過去時,中斷產生,通過系統的中斷處理機制,最終會調用到 hrtimer_interrrupt() 函數,該函數從紅黑樹中得到所有到期的 Timer,並負責調用 hrtimer 數據結構中維護的用戶處理函數(或者通過軟中斷執行用戶指定操作);hrtimer_interrupt 還從紅黑樹中讀取下一個到期的 hrtimer,並且通過 clock_event_device 操作時鐘硬件將下一次中斷到期時間設置為 90ns 之後。如此反復操作。
這樣就突破了 tick 的精度限制,用戶操作可以精確到 ns 級別,當然中斷依然存在延遲,這種延遲在幾百個納秒級別,還是比較高的精度。
Tick 時鐘模擬
在高精度時鐘模式下,內核系統依然需要一個定時觸發的 tick 中斷,以便驅動任務切換等重要操作。可是我們在上一節看到,高精度時鐘模式下,系統產生時間中斷的間隔是不確定的,假如系統中沒有創建任何 hrtimer,就不會有時鐘中斷產生了。但 Linux 內核必須要一個嚴格定時觸發的 tick 中斷。
因此系統必須創建一個模擬 tick 時鐘的特殊 hrtimer,並且該時鐘按照 tick 的間隔時間(比如 10ms)定期啟動自己,從而模擬出 tick 時鐘,不過在 tickless 情況下,會跳過一些 tick。關於 tickless,和本文主旨無關,不再贅述。
內核時間系統的總體運行情況
 
至此,我們可以用下面這張圖來總結高精度模式下,內核時間系統的總體運行情況。
圖 2. 內核時間系統概覽
Linux 用 Generic Timer Framework 層來屏蔽底層硬件的細節,對上抽象出 Clock Sources 和 Clock Event 兩個數據結構,分別用來表示計時的硬件和定時的硬件。
用基於紅黑樹的 hrtimer 系統維護高精度時鐘,並用一個特殊的 hrtimer 模擬系統時鐘 tick,產生定期的系統時鐘中斷。
模擬的系統時鐘 tick 將驅動傳統的低精度定時器系統(基於時間輪)和內核進程調度。
用戶層 Timer 的支持和改變
高精度時鐘主要應用於實時系統。在用戶層,實時時鐘的編程接口就是我們在第一部分介紹的 POSIX Timer。本文的第三部分介紹了基於 2.6.16 之前內核的 POSIX Timer 實現細節。
當 hrtimer 加入內核之後,POSIX Timer 的實現細節有一些改變,其中 per process 和 per thread 定時器的實現基本沒有變化。但針對 CLOCK_REALTIME 和 CLOCK_MONOTONIC 兩個時鐘源的基本實現有所改變。以前它們依賴內核中的動態定時器實現,現在這類 Timer 都采用了新的 hrtimer。換句話說,每個時鐘源為 CLOCK_REALTIME/CLOCK_MONOTONIC 的 POSIX Timer 都由一個內核 hrtimer 實現。
傳統的間隔 Timer 雖然不屬於實時應用,也沒有很高的時鐘精度要求,但在新的內核中,間隔 Timer 也使用了 hrtimer,而非傳統的動態 Timer。因此 setitimer 在內核中也不再由時間輪管理了。
總體來說,用戶請求的 Timer,無論是精度較低的間隔 Timer 還是精度高的 POSIX Timer,內核都采用 hrtimer 來支持。而由時間輪算法維護的內核動態 Timer 則僅僅在內核內部使用,比如一些驅動程序中還依舊使用 add_timer() 等動態 Timer 接口實現定時需求。
時區問題
結束之前,我們探討一個尚未展開的話題,即時區問題。這是非常容易讓人迷惑的一個話題。因此放在文章的結尾處討論會好些。
首先介紹兩個縮寫: UTC 和 LCT。
UTC 就是 Coordinated Universal Time,是全世界通用的時間標准。它是格林威治時間 (GMT) 的後繼者,在計算機領域,GMT 術語不再廣泛使用,因為它的精度不夠高。UTC 是 1963 年標准化的,采用了高精度的原子鐘。因此在科學領域,包括計算機科學,都采用 UTC 而不再使用 GMT 這個術語。我們可以認為 UTC 就是時區 0 的標准時間。LCT(Local Civil Time) 即當地時間,比如北京時間。
假如您耐心讀到了這裡,應該已經了解了系統時間 (system time) 和硬件時間 (RTC time) 的區別。硬件時間存放在 RTC(Real Time Clock) 硬件中。Linux 系統啟動時,會讀取 RTC 時間,並該時間來初始化系統時間;正常運行時,系統時間在每次 tick 中斷中加以更新和維護;當系統關閉時,Linux 用系統時間來更新硬件時間。
Linux 系統時間總是 UTC 時間。那麼硬件 RTC 中保存的是 UTC 還是 LCT 呢?
微軟的 Windows 系統認定該時間為 LCT,即當地時間。我在上海的家裡打開電腦,RTC 的時間是 2013-01-25 10:00:00,當系統啟動後,會發現屏幕最右下角顯示的當前時間就是 2013 年 1 月 25 日上午 10 點。
而在 Linux 系統中,RTC 的時間究竟是 LCT 還是 UTC 是由一個配置文件決定。RedHat 發行版中,該配置文件叫做/etc/sysconfig/clock。當該文件中有”UTC=true”這一行設定時,Linux 系統會將 RTC 時間解讀為 UTC 時間,否則就解讀為 LCT。(Debian 發行版依賴/etc/default/rcS 的設定來決定從 RTC 讀入的是 UTC 還是 LCT)假設 RTC 中的時間還是 2013-01-25 10:00:00,並且/etc/sysconfig/clock 中有一行”UTC=true”,那麼系統啟動後就會將系統時間設置為 2013-01-25 10:00:00。如果/etc/sysconfig/clock 中沒有這一行,系統 init 進程會將 RTC 中的時間解釋為 LCT,並根據當前的時區配置計算出 UTC 時間,再用該時間設置系統時間 (hwclock 命令)。RTC 時間不變,現在的系統時間就變成了 2013-01-25 02:00:00,因為我的電腦在上海,系統計算出 UTC 為 8 小時之前。我們用 time()、gettimeofday() 等獲得的時間值都是系統時間,即 UTC 時間。
可是桌面程序顯示時間時,最好顯示當地時間,您恐怕也不願意每次看時間都需要在腦海中把格林威治時間轉成當地時間吧。因此桌面應用通常會顯示本地時間,我們常用的 date 命令也缺省顯示 LCT。這是怎麼做到的呢?
查看 date 的源代碼,可以發現它用 localtime() 將調用 gettimeofday() 得到的 UTC 時間轉換為 LCT 時間再進行輸出。
那麼 localtime() 是如何轉換 LCT 的呢?感謝 POSIX 在這裡有一個標准,Linux 系統將時區信息寫入/etc/localtime 文件。該文件一般是/usr/share/zone 中某個文件的拷貝或者軟鏈接。LibC 的 localtime 函數會讀取/etc/localtime 獲取本機的時區設置,然後進行復雜的時區轉換,將給定 time_t 表示的 UTC 時間轉換為 LCT。此外,在讀取/etc/localtime 之前,localtime() 會先讀取環境變量 TZ,因此用戶也可以通過設置該環境變量來臨時改變時區設置。/etc/localtime 文件中還包含了 Day Light Saving,即夏令時的信息。在實行夏令時的地區,/etc/localtime 文件中包含了如何計算夏令時的必要信息,因此 LibC 函數 localtime 才能夠正確地將 UTC 轉換為 LCT。
結束語
至此本文終於告一段落,用了 4 篇文章走馬觀花地試圖指出時間系統的完整圖景,不足之處甚至錯誤一定很多。希望讀者包涵並和我交流。