定时器有哪三种类型

计时

在linux中,一般由文件下的alarm函数和setitimer来设置定时器,到时间则发出SIGALARM,并调用指定的到期信号处理函数,

signal(SIGALRM, handler);函数来设置到期事件处理函数,而这个到期事件处理函数在游双的书例子里可以看到,是定时器类里的tick函数,即每隔一个周期调用tick()一次,注意要区分timer到期的回调函数和SIGALARM的回调函数

封装timer

在服务器编程里,要处理定时事件,会封装个定时器timer类,其中一般会包含到期时间和回调函数,如muduo中timer.h的实现,和l游双书中的定时器那一章的种种例子,并根据不同实现方式增加额外的数据如链表的节点

而定时器应该给出的用户接口有注册定时器,注销定时器;注册定时器应增加区分重复定时器和一次性定时器

还应该给出定期触发的函数,即上面提到的tick(),在tick函数里判断timer里哪些是已经过期的,触发定时事件,根据定时器是否是重复的删除或者重新设置此定时器

定时器实现类型

定时器会用到什么操作呢?它的插入,指定注销,注销到期的定时器,根据这几点看一下如何设计定时器,ps.注意区分指定注销和注销到期,因为以下的实现大多是已经排序好的,注销到期的一般是从头开始往下找,而指定注销是注销当中某个节点的定时器

先说明libevent中的实现是最小堆,muduo是采用了红黑树来实现,以下列出几种类型的定时器实现

最简单的实现:双向链表

直接利用链表实现,每一个定时器作为一个链表的节点，这样做最直观,而几种操作的复杂度是:

添加的时候就直接插入到链表末端，时间复杂度O(1)

找到到期timer,则需要遍历全部,时间复杂度为O(n)

代码请看参考资料[1]

优化的链表:排序双向链表

优化操作:每次插入按到期时间进行排序,时间复杂度是:

插入为O(n),找到到期timer时间复杂度是O(1)的操作,指定timer删除操作,是O(1)的复杂度,这也是为什么要用双向链表的原因,直接传入一个链表节点进行删除,,ps:这里排序链表判断到期虽然会有个while循环,是为了找到地一个非过期并执行前面过期的所有回调函数,平均下来还是个O(1)的操作

代码:参考资料[1]

最小堆实现

优化点:最小堆的插入操作是log(n),参考下堆的插入操作:插入到堆最后面以后,进行上浮调整,最大调整次数为树的高度,即log(n),

到期触发的时间复杂度为O(1),及取最值,而堆这个结构最适合做这个,在游双的书中能看到,最小堆的实现alarm信号发送的时间设置成堆中最近的触发时间,每次取完后其实还有个log(n)的heapify调整时间,估计参考资料[1]和游双都把这个操作延后到平时(即延迟销毁,游双的书第11章第215页)了,

,指定删除操作则略微麻烦,这也是为什么muduo不采用这个方法的原因

(如果del_timer函数的参数,传入timer作参数直接删除再堆化一下就行,如果传入参数为定时器序号,则遍历到再删除为O(n),用一个map来存序号到定时器在堆中位置,则为时间O(1))(但是每次变换都)

代码:参考资料[1]或者游双的书

红黑树实现

muduo的实现,顺便提下,heap比起红黑树的好处是,像陈硕书中说的:内存的局部性更好,参考资料[1]说的内存使用率更好,且性能会相差一点,

红黑树对比堆查找特定的timer速度会快一点(参考[1]说的)

有时间复杂度就不分析了,muduo书中还提到了了一下set,map,multiset,multimap的选择

代码:参考muduo(直接用了现成的数据结构)或者参考资料[1]或者游双的书

时间轮

时间轮的介绍先略过TODO在游双的书中和陈硕的书中示例代码部分都有提到,

前文没有分清定时器的概念,晚点再改TODO

首先要把socket fd和定时器的指针加以封装,以便删除使用,即可以通过这个类来访问fd和timer*,要删除时间轮中的某个fd对应的timer*我们直接访问这个数据结构,在游双的书里取名为client_data

封装timer类,包括时间,到期执行的回调函数,这个类是以便时间轮使用,在时间轮中,我们是直接用timer*来排序使用的,

分析下各种操作的时间复杂度

插入:直接调用API传入timer*,而时间轮里每个轮里的是链表,链表删除直接O(1)

添加:插入操作是对时间进行取模放入那个槽中,时间复杂度也是O(1)

删除:直接传入timer*,O(1)

到期触发:是n个定时器,p个槽,根据哈希函数不同值均匀分布的特点,大概时间复杂度是O(n/p),游双的书中称之为:比O(n)好很多

使用IO复用