1.Linux内核时钟系统和定时器实现
**Linux2.6.16之前**，内核只支持低精度时钟，内核定时器的工作方法：
在里面工作方法下，Linux2.6.16之前，内核软件定时器采用**timerwheel多级时间轮的实现机制，维护操作系统的所有定时风波。timerwheel的触发是基于系统tick周期性中断**。
所以说这之前，linux只能支持ms级别的时钟，随着时钟源硬件设备的精度增强和软件高精度计时的需求，有了高精度时钟的内核设计。
Linux2.6.16，内核支持了高精度的时钟中国linux操作系统，内核采用新的定时器hrtimer，其实现逻辑和Linux2.6.16之前定时器逻辑区别：
旧内核的定时器实现依赖于系统定时器硬件定期的tick，基于该tick，内核会扫描timerwheel处理超时风波，会更新jiffies，walltime(墙壁时间，现实时间)，process的使用时间等等工作。
新的内核不再见直接支持周期性的tick，新内核定时器框架采用了**基于风波触发，而不是原先的周期性触发**。新内核实现了hrtimer(highresolutiontimer)，hrtimer的设计目的，就是为了解决timewheel的缺点：
新内核的hrtimer的触发和设置不像之前在定期的tick中断中进行，而是动态调整的，即基于风波触发，**hrtimer的工作原理：通过将高精度时钟硬件的上次中断触发时间设置为黑红树中最早到期的Timer的时间，时钟到期后从黑红树中得到下一个Timer的到期时间，并设置硬件，这般循环反复。
在高精度时钟模式下，操作系统内核依然须要周期性的tick中断，便于刷新内核的一些任务。上面可以晓得，hrtimer是基于风波的，不会周期性出发tick中断，所以为了实现周期性的tick中断(dynamictick**)：系统创建了一个模拟tick时钟的特殊hrtimer，将其超时时间设置为一个tick时长，在超时回去后，完成对应的工作，之后再度设置下一个tick的超时时间，借此达到周期性tick中断的需求。
引入了dynamictick,是为了才能在使用高精度时钟的同时节省能源,，这样会形成tickless情况下，会跳过一些tick。这儿只是简单介绍linux 定时器 驱动，有兴趣可以读kernel源码。
上图1是**Linux2.6.16**以来内核定时器实现的结构，
新内核对相关的时间硬件设备进行了统一的封装，定义了主要有下边两个结构：
当前内核同时存在新旧timerwheel和hrtimer两套timer的实现，内核启动后会进行从低精度模式到高精度时钟模式的切换，hrtimer模拟的tick中断将驱动传统的低精度定时器系统（基于时间轮）和内核进程调度。
内核定时器系统降低了hrtimer以后，对于用户层开放的定时器相关插口基本都是通过hrtimer进行实现的，从内核源码可以看见:
1
2
3
4
5
6
7
8
9
https://github.com/torvalds/linux/blob/master/kernel/time/hrtimer.c
* 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插口：
1
2
3
4
alarm()
sleep()
usleep()
nanosleep()
alarm()函数可以设置一个定时器，在特定时间超时，并形成SIGALRM讯号，倘若不忽视或不捕捉该讯号，该进程会被中止。
1
2
3
unsigned int alarm(unsigned int seconds);
return：0或到期剩余秒数
这么alarm在是**怎样实现**的？Glibc中alarm是基于间隔定时器itimer来实现的(文章旁边会说到itimer是基于hrtimer实现的)。如下alarm在库函数下的实现,alarm调用了setitimer系统调用：
1
2
3
4
5
6
7
8
9
10
11
12
https://github.com/lattera/glibc/blob/master/sysdeps/unix/alarm.c
unsigned int
alarm (seconds)
unsigned int seconds;
{
...
if (__setitimer (ITIMER_REAL, &new, &old) < 0)
return 0;
...
}
libc_hidden_def (alarm)
sleep和alarm的功能类似，不过sleep会让进程挂起，在定时器超时内核会形成SIGALRM讯号，假若不忽视或不捕捉该讯号，该进程会被中止。
这么sleep是**怎样实现**的？Glibc的sleep实现如下：可见虽然调用alarm实现的，在alarm的基础上注册了SIGALRM讯号处理函数，用于在定时器到期时，捕获到讯号，回到睡眠的地方。所以虽然可以看出sleep就是对alarm的特化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
https://github.com/lattera/glibc/blob/master/sysdeps/posix/sleep.c
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支持精度更高的微妙级别的定时操作，
1
2
3
4
5
6
7
8
9
10
11
12
https://github.com/lattera/glibc/blob/master/sysdeps/unix/sysv/linux/usleep.c
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实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
https://github.com/anonymalias/glibc/blob/master/sysdeps/unix/bsd/usleep.c
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()glibc的API是直接调用linux内核的nanosleep，内核的nanosleep采用了hrtimer进行实现。
**alarm(),sleep()系列，以及旁边的间隔定时器itimer都是基于SIGALRM讯号进行触发的。所以它们是不能同时使用的**。
2.2间隔定时器itimer
间隔定时器的插口如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 */
suseconds_t tv_usec; /* microseconds */
};
可以通过调用里面两个API插口来设置和获取间隔定时器信息。系统为**每位进程**提供了3种itimer，每种定时器在不同时间域递减，当定时器超时，还会向进程发送一个讯号，但是重置定时器。3种定时器的类型linux vi ，如下表所示：
取值涵义讯号发送
ITIMER_REAL
定时真实时间，与alarm类型相同。
SIGALRM
ITIMER_VIRT
定时进程在用户态下的实际执行时间。
SIGVTALRM
ITIMER_PROF
定时进程在用户态和核态度下的实际执行时间。
SIGPROF
表1参数which与定时器类型
在Linux2.6.16之前，itimer的实现是基于内核定时器timerwheel封装成的定时器插口。内核封装的定时器插口是提供给其他内核模块使用，也是其他定时器的基础。itimer通过内核定时器的封装，生成提供给用户层使用的插口setitimer和getitimer。内核定时器timerwheel提供的内核态调用插口为:可参考
1
2
3
4
5
https://github.com/torvalds/linux/blob/master/kernel/time/timer.c
add_timer()
del_timer()
init_timer()
在Linux2.6.16以来，itimer不再采用基于timerwheel的内核定时器进行实现。而是换成了高精度的内核定时器hrtimer进行实现。具体实现可参考：
假如定时器超时时，进程是处于运行状态，这么超时的讯号会被立即传送给该进程，否则讯号会被延后传送，延后时间要按照系统的负载情况。所以这儿有一个BUG：**当系统负载很重的情况下，对于ITIMER_REAL定时器有可能在上一次超时讯号传递完成前再度超时，这样才会造成第二次超时的讯号遗失**。
每位进程中同一种定时器只能使用一次。
该系统调用在POSIX.1-2001中定义了，但在POSIX.1-2008中已被废弃。所以建议使用POSIX定时器API（timer_gettime,timer_settime）取代。
函数alarm本质上设置的是低精确、非重载的ITIMER_REAL类定时器，它只能精确到秒，但是每次设置只能形成一次定时。函数setitimer设置的定时器则不同，它们不但可以计时到微妙（理论上），能够手动循环定时。在一个Unix进程中，不能同时使用alarm和ITIMER_REAL类定时器。
下边是测试代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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.3POSIX定时器
POSIX定时器的是**为了解决间隔定时器itimer的以下问题**：
POSIX定时器提供的定时器API如下：
1
2
3
4
5
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级别的精度
1
2
3
4
5
6
7
8
9
10
11
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_tclock_id,structsigevent*evp,timer_t*timerid)
创建一个POSIXtimer,在创建的时侯，须要强调定时器的类型，定时器超时通知机制。创建成功后通过参数返回创建的定时器的ID。
参数clock_id拿来指定定时器时钟的类型，时钟类型有以下6种：
structsigevent设置了定时器到期时的通知方法和处理方法等，结构的定义如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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来分辨是那个定时器形成了讯号。要实现这些功能，程序必须在为讯号安装处理程序时，使用structsigaction的成员sa_flags中的标志符SA_SIGINFO。
sigev_notify的值可取以下几种：
timer_settime(timer_ttimerid,intflags,conststructitimerspec*value,structitimerspect*ovalue)
创建POSIX定时器后，该定时器并没有启动，须要通过timer_settime()插口设置定时器的到期时间和周期触发时间。
flags数组标示到期时间是一个绝对时间还是一个相对时间。
1
2
3
4
https://github.com/lattera/glibc/blob/master/bits/time.h
/* Flag to indicate time is absolute. */
假如flags的值为TIMER_ABSTIME，则value的值为一个**绝对时间。否则，value为一个相对时间**。
timer_getoverrun(timer_ttimerid)
取得一个定时器的超限运行次数：有可能一个定时器到期了，而同一定时器上一次到期时形成的讯号还处于挂起状态。在这些情况下，其中的一个讯号可能会遗失。这就是定时器超限。程序可以通过调用timer_getoverrun来确定一个特定的定时器出现这些超限的次数。定时器超限只能发生在同一个定时器形成的讯号上。由多个定时器，甚至是那些使用相同的时钟和讯号的定时器，所形成的讯号就会排队而不会遗失。
执行成功时，timer_getoverrun()会返回定时器初次到期与通知进程(比如通过讯号)定时器已到期之间额外发生的定时器到期次数。举例来说，在我们之前的反例中，一个1ms的定时器运行了10ms，则此调用会返回9。假如超限运行的次数等于或小于DELAYTIMER_MAX，则此调用会返回DELAYTIMER_MAX。
执行失败时，此函数会返回-1并将errno设定会EINVAL，这个惟一的错误情况代表timerid指定了无效的定时器。
timer_delete(timer_ttimerid)
删掉一个定时器：一次成功的timer_delete()调用会销毁关联到timerid的定时器而且返回0。执行失败时，此调用会返回-1并将errno设定会EINVAL，这个惟一的错误情况代表timerid不是一个有效的定时器。
POSIX定时器通过调用内核的posix_timer进行实现，但glibc对POSIXtimer进行了一定的封装，比如假如POSIXtimer到期通知形式被设置为SIGEV_THREAD时，glibc须要自己完成一些辅助工作，由于内核未能在Timer到期时启动一个新的线程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
https://github.com/lattera/glibc/blob/master/nptl/sysdeps/unix/sysv/linux/timer_create.c
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启动一个普通的POSIXTimer，将其通知方法设置为：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^32ticks，在系统tick精度为10ms时，内核时间轮所能表示的时间跨径为42949672.96s，约为497天。
这么多级时间轮怎样工作的呢：
定时器的插入，首先都要按照定时器的超时时间与每级时间轮所能表示的时长进行比较，来感觉插入到哪个轮子中，再依照当前轮子已走的索引，估算出待插入定时器在该轮子中应插入的spoke。
1
2
3
4
5
多级时间轮定时器触发机制为周期性tick出发，每位tick到来，最低级的tv1的spokeindex就会+1，假若该spoke中有timer，这么就处理该timerlist中的所有超时timer。
Cascade可以翻译成降级处理。每位tick到来，都只会去检查最低级的tv1的时间轮，由于多级时间轮的设计决定了最低级的时间轮永远保存这近来要超时的定时器。
多级时间轮最重要的一个处理流程就是cascade，当每一级(不仅最中级)时间轮走到超出该级时间轮的范围时linux 定时器 驱动，才会触发上一级时间轮所在spoke+1的cascade过程，假如上一级时间轮也走下来时间轮的范围，也同样会触发cascade过程，这是一个递归过程。
在cascade过程中存在一种极限情况，所有的时间轮就会进行cascade处理，这个时侯tv2,tv3,tv4,tv5的hlsit_head[0]就会发送变动，这个过程在定时数目比较大的情况下，会是一个比较历时的处理流程。
参考：
%E5%B9%B6%E5%8F%91/2014/07/26/%E5%AE%9A%E6%97%B6%E5%99%A8%EF%BC%88Timer%EF%BC%89%E7%9A%84%E5%AE%9E%E7%8E%B0.html
本文原创地址：//gulass.cn/lnhdsqcdjddg.html编辑：刘遄，审核员：暂无
