下定时器的实现方式分析.docx
《下定时器的实现方式分析.docx》由会员分享，可在线阅读，更多相关《下定时器的实现方式分析.docx（13页珍藏版）》请在冰点文库上搜索。
下定时器的实现方式分析
Linux下定时器的实现方式分析
定时器属于基本的基础组件，不管是用户空间的程序开发，还是内核空间的程序开发，很多时候都需要有定时器作为基础组件的支持，但使用场景的不同，对定时器的实现考虑也不尽相同，本文讨论了在Linux环境下，应用层和内核层的定时器的各种实现方法，并分析了各种实现方法的利弊以及适宜的使用环境。
首先，给出一个基本模型，定时器的实现，需要具备以下几个行为，这也是在后面评判各种定时器实现的一个基本模型[1]：
StartTimer（Interval,TimerId,ExpiryAction）
注册一个时间间隔为Interval后执行ExpiryAction的定时器实例，其中，返回TimerId以区分在定时器系统中的其他定时器实例。
StopTimer（TimerId）
根据TimerId找到注册的定时器实例并执行Stop。
PerTickBookkeeping（）
在一个Tick内，定时器系统需要执行的动作，它最主要的行为，就是检查定时器系统中，是否有定时器实例已经到期。
注意，这里的Tick实际上已经隐含了一个时间粒度（granularity）的概念。
ExpiryProcessing（）
在定时器实例到期之后，执行预先注册好的ExpiryAction行为。
上面说了基本的定时器模型，但是针对实际的使用情况，又有以下2种基本行为的定时器：
Single-ShotTimer
这种定时器，从注册到终止，仅仅只执行一次。
RepeatingTimer
这种定时器，在每次终止之后，会自动重新开始。
本质上，可以认为RepeatingTimer是在Single-ShotTimer终止之后，再次注册到定时器系统里的Single-ShotTimer，因此，在支持Single-ShotTimer的基础上支持RepeatingTimer并不算特别的复杂。
在2.4的内核中，并没有提供POSIXtimer[2]的支持，要在进程环境中支持多个定时器，只能自己来实现，好在Linux提供了setitimer
（2）的接口。
它是一个具有间隔功能的定时器（intervaltimer），但如果想在进程环境中支持多个计时器，不得不自己来管理所有的计时器。
setitimer
（2）的定义如下：
清单1.setitimer的原型
#includesys/time.hintsetitimer（intwhich,conststructitimerval*new_value,structitimerval*old_value）；
setitimer能够在Timer到期之后，自动再次启动自己，因此，用它来解决Single-ShotTimer和RepeatingTimer的问题显得很简单。
该函数可以工作于3种模式：
ITIMER_REAL以实时时间（realtime）递减，在到期之后发送SIGALRM信号
ITIMER_VIRTUAL仅进程在用户空间执行时递减，在到期之后发送SIGVTALRM信号
ITIMER_PROF进程在用户空间执行以及内核为该进程服务时（典型如完成一个系统调用）都会递减，与ITIMER_VIRTUAL共用时可度量该应用在内核空间和用户空间的时间消耗情况，在到期之后发送SIGPROF信号
定时器的值由下面的结构定义：
structitimerval{
structtimevalit_interval；/*nextvalue*/
structtimevalit_value；/*currentvalue*/
}；
structtimeval{
longtv_sec；/*seconds*/
longtv_usec；/*microseconds*/
}；
setitimer（）以new_value设置特定的定时器，如果old_value非空，则它返回which类型时间间隔定时器的前一个值。
定时器从it_value递减到零，然后产生一个信号，并重新设置为it_interval，如果此时it_interval为零，则该定时器停止。
任何时候，只要it_value设置为零，该定时器就会停止。
由于setitimer（）不支持在同一进程中同时使用多次以支持多个定时器，因此，如果需要同时支持多个定时实例的话，需要由实现者来管理所有的实例。
用setitimer（）和链表，可以构造一个在进程环境下支持多个定时器实例的Timer，在一般的实现中的PerTickBookkeeping时，会递增每个定时器的elapse值，直到该值递增到最初设定的interval则表示定时器到期。
基于链表实现的定时器可以定义为：
typedefinttimer_id；
/*
*Thetypeofcallbackfunctiontobecalledbytimerschedulerwhenatimer
*hasexpired.
*
*@paramidThetimerid.
*@paramuser_dataTheuserdata.
*$paramlenThelengthofuserdata.
*/
typedefinttimer_expiry（timer_idid,void*user_data,intlen）；
/*
*Thetypeofthetimer
*/
structtimer{
LIST_ENTRY（timer）entries；/*listentry*/
timer_idid；/*timerid*/
intinterval；/*timerinterval（second）*/
intelapse；/*0-interval*/
timer_expiry*cb；/*callifexpiry*/
void*user_data；/*callbackarg*/
intlen；/*user_datalength*/
}；
定时器的时间间隔以interval表示，而elapse则在PerTickBookkeeping（）时递增，直到interval表示定时器中止，此时调用回调函数cb来执行相关的行为，而user_data和len为用户可以传递给回调函数的参数。
所有的定时器实例以链表来管理：
/*
*Thetimerlist
*/
structtimer_list{
LIST_HEAD（listheader,timer）header；/*listheader*/
intnum；/*timerentrynumber*/
intmax_num；/*maxentrynumber*/
void（*old_sigfunc）（int）；/*saveprevioussignalhandler*/
void（*new_sigfunc）（int）；/*oursignalhandler*/
structitimervalovalue；/*oldtimervalue*/
structitimervalvalue；/*ourinternaltimervalue*/
}；
这里关于链表的实现使用了BSD风格关于链表的一组宏，避免了再造轮子；该结构中，old_sigfunc在init_timer初始定时器链表时候用来保存系统对SIGALRM的处理函数，在定时器系统destory时用来恢复到之前的处理函数；ovalue的用途与此类似。
/*
*Createatimerlist.
*
*@paramcountThemaximumnumberoftimerentriestobesupportedinitially.
*
*@return0meansok,theothermeansfail.
*/
intinit_timer（intcount）
{
intret=0；
if（count=0||countMAX_TIMER_NUM）{
printf（"thetimermaxnumberMUSTlessthan%d.\n",MAX_TIMER_NUM）；
return-1；
}
memset（&timer_list,0,sizeof（structtimer_list））；
LIST_INIT（&timer_list.header）；
timer_list.max_num=count；
/*Registerourinternalsignalhandlerandstoreoldsignalhandler*/
if（（timer_list.old_sigfunc=signal（SIGALRM,sig_func））==SIG_ERR）{
return-1；
}
timer_list.new_sigfunc=sig_func；
/*Settingourintervaltimerfordriverourmutil-timerandstoreoldtimervalue*/
timer_list.value.it_value.tv_sec=TIMER_START；
timer_list.value.it_value.tv_usec=0；
timer_list.value.it_interval.tv_sec=TIMER_TICK；
timer_list.value.it_interval.tv_usec=0；
ret=setitimer（ITIMER_REAL,&timer_list.value,&timer_list.ovalue）；
returnret；
}
/*
*Destroythetimerlist.
*
*@return0meansok,theothermeansfail.
*/
intdestroy_timer（void）
{
structtimer*node=NULL；
if（（signal（SIGALRM,timer_list.old_sigfunc））==SIG_ERR）{
return-1；
}
if（（setitimer（ITIMER_REAL,&timer_list.ovalue,&timer_list.value））0）{
return-1；
}
while（！
LIST_EMPTY（&timer_list.header））{/*Delete.*/
node=LIST_FIRST（&timer_list.header）；
LIST_REMOVE（node,entries）；
/*Freenode*/
printf（"Removeid%d\n",node-id）；
free（node-user_data）；
free（node）；
}
memset（&timer_list,0,sizeof（structtimer_list））；
return0；
}
添加定时器的动作非常的简单，本质只是一个链表的插入而已：
/*
*Addatimertotimerlist.
*
*@paramintervalThetimerinterval（second）.
*@paramcbWhencb！
=NULLandtimerexpiry,callit.
*@paramuser_dataCallback'sparam.
*@paramlenThelengthoftheuser_data.
*
*@returnThetimerID,if==INVALID_TIMER_ID,addtimerfail.
*/
timer_idadd_timer（intinterval,timer_expiry*cb,void*user_data,intlen）
{
structtimer*node=NULL；
if（cb==NULL||interval=0）{
returnINVALID_TIMER_ID；
}
if（timer_list.numtimer_list.max_num）{
timer_list.num++；
}else{
returnINVALID_TIMER_ID；
}
if（（node=malloc（sizeof（structtimer）））==NULL）{
returnINVALID_TIMER_ID；
}
if（user_data！
=NULL||len！
=0）{
node-user_data=malloc（len）；
memcpy（node-user_data,user_data,len）；
node-len=len；
}
node-cb=cb；
node-interval=interval；
node-elapse=0；
node-id=timer_list.num；
LIST_INSERT_HEAD（&timer_list.header,node,entries）；
returnnode-id；
}
注册的信号处理函数则用来驱动定时器系统：
/*TickBookkeeping*/
staticvoidsig_func（intsigno）
{
structtimer*node=timer_list.header.lh_first；
for（；node！
=NULL；node=node-entries.le_next）{
node-elapse++；
if（node-elapse=node-interval）{
node-elapse=0；
node-cb（node-id,node-user_data,node-len）；
}
}
}
它主要是在每次收到SIGALRM信号时，执行定时器链表中的每个定时器elapse的自增操作，并与interval相比较，如果相等，代表注册的定时器已经超时，这时则调用注册的回调函数。
上面的实现，有很多可以优化的地方：
考虑另外一种思路，在定时器系统内部将维护的相对interval转换成绝对时间，这样，在每PerTickBookkeeping时，只需将当前时间与定时器的绝对时间相比较，就可以知道是否该定时器是否到期。
这种方法，把递增操作变为了比较操作。
并且上面的实现方式，效率也不高，在执行StartTimer，StopTimer，PerTickBookkeeping时，算法复杂度分别为O
（1），O（n），O（n），可以对上面的实现做一个简单的改进，在StartTimer时，即在添加Timer实例时，对链表进行排序，这样的改进，可以使得在执行StartTimer，StopTimer，PerTickBookkeeping时，算法复杂度分别为O（n），O
（1），O
（1）。
改进后的定时器系统如下图1：
图1.基于排序链表的定时器
Linux自2.6开始，已经开始支持POSIXtimer[2]所定义的定时器，它主要由下面的接口构成：
#includesignal.h
#includetime.hinttimer_create（clockid_tclockid,structsigevent*evp,
timer_t*timerid）；
inttimer_settime（timer_ttimerid,intflags,
conststructitimerspec*new_value,
structitimerspec*old_value）；
inttimer_gettime（timer_ttimerid,structitimerspec*curr_value）；
inttimer_getoverrun（timer_ttimerid）；
inttimer_delete（timer_ttimerid）；
这套接口是为了让操作系统对实时有更好的支持，在链接时需要指定-lrt。
timer_create
（2）：
创建了一个定时器。
timer_settime
（2）：
启动或者停止一个定时器。
timer_gettime
（2）：
返回到下一次到期的剩余时间值和定时器定义的时间间隔。
出现该接口的原因是，如果用户定义了一个1ms的定时器，可能当时系统负荷很重，导致该定时器实际山10ms后才超时，这种情况下，overrun=9ms。
timer_getoverrun
（2）：
返回上次定时器到期时超限值。
timer_delete
（2）：
停止并删除一个定时器。
上面最重要的接口是timer_create
（2），其中，clockid表明了要使用的时钟类型，在POSIX中要求必须实现CLOCK_REALTIME类型的时钟。
evp参数指明了在定时到期后，调用者被通知的方式。
该结构体定义如下：
unionsigval{
intsival_int；
void*sival_ptr；
}；
structsigevent{
intsigev_notify；/*Notificationmethod*/
intsigev_signo；/*Timerexpirationsignal*/
unionsigvalsigev_value；/*Valueaccompanyingsignalorpassedtothreadfunction*/
void（*sigev_notify_function）（unionsigval）；
/*Functionusedforthreadnotifications（SIGEV_THREAD）*/
void*sigev_notify_attributes；
/*Attributesfornotificationthread
（SIGEV_THREAD）*/
pid_tsigev_notify_thread_id；
/*IDofthreadtosignal（SIGEV_THREAD_ID）*/
}；
其中，sigev_notify指明了通知的方式：
SIGEV_NONE
当定时器到期时，不发送异步通知，但该定时器的运行进度可以使用timer_gettime
（2）监测。
SIGEV_SIGNAL
当定时器到期时，发送sigev_signo指定的信号。
SIGEV_THREAD
当定时器到期时，以sigev_notify_function开始一个新的线程。
该函数使用sigev_value作为其参数，当sigev_notify_attributes非空，则制定该线程的属性。
注意，由于Linux上线程的特殊性，这个功能实际上是由glibc和内核一起实现的。
SIGEV_THREAD_ID（Linux-specific）
仅推荐在实现线程库时候使用。
如果evp为空的话，则该函数的行为等效于：
sigev_notify=SIGEV_SIGNAL，sigev_signo=SIGVTALRM，sigev_value.sival_int=timerID。
由于POSIXtimer[2]接口支持在一个进程中同时拥有多个定时器实例，所以在上面的基于setitimer（）和链表的PerTickBookkeeping动作就交由Linux内核来维护，这大大减轻了实现定时器的负担。
由于POSIXtimer[2]接口在定时器到期时，有更多的控制能力，因此，可以使用实时信号避免信号的丢失问题，并将sigev_value.sival_int值指定为timerID，这样，就可以将多个定时器一起管理了。
需要注意的是，POSIXtimer[2]接口只在进程环境下才有意义（fork
（2）和exec
（2）也需要特殊对待），并不适合多线程环境。
与此相类似的，Linux提供了基于文件描述符的相关定时器接口：
#includesys/timerfd.hinttimerfd_create（intclockid,intflags）；
inttimerfd_settime（intfd,intflags,
conststructitimerspec*new_value,
structitimerspec*old_value）；
inttimerfd_gettime（intfd,structitimerspec*curr_value）；
这样，由于基于文件描述符，使得该接口可以支持select
（2），poll
（2）等异步接口，使得定时器的实现和使用更加的方便，更重要的是，支持fork
（2），exec
（2）这样多进程的语义，因此，可以用在多线程环境之中，它们的使用比POSIXtimer[2]更加的灵活，其根本原因在于定时器的管理统一到了unix/linux基本哲学之一--"一切皆文件"之下。
最小堆指的是满足除了根节点以外的每个节点都不小于其父节点的堆。
这样，堆中的最小值就存放在根节点中，并且在以某个结点为根的子树中，各节点的值都不小于该子树根节点的值。
一个最小堆的例子如下图2：
图2.最小堆
一个最小堆，一般支持以下几种操作：
Insert（TimerHeap,Timer）：
在堆中插入一个值，并保持最小堆性质，具体对应于定时器的实现，则是把定时器插入到定时器堆中。
根据最小堆的插入算法分析，可以知道该操作的时间复杂度为O（lgn）。
Minimum（TimerHeap）：
获取最小堆的中最小值；在定时器系统中，则是返回定时器堆中最先可能终止的定时器。
由于是最小堆，只需返回堆的root即可。
此时的算法复杂度为O
（1）。
ExtractMin（TimerHeap）：
在定时器到期后，执行相关的动作，它的算法复杂度为O
（1）。
最小堆本质上是一种最小优先级队列（min-priorityqueue）。
定时可以作为最小优先级队列的一个应用，该优先级队列把定时器的时间间隔值转化为一个绝对时间来处理，ExtractMin操则是在所有等待的定时器中，找出最先超时的定时器。
在任何时候，一个新的定时器实例都可通过Insert操作加入到定时器队列中去。
在pjsip项目的基础库pjlib中，有基于最小堆实现的定时器，它主要提供了以下的几个接口：
/*
*Createatimerheap.
*/
PJ_DECL（pj_status_t）pj_timer_heap_create（pj_pool_t*pool,
pj_size_tcount,
pj_timer_heap_t*ht）；
/*
*Destroythetimerheap.
*/
PJ_DECL（void）pj_timer_heap_destroy（pj_timer_heap_t*ht）；
/*
*Initializeatimerentry.Applicationshouldcallthisfunctionatleast
*oncebeforeschedulingtheentrytothetimerheap,toproperlyinitialize
*thetimerentry.
*/
PJ_DECL（pj_timer_entry*）pj_timer_entry_init（pj_timer_entry*entry,
intid,
void*user_data,
pj_timer_heap_callback*cb）；
/*
*Scheduleatime
升级会员 