第七章 维护定时器7.1 定时器网络协议大量使用定时器实现与时间有关的功能当以下任一情况发生时，定时器模块存在性能问题:定时器算法由CPU实现：每一个硬件时钟滴答都要中断CPU。若时钟精度在微秒量级，中断处理开销很大。要求细粒度定时器（如微秒量级）：启动/终止延迟要小同时活跃的定时器数目很大：要求启动/终止延迟小当网络速度提高时，定时器精度要提高：需要细粒度的定时器精确测量RTT，以及加快重传与恢复启动/终止速度要提高：包速率提高了定时器模块的组成StartTimer (Interval, RequestID, ExpiryAction)：启动一个定时器，定时器在Interval个时间单位后超时 StopTimer (RequestID)：终止指定的定时器PerTickBookkeeping：每隔1个定时器粒度，检查是否有定时器超时；若有，调用ExpiryProcessingExpiryProcessing：执行StartTimer()中指定的ExpiryAction 选择定时器算法的性能指标两个性能指标：定时器数据结构占用的空间（空间复杂度）定时器模块中例程的调用延迟（从调用到完成的时间）（时间复杂度）以上两个性能指标都与定时器的数量（平均数量或最大数量）有关。7.2 简单的定时器方案方案一：StartTimer()找到一个内存位置（变量），设置该位置的值为Interval。每隔1个定时器粒度，PerTickBookkeeping递减每个活跃的定时器；若某个定时器的值变为0，调用相应的ExpiryAction。复杂度分析：每个定时器只使用一个内存位置，所用空间最小PerTickBookkeeping的执行时间为O(n)，其余为O(1)适合活跃定时器少、PerTickBookkeeping实现快的场合简单的定时器方案（2）方案二（用于较早的UNIX版本）：定时器保存在一个有序链表中，按照定时器到期的绝对时间由低到高存储。每个时钟滴答，PerTickBookkeeping递增当前时间，然后和表头进行比较，将超时的表头元素删除。新增一个定时器时，StartTimer搜索链表，找到一个合适的位置插入新定时器。 方案二的复杂度分析PerTickBookkeeping的平均时间为O(1)。StartTimer的最大时间为O(n)。如果定时器链表是双向链表，StopTimer的时间可为O(1)。需要O(n)的额外空间，用于保存双向链表中的前向指针和后向指针。 若有硬件定时器支持，可以避免每个时钟滴答的中断开销（将硬件定时器设为第一个定时器的到期时间），但有些处理器架构不提供这种能力。 简单的定时器方案（3）方案三：将方案二中的链表换成基于树的数据结构（如非平衡二叉树），将StartTimer的延迟从O(n)减少到O(log(n)。小结：以上三种简单方案中， PerTickBookkeeping或StartTimer的时间复杂度至少是O(log(n)，对于高速实现来说这是一个问题。 7.3 定时轮（Timing wheels）一个较简单的定时器问题：定时器的值为不大于MaxInterval的较小整数，粒度为1个时间单位。解决思路：用桶排序代替优先级链表 定时轮示意图定时轮的数据结构一个长度为MaxInterval的循环数组。当前时间由指向数组元素的一个指针表示（若指针指向第i个数组元素，当前时间为i时间单位）。每个数组元素包含一个指针，指向一个在该时刻到期的定时器链表。每一次时钟滴答，PerTickBookkeeping将指针下移一个元素。 定时轮的操作StartTimer：为设置某个定时器的值为当前时间（设为i）后j个时间单位，以（(i+j) mod MaxInterval）为索引，将定时器插到相应定时器链表的表头。PerTickBookkeeping：当前指针下移一个位置，检查指向的数组元素；若数组元素为空，什么也不做；若数组元素非空，对链表中的每个定时器调用ExpiryProcessing。 定时轮的复杂度分析StartTimer的时间为O(1)。如果没有定时器到期，PerTickBookkeeping的时间为O(1)。如果定时器链表为双向链表，StopTimer的时间也是O(1)。 定时轮的使用限制使用定时轮的假设：系统中某个实体原本就要在每个时钟滴答做O(1)的工作（如依靠CPU计时），只需让该实体顺带多执行几条指令走过空桶。（分摊开销）定时轮的使用限制：如果系统依靠硬件计时，中断开销太大！如果MaxInterval很大，需要很大的数组如何推广定时轮方法到更大的定时器值？ 7.4 哈希轮（Hashed Wheels）一个有用的类比：定时轮类似于用元素（定时器值）作为索引，将元素插入到一个数组中。如果元素的值域很大，数组很稀疏，可先对元素值做一个哈希运算，用哈希值作为数组索引。由类比得到的启发：如果要实现的定时器值很大，能否先对定时器值做一个哈希来生成索引呢？ 哈希轮的原理最简单的哈希函数：令表的长度为2k，用定时器值除以表长，取余数（最低k位）作为哈希值。启动定时器：用定时器值除以表长，取余数加到当前时间指针上生成数组索引，将商保存到数组索引指向的链表中。 哈希轮示例冲突链表的维护（1）方法一：在每个hash bucket中，定时器按到期时间从小到大排列（有序链表）。 算法维护一个时间变量t，每当指针回到数组起始位置时，t+。每个时钟滴答，当前时间指针下移一个位置，用t 与表头元素（商）进行比较。最坏情况下，StartTimer的时间为O(n)。 冲突链表的维护（2）方法二：在每个hash bucket中，新加入的定时器放在表头（无序链表）每个时钟滴答，当前时间指针下移一个位置；如果元素所指链表非空，递减链表中每一个元素（高24位定时器值）；若某个元素为0，调用相应的ExpiryProcessing方法二的复杂度分析StartTimer最坏及平均延迟均为O(1)若定时器数量nTableSize，PerTickBookkeeping的平均延迟仍为O(1)，这是因为：每隔TableSize个时钟滴答，所有活跃定时器都做了一次减1，平均每个时钟滴答的运算次数是n/TableSize次。如果所有定时器都哈希到一个hash bucket，那么，每隔TableSize个时钟滴答要做O(n)的工作，但在其余的每个时钟滴答内只做O(1)的工作，平均来说仍是O(1)。若希望每个时钟滴答内所做的工作少且有界，只需令哈希表长度比需要支持的并发定时器数量大即可。哈希函数的选择以上复杂度分析结果对任何一种哈希函数均适用哈希函数的选择并不重要：哈希函数只影响PerTickBookkeeping延迟的突发性，并不影响它的平均延迟不管采用什么哈希函数，PerTickBookkeeping的最坏情况延迟总是O(n) 因此，只需选择简单的哈希函数就可以了。7.5 分层定时轮（Hierarchical Wheels）为表示最长时间为100天（8640000秒）的定时器，只需使用以下4个不同时间粒度的数组：一个长度为100的数组，每个元素表示1天一个长度为24的数组，每个元素表示1小时一个长度为60的数组，每个元素表示1分钟一个长度为60的数组，每个元素表示1秒钟所需空间： 100+24+60+60=244个存储位置举例设置定时器假定当前时间是11天10时24分30秒，需设置一个时长为50分45秒的定时器：首先计算定时器的绝对到期时间为11天11时15分15秒；将定时器插入到小时数组中当前指针（10时）向下一个元素（11时）所指的链表中，将余数（15分15秒）存入该位置。秒数组的工作方式秒数组按如下方式工作：在硬件时钟的每个滴答，秒指针加1如果当前元素所指链表非空，对链表中的每个元素执行ExpiryProcessing其它三个数组的更新为推动分层定时轮，系统中总有以下时钟：一个60秒的定时器：用来更新分钟数组一个60分钟的定时器：用来更新小时数组一个24小时的定时器：用来更新天数组以60秒定时器为例：每当60秒定时器到期，将当前分钟指针下移1个位置，为分钟指针指向的定时器（链）执行ExpiryProcessing，重新插入一个60秒定时器。时间到达指定的小时当时间到达11时（此时小时指针指向元素11，分钟指针和秒指针都指向各自数组的元素0）：ExpiryProcessing检查链表中的元素，获得剩余时间15分15秒将定时器移动到分钟数组当前指针（0）向后15个元素（15分）的链表中，存入余数15秒。时间到达指定的分和秒当分钟指针到达第15个元素时（此时秒指针指向元素0）：ExpiryProcessing检查链表中的元素，获得剩余时间15秒将定时器移动到秒数组，放入当前秒指针（0）向后15个元素（15秒）的链表中当秒指针到达第15个元素时：定时器到期，执行用户的ExpiryProcessing7.6 BSD实现原先的BSD实现：将定时器组织在一个有序链表中，每个定时器值为距离前一个定时器到期时间的时长。设置和取消定时器时沿链表查找，时间复杂度为O(n)。查找定时器的过程中，中断被锁定。改进的实现：基于哈希轮，启动、取消和维护定时器都只需常数时间，中断被锁定的时间很短可支持几千个同时活跃的时钟 7.7 获得细粒度定时器早期的BSD实现，定时器粒度为200ms。即使使用定时轮，粒度也不可能低于定时器滴答的粒度（典型地为1ms）。通过提高定时器芯片的中断频率来获得细粒度定时器，中断处理开销太大：在500MHz的Pentium CPU上测得一次中断处理的开销约为4.5微秒如果定时器硬件每10微秒中断一次，则中断处理开销就要占到45%运用系统思维整个CPU时间充满了各种转换事件，包括系统调用、异常（如缺页）、硬件中断等。设想：在处理转换事件的代码中加入对定时器的检查，不会增加很多开销。但和硬件时钟中断不同的是，转换事件的发生频率不可预测。经实际测量：转换事件之间的平均延迟在530微秒之间变化超过100微秒的延迟仅有6%的发生率最大延迟从未超过1ms提供“软”定时器设施放宽系统要求（P3）：不试图实现一个总能提供微秒级定时器的“硬”定时器设施，而是实现一个经常能提供10微秒定时器的“软”定时器设施。为限制软定时器设施的误差，可以增加一个每隔1ms中断一次的硬件时钟中断。许多网络应用可以从软定时器受益，如使用快速重传进行错误恢复时，多数情况下可以很快（小于1ms）进行。7.8 小结定时轮：无论有多少个定时器，可将定时器实现的开销降至常数，这使得一个定时器设施可以支持非常多的定时器。软件定时器：可以减少由PerTickBookkeeping引起的操作系统开销，使得一个定时器设施在多数情况下可以提供细粒度的定时器。