Timer的设计

这两天闲来无事的时候想了想timer的设计思路及实现方式。今天偶然的看到了Linux内核中关于timer的管理方式。现在总结下几种可以实现的方式，但是现在并没有自己动手做，缺少数据支撑，仅仅是停留在脑子里的一些想法，可以在后期补充实现，然后测试相关性能数据，做到有理有据。

关于timer，一般抽象出来的接口大概需要以下几个。

init_timer(timer_t *timer, time_t time, func_t callback_func);
add_timer(timer_t *timer);
del_timer(timer_t *timer);

大概就是这么一个意思，init_timer初始化函数，传入相关timer触发时间，以及相应的回调函数。add_timer将timer放入到相应实现中，使其生效，在timer的设定时间触发相应的回调函数。del_timer删除相应的timer，使其无效。

timer内部实现为时钟每过一个tick更新时钟，然后check是否有timer满足触发条件，如果满足触发，并且将timer移除队列，如果不满足，那么NOP。

想要维护系统中所有的timer我能想到的有一下几个方法：

1.使用单链表的方式

这个属于最朴素的想法了，将所有的timer按照时间先后顺序排成一个链表，先触发的在链表头部，后触发的在链表尾部，这样，每个时钟中断到来的时候检查链表头部，看是否满足触发条件，如果满足触发条件则进行相应回调函数。

但是，这种方法在新的timer加入时，时间复杂度是O(n)，这种方法在timer非常多的情况下，性能会变的极差，影响可用性，所以这种实现方式基本上在高性能的要求下不予考虑。

2.使用红黑树的方式

为了改善单链表上插入性能的劣势，可以选用红黑树作为维护timer的数据结构，这样在新的timer加入时时间复杂度，为O(log(n))，在一定数量级范围内，这等同与常数复杂度。

但是，使用这种方法也有弊端，劣势就在与维护红黑树代价比较高，由于在每一次timer被触发时会被移除，所以会带来红黑树旋转的开销。

3.借用Linux分级别hash方式

Linux内核在维护timer时使用了一种分级别的维护方式，有点类似与任务调度中多重队列调度的感觉。

这个地方还没能完全理解，需要再读之后再分析

3比2在插入时性能肯定是要好，但是在timer事件到来时则不一定。

实践出真知，等实验结束后在做定夺。