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

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

• 系統(tǒng)啟動后，會讀取時(shí)鐘源設(shè)備(RTC, HPET，PIT…),初始化當(dāng)前系統(tǒng)時(shí)間；

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

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

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

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

所以說這之前，linux只能支持ms級別的時(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)核會掃描timer wheel處理超時(shí)事件，會更新jiffies，wall time(墻上時(shí)間，現(xiàn)實(shí)時(shí)間)，process的使用時(shí)間等等工作。

新的內(nèi)核不再會直接支持周期性的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級別的精度，hrtimer可以支持ns級別；
• Timer wheel與內(nèi)核其他模塊的高耦合性；

新內(nèi)核的hrtimer的觸發(fā)和設(shè)置不像之前在定期的tick中斷中進(jìn)行，而是動態(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是基于事件的，不會周期性出發(fā)tick中斷，所以為了實(shí)現(xiàn)周期性的tick中斷(dynamic tick)：系統(tǒng)創(chuàng)建了一個(gè)模擬 tick 時(shí)鐘的特殊 hrtimer，將其超時(shí)時(shí)間設(shè)置為一個(gè)tick時(shí)長，在超時(shí)回來后，完成對應(yīng)的工作，然后再次設(shè)置下一個(gè)tick的超時(shí)時(shí)間，以此達(dá)到周期性tick中斷的需求。

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

 

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

新內(nèi)核對相關(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)核啟動后會進(jìn)行從低精度模式到高精度時(shí)鐘模式的切換，hrtimer模擬的tick中斷將驅(qū)動傳統(tǒng)的低精度定時(shí)器系統(tǒng)（基于時(shí)間輪）和內(nèi)核進(jìn)程調(diào)度。

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

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

 

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

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

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

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

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

alarm:

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

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

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

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

sleep:

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

 

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

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

}
weak_alias (__sleep, sleep)

usleep:

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

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實(shí)現(xiàn)如下：

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是直接調(diào)用linux內(nèi)核的nanosleep，內(nèi)核的nanosleep采用了hrtimer進(jìn)行實(shí)現(xiàn)。

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

2.2 間隔定時(shí)器itimer

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

#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);
結(jié)構(gòu)定義：
struct itimerval {
    struct timeval it_interval; /* next value ：間隔時(shí)間*/
    struct timeval it_value;    /* current value：到期時(shí)間*/
};
struct timeval {
    time_t      tv_sec;         /* seconds */
    s

可以通過調(diào)用上面兩個(gè)API接口來設(shè)置和獲取間隔定時(shí)器信息。系統(tǒng)為每個(gè)進(jìn)程提供了3種itimer，每種定時(shí)器在不同時(shí)間域遞減，當(dāng)定時(shí)器超時(shí)，就會向進(jìn)程發(fā)送一個(gè)信號，并且重置定時(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)用接口為:可參考

add_timer() 
del_timer() 
init_timer()

在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í)的信號會被立刻傳送給該進(jìn)程，否則信號會被延遲傳送，延遲時(shí)間要根據(jù)系統(tǒng)的負(fù)載情況。所以這里有一個(gè)BUG：當(dāng)系統(tǒng)負(fù)載很重的情況下，對于ITIMER_REAL定時(shí)器有可能在上一次超時(shí)信號傳遞完成前再次超時(shí)，這樣就會導(dǎo)致第二次超時(shí)的信號丟失。

每個(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í)到微妙（理論上），還能自動循環(huán)定時(shí)。在一個(gè)Unix進(jìn)程中，不能同時(shí)使用alarm和ITIMER_REAL類定時(shí)器。

下面是測試代碼：

#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;

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

    //間隔定時(shí)器間隔：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定時(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í)器到期后，只能通過信號(SIGALRM,SIGVTALRM,SIGPROF)的方式通知進(jìn)程，POSIX定時(shí)器到期后不僅可以通過信號進(jìn)行通知，還可以使用自定義信號，還可以通過啟動一個(gè)線程來進(jìn)行通知。
• itimer支持us級別，POSIX定時(shí)器支持ns級別。

POSIX定時(shí)器提供的定時(shí)器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);

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

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

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

it_value表示定時(shí)間經(jīng)過這么長時(shí)間到時(shí)，當(dāng)定時(shí)器到時(shí)候，就會將it_interval的值賦給it_value。如果it_interval等于0，那么表示該定時(shí)器不是一個(gè)時(shí)間間隔定時(shí)器，一旦it_value到期后定時(shí)器就回到未啟動狀態(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)啟動開始到現(xiàn)在為止的時(shí)間；
• CLOCK_PROCESS_CPUTIME_ID：本進(jìn)程啟動到執(zhí)行到當(dāng)前代碼，系統(tǒng)CPU花費(fèi)的時(shí)間；
• CLOCK_THREAD_CPUTIME_ID：本線程啟動到執(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)的定義如下：

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

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

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

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

sigev_notify的值可取以下幾種：

• SIGEV_NONE：定時(shí)器到期后什么都不做，只提供通過timer_gettime和timer_getoverrun查詢超時(shí)信息。
• SIGEV_SIGNAL：定時(shí)器到期后，內(nèi)核會將sigev_signo所指定的信號，傳送給進(jìn)程，在信號處理程序中，si_value會被設(shè)定為sigev_value的值。
• SIGEV_THREAD：定時(shí)器到期后，內(nèi)核會以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í)器并沒有啟動，需要通過timer_settime()接口設(shè)置定時(shí)器的到期時(shí)間和周期觸發(fā)時(shí)間。

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

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

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

timer_getoverrun(timer_t timerid)

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

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

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

timer_delete (timer_t timerid)

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

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

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 發(fā)現(xiàn)用戶需要啟動新線程通知時(shí)，會自動調(diào)用 pthread_once 啟動一個(gè)輔助線程（__start_helper_thread），用 sigev_notify_attributes 中指定的屬性設(shè)置該輔助線程。

然后 glibc 啟動一個(gè)普通的 POSIX Timer，將其通知方式設(shè)置為：SIGEV_SIGNAL | SIGEV_THREAD_ID。這樣就可以保證內(nèi)核在 timer 到期時(shí)通知輔助線程。通知的 Signal 號為 SIGTIMER，并且攜帶一個(gè)包含了到期函數(shù)指針的數(shù)據(jù)。這樣，當(dāng)該輔助 Timer 到期時(shí)，內(nèi)核會通過 SIGTIMER 通知輔助線程，輔助線程可以在信號攜帶的數(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)目中，對于系統(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ī)制，盡量都會減少使用。

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)行睡眠。基于周期性睡眠的定時(shí)器系統(tǒng)，每次只需遍歷堆頂?shù)亩〞r(shí)器是否到期，即可。堆頂定時(shí)器超時(shí)后，繼續(xù)調(diào)整堆，使其保持為小根堆并同時(shí)對堆頂定時(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)方式有兩種：一級時(shí)間輪和多級時(shí)間輪。

一級時(shí)間輪

一級時(shí)間輪如下圖所示：一個(gè)輪子(數(shù)組實(shí)現(xiàn))，輪子的每個(gè)槽(spoke)后面會掛一個(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.

所有這種一級時(shí)間輪的實(shí)現(xiàn)方式所帶來的空間復(fù)雜度還是不小的。特別是在需要跨度比較長的定時(shí)器時(shí)。基于此，就出現(xiàn)了多級時(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ù)。

 

多級時(shí)間輪

多級時(shí)間輪的實(shí)現(xiàn)方式被比作經(jīng)典的”水表實(shí)現(xiàn)方式”，一級時(shí)間輪只有一個(gè)進(jìn)制，多級時(shí)間輪采用了不同的進(jìn)制，最低級的時(shí)間輪每個(gè)spoke表示基本的時(shí)間精度，次級時(shí)間輪每個(gè)spoke表示的時(shí)間精度為最低級時(shí)間輪所能表示時(shí)間長度，依次類推。例如內(nèi)核的時(shí)間輪采用5級時(shí)間輪，每一級時(shí)間輪spoke個(gè)數(shù)從低級到高級分別為：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天。

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

 

• Insert：

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

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

• Cascade：

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

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

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