定时器的算法分析

定时器允许在将来的某一时刻执行我们预先设定的操作。在稍微复杂点的程序中，定时器通常会被广泛使用。

实现一个简单的定时器并不难。每个定时器都包含一个字段，表示定时器需要多长时间到期，当程序检查定时器时，根据时间判断定时器是否到期。如果已到期，则执行相应的操作并删除定时器，否则不做任何处理。

定时器的常见操作有3个：添加定时器, 检查定时器是否到期， 删除定时器。我们来分析下各种常用算法的性能问题。

链表：

将所有的定时器放在一个链表中。这使得每次检查定时器，都得扫描整个链表，当定时器数量非常大时，扫描是很耗时的操作。

维护一个排序的链表，这会提高检查的性能，但插入又会比较耗时。

红黑树：

在分析红黑树之前，我们先从二叉搜索树谈起。不严格的定义就是：左子树上所有结点的值均小于它的点的值，右子树上所有结点的值均大于它的根结点的值,如下图:
                

从上图可知，对于同样的数据集合，可以构造出多种不同的二叉搜索树。根据二叉搜索树的特性，我们很容易分析出各操作的时间复杂度：查找、最大值、最小值、增加结点，删除结点的时间复杂度都是O(h)，h为树的深度。显然，为了提高各操作的性能，我们需要尽量降低树的深度。于是平衡二叉搜索树的概念被提出。

平衡二叉搜索树的左右两个子树的高度差不超过1， AVL树是严格的平衡树。红黑树也是众多平衡树中的一种，它会确保没有一条路径会比其它路径长出两倍，因而是近似平衡的。
                                                        
        

在插入和删除结点的时候，为了保持树的平衡性，需要对其它结点做出调整，这是通过“旋转”操作来完成的，因此红黑树的插入和删除操作有些复杂。但红黑树能保证查询、插入、删除操作都能在O(lg2n)内完成，这在数据量很大的时候，性能远好于链表。Linux内核中很多模块都使用了红黑树，具体代码见；。

小根堆：

小根堆可以近似看成一颗完全二叉树。不严格的定义为：父结点的值小于等于子结点的值，如下图：

                    

堆中的元素存放在数组中，其中第一元素就是最小的,所以找最小值的时间是O(1)。

插入结点: 先将数据放到最后一个结点，为了维护堆的性质，将该结点一直往上进行交换即可。时间复杂度为O(lg2n)。

删除结点: 取走第一个，将最后一个填写到第一个位置。为了维护堆的性质，将结点一直往下进行交换即可。时间复杂度为O(lg2n)。

结论：小根堆的删除操作比红黑树略微慢些，但也在相同数量级O(lg2n)。在定时器这类应用中，由于需要频繁取最小值进行判断，所以用小根堆会更合适些，取最小值时间复杂度为O(1)。

内核的定时器实现采用时间轮算法（kernel/timer.c）：

      直接上数据结构图。

         

      Tv1是2^8=256个大小的数组，tv2,tv3,tv4,tv5分别是2^6=64个大小的数组，每个元素都是一个链表。

      Tv1是保存0-255 jiffies的。

      Tv2保存2^8-2^(8+6)-1 jiffies的。 

      依次类推。

增加定时器的操作，直接看代码，很简单:
  
 

定时器的迁移：

当tv1的定时器全部执行完毕，就将tv2的某一个链表的数据搬移到前255个。当tv2的链表执行完成，将tv3的某一链表搬移到tv2的64个中，等等。

为了周期性地补充base->tv1.vec, 在64次补充当中，63次足以把base->tv2指向的链表分成base->tv1指向的256个链表。依次地，base->tv2.vec数组必须在0.006%的情况下得到补充，即使16.4秒一次。类似地，每17分28秒补充一次base->tv3.vec,每18小时38分补充一次base->tv4.vec,而base->tv5.vec不需要补充。

时间轮算法很好的保证了性能，而且也比较容易理解。

参考资料：

《算法导论》

《深入理解Linux内核》

《libevent源代码》