七章维护定时器.ppt

《七章维护定时器.ppt》由会员分享，可在线阅读，更多相关《七章维护定时器.ppt（34页珍藏版）》请在三一文库上搜索。

1、第七章 维护定时器,7.1 定时器,网络协议大量使用定时器实现与时间有关的功能 当以下任一情况发生时，定时器模块存在性能问题: 定时器算法由CPU实现：每一个硬件时钟滴答都要中断CPU。若时钟精度在微秒量级，中断处理开销很大。 要求细粒度定时器（如微秒量级）：启动/终止延迟要小 同时活跃的定时器数目很大：要求启动/终止延迟小 当网络速度提高时， 定时器精度要提高：需要细粒度的定时器精确测量RTT，以及加快重传与恢复 启动/终止速度要提高：包速率提高了,定时器模块的组成,StartTimer (Interval, RequestID, ExpiryAction)： 启动一个定时器，定时器在Int

2、erval个时间单位后超时 StopTimer (RequestID)： 终止指定的定时器 PerTickBookkeeping： 每隔1个定时器粒度，检查是否有定时器超时；若有，调用ExpiryProcessing ExpiryProcessing： 执行StartTimer()中指定的ExpiryAction,选择定时器算法的性能指标,两个性能指标： 定时器数据结构占用的空间（空间复杂度） 定时器模块中例程的调用延迟（从调用到完成的时间）（时间复杂度） 以上两个性能指标都与定时器的数量（平均数量或最大数量）有关。,7.2 简单的定时器方案,方案一： StartTimer()找到一个内存位置

3、（变量），设置该位置的值为Interval。 每隔1个定时器粒度，PerTickBookkeeping递减每个活跃的定时器；若某个定时器的值变为0，调用相应的ExpiryAction。 复杂度分析： 每个定时器只使用一个内存位置，所用空间最小 PerTickBookkeeping的执行时间为O(n)，其余为O(1) 适合活跃定时器少、PerTickBookkeeping实现快的场合,简单的定时器方案（2）,方案二（用于较早的UNIX版本）： 定时器保存在一个有序链表中，按照定时器到期的绝对时间由低到高存储。 每个时钟滴答，PerTickBookkeeping递增当前时间，然后和表头进行比较，将

4、超时的表头元素删除。 新增一个定时器时，StartTimer搜索链表，找到一个合适的位置插入新定时器。,方案二的复杂度分析,PerTickBookkeeping的平均时间为O(1)。 StartTimer的最大时间为O(n)。 如果定时器链表是双向链表，StopTimer的时间可为O(1)。 需要O(n)的额外空间，用于保存双向链表中的前向指针和后向指针。 若有硬件定时器支持，可以避免每个时钟滴答的中断开销（将硬件定时器设为第一个定时器的到期时间），但有些处理器架构不提供这种能力。,简单的定时器方案（3）,方案三： 将方案二中的链表换成基于树的数据结构（如非平衡二叉树），将StartTimer

5、的延迟从O(n)减少到O(log(n)。 小结： 以上三种简单方案中， PerTickBookkeeping或StartTimer的时间复杂度至少是O(log(n)，对于高速实现来说这是一个问题。,7.3 定时轮（Timing wheels）,一个较简单的定时器问题： 定时器的值为不大于MaxInterval的较小整数，粒度为1个时间单位。 解决思路： 用桶排序代替优先级链表,定时轮示意图,定时轮的数据结构,一个长度为MaxInterval的循环数组。 当前时间由指向数组元素的一个指针表示（若指针指向第i个数组元素，当前时间为i时间单位）。 每个数组元素包含一个指针，指向一个在该时刻到期的定时

6、器链表。 每一次时钟滴答，PerTickBookkeeping将指针下移一个元素。,定时轮的操作,StartTimer： 为设置某个定时器的值为当前时间（设为i）后j个时间单位，以（(i+j) mod MaxInterval）为索引，将定时器插到相应定时器链表的表头。 PerTickBookkeeping： 当前指针下移一个位置，检查指向的数组元素； 若数组元素为空，什么也不做；若数组元素非空，对链表中的每个定时器调用ExpiryProcessing。,定时轮的复杂度分析,StartTimer的时间为O(1)。 如果没有定时器到期，PerTickBookkeeping的时间为O(1)。 如果定

7、时器链表为双向链表，StopTimer的时间也是O(1)。,定时轮的使用限制,使用定时轮的假设： 系统中某个实体原本就要在每个时钟滴答做O(1)的工作（如依靠CPU计时），只需让该实体顺带多执行几条指令走过空桶。（分摊开销） 定时轮的使用限制： 如果系统依靠硬件计时，中断开销太大！ 如果MaxInterval很大，需要很大的数组 如何推广定时轮方法到更大的定时器值？,7.4 哈希轮（Hashed Wheels）,一个有用的类比： 定时轮类似于用元素（定时器值）作为索引，将元素插入到一个数组中。 如果元素的值域很大，数组很稀疏，可先对元素值做一个哈希运算，用哈希值作为数组索引。 由类比得到的启发

8、： 如果要实现的定时器值很大，能否先对定时器值做一个哈希来生成索引呢？,哈希轮的原理,最简单的哈希函数： 令表的长度为2k，用定时器值除以表长，取余数（最低k位）作为哈希值。 启动定时器： 用定时器值除以表长，取余数加到当前时间指针上生成数组索引，将商保存到数组索引指向的链表中。,哈希轮示例,冲突链表的维护（1）,方法一： 在每个hash bucket中，定时器按到期时间从小到大排列（有序链表）。 算法维护一个时间变量t，每当指针回到数组起始位置时，t+。 每个时钟滴答，当前时间指针下移一个位置，用t 与表头元素（商）进行比较。 最坏情况下，StartTimer的时间为O(n)。,冲突链表的维

9、护（2）,方法二： 在每个hash bucket中，新加入的定时器放在表头（无序链表） 每个时钟滴答，当前时间指针下移一个位置；如果元素所指链表非空，递减链表中每一个元素（高24位定时器值）；若某个元素为0，调用相应的ExpiryProcessing,方法二的复杂度分析,StartTimer最坏及平均延迟均为O(1) 若定时器数量nTableSize，PerTickBookkeeping的平均延迟仍为O(1)，这是因为： 每隔TableSize个时钟滴答，所有活跃定时器都做了一次减1，平均每个时钟滴答的运算次数是n/TableSize次。 如果所有定时器都哈希到一个hash bucket，那么

10、，每隔TableSize个时钟滴答要做O(n)的工作，但在其余的每个时钟滴答内只做O(1)的工作，平均来说仍是O(1)。 若希望每个时钟滴答内所做的工作少且有界，只需令哈希表长度比需要支持的并发定时器数量大即可。,哈希函数的选择,以上复杂度分析结果对任何一种哈希函数均适用 哈希函数的选择并不重要： 哈希函数只影响PerTickBookkeeping延迟的突发性，并不影响它的平均延迟 不管采用什么哈希函数，PerTickBookkeeping的最坏情况延迟总是O(n) 因此，只需选择简单的哈希函数就可以了。,7.5 分层定时轮（Hierarchical Wheels）,为表示最长时间为100天（

11、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秒）存入该位置。,秒数组的工作方式,秒数组按如下方式工作：

12、 在硬件时钟的每个滴答，秒指针加1 如果当前元素所指链表非空，对链表中的每个元素执行ExpiryProcessing,其它三个数组的更新,为推动分层定时轮，系统中总有以下时钟： 一个60秒的定时器：用来更新分钟数组 一个60分钟的定时器：用来更新小时数组 一个24小时的定时器：用来更新天数组 以60秒定时器为例： 每当60秒定时器到期，将当前分钟指针下移1个位置，为分钟指针指向的定时器（链）执行ExpiryProcessing，重新插入一个60秒定时器。,时间到达指定的小时,当时间到达11时（此时小时指针指向元素11，分钟指针和秒指针都指向各自数组的元素0）： ExpiryProcessing

13、检查链表中的元素，获得剩余时间15分15秒 将定时器移动到分钟数组当前指针（0）向后15个元素（15分）的链表中，存入余数15秒。,时间到达指定的分和秒,当分钟指针到达第15个元素时（此时秒指针指向元素0）： ExpiryProcessing检查链表中的元素，获得剩余时间15秒 将定时器移动到秒数组，放入当前秒指针（0）向后15个元素（15秒）的链表中 当秒指针到达第15个元素时： 定时器到期，执行用户的ExpiryProcessing,7.6 BSD实现,原先的BSD实现： 将定时器组织在一个有序链表中，每个定时器值为距离前一个定时器到期时间的时长。 设置和取消定时器时沿链表查找，时间复杂度

14、为O(n)。查找定时器的过程中，中断被锁定。 改进的实现： 基于哈希轮，启动、取消和维护定时器都只需常数时间，中断被锁定的时间很短 可支持几千个同时活跃的时钟,7.7 获得细粒度定时器,早期的BSD实现，定时器粒度为200ms。 即使使用定时轮，粒度也不可能低于定时器滴答的粒度（典型地为1ms）。 通过提高定时器芯片的中断频率来获得细粒度定时器，中断处理开销太大： 在500MHz的Pentium CPU上测得一次中断处理的开销约为4.5微秒 如果定时器硬件每10微秒中断一次，则中断处理开销就要占到45%,运用系统思维,整个CPU时间充满了各种转换事件，包括系统调用、异常（如缺页）、硬件中断等。

15、 设想： 在处理转换事件的代码中加入对定时器的检查，不会增加很多开销。 但和硬件时钟中断不同的是，转换事件的发生频率不可预测。经实际测量： 转换事件之间的平均延迟在530微秒之间变化 超过100微秒的延迟仅有6%的发生率 最大延迟从未超过1ms,提供“软”定时器设施,放宽系统要求（P3）： 不试图实现一个总能提供微秒级定时器的“硬”定时器设施，而是实现一个经常能提供10微秒定时器的“软”定时器设施。 为限制软定时器设施的误差，可以增加一个每隔1ms中断一次的硬件时钟中断。 许多网络应用可以从软定时器受益，如使用快速重传进行错误恢复时，多数情况下可以很快（小于1ms）进行。,7.8 小结,定时轮： 无论有多少个定时器，可将定时器实现的开销降至常数，这使得一个定时器设施可以支持非常多的定时器。 软件定时器： 可以减少由PerTickBookkeeping引起的操作系统开销，使得一个定时器设施在多数情况下可以提供细粒度的定时器。,