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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. 用戶層定時(shí)器API接口

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

2.1 常見定時(shí)功能的API：sleep系列

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

alarm:

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

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

sleep:

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

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

usleep:

usleep支持精度更高的微妙級(jí)別的定時(shí)操作，

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

nanosleep:

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

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

2.2 間隔定時(shí)器itimer

間隔定時(shí)器的接口如下：

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

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

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

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

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

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

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

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

下面是測(cè)試代碼：

2.3 POSIX定時(shí)器

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

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

POSIX定時(shí)器提供的定時(shí)器API如下：

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

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

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

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

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

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

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

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

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

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

sigev_notify的值可取以下幾種：

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

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

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

flags字段標(biāo)識(shí)到期時(shí)間是一個(gè)絕對(duì)時(shí)間還是一個(gè)相對(duì)時(shí)間。

如果flags的值為TIMER_ABSTIME，則value的值為一個(gè)絕對(duì)時(shí)間。否則，value為一個(gè)相對(duì)時(shí)間。

timer_getoverrun(timer_t timerid)

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

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

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

timer_delete (timer_t timerid)

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

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

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

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

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

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

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

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

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

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

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

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

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

一級(jí)時(shí)間輪

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

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

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

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

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

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

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

多級(jí)時(shí)間輪

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

那么多級(jí)時(shí)間輪如何工作的呢：

• Insert：

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

• Schedule：

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

• Cascade：

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

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

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