引子
時間系統的工作需要軟硬件以及操作系統的互相協作，在上一部分，我們已經看到大多數時間函數都依賴內核系統調用，GlibC 僅僅做了一次請求的轉發。因此必須深入內核代碼以便了解更多的細節。
內核自身的正常運行也依賴於時鐘系統。Linux 是一個典型的分時系統，CPU 時間被分成多個時間片，這是多任務實現的基礎。Linux 內核依賴 tick，即時鐘中斷來進行分時。
為了滿足應用和內核自己的需求，內核時間系統必須提供以下三個基本功能：
提供系統 tick 中斷（驅動調度器，實現分時）
維護系統時間
維護軟件定時器
目前的 Linux 內核版本為 3.8，其時間系統比較復雜，復雜的原因來自幾個方面：
首先 Linux 要支持不同的硬件體系結構和時鐘電路，Linux 是一個通用操作系統，支持平台的多樣性導致時間系統必須包含各種各樣的硬件處理和驅動代碼。
其次，早期 Linux 的時鐘實現采用低精度時鐘框架（ms 級別），隨著硬件的發展和軟件需求的發展，越來越多的呼聲是提高時鐘精度（ns 級別）；經過若干年的努力，人們發現無法在早期低精度時鐘體系結構上優雅地擴展高精度時鐘。最終，內核采用了兩套獨立的代碼實現，分別對應於高精度和低精度時鐘。這使得代碼復雜度增加。
最後，來自電源管理的需求進一步增加了時間系統的復雜性。Linux 越來越多地被應用到嵌入式設備，對節電的要求增加了。當系統 idle 時，CPU 進入節電模式，此時一成不變的時鐘中斷將頻繁地打斷 CPU 的睡眠狀態，新的時間系統必須改變以應對這種需求，在系統沒有任務執行時，停止時鐘中斷，直到有任務需要執行時再恢復時鐘。
以上幾點，造成了內核時間系統的復雜性。不過 Linux 內核並不是從一開始就如此復雜，所以還是讓我們從頭說起吧。
早期的 Linux 時間系統
在 Linux 2.6.16 之前，內核只支持低精度時鐘。內核圍繞著 tick 時鐘來實現所有的時間相關功能。Tick 是一個定期觸發的中斷，一般由 PIT (Programmable Interrupt Timer) 提供，大概 10ms 觸發一次 (100HZ)，精度很低。在這個簡單體系結構下，內核如何實現三個基本功能？
第一大功能：提供 tick 中斷。
以 x86 為例，系統初始化時選擇一個能夠提供定時中斷的設備 (比如 Programmable Interrupt Timer, PIT)，配置相應的中斷處理 IRQ 和相應的處理例程。當硬件設備初始化完成後，便開始定期地產生中斷，這便是 tick 了。非常簡單明了，需要強調的是 tick 中斷是由硬件直接產生的真實中斷，這一點在當前的內核實現中會改變，我們在第四部分介紹。
第二大功能：維護系統時間。
RTC (Real Time Clock) 有獨立的電池供電，始終保存著系統時間。Linux 系統初始化時，讀取 RTC，得到當前時間值。
讀取 RTC 是一個體系結構相關的操作，對於 x86 機器，定義在 arch\x86\kernel\time.c中。可以看到最終的實現函數為 mach_get_cmos_time，它直接讀取 RTC 的 CMOS 芯片獲得當前時間。如前所述，RTC 芯片一般都可以直接通過 IO 操作來讀取年月日等時間信息。得到存儲在 RTC 中的時間值之後，內核調用 mktime () 將 RTC 值轉換為一個距離 Epoch（既 1970 年元旦）的時間值。此後直到下次重新啟動，Linux 不會再讀取硬件 RTC 了。
雖然內核也可以在每次需要的得到當前時間的時候讀取 RTC，但這是一個 IO 調用，性能低下。實際上，在得到了當前時間後，Linux 系統會立即啟動 tick 中斷。此後，在每次的時鐘中斷處理函數內，Linux 更新當前的時間值，並保存在全局變量 xtime 內。比如時鐘中斷的周期為 10ms，那麼每次中斷產生，就將 xtime 加上 10ms。
當應用程序通過 time 系統調用需要獲取當前時間時，內核只需要從內存中讀取 xtime 並返回即可。就這樣，Linux 內核提供了第二大功能，維護系統時間。
第三大功能：軟件定時器
能夠提供可編程定時中斷的硬件電路都有一個缺點，即同時可以配置的定時器個數有限。但現代 Linux 系統中需要大量的定時器：內核自己需要使用 timer，比如內核驅動的某些操作需要等待一段給定的時間，或者 TCP 網絡協議棧代碼會需要大量 timer；內核還需要提供系統調用來支持 setitimer 和 POSIX timer。這意味著軟件定時器的需求數量將大於硬件能夠提供的 timer 個數，內核必須依靠軟件 timer。
簡單的軟件 timer 可以通過 timer 鏈表來實現。需要添加新 timer 時，只需在一個全局的鏈表中添加一個新的 Timer 元素。每次 tick 中斷來臨時，遍歷該鏈表，並觸發所有到期的 Timer 即可。但這種做法缺乏可擴展性：當 Timer 的數量增加時，遍歷鏈表的花銷將線形增加。如果將鏈表排序，則 tick 中斷中無須遍歷列表，只需要查看鏈表頭即可，時間為 O(1)，但這又導致創建新的 Timer 的時間復雜度變為 O(n)，因為將一個元素插入排序列表的時間復雜度為 O（N）。這些都是可行但擴展性有限的算法。在 Linux 尚未大量被應用到服務器時，系統中的 timer 個數不多，因此這種基於鏈表的實現還是可行的。
但隨著 Linux 開始作為一種服務器操作系統，用來支持網絡應用時，需要的 timer 個數劇增。一些 TCP 實現對於每個連接都需要 2 個 Timer，此外多媒體應用也需要 Timer，總之 timer 的個數達到了需要考慮擴展性的程度。
timer 的三個操作：添加 (add_timer)、刪除 (del_timer) 以及到期處理（tick 中斷）都對 timer 的精度和延遲有巨大影響，timer 的精度和延遲又對應用有巨大影響。例如，add_timer 的延遲太大，那麼高速 TCP 網絡協議就無法實現。為此，從 Linux2.4 開始，內核通過一種被稱為時間輪的算法來保證 add_timer()、del_timer() 以及 expire 處理操作的時間復雜度都為 O(1)。
時間輪算法簡述
時間輪算法是一種實現軟件 timer 的算法，由計算機科學家 George Varghese 等提出，在 NetBSD(一種操作系統) 上實現並替代了早期內核中的 callout 定時器實現。
最原始的時間輪如下圖所示。
圖 1. 原始的時間輪
上圖中的輪子有 8 個 bucket，每個 bucket 代表未來的一個時間點。我們可以定義每個 bucket 代表一秒，那麼 bucket [1] 代表的時間點就是“1 秒鐘以後”，bucket [8] 代表的時間點為“8 秒之後”。Bucket 存放著一個 timer 鏈表，鏈表中的所有 Timer 將在該 bucket 所代表的時間點觸發。中間的指針被稱為 cursor。這樣的一個時間輪工作如下：
加入Timer：如果新 Timer 在時間點 6 到期，它就被加入 bucket[6] 的 timer 鏈表。定位 bucket[6] 是一個數組訪問的過程，因此這個操作是 O(1) 的。
刪除Timer：類似的，刪除 Timer 也是 O(1) 的。比如刪除一個 6 秒鐘後到期的 timer，直接定位到 bucket[6], 然後在鏈表中刪除一個元素是 O(1) 的。
處理Timer的邏輯在時鐘中斷程序中，每次時鐘中斷產生時，cursor 增加一格，然後中斷處理代碼檢查 cursor 所指向的 bucket，假如該 bucket 非空，則觸發該 bucket 指向的 Timer 鏈表中的所有 Timer。這個操作也是 O(1) 的。
全都是 O(1) 操作？那這個算法豈不是完美的？可惜不是，我們的這個時間輪有一個限制：新 Timer 的到期時間必須在 8 秒之內。這顯然不能滿足實際需要，在 Linux 系統中，我們可以設置精度為 1 個 jiffy 的定時器，最大的到期時間范圍可以達到 (2^32-1/2 ) 個 jiffies(一個很大的值)。如果采用上面這樣的時間輪，我們需要很多個 bucket，需要巨大的內存消耗。這顯然是不合理的。
為了減少 bucket 的數量，時間輪算法提供了一個擴展算法，即 Hierarchy 時間輪。圖 1 裡面的輪實際上也可以畫成一個數組，
圖 2. 時間輪的另一種表示
Hierarchy 時間輪將單一的 bucket 數組分成了幾個不同的數組，每個數組表示不同的時間精度，下圖是其基本思路：
圖 3. Hierarchy 時間輪
這樣的一個分層時間輪有三級，分別表示小時，分鐘和秒。在 Hour 數組中，每個 bucket 代表一個小時。采用原始的時間輪，如果我們要表示一天，且 bucket 精度為 1 秒時，我們需要 24*60*60=86,400 個 bucket；而采用分層時間輪，我們只需要 24+60+60=144 個 bucket。
讓我們簡單分析下采用這樣的數據結構，Timer 的添加/刪除/處理操作的復雜度。
添加Timer
根據其到期值，Timer 被放到不同的 bucket 數組中。比如當前時間為 (hour:11, minute:0, second:0)，我們打算添加一個 15 分鐘後到期的 Timer，就應添加到 MINUTE ARRAY 的第 15 個 bucket 中。這樣的一個操作是 O(m) 的，m 在這裡等於 3，即 Hierarchy 的層數。
圖 4. 添加 15 分鐘到期 Timer
刪除Timer：
Timer 本身有指向 bucket 的指針，因此刪除 Timer 是 O(1) 的操作，比如刪除我們之前添加的 15 分鐘後到期的 Timer，只需要從該 Timer 的 bucket 指針讀取到 MINUTE ARRAY Element 15 的指針，然後從該 List 中刪除自己即可。
定時器處理：
每個時鐘中斷產生時（時鐘間隔為 1 秒），將 SECOND ARRAY 的 cursor 加一，假如 SECOND ARRAY 當前 cursor 指向的 bucket 非空，則觸發其中的所有 Timer。這個操作是 O(1) 的。
可以看到，添加，刪除定時器處理的操作復雜度都很低。
難道 Hierarchy 時間輪完美了？可惜還不是。
為了處理 60 秒之外的那些保存在 MINUTES ARRAY 和 HOUR ARRAY 中的 Timer，時鐘中斷處理還需要做一些額外的工作：每當 SECOND ARRAY 處理完畢，即 cursor 又回到 0 時，我們應該將 MINUTE ARRAY 的當前 cursor 加一，並查看該 cursor 指向的 bucket 是否為空，如果非空，則需要將這些 Timer 移動到前一個 bucket 中。此外 MINUTE ARRAY 的 bucket[0] 的 Timer 這時候應該都移動到 SECOND ARRAY 中。同樣，當 MINUTE ARRAY 的 cursor 重新回到 0 時，我們還需要對 HOUR ARRAY 做類似的處理。這個操作是 O(m) 的，其中 m 是 MINUTE ARRAY 或者 HOUR ARRAY 的 bucket 中時鐘的個數。多數情況下 m 遠遠小於系統中所有 active 的 Timer 個數，但的確，這還是一個費時的操作。
Linux 內核采用的就是 Hierarchy 時間輪算法，Linux 內核中用 jiffies 表示時間而不是時分秒，因此 Linux 沒有采用 Hour/Minutes/Second 來分層，而是將 32bit 的 jiffies 值分成了 5 個部分，用來索引五個不同的數組（Linux 術語叫做 Timer Vector，簡稱 TV），分別表示五個不同范圍的未來 jiffies 值。
這個時間輪的精度為 1 個 jiffy，或者說一個 tick。每個時鐘中斷中，Linux 處理 TV1 的當前 bucket 中的 Timer。當 TV1 處理完（類似 SECOND ARRAY 處理完時），Linux 需要處理 TV2，TV3 等。這個過程叫做 cascades。TV2 當前 bucket 中的時鐘需要從鏈表中讀出，重新插入 TV2；TV2->bucket[0] 裡面的 timer 都被插入 TV1。這個過程和前面描述的時分秒的時間輪時一樣的。cascades 操作會引起不確定的延遲，對於高精度時鐘來講，這還是一個致命的缺點。
但時間輪還是所有 Timer 實現的基礎，在它的基礎上，Linux 提供了間隔 Timer 和 POSIX Timer 供應用程序使用。
動態 Timer、Interval Timer 和 POSIX Timer
早期 Linux 考慮兩種定時器：內核自身需要的 timer，也叫做動態定時器；其次是來自用戶態的需要, 即 setitimer 定時器，也叫做間隔定時器。2.5.63 開始支持 POSIX Timer。2.6.16 引入了高精度 hrtimer。本節介紹 hrtimer 出現之前 Linux 內核中動態 Timer，間隔 Timer 和 POSIX Timer 的概念，發展和實現原理。
動態 Timer
動態 timer 由內核自身使用，其實也是其他 Timer 的實現基礎。使用動態 Timer 的接口函數有三個：
add_timer()
del_timer()
init_timer()
使用時，先調用 init_timer() 初始化一個定時器，指定到期時間和到期處理函數；初始化完成後，內核代碼可以用 add_timer() 啟動定時器，或者用 del_timer() 來取消一個已經啟動的定時器。
add_timer 采用時間輪算法將定時器加入 per CUP 變量 tvec_bases 中，根據其 expire 時間，可能被加入 5 個 Timer Vector 之一。此後，tick 中斷將根據時間輪算法處理。當本 timer 到期時，觸發其處理函數。
動態 Timer 有兩個方面的用途：一是內核自己使用，比如某些驅動程序需要定時服務的時候使用它；二是用來實現用戶層 Timer。下面首先講解間隔 Timer。
間隔 timer
間隔 timer 就是應用程序調用setitimer建立的定時器。
Linux 的間隔 Timer 實現經歷了一個簡單的發展過程。
Linux2.4 版本內核在進程描述符中有以下這些數據結構，用來實現間隔 timer:
struct timer_list real_timer;
unsigned long it_real_value, it_prof_value, it_virt_value;
unsigned long it_real_incr, it_prof_incr, it_virt_incr;
real_timer 是一個動態 timer，用於 ITIMER_REAL 時鐘。其他的 unsigned long 類型的值分別用來維護各種時鐘的到期時間和到期後的 interval 時間，用 jiffies 值表示。
ITIMER_REAL 是用內核動態 Timer 來實現的，每次創建 ITIMER_REAL 時鐘時，內核調用 init_timer 創建一個定時器對象，並用 add_timer 將該定時器添加到系統 Timer 時間輪中，該定時器的到期處理函數被設定為 it_real_fn()。此函數將向當前進程發送 SIGALRM 信號，並重新調用 add_timer() 重新啟動自身。這樣便實現了 ITIMER_REAL 時鐘。進程描述符中的 it_real_value 僅用於讀取，以便用戶通過 /proc 讀取時鐘信息。
另外兩種間隔 Timer 則不能簡單地依靠動態 Timer 來實現。因為它們參照的是進程的時間而非實時時間，因此要依賴進程的時間統計。實現原理如下：
每次時鐘中斷產生時，內核判斷中斷觸發時進程是否正處於內核態，如果在內核態，則將 it_prof_value 和 it_virt_value 都減一；如果在用戶態，則只對 it_prof_value 減一，而 it_virt_value 不變。當 it_prof_value 為 0 時，對當前進程發送 SIGPROF 信號，並把 it_prof_incr 的值重新填入 it_prof_value，等待下次到期觸發。當 it_virt_value為 0 時，則對當前進程發送 SIGVTALRM 信號，並用it_virt_incr的值重新填充 it_virt_value。這樣就實現了 POSIX 對 setitimer 所定義的 ITIMER_VIRTUAL 和 ITIMER_PROF 時鐘。
不過這種實現有一個問題：在 Linux 中線程是一個單獨的調度實體，即輕量級進程。因此一個進程中的每個線程都擁有自己的進程描述符。這意味著每個線程都有自己的 it_virt_value 和 it_prof_value。因此 ITIMER_VIRTUAL，ITIMER_PROF 的計時范圍是 per-thread，而 POSIX 規定間隔 Timer 必須是 per-process 的。
比如某進程有 2 個線程，現在建立一個 2 秒到期的 ITIMER_VIRTUAL，假設第一個線程得到了 1 秒的 CPU 時間，此時線程 2 也得到了 1 秒的 CPU 時間。按照 POSIX 標准，此時定時器應該到期。但是根據我們前面所描述的原理，這個時候 ITIMER_VIRTUAL 並沒有被觸發。如果是在 Thread1 中調用 setitimer，則線程 2 的進程描述符中 it_virt_value 為 0，線程 1 進程描述符中的 it_virt_value 此時為 1 秒，還沒有到期，因此進程則必須等到線程 1 運行到 2 秒才能觸發這個定時器。這不符合 POSIX 標准，因此從 2.6.12 開始，對上述基本實現進行了一定的改進，雖然從原理上說，這個改進很小，但代碼卻有比較大的改變。
Per-process ITIMER_VIRTUAL 和 ITIMER_PROF
2.6.12 中合並了 Roland McGrath 的 per-process timer 系列 Patch。使得 itimer.c，posix-timer.c 有了不少改變，還多了一個 posix-cpu-timer.c 文件。雖然代碼實現上有很大的不同，但實際上基本的實現思路還是和之前介紹的差不多，不過進一步考慮了對多線程情況下的修正。這裡簡單介紹一下實現的思路。
每個進程描述符中，引入了兩個計數器：utime 和 stime。utime 代表當前進程（也可能是一個線程）花費在用戶態的時間。
在時鐘中斷中，如果內核發現中斷時當前進程（線程）正在用戶態，則 utime 增加一個 jiffies；如果在內核態則 utime 不增加，stime 增加。總的說來，就是統計好當前進程或線程的運行時間。現在，按下時鐘中斷暫且不表。
創建 ITIMER_VIRTUAL時 (內核響應函數為do_setitimer)，內核將該 Timer 的value 和 interval 分別設置到當前進程描述符的 signal->it_virt_value 和 signal->it_virt_incr 中。假設一個程序有 2 個線程，Thread1 和 Thread2。內核將有兩個進程描述符對應這兩個線程，taskStruct1 和 taskStruct2。再假設程序是在 Thread1 中調用 setitimer。那麼 taskStrcut1的signal->it_virt_value 和 signal->it_virt_incr 被設置；而 taskStruct2 的相應數據則保持為 0。讓我們再回到時鐘中斷。
統計完 utime 和 stime 之後，時鐘中斷開始檢查當前進程描述符的 signal->it_virt_value 值，如果該值非零，則表明有一個 ITIMER_VITURAL，到期時間為 signal->it_virt_value。老的內核實現在這裡就判斷 utime 是否大於 it_virt_value，如果大於則表明時鐘到期。為了統計多線程情況，從 2.6.12 開始，時鐘中斷在這裡不僅要查看當前進程描述符的 utime，還要加上當前進程組中所有線程的 utime，然後再判斷總的 utime 是否大於 signal->it_virt_value。比如前面所假設的例子，Thread2 被時鐘中斷打斷時，統計自己的 utime，但由於其 signal->it_virt_value 為 0，因此沒有其他的工作需要做了。當 Thread1 被時鐘中斷打斷時，其 signal->it_virt_value 大於 0，因此中斷處理中要遍歷線程組中所有的線程，將每個線程的 utime 匯總，即總的 utime=taskStruct1->utime+taskStruct2->utime。再用這個總的 utime 和 signal->it_virt_value（即時鐘到期時間）進行比較是否到期。僅此而已。
ITIMER_PROF 的思路類似，但它不僅要比較 utime，還要比較 stime。不再贅述。
Posix timer
從 2.5.63 開始，內核能夠支持 posix timer 了，之前，其支持是有限的：只支持 CLOCK_REALTIME 和 CLOCK_MONOTONIC 兩種 clock ID。這兩種 POSIX Timer 建立在內核動態 Timer 之上，精度是一個 tick。比如，創建 realtime 定時器，內核將調用 init_timer() 創建一個動態 Timer，並制定其到期處理函數位 posix_timer_fn；當啟動該定時器時，內核將調用 add_timer() 啟動該內核動態 Timer；當該定時器到期時，將觸發 posix_timer_fn，該函數采用定時器注冊的通知方式進行處理，比如 SIGEV_SIGNAL，該函數就會調用 sigaddset 發送一個信號。
其他兩種 Timer(CLOCK_PROCESS_CPUTIME_ID 和 CLOCK_THREAD_CPUTIME_ID) 的實現有點兒復雜。因為用戶可以創建任意多的 POSIX Timer。CLOCK_REALTIME 和 CLOCK_MONOTONIC 基於數量不限的動態 Timer，因此可以創建任意數目的定時器。
但 CLOCK_PROCESS_CPUTIMER_ID 和 CLOCK_THREAD_CPUTIME_ID，並不依賴動態 Timer，必須在進程描述符中想辦法。
2.6.12 在進程描述符中引入了兩個 cpu_timers 數組 (所謂 CPU TIME，即進程/線程真正在 CPU 上執行的時間，包括內核態時間和用戶態的時間):
一個在進程描述符 task_stuct 中。另一個放在進程描述符的 signal 數據結構中。用 task 表示進程描述符，兩個 cpu timers 數組如下：
task->cpu_timers[3]：用來維護 per-thread 的 CPU Timer
task->signal->cpu_timers[3]：用來維護 per-process 的 CPU Timer.
該數組的每個元素都維護一個 Timer 列表。如下圖所示：
圖 5. 進程控制塊中的 CPU-TIMER
可以看到 Linux 采用排序列表來存放 CLOCK_PROCESS_CPUTIMER_ID 和 CLOCK_THREAD_CPUTIME_ID 的 Timer，即上圖中紅色的列表（cpu_timer[CPUCLOCK_SCHED]）。每當定時中斷發生時，會檢查這兩個鏈表，如果發現有到期的定時器就觸發它們。通過這兩個數組，內核支持用戶創建任意多 CLOCK_PROCESS_CPUTIMER_ID/CLOCK_THREAD_CPUTIME_ID 類型的 POSIX 定時器。
小結
隨著時光推移，精度為 jiffy 的時鐘已經不能滿足所有的要求了。越來越強的呼聲是高精度時鐘，通過提高 HZ 畢竟是有限的，一些系統上已經采用了 1000 的 HZ 配置，再繼續增高將導致時鐘中斷的開銷過大，從而降低整個系統的處理能力。經過了多年的不斷嘗試和開發，Linux 內核終於在 2.6.16 版本中加入了 HRTIMER。我們在下一部分將繼續介紹內核的高精度時間系統。
