一个高效的定时器分析及设计一个高效的定时器分析及设计
对于一个游戏而言，定时器是必须的，而它一般作为一个游戏基本公共组件，而定时器在游戏逻辑中运用是非
常明显的(比如吃药回血，每几秒回血多少)，而对于游戏逻辑而言需要开发一个高效率高精度(毫秒级别)的定时
器。 一：分析Ace库定时器实现方式 1.Ace种定时器实现有4种，这里不具体介绍实现细节，主要介绍
实现数据结构，性能。 具体的4种定时器都是从ACE_Timer_Queue_T继承，每种定时器用不同的数据结构
来实现具体Timer的算法。 1）ACE_Timer_Heap定时器，根据触发时间建立一个优先级队列(一个堆数据结
构)来维护所有的定时器，代价就是删除和插入过程为O(l
对于一个游戏而言，定时器是必须的，而它一般作为一个游戏基本公共组件，而定时器在游戏逻辑中运用是非常明显的
(比如吃药回血，每几秒回血多少)，而对于游戏逻辑而言需要开发一个高效率高精度(毫秒级别)的定时器。
一：分析Ace库定时器实现方式
1.Ace种定时器实现有4种，这里不具体介绍实现细节，主要介绍实现数据结构，性能。
具体的4种定时器都是从ACE_Timer_Queue_T继承，每种定时器用不同的数据结构来实现具体Timer的算法。
1）ACE_Timer_Heap定时器，根据触发时间建立一个优先级队列(一个堆数据结构)来维护所有的定时器，代价就是删除
和插入过程为O(logn),代价比较高。
2）ACE_Timer_List定时器，根据触发时间建立一个有序的双向链表，代价就是插入定时器代价较高。
3）ACE_Timer_Hash定时器，采用开链的Hash方式每一个桶为一个单链表，在检查所有桶超时的时候会遍历链表所有的
元素。为了提高效率这里所用的Hash桶应该足够 大，而对于定时器一般是频繁的超时响应定时器，已经插入和删除，响应会
采用迭代的方式。所以效率并不是那么高效。
4）ACE_Timer_Wheel定时器，采用的一种时间轮的方式，具体实现就好象一个轮子上面有很多插槽，每一个插槽下面
包括一个有序双向链表，在Ace中把轮子叫做Wheel,插槽叫做Spoke，每一个定时器被Hash到Spoke中，而Spoke也可以理解
为timer的分辨率，而Spoke的计算公式为 :( 触发时间 >> 分辨率的位数)&(spoke大小-1).然后在根据触发时间把定时器插入到
每一个Spoke的有序双向链表中， 与Ace_timer_Hash的实现类似，只是这里用户可以指定Spoke大小。这里代价就是插入的
时候可能坏为O(n).
我们公司现在CTimer就是采用Ace的ACE_Timer_Wheel原理设计的。
这里有一个图更能直观的描述这种思想:
实现方式为Vector,list组合。
二: 本文介绍一种采用linux中断处理的定时器设计方式
此定时器的查找，删除，插入都是O(1)
1） 介绍设计原理
定时器是基于时间的中断函数，即是根据触发时间来超时响应。所以只要我们设计一个基于时间的Hash算法。只要我们
能我们把一个函数触发时间全部Hash到此Hash算法的桶中，就实现了查找，插入，删除O(1)的操作了，其实不然基于时间的
hash算法好像挺复杂，而且桶的数量太大，内存消耗太多，所以把一个时间直接Hash代价太大。是否有一种其他的方式
呢，linux中断处理采用一种类似水表计算水量的方式，方式就是生活中的水表，个指针转一圈后一个转一格，假设每一个圈
都是10个刻度，个圈能表示10，那么第二圈没一个刻度表示个圈的1圈，就能表示10*10, 二个圈一共就能表示10*10 + 10。
以此类推，5个圈就能表示10^5+10^4+10^3+10^2+10...
一个32bits的整数，如果到1毫秒，则2^32位可以表示49.3天，而一般服务器应该不会直接运行49.3天，这里我们采用5个
轮子(即圈), 轮子大小分别为256,64,64,64,64 ,轮子依次类推表示范围在0~256, 256~256*64, 256*64~256*64^2,
256*64^2~256*64^3, 256*64^3~256*64^4, 假设这里精度为n毫秒，个轮子表示n*256秒时间内触发函数，第二个轮子的第二
个插孔则表示n*256*2时间范围内的，
2）一些定义:
A. 轮子，这里采用的轮子与上面介绍的Ace轮子大概一样，一个循环列队，每一个插槽你们有一个双向链表，注意这里链
表不需要排序，所以在插入的是O(1)的操作。轮子为5个。
3) 操作：
A. Hash算法:这里Hash算法根据他的多少时间后触发，直接Hash得到轮子以及插槽，然后插入到某个插槽双向的链表
中。
B.定时器触发: 定时器触发只会触发个轮子超时的所有定时器，因为后面4个轮子定时器表示都在前1轮子触发完了才会触
发，所以这里让后面4个轮子维护表示将要发生的定时。这里会根据当个轮子转第几圈后，第二个轮子会把第几插槽的所有定
时器全部插入到个轮子中，依次类推，第二个轮子转一个第三个轮子某个插槽又会插入到第二个轮子中。。。
剩余8页未读，继续阅读
资源评论
