高性能定时器策略之时间轮定时器算法

　　时间轮定时器是有多个时间槽（slot）组成，每个时间槽代表时间的基本跨度。类似于一个时钟，时钟指针以恒定的速度每往下走一步，代表一个时间跨度。
　　时间槽的个数是固定的，用SN（SlotNum）表示，每转动一次可称为一个滴答（tick），所以转动一周也就需要个SN滴答。每一个滴答需要的槽间间隔为SI（SlotInterval），则转一周也就共需要（SNSI）时间单位。
　　时间轮的每个槽都指向一个定时器链表，每个链表的定时器都有一个相同的特性：相差（SNSI）的整数倍，也即是一周的整数倍。正是由于时间轮有这样的特性，所以可以根据定时器的触发时间和时间轮的槽数，把定时器hash到对应的链表上。
　　一个简单的时间轮如下图：
　　比如我们要插入一个超时时间为TI的定时器，那么计算器应该插入到槽对应的链表的方式如下：
　　TS（CS（TISI））SN
　　CS代表当前的槽位，因为时间轮定时器不停的在走。
　　时间轮采用的是hash的思想，把各个定时器分散到不同槽的链表中，这个避免了单个链表的过长，提高了效率。
　　从上面的公式可以看出，对时间轮而言，当SI越小的时候，定时器的精度就越高；当SN槽数越多时，效率越高，因为定时器被分配到不同的链表中，链表的长度也就相对短了，提高了遍历效率。
　　下面实现一个简单的时间轮，代码如下：
　　includestdio。hincludestdlib。hincludestring。hincludeunistd。hincludesystime。hincludesyssocket。hincludesystypes。hincludesysepoll。hincludeincludetime。hdefineBUFFERSIZE64缓冲区长度defineSLOTSNUM60时间轮上槽的数目结构体声明typedefstructtwtimertwtimer；typedefstructclientdateclientdate；EPOLL回调函数typedefvoid（epollcallbackt）（int，int）；structtwtimer｛introtation；记录定时器在时间轮上转多少圈后触发inttimeslot；记录定时器属于时间轮上的槽位（对应的链表）void（cbfunc）（clientdate）；定时器回调函数clientdateuserdate；client数据twtimerprev；指向前一个定时器twtimernext；指向下一个定时器｝；用户数据structclientdate｛intsockfd；charbuf〔BUFFERSIZE〕；twtimertime；｝；每1秒时间轮转动一次，也即是槽间隔为1秒staticconstintSI1；时间轮的槽，其中每个元素指向一个定时器链表，链表无序twtimerslots〔SLOTSNUM〕；事件的当前槽intcurslot0；twtimermalloctwtimer（introtation，inttimeslot）｛twtimertimer（twtimer）malloc（sizeof（twtimer））；memset（timer，0，sizeof（twtimer））；timerrotationrotation；timertimeslottimeslot；timerprevNULL；timernextNULL；timercbfuncNULL；timeruserdateNULL；returntimer；｝voidfreetwtimer（twtimertimer）｛if（NULLtimer）returnNULL；if（NULL！timeruserdate）free（timeruserdate）；free（timer）；｝voidtimewheel（）｛inti0；for（i0；iSLOTSNUM；i）slots〔i〕NULL；｝遍历每个槽，销毁定时器voiddeltimewheel（）｛inti0；for（i0；iSLOTSNUM；i）｛twtimertmpslots〔i〕；while（tmp）｛slots〔i〕tmpnext；freetwtimer（tmp）；tmpslots〔i〕；｝｝｝根据定时器timeout创建一个定时器，并把它插入到一个合适的槽中twtimeraddtimer（inttimeout）｛if（timeout0）returnNULL；intticks0；待插入的超时时间小于时间轮的槽间隔SI，则将ticks向上调整为1，否则将ticks向下调整为timeoutSIif（timeoutSI）｛ticks1；｝else｛tickstimeoutSI；｝计算待插入的定时器在时间轮转动多少圈后被触发introtationticksSLOTSNUM；计算待插入的定时器应该被插入到哪个槽中intts（curslot（ticksSLOTSNUM））SLOTSNUM；创建新的定时器，它在时间轮转动rotation圈后被触发twtimertimermalloctwtimer（rotation，ts）；若第ts个槽为空，则插入定时器，并将该定时器置为该槽的头结点if（！slots〔ts〕）｛printf（addtimer，rotationisd，tsisd，curslotisd，rotation，ts，curslot）；slots〔ts〕timer；｝else否则，将定时器插入其中｛printf（slots〔d〕isnotnull，ts）；timernextslots〔ts〕；slots〔ts〕prevtimer；slots〔ts〕timer；｝returntimer；｝voiddeltimer（twtimertimer）｛if（！timer）return；inttstimertimeslot；slots〔ts〕是目标定时器所在槽头结点，若目标定时器为头结点，则需要重置第ts个槽的头结点if（timerslots〔ts〕）｛slots〔ts〕slots〔ts〕next；if（slots〔ts〕）｛slots〔ts〕prevNULL；｝｝else｛timerprevnexttimernext；if（timernext）｛timernextprevtimerprev；｝｝freetwtimer（timer）；｝SI时间到后，调用该函数，时间轮向前滚动一个槽的间隔voidtick（）｛twtimertmpslots〔curslot〕；遍历该槽对应链表的所有定时器，查看是否触发while（tmp）｛if（tmprotation0）｛tmprotation；tmptmpnext；｝else到期，执行任务｛tmpcbfunc（tmpuserdate）；if（tmpslots〔curslot〕）｛printf（deleteheadincurslot，curslotd，curslot）；slots〔curslot〕tmpnext；freetwtimer（tmp）；if（slots〔curslot〕）slots〔curslot〕prevNULL；tmpslots〔curslot〕；｝else｛tmpprevnexttmpnext；if（tmpnext）｛tmpnextprevtmpprev；｝twtimertmp2tmpnext；freetwtimer（tmp）；tmptmp2；｝｝｝更新时间轮的当前槽，以反映时间轮的转数curslotcurslotSLOTSNUM；｝
　　测试如下inttotal0；记录1s定时器触发次数voidtest（clientdatecd）｛printf（totald，total）；｝voidtestaddtimer（inttimeout，void（cbfunc）（clientdate））｛twtimertimer；timeraddtimer（timeout）；timercbfunccbfunc；｝voidtestcretetimer（）｛创建一一个2秒5秒10秒70秒，85秒的定时器testaddtimer（2，test）；testaddtimer（5，test）；testaddtimer（10，test）；testaddtimer（70，test）；testaddtimer（85，test）；timetnow；structtmtmnow；time（now）；tmnowlocaltime（now）；printf（testcretetimerdatetime：dddd：d：d，tmnowtmyear1900，tmnowtmmon1，tmnowtmmday，tmnowtmhour，tmnowtmmin，tmnowtmsec）；｝保存触发定时器相应的fd和回调，在该回调中进行遍历时间轮typedefstructepollcallbackinfo｛intiFd；epollcallbacktpfEpollCallBack；｝epollcallbackinfo；创建一个触发定时器intcreateTimer（longlMSec，intepfd，epollcallbacktpfEpollCallback）｛structitimerspecestTimer；structepolleventevent；inttimerfd；intiSec（int）（lMSec1000）；intret1；memset（event，0，sizeof（event））；event。eventsEPOLLINEPOLLHUPEPOLLERR；memset（stTimer，0，sizeof（stTimer））；stTimer。itvalue。tvseciSec；stTimer。itvalue。tvnsec（lMSec1000）1000000；stTimer。itinterval。tvseciSec；stTimer。itinterval。tvnsec（lMSec1000）1000000；timerfdtimerfdcreate（CLOCKMONOTONIC，0）；if（1！timerfd）｛if（0timerfdsettime（timerfd，0，stTimer，NULL））｛epollcallbackinfopmalloc（sizeof（epollcallbackinfo））；piFdtimerfd；ppfEpollCallbackpfEpollCallback；event。data。ptrp；retepollctl（epfd，EPOLLCTLADD，timerfd，event）；｝else｛printf（timerfdsettimeFailed）；｝定时器时间设定或添加epoll错误时，释放资源if（0！ret）｛printf（addtoepollfailedorsettimefailed）；close（timerfd）；timerfd1；｝｝else｛printf（createtimerfdfailed）；｝returntimerfd；｝voidtimerreadtimerFd（inttimerfd）｛uint64texp；（void）read（timerfd，exp，sizeof（uint64t））；total；return；｝epoll上定时器回调，每触发一次则调用一次tick（）voidcommomTimerCB（intuiEvent，intiTimeFd）｛timerreadtimerFd（iTimeFd）；tick（）；｝intmain（）｛structepolleventwaitevent〔100〕；intepfd；inttimerfd；epollcallbacktpfEpllCallback；inti0；structitimerspecestTimer；longlMSec1000；1s定时器时间intcount；epfdepollcreate（1）；if（1epfd）｛printf（epollcreateerror）；return1；｝printf（createepollfd：d，epfd）；timewheel（）；testcreatetimer（）；timerfdcreateTimer（lMSec，epfd，（epollcallbackt）commomTimerCB）；if（1timerfd）｛printf（failedtocreatetimer）；return1；｝for（；；）｛waitfdsepollwait（epfd，waitevent，100，1）；printf（countd，count）；for（i0；iwaitfds；i）｛epollcallbackinfot（epollcallbackinfo）waitevent〔i〕。data。ptr；pfEpllCallback（epollcallbackt）（unsignedlong）tpfEpllCallback；pfEpllCallback（waitevent〔i〕。events，tiFd）；｝｝return0；｝