1. Linux內核時鐘系統和定時器實現

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

• 系統啟動后，會讀取時鐘源設備(RTC, HPET，PIT…),初始化當前系統時間；

• 內核會根據HZ(系統定時器頻率，節拍率)參數值，設置時鐘事件設備，啟動tick(節拍)中斷。HZ表示1秒種產生多少個時鐘硬件中斷，tick就表示連續兩個中斷的間隔時間。在我電腦上，HZ=250， 一個tick = 1/HZ, 所以默認一個tick為4ms。

cat /boot/config-`uname -r` | grep 'CONFIG_HZ='
CONFIG_HZ=250

• 設置時鐘事件設備后，時鐘事件設備會定時產生一個tick中斷，觸發時鐘中斷處理函數，更新系統時鐘,并檢測timer wheel，進行超時事件的處理。

在上面工作方式下，Linux 2.6.16 之前，內核軟件定時器采用timer wheel多級時間輪的實現機制，維護操作系統的所有定時事件。timer wheel的觸發是基于系統tick周期性中斷。

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

Linux 2.6.16 ，內核支持了高精度的時鐘，內核采用新的定時器hrtimer，其實現邏輯和Linux 2.6.16 之前定時器邏輯區別：

• hrtimer采用紅黑樹進行高精度定時器的管理，而不是時間輪；

• 高精度時鐘定時器不在依賴系統的tick中斷，而是基于事件觸發。

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

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

• 低精度；timer wheel只能支持ms級別的精度，hrtimer可以支持ns級別；

• Timer wheel與內核其他模塊的高耦合性；

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

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

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

上圖1是Linux 2.6.16以來內核定時器實現的結構，

新內核對相關的時間硬件設備進行了統一的封裝，定義了主要有下面兩個結構：

• 時鐘源設備(closk source device)：抽象那些能夠提供計時功能的系統硬件，比如 RTC(Real Time Clock)、TSC(Time Stamp Counter)，HPET，ACPI PM-Timer，PIT等。不同時鐘源提供的精度不一樣，現在pc大都是支持高精度模式(high-resolution mode)也支持低精度模式(low-resolution mode)。

• 時鐘事件設備(clock event device)：系統中可以觸發 one-shot（單次）或者周期性中斷的設備都可以作為時鐘事件設備。

當前內核同時存在新舊timer wheel 和 hrtimer兩套timer的實現，內核啟動后會進行從低精度模式到高精度時鐘模式的切換，hrtimer模擬的tick中斷將驅動傳統的低精度定時器系統（基于時間輪）和內核進程調度。

內核定時器系統增加了hrtimer之后，對于用戶層開放的定時器相關接口基本都是通過hrtimer進行實現的，從內核源碼可以看到:

   
    *  These timers are currently used for:
    *   - itimers
    *   - POSIX timers
    *   - nanosleep
    *   - precise in-kernel timing
    *

2. 用戶層定時器API接口

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

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

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

alarm()
sleep()
usleep()
nanosleep()

alarm:

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

#include <unistd.h>
unsigned int alarm(unsigned int seconds);
                                              return：0或到期剩余秒數

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

unsigned int 
alarm (seconds)
     unsigned int seconds;
{
  ...
  if (__setitimer (ITIMER_REAL, &new, &old) < 0)
    return 0;
  ...
}
libc_hidden_def (alarm)

sleep:

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

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

unsigned int
__sleep (unsigned int seconds)
{
    ...
    struct sigaction act, oact;
    ...
    //注冊信號回調函數
    act.sa_handler = sleep_handler;
    act.sa_flags = 0;
    act.sa_mask = oset;
    if (sigaction (SIGALRM, &act, &oact) < 0)
        return seconds;
    ...
    //調用alarm API進行操作
    remaining = alarm (seconds);

}
weak_alias (__sleep, sleep)

usleep:

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

int usleep (useconds_t useconds)
{
  struct timespec ts = { .tv_sec = (long int) (useconds / 1000000),
             .tv_nsec = (long int) (useconds % 1000000) * 1000ul };

  /* Note the usleep() is a cancellation point.  But since we call
     nanosleep() which itself is a cancellation point we do not have
     to do anything here.  */
  return __nanosleep (&ts, NULL);
}

Bsd的usleep實現如下：

int usleep (useconds)
     useconds_t useconds;
{
  struct timeval delay;

  delay.tv_sec = 0;
  delay.tv_usec = useconds;

  return __select (0, (fd_set *) NULL, (fd_set *) NULL, (fd_set *) NULL,
           &delay);
}

nanosleep:

nanosleep()glibc的API是直接調用linux內核的nanosleep，內核的nanosleep采用了hrtimer進行實現。

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

2.2 間隔定時器itimer

間隔定時器的接口如下：

#include <sys/time.h>

int getitimer(int which, struct itimerval *curr_value);
int setitimer(int which, const struct itimerval *new_value,
        struct itimerval *old_value);
結構定義：
struct itimerval {
    struct timeval it_interval; /* next value ：間隔時間*/
    struct timeval it_value;    /* current value：到期時間*/
};
struct timeval {
    time_t      tv_sec;         /* seconds */
    s

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

表1 參數which與定時器類型

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

add_timer() 
del_timer() 
init_timer()

在Linux 2.6.16 以來，itimer不再采用基于timer wheel的內核定時器進行實現。而是換成了高精度的內核定時器hrtimer進行實現。

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

每個進程中同一種定時器只能使用一次。

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

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

下面是測試代碼：

#include <unistd.h>
#include <signal.h>
#include <sys/time.h>

#include <iostream>

void sig_handler(int signo)
{
    std::cout<<"recieve sigal: "<<signo<<std::endl;
}

int main()
{
    signal(SIGALRM, sig_handler);

    struct itimerval timer_set;

    //啟動時間（5s后啟動）
    timer_set.it_value.tv_sec = 5;
    timer_set.it_value.tv_usec = 0;

    //間隔定時器間隔：2s
    timer_set.it_interval.tv_sec = 2;
    timer_set.it_interval.tv_usec = 0;

    if(setitimer(ITIMER_REAL, &timer_set, NULL) < 0)
    {
        std::cout<<"start timer failed..."<<std::endl;
        return 0;
    }

    int temp;
    std::cin>>temp;

    return 0;
}

2.3 POSIX定時器

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

• 一個進程同一時刻只能有一個同一種類型(ITIMER_REAL, ITIMER_PROF, ITIMER_VIRT)的itimer。POSIX定時器在一個進程中可以創建任意多個timer。

• itimer定時器到期后，只能通過信號(SIGALRM,SIGVTALRM,SIGPROF)的方式通知進程，POSIX定時器到期后不僅可以通過信號進行通知，還可以使用自定義信號，還可以通過啟動一個線程來進行通知。

• itimer支持us級別，POSIX定時器支持ns級別。

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

int timer_create(clockid_t clock_id, struct sigevent *evp, timer_t *timerid)；
int timer_settime(timer_t timerid, int flags, const struct itimerspec *value, struct itimerspect *ovalue);
int timer_gettime(timer_t timerid,struct itimerspec *value);
int timer_getoverrun(timer_t timerid);
int timer_delete (timer_t timerid);

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

struct itimerspec
{
    struct timespec it_interval;    // 時間間隔
    struct timespec it_value;       // 首次到期時間
};

struct timespec
{
    time_t  tv_sec    //Seconds.
    long    tv_nsec   //Nanoseconds.
};

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

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

創建一個POSIX timer,在創建的時候，需要指出定時器的類型，定時器超時通知機制。創建成功后通過參數返回創建的定時器的ID。

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

CLOCK_REALTIME：系統實時時間，即日歷時間；

• CLOCK_MONOTONIC：從系統啟動開始到現在為止的時間；

• CLOCK_PROCESS_CPUTIME_ID：本進程啟動到執行到當前代碼，系統CPU花費的時間；

• CLOCK_THREAD_CPUTIME_ID：本線程啟動到執行到當前代碼，系統CPU花費的時間；

• CLOCK_REALTIME_HR：CLOCK_REALTIME的細粒度（高精度）版本；

• CLOCK_MONOTONIC_HR：CLOCK_MONOTONIC的細粒度版本；

struct sigevent設置了定時器到期時的通知方式和處理方式等，結構的定義如下：

struct sigevent
{
    int sigev_notify;   //設置定時器到期后的行為
    int sigev_signo;    //設置產生信號的信號碼
    union sigval   sigev_value; //設置產生信號的值
    void (*sigev_notify_function)(union sigval);//定時器到期，從該地址啟動一個線程
    pthread_attr_t *sigev_notify_attributes;    //創建線程的屬性
}

union sigval
{
    int sival_int;  //integer value
    void *sival_ptr; //pointer value
}

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

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

sigev_notify的值可取以下幾種：

• SIGEV_NONE：定時器到期后什么都不做，只提供通過timer_gettime和timer_getoverrun查詢超時信息。

• SIGEV_SIGNAL：定時器到期后，內核會將sigev_signo所指定的信號，傳送給進程，在信號處理程序中，si_value會被設定為sigev_value的值。

• SIGEV_THREAD：定時器到期后，內核會以sigev_notification_attributes為線程屬性創建一個線程，線程的入口地址為sigev_notify_function，傳入sigev_value作為一個參數。

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

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

flags字段標識到期時間是一個絕對時間還是一個相對時間。

/* Flag to indicate time is absolute.  */
#   define TIMER_ABSTIME        1

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

timer_getoverrun(timer_t timerid)

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

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

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

timer_delete (timer_t timerid)

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

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

int
timer_create (clock_id, evp, timerid)
     clockid_t clock_id;
     struct sigevent *evp;
     timer_t *timerid;
{
    if (evp == NULL || __builtin_expect (evp->sigev_notify != SIGEV_THREAD, 1))
    {
        ...
    }
    else
    {
          ...
          /* Create the helper thread.  */
          pthread_once (&__helper_once, __start_helper_thread);
          ...
    }
    ...
}

可以看到 GLibc 發現用戶需要啟動新線程通知時，會自動調用 pthread_once 啟動一個輔助線程（__start_helper_thread），用 sigev_notify_attributes 中指定的屬性設置該輔助線程。

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

3. 自定義定時器實現方案

在業務項目中，對于系統提供的定時器API往往很難滿足我們的需求：

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

POSIX定時器在itimer基礎上進行了很大的改進，解決了itimer的不足，可以說POSIX定時器可以滿足了業務很多的需求。

3.1 基于小根堆的定時器實現

小根堆定時器的實現方式，是最常見的一種實現定時器的方式。堆頂時鐘保存最先到期的定時器，基于事件觸發的定時器系統可以根據堆頂定時器到期時間，進行睡眠。基于周期性睡眠的定時器系統，每次只需遍歷堆頂的定時器是否到期，即可。堆頂定時器超時后，繼續調整堆，使其保持為小根堆并同時對堆頂定時器進行超時判斷。

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

3.2 基于時間輪的定時器實現

定時器的實現方式有兩種：一級時間輪和多級時間輪。

一級時間輪

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

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

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

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

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

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

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

多級時間輪

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

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

• Insert：

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

#define WHEEL_THRESHOLD_LEVEL_1 (0x01 << 8) 
#define WHEEL_THRESHOLD_LEVEL_2 (0x01 << (8 + 6))
#define WHEEL_THRESHOLD_LEVEL_3 (0x01 << (8 + 2 * 6))
#define WHEEL_THRESHOLD_LEVEL_4 (0x01 << (8 + 3 * 6))
#define WHEEL_THRESHOLD_LEVEL_5 (0x01 << (8 + 4 * 6))

• Schedule：

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

• Cascade：

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

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

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