1. Linux內(nèi)核時鐘系統(tǒng)和定時器實現(xiàn)

Linux 2.6.16之前，內(nèi)核只支持低精度時鐘，內(nèi)核定時器的工作方式：

• 系統(tǒng)啟動后，會讀取時鐘源設(shè)備(RTC, HPET，PIT…),初始化當(dāng)前系統(tǒng)時間；
• 內(nèi)核會根據(jù)HZ(系統(tǒng)定時器頻率，節(jié)拍率)參數(shù)值，設(shè)置時鐘事件設(shè)備，啟動tick(節(jié)拍)中斷。HZ表示1秒種產(chǎn)生多少個時鐘硬件中斷，tick就表示連續(xù)兩個中斷的間隔時間。在我電腦上，HZ=250， 一個tick = 1/HZ, 所以默認(rèn)一個tick為4ms。

• 設(shè)置時鐘事件設(shè)備后，時鐘事件設(shè)備會定時產(chǎn)生一個tick中斷，觸發(fā)時鐘中斷處理函數(shù)，更新系統(tǒng)時鐘,并檢測timer wheel，進(jìn)行超時事件的處理。

在上面工作方式下，Linux 2.6.16 之前，內(nèi)核軟件定時器采用timer wheel多級時間輪的實現(xiàn)機(jī)制，維護(hù)操作系統(tǒng)的所有定時事件。timer wheel的觸發(fā)是基于系統(tǒng)tick周期性中斷。

所以說這之前，linux只能支持ms級別的時鐘，隨著時鐘源硬件設(shè)備的精度提高和軟件高精度計時的需求，有了高精度時鐘的內(nèi)核設(shè)計。

Linux 2.6.16 ，內(nèi)核支持了高精度的時鐘，內(nèi)核采用新的定時器hrtimer，其實現(xiàn)邏輯和Linux 2.6.16 之前定時器邏輯區(qū)別：

• hrtimer采用紅黑樹進(jìn)行高精度定時器的管理，而不是時間輪；
• 高精度時鐘定時器不在依賴系統(tǒng)的tick中斷，而是基于事件觸發(fā)。

舊內(nèi)核的定時器實現(xiàn)依賴于系統(tǒng)定時器硬件定期的tick，基于該tick，內(nèi)核會掃描timer wheel處理超時事件，會更新jiffies，wall time(墻上時間，現(xiàn)實時間)，process的使用時間等等工作。

新的內(nèi)核不再會直接支持周期性的tick，新內(nèi)核定時器框架采用了基于事件觸發(fā)，而不是以前的周期性觸發(fā)。新內(nèi)核實現(xiàn)了hrtimer(high resolution timer)，hrtimer的設(shè)計目的，就是為了解決time wheel的缺點：

• 低精度；timer wheel只能支持ms級別的精度，hrtimer可以支持ns級別；
• Timer wheel與內(nèi)核其他模塊的高耦合性；

新內(nèi)核的hrtimer的觸發(fā)和設(shè)置不像之前在定期的tick中斷中進(jìn)行，而是動態(tài)調(diào)整的，即基于事件觸發(fā)，hrtimer的工作原理：通過將高精度時鐘硬件的下次中斷觸發(fā)時間設(shè)置為紅黑樹中最早到期的 Timer 的時間，時鐘到期后從紅黑樹中得到下一個 Timer 的到期時間，并設(shè)置硬件，如此循環(huán)反復(fù)。

在高精度時鐘模式下，操作系統(tǒng)內(nèi)核仍然需要周期性的tick中斷，以便刷新內(nèi)核的一些任務(wù)。前面可以知道，hrtimer是基于事件的，不會周期性出發(fā)tick中斷，所以為了實現(xiàn)周期性的tick中斷(dynamic tick)：系統(tǒng)創(chuàng)建了一個模擬 tick 時鐘的特殊 hrtimer，將其超時時間設(shè)置為一個tick時長，在超時回來后，完成對應(yīng)的工作，然后再次設(shè)置下一個tick的超時時間，以此達(dá)到周期性tick中斷的需求。

引入了dynamic tick,是為了能夠在使用高精度時鐘的同時節(jié)約能源,，這樣會產(chǎn)生tickless 情況下，會跳過一些 tick。這里只是簡單介紹，有興趣可以讀kernel源碼。

上圖1是Linux 2.6.16以來內(nèi)核定時器實現(xiàn)的結(jié)構(gòu)，

新內(nèi)核對相關(guān)的時間硬件設(shè)備進(jìn)行了統(tǒng)一的封裝，定義了主要有下面兩個結(jié)構(gòu)：

• 時鐘源設(shè)備(closk source device)：抽象那些能夠提供計時功能的系統(tǒng)硬件，比如 RTC(Real Time Clock)、TSC(Time Stamp Counter)，HPET，ACPI PM-Timer，PIT等。不同時鐘源提供的精度不一樣，現(xiàn)在pc大都是支持高精度模式(high-resolution mode)也支持低精度模式(low-resolution mode)。
• 時鐘事件設(shè)備(clock event device)：系統(tǒng)中可以觸發(fā) one-shot（單次）或者周期性中斷的設(shè)備都可以作為時鐘事件設(shè)備。

當(dāng)前內(nèi)核同時存在新舊timer wheel 和 hrtimer兩套timer的實現(xiàn)，內(nèi)核啟動后會進(jìn)行從低精度模式到高精度時鐘模式的切換，hrtimer模擬的tick中斷將驅(qū)動傳統(tǒng)的低精度定時器系統(tǒng)（基于時間輪）和內(nèi)核進(jìn)程調(diào)度。

內(nèi)核定時器系統(tǒng)增加了hrtimer之后，對于用戶層開放的定時器相關(guān)接口基本都是通過hrtimer進(jìn)行實現(xiàn)的，從內(nèi)核源碼可以看到:

2. 用戶層定時器API接口

上面介紹完linux內(nèi)核定時器的實現(xiàn)后，下面簡單說一下，基于內(nèi)核定時器實現(xiàn)的，對用戶層開放的定時器API：間隔定時器itimer和POSIX定時器。

2.1 常見定時功能的API：sleep系列

在介紹itimer和POSIX定時器之前，我們先看看我們經(jīng)常遇到過具有定時功能的庫函數(shù)API接口：

alarm:

alarm()函數(shù)可以設(shè)置一個定時器，在特定時間超時，并產(chǎn)生SIGALRM信號，如果不忽略或不捕捉該信號，該進(jìn)程會被終止。

那么alarm在是如何實現(xiàn)的？Glibc中alarm是基于間隔定時器itimer來實現(xiàn)的(文章后面會說到itimer是基于hrtimer實現(xiàn)的)。如下alarm在庫函數(shù)下的實現(xiàn),alarm調(diào)用了setitimer系統(tǒng)調(diào)用：

sleep:

sleep和alarm的功能類似，不過sleep會讓進(jìn)程掛起， 在定時器超時內(nèi)核會產(chǎn)生SIGALRM信號，如果不忽略或不捕捉該信號，該進(jìn)程會被終止。

那么sleep是如何實現(xiàn)的？Glibc的sleep實現(xiàn)如下：可見其實調(diào)用alarm實現(xiàn)的，在alarm的基礎(chǔ)上注冊了SIGALRM信號處理函數(shù)，用于在定時器到期時，捕獲到信號，回到睡眠的地方。所以其實可以看出sleep就是對alarm的特化。

usleep:

usleep支持精度更高的微妙級別的定時操作，

Bsd的usleep實現(xiàn)如下：

nanosleep:

nanosleep()glibc的API是直接調(diào)用linux內(nèi)核的nanosleep，內(nèi)核的nanosleep采用了hrtimer進(jìn)行實現(xiàn)。

alarm(), sleep()系列，以及后面的間隔定時器itimer都是基于SIGALRM信號進(jìn)行觸發(fā)的。所以它們是不能同時使用的。

2.2 間隔定時器itimer

間隔定時器的接口如下：

可以通過調(diào)用上面兩個API接口來設(shè)置和獲取間隔定時器信息。系統(tǒng)為每個進(jìn)程提供了3種itimer，每種定時器在不同時間域遞減，當(dāng)定時器超時，就會向進(jìn)程發(fā)送一個信號，并且重置定時器。3種定時器的類型，如下表所示：

表1 參數(shù)which與定時器類型

在Linux 2.6.16 之前，itimer的實現(xiàn)是基于內(nèi)核定時器timer wheel封裝成的定時器接口。內(nèi)核封裝的定時器接口是提供給其他內(nèi)核模塊使用，也是其他定時器的基礎(chǔ)。itimer通過內(nèi)核定時器的封裝，生成提供給用戶層使用的接口setitimer和getitimer。內(nèi)核定時器timer wheel提供的內(nèi)核態(tài)調(diào)用接口為:可參考

在Linux 2.6.16 以來，itimer不再采用基于timer wheel的內(nèi)核定時器進(jìn)行實現(xiàn)。而是換成了高精度的內(nèi)核定時器hrtimer進(jìn)行實現(xiàn)。

如果定時器超時時，進(jìn)程是處于運行狀態(tài)，那么超時的信號會被立刻傳送給該進(jìn)程，否則信號會被延遲傳送，延遲時間要根據(jù)系統(tǒng)的負(fù)載情況。所以這里有一個BUG：當(dāng)系統(tǒng)負(fù)載很重的情況下，對于ITIMER_REAL定時器有可能在上一次超時信號傳遞完成前再次超時，這樣就會導(dǎo)致第二次超時的信號丟失。

每個進(jìn)程中同一種定時器只能使用一次。

該系統(tǒng)調(diào)用在POSIX.1-2001中定義了，但在POSIX.1-2008中已被廢棄。所以建議使用POSIX定時器API（timer_gettime, timer_settime）代替。

函數(shù)alarm本質(zhì)上設(shè)置的是低精確、非重載的ITIMER_REAL類定時器，它只能精確到秒，并且每次設(shè)置只能產(chǎn)生一次定時。函數(shù)setitimer 設(shè)置的定時器則不同，它們不但可以計時到微妙（理論上），還能自動循環(huán)定時。在一個Unix進(jìn)程中，不能同時使用alarm和ITIMER_REAL類定時器。

下面是測試代碼：

2.3 POSIX定時器

POSIX定時器的是為了解決間隔定時器itimer的以下問題：

• 一個進(jìn)程同一時刻只能有一個同一種類型(ITIMER_REAL, ITIMER_PROF, ITIMER_VIRT)的itimer。POSIX定時器在一個進(jìn)程中可以創(chuàng)建任意多個timer。
• itimer定時器到期后，只能通過信號(SIGALRM,SIGVTALRM,SIGPROF)的方式通知進(jìn)程，POSIX定時器到期后不僅可以通過信號進(jìn)行通知，還可以使用自定義信號，還可以通過啟動一個線程來進(jìn)行通知。
• itimer支持us級別，POSIX定時器支持ns級別。

POSIX定時器提供的定時器API如下：

其中時間結(jié)構(gòu)itimerspec定義如下：該結(jié)構(gòu)和itimer的itimerval結(jié)構(gòu)用處和含義類似，只是提供了ns級別的精度

it_value表示定時間經(jīng)過這么長時間到時，當(dāng)定時器到時候，就會將it_interval的值賦給it_value。如果it_interval等于0，那么表示該定時器不是一個時間間隔定時器，一旦it_value到期后定時器就回到未啟動狀態(tài)。

timer_create(clockid_t clock_id, struct sigevent *evp, timer_t *timerid)

創(chuàng)建一個POSIX timer,在創(chuàng)建的時候，需要指出定時器的類型，定時器超時通知機(jī)制。創(chuàng)建成功后通過參數(shù)返回創(chuàng)建的定時器的ID。

參數(shù)clock_id用來指定定時器時鐘的類型，時鐘類型有以下6種：

CLOCK_REALTIME：系統(tǒng)實時時間，即日歷時間；

• CLOCK_MONOTONIC：從系統(tǒng)啟動開始到現(xiàn)在為止的時間；
• CLOCK_PROCESS_CPUTIME_ID：本進(jìn)程啟動到執(zhí)行到當(dāng)前代碼，系統(tǒng)CPU花費的時間；
• CLOCK_THREAD_CPUTIME_ID：本線程啟動到執(zhí)行到當(dāng)前代碼，系統(tǒng)CPU花費的時間；
• CLOCK_REALTIME_HR：CLOCK_REALTIME的細(xì)粒度（高精度）版本；
• CLOCK_MONOTONIC_HR：CLOCK_MONOTONIC的細(xì)粒度版本；

struct sigevent設(shè)置了定時器到期時的通知方式和處理方式等，結(jié)構(gòu)的定義如下：

如果sigevent傳入NULL，那么定時器到期會產(chǎn)生默認(rèn)的信號，對CLOCK_REALTIMER來說，默認(rèn)信號就是SIGALRM，如果要產(chǎn)生除默認(rèn)信號之外的其他信號，程序必須將evp->sigev_signo設(shè)置為期望的信號碼。

如果幾個定時器產(chǎn)生了同一個信號，處理程序可以用 sigev_value來區(qū)分是哪個定時器產(chǎn)生了信號。要實現(xiàn)這種功能，程序必須在為信號安裝處理程序時，使用struct sigaction的成員sa_flags中的標(biāo)志符SA_SIGINFO。

sigev_notify的值可取以下幾種：

• SIGEV_NONE：定時器到期后什么都不做，只提供通過timer_gettime和timer_getoverrun查詢超時信息。
• SIGEV_SIGNAL：定時器到期后，內(nèi)核會將sigev_signo所指定的信號，傳送給進(jìn)程，在信號處理程序中，si_value會被設(shè)定為sigev_value的值。
• SIGEV_THREAD：定時器到期后，內(nèi)核會以sigev_notification_attributes為線程屬性創(chuàng)建一個線程，線程的入口地址為sigev_notify_function，傳入sigev_value作為一個參數(shù)。

timer_settime(timer_t timerid, int flags, const struct itimerspec *value, struct itimerspect *ovalue)

創(chuàng)建POSIX定時器后，該定時器并沒有啟動，需要通過timer_settime()接口設(shè)置定時器的到期時間和周期觸發(fā)時間。

flags字段標(biāo)識到期時間是一個絕對時間還是一個相對時間。

如果flags的值為TIMER_ABSTIME，則value的值為一個絕對時間。否則，value為一個相對時間。

timer_getoverrun(timer_t timerid)

取得一個定時器的超限運行次數(shù)：有可能一個定時器到期了，而同一定時器上一次到期時產(chǎn)生的信號還處于掛起狀態(tài)。在這種情況下，其中的一個信號可能會丟失。這就是定時器超限。程序可以通過調(diào) 用timer_getoverrun來確定一個特定的定時器出現(xiàn)這種超限的次數(shù)。定時器超限只能發(fā)生在同一個定時器產(chǎn)生的信號上。由多個定時器，甚至是那 些使用相同的時鐘和信號的定時器，所產(chǎn)生的信號都會排隊而不會丟失。

執(zhí)行成功時，timer_getoverrun()會返回定時器初次到期與通知進(jìn)程(例如通過信號)定時器已到期之間額外發(fā)生的定時器到期次數(shù)。舉例來說，在我們之前的例子中，一個1ms的定時器運行了10ms，則此調(diào)用會返回9。如果超限運行的次數(shù)等于或大于DELAYTIMER_MAX，則此調(diào)用會返回DELAYTIMER_MAX。

執(zhí)行失敗時，此函數(shù)會返回-1并將errno設(shè)定會EINVAL，這個唯一的錯誤情況代表timerid指定了無效的定時器。

timer_delete (timer_t timerid)

刪除一個定時器：一次成功的timer_delete()調(diào)用會銷毀關(guān)聯(lián)到timerid的定時器并且返回0。執(zhí)行失敗時，此調(diào)用會返回-1并將errno設(shè)定會 EINVAL，這個唯一的錯誤情況代表timerid不是一個有效的定時器。

POSIX定時器通過調(diào)用內(nèi)核的posix_timer進(jìn)行實現(xiàn)，但glibc對POSIX timer進(jìn)行了一定的封裝，例如如果POSIX timer到期通知方式被設(shè)置為 SIGEV_THREAD 時，glibc 需要自己完成一些輔助工作，因為內(nèi)核無法在 Timer 到期時啟動一個新的線程。

可以看到 GLibc 發(fā)現(xiàn)用戶需要啟動新線程通知時，會自動調(diào)用 pthread_once 啟動一個輔助線程（__start_helper_thread），用 sigev_notify_attributes 中指定的屬性設(shè)置該輔助線程。

然后 glibc 啟動一個普通的 POSIX Timer，將其通知方式設(shè)置為：SIGEV_SIGNAL | SIGEV_THREAD_ID。這樣就可以保證內(nèi)核在 timer 到期時通知輔助線程。通知的 Signal 號為 SIGTIMER，并且攜帶一個包含了到期函數(shù)指針的數(shù)據(jù)。這樣，當(dāng)該輔助 Timer 到期時，內(nèi)核會通過 SIGTIMER 通知輔助線程，輔助線程可以在信號攜帶的數(shù)據(jù)中得到用戶設(shè)定的到期處理函數(shù)指針，利用該指針，輔助線程調(diào)用 pthread_create() 創(chuàng)建一個新的線程來調(diào)用該處理函數(shù)。這樣就實現(xiàn)了 POSIX 的定義。

3. 自定義定時器實現(xiàn)方案

在業(yè)務(wù)項目中，對于系統(tǒng)提供的定時器API往往很難滿足我們的需求：

itimer在進(jìn)程中每種timer類型(ITIMER_REAL, ITIMER_PROF, ITIMER_VIRT)只能使用一個，另外一點就是他是基于signal進(jìn)行超時提醒，不僅和alarm，sleep這些api沖突，而且在業(yè)務(wù)代碼中signal是個很不可控的機(jī)制，盡量都會減少使用。

POSIX定時器在itimer基礎(chǔ)上進(jìn)行了很大的改進(jìn)，解決了itimer的不足，可以說POSIX定時器可以滿足了業(yè)務(wù)很多的需求。

3.1 基于小根堆的定時器實現(xiàn)

小根堆定時器的實現(xiàn)方式，是最常見的一種實現(xiàn)定時器的方式。堆頂時鐘保存最先到期的定時器，基于事件觸發(fā)的定時器系統(tǒng)可以根據(jù)堆頂定時器到期時間，進(jìn)行睡眠。基于周期性睡眠的定時器系統(tǒng)，每次只需遍歷堆頂?shù)亩〞r器是否到期，即可。堆頂定時器超時后，繼續(xù)調(diào)整堆，使其保持為小根堆并同時對堆頂定時器進(jìn)行超時判斷。

小根堆定時器在插入時的時間復(fù)雜度在O(lgn)(n為插入時定時器堆的定時器數(shù)量)，定時器超時處理時調(diào)整堆的復(fù)雜度在所有定時器都超時情況下為：O(nlgn)。在一般情況下，小根堆的實現(xiàn)方式可滿足業(yè)務(wù)的基本需求。

3.2 基于時間輪的定時器實現(xiàn)

定時器的實現(xiàn)方式有兩種：一級時間輪和多級時間輪。

一級時間輪

一級時間輪如下圖所示：一個輪子(數(shù)組實現(xiàn))，輪子的每個槽(spoke)后面會掛一個timer列表，表示當(dāng)命中該spoke時，timer列表的所有定時器全部超時。

如果定時器輪的精度是1ms，那么spoke個數(shù)為2^10時，僅僅能夠表示1s，2^20表示17.476min.

如果精度為1s，那么spoke個數(shù)為2^10時，能夠表示17min，2^20表示12day.

所有這種一級時間輪的實現(xiàn)方式所帶來的空間復(fù)雜度還是不小的。特別是在需要跨度比較長的定時器時。基于此，就出現(xiàn)了多級時間輪，也就是linux2.6.16之前內(nèi)核所采用的定時器的實現(xiàn)方式。

簡單時間輪還有很多實現(xiàn)方式，此時時間輪的每個spoke的含義不再是時間精度，而是某個hashkey， 例如ACE當(dāng)中采用的簡單時間輪，輪子的含義：

( 觸發(fā)時間 >> 分辨率的位數(shù))&(spoke大小-1)

每個spoke所鏈接的timer列表可以采用很高效的multimap來實現(xiàn)，讓timer的插入時間可以降到O(lgn)，到期處理時間最壞為O(nlgn)，n為每個spoke中的timer個數(shù)。

多級時間輪

多級時間輪的實現(xiàn)方式被比作經(jīng)典的”水表實現(xiàn)方式”，一級時間輪只有一個進(jìn)制，多級時間輪采用了不同的進(jìn)制，最低級的時間輪每個spoke表示基本的時間精度，次級時間輪每個spoke表示的時間精度為最低級時間輪所能表示時間長度，依次類推。例如內(nèi)核的時間輪采用5級時間輪，每一級時間輪spoke個數(shù)從低級到高級分別為：8,6,6,6,6，所能表達(dá)的時間長度為：2^6 * 2^6 * 2^6 * 2^6 * 2^8 = 2^32 ticks，在系統(tǒng)tick精度為10ms時，內(nèi)核時間輪所能表示的時間跨度為42949672.96s，約為497天。

那么多級時間輪如何工作的呢：

• Insert：

定時器的插入，首先都要根據(jù)定時器的超時時間與每級時間輪所能表示的時長進(jìn)行比較，來覺得插入到那個輪子中，再根據(jù)當(dāng)前輪子已走的索引，計算出待插入定時器在該輪子中應(yīng)插入的spoke。

• Schedule：

多級時間輪定時器觸發(fā)機(jī)制為周期性tick出發(fā)，每個tick到來，最低級的tv1的spoke index都會+1，如果該spoke中有timer，那么就處理該timer list中的所有超時timer。

• Cascade：

Cascade可以翻譯成降級處理。每個tick到來，都只會去檢測最低級的tv1的時間輪，因為多級時間輪的設(shè)計決定了最低級的時間輪永遠(yuǎn)保存這最近要超時的定時器。

多級時間輪最重要的一個處理流程就是cascade，當(dāng)每一級(除了最高級)時間輪走到超出該級時間輪的范圍時，就會觸發(fā)上一級時間輪所在spoke+1的cascade過程，如果上一級時間輪也走出來時間輪的范圍，也同樣會觸發(fā)cascade過程，這是一個遞歸過程。

在cascade過程中存在一種極限情況，所有的時間輪都會進(jìn)行cascade處理，這個時候tv2, tv3, tv4, tv5的hlsit_head[0]都會發(fā)送變動，這個過程在定時數(shù)量比較大的情況下，會是一個比較耗時的處理流程。