程序使用的多数定时器都是操作超时定时器,只有少量定时器是周期任务定时器。这些超时定时器的特点是,很大的几率上的会在没有超时前就被重置了。所以有以下的讨论。
1、需要常数时间的插入,即说能快速插入。
2、需要常数时间的删除,即能快速删除。
3、精度不需要太高,比如1秒定时,可以在两秒后才激发。
4、定时器在很大的几率上,没超时前就被重置/删除。
总结起来特点就是
StartTimer StopTimer PerTickBookkeeping
O(1) O(1) O(?)
实现方式:
1、创建一个32个节点,每个节点分别代表1s, 2s, 4s, ..., 2^32s的定时器(可见最小精度是1s)。
2、所有的定时器按照最接近的2次幂加入到对应的节点中而形成一个双向链表,比如60秒的定时器加入到64秒的节点中去。
3、因为是双向链表,可见删除定时器是一件很简单的事情。
4、按照前面的3点看,知道60秒的定时器的效果跟64秒的差别不大,这就是所谓的精度不高。
5、如果准确的60秒的定时器,方式1是使用1秒定时器,方式2是把60秒拆分为32+16+8+4即可,就是先将它加入32秒的定时器中,然后超时之后再加入到16秒的定时器中,然后加入到8秒的定时器中。
结论,虽然60秒的定时器需要做额外的出来,所以在超时处理上比较费时间,不过前面说到,超时定时器在没有超时之前就被重置了,所以通常不会耗费很大的CPU时间。
总的来说,这个实现跟linux下的时间轮定时器的实现很像,并且区别也不大。一个区别是,时间轮是按照超时时间来处理,而这里是按照定时器的周期时间来处理。所以每次都只需要将节点加入到对于那个的链表未就可以了。