Daly的游戏人生

高效的Timer实现

    很多程序都需要处理一系列定时事件,一个Timer程序就是实现定时事件集合的管理。
    每个timer事件项一般包括超时值(delay), 标识(key)和回调函数,Timer程序的作用就是实现插入,删除,更新和调用。

方法1. 链表
   最简单的实现是有序链表。list_head保存到当前时间的剩余时间remain_time,后一节点保存与前一节点的超时时间的差(而不是到当前时间的差)。
   更新:每次tick update时,只需要更新链表头节点remain_time,如果remain_time <= 0, 调用函数,删除该头节点,然后更新后一个节点的remain_time,如此类推直到头结点remain_time > 0或链表为空.  O(1)
   插入:相当于插入排序。有序插入到适当位置,更新后一个节点的remain_time.  
   删除:遍历链表搜索,删除节点,更新后一个节点的remain_time. 
   例子:live555流媒体服务器

方法2. 最小堆(优先队列)
   方法与链表类似,插入/删除效率从O(n)变为O(lgN)
   libevent中有min-heap实现一个优先队列,根节点是最先触发的超时时间, 与方法1一样,只需更新根节点。根节点超时后,调整堆即可

方法3. Hash或分级
   根据超时值的范围(比如CPU的流逝ticks)进行hash,hash后每个bucket实现方法1所示的链表. 较方法1减少了搜索次数
   例子:MudOS定时器

方法4. 分级hash
   这是linux内核timer的实现方法,值得参考。见文献[1]
   方法:假设定时值以tick为单位,每tick更新timer一次。
         定时值范围为0 ~ 2^32个tick(32个bit), 则把他分成4级,每级做一个hash, 每个则有256个bucket (刚好8bit)
         000000000  00000000  00000000  00000000
         ---------  --------  --------  --------
            A          B         C         D
         插入:算出 tick_trig = delay + 当前tick, mask = tick_trig & 0xFF000000,
               如果mask不等于0,在A hash表插入timer项, 否则进入下一级,mask = tick_trig & 0x00FF0000, 插入B hash表,如此类推。
         更新:每次tick++, 先检查D hash表(最低8位的与操作)有无timer项,如果有,执行函数并删除。
               如果tick满255进位, 则检查C hash表中对应位置有否timer项,如果有,重新插入(此处的timer项必定会插入D hash表中),如此类推
         这样,插入,更新,删除都做到O(1)了
   疑惑:这个方法用于内核级程序。对于用户级程序,每次update的间隔不恒定(即每次tick不一定是+1),这时需要扫描tick之前的几个bucket了
   


参考文献

[1] George Varghese , Tony Lauck. Hashed and Hierarchical Timing Wheels: Efficient Data Structures for Implementing a Timer Facility (1996)

[2] libevent 源码
[3] <understanding linux kernel 3rd ed>
[4] MudOS 源码



posted on 2010-05-26 20:44 Daly 阅读(4283) 评论(2)  编辑 收藏 引用 所属分类: 数据结构与算法

评论

# re: 高效的Timer实现[未登录] 2010-05-27 10:58 ~

还是最小堆(优先队列)安逸。  回复  更多评论   

# re: 高效的Timer实现 2013-11-07 11:57 嘿嘿

用一个std::set就可以搞定了.....  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理