定时器是很多程序都需要使用到的功能。

    现代操作系统有一个很重要的功能——进程切换，执行一个进程一半的时候跑去执行另一个进程。这是怎么做到的呢？

    就是由可编程硬件定时器发出信号（操作系统启动的时候设置），触发了操作系统注册的处理函数，在这个处理函数里把进程切换掉。

    硬件定时器是很珍贵的，我们基本上都是使用软件定时器。软件定时器说白了就是一个线程一直跑，看到注册的时间到了，就调用相应的回调函数。

    对于一个游戏而言，定时器是必须的，而它一般作为一个游戏基本公共组件，而定时器在游戏逻辑中运用是非常明显的(比如吃药回血，每几秒回血多少)，而对于游戏逻辑而言需要开发一个高效率高精度(毫秒级别)的定时器。

 

几个问题：

1、定时器任务怎么调度

2、是否为每个任务开启一个线程

3、如何设计会高效，不至于定时器线程占用太多cpu

 

参见的几种定时器调度实现方式：

1、排序链表（双向链表）

2、最小堆

3、哈希：需要内存过大

4、简单时间轮

5、水表时间论轮

 定时器实现算法复杂度

实现方式	StartTimer	StopTimer	PerTickBookkeeping
基于链表	O(1)	O(n)	O(n)
基于排序链表	O(n)	O(1)	O(1)
基于最小堆	O(lgn)	O(1)	O(1)
基于时间轮	O(1)	O(1)	O(1)

     

一：分析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).

    

      这里有一个图更能直观的描述这种思想:

     

           实现方式为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个轮子维护表示将要发生的定时。这里会根据当第一个轮子转第几圈后，第二个轮子会把第几插槽的所有定时器全部插入到第一个轮子中，依次类推，第二个轮子转一个第三个轮子某个插槽又会插入到第二个轮子中。。。

           

   4）注意的地方:

          A.将一个定时器插入到它应该所处的定时器轮子插槽中。

          B.定时器的迁移，也即将一个定时器从它原来所处的轮子插槽迁移到另一个轮子插槽中。

          C.超时响应执行当前已经到期的定时器。 

 

 

 

 

Reference：