简单的定时器方案（2）*方案二（用于较早的UNIX版本）：*定时器保存在一个有序链表中，按照定时器到期的绝对时间由低到高存储*每个定时器滴答，PerTickBookkeeping递增当前时间，然后和表头进行比较，将超时的表头元素删除，调用ExpiryAction*新增一个定时器时，StartTimer搜索链表，找到一个合适的位置插入新定时器10:23:1210:23:24ghead10:24:03FIGURE 7.2 Timerqueueexampleusedtoillustrate Scheme2
简单的定时器方案（2） 方案二（用于较早的UNIX版本）： 定时器保存在一个有序链表中，按照定时器到期的绝对时间 由低到高存储 每个定时器滴答，PerTickBookkeeping递增当前时间，然后和 表头进行比较，将超时的表头元素删除，调用ExpiryAction 新增一个定时器时，StartTimer搜索链表，找到一个合适的位 置插入新定时器
方案二的复杂度分析* PerTickBookkeeping的平均时间为O(1)StartTimer的最大时间为O(n)如果定时器链表是双向链表，StopTimer的时间可为0(1)需要O(n)的额外空间，用于保存双向链表中的前向指针和后向指针*若有硬件定时器支持，可将硬件定时器设为表头定时器的到期时间，可以避免每个定时器滴答的处理开销，但有些处理器架构不提供这种能力
方案二的复杂度分析 PerTickBookkeeping的平均时间为O(1) StartTimer的最大时间为O(n) 如果定时器链表是双向链表，StopTimer的时间可 为O(1) 需要O(n)的额外空间，用于保存双向链表中的前 向指针和后向指针 若有硬件定时器支持，可将硬件定时器设为表头 定时器的到期时间，可以避免每个定时器滴答的 处理开销，但有些处理器架构不提供这种能力
简单的定时器方案（3）*方案三：*将方案二中的链表换成基于树的数据结构（如非平衡二叉树），将StartTimer的延迟从O(n)减少到o(log(n)*小结：* 以上三种简单方案中，PerTickBookkeeping或StartTimer的时间复杂度至少是O(log(n)，对于高速实现来说这是一个问题
简单的定时器方案（3） 方案三： 将方案二中的链表换成基于树的数据结构（如 非平衡二叉树），将StartTimer的延迟从O(n)减 少到O(log(n)) 小结： 以上三种简单方案中， PerTickBookkeeping或 StartTimer的时间复杂度至少是O(log(n))，对于 高速实现来说这是一个问题
7.3定时轮（Timingwheels）*一个较简单的定时器问题：*定时器的值为不大于Maxlnterval的较小整数*方案2和方案3使用优先级队列组织定时器：*减小了PerTickBookkeeping的处理复杂度*增加了StartTimer的复杂度（需要维护优先级队列）*如何降低StartTimer的复杂度？*需要找到一种比有序链表或树更高效的优先级队列*使用桶排序
7.3 定时轮（Timing wheels） 一个较简单的定时器问题： 定时器的值为不大于MaxInterval的较小整数 方案2和方案3使用优先级队列组织定时器： 减小了PerTickBookkeeping的处理复杂度 增加了StartTimer的复杂度（需要维护优先级队列） 如何降低StartTimer的复杂度？ 需要找到一种比有序链表或树更高效的优先级队列 使用桶排序
定时轮的数据结构*一个长度为Maxlnterval的循环数组当前时间由指向数组元素的一个指ElementoElement1针表示（若指针指向第i个数组元素，当前时间为第i个时间单位）ElementiCurrent time.Listof timers toElementi+*每个数组元素包含一个指针，指向expire at This Time一个在该时刻到期的定时器链表ElemenMAXINTERVAL-1FIGU RE 7.3Array of lists used by Scheme 4 for timer intervals up to MAXINTERVAL*每一次定时器滴答PerTickBookkeeping将指针下移一个元素
定时轮的数据结构 一个长度为MaxInterval的循环数组 当前时间由指向数组元素的一个指 针表示（若指针指向第 i 个数组元 素，当前时间为第 i 个时间单位） 每个数组元素包含一个指针，指向 一个在该时刻到期的定时器链表 每一次定时器滴答， PerTickBookkeeping将指针下移一 个元素