高性能定时器的设计与实现

刘启铨

（中兴软创科技股份有根公司，江苏 南京 210012）

目前主要有几种定时器处理方法，第一种方法是使用LINUX系统内部的三个定时器（定时器在初始化时，被赋予一个初始值，随时间递减，递减至0后发出信号，同时恢复初始值。在任务中，我们可以使用一种或者全部三种定时器，但同一时刻同一类型的定时器只能使用一个）；第二种是使用alarm定时发送一个信号。前者定时器个数很少、效率较低、准确性较差；后者定时器个数少、效率低，准确性差，共同的是无法同时并发，信号容易丢失，需要很小心的处理信号的问题。因此这些传统的定时器距离我们的要求还存在着很大的差距，根本不可能符合计费系统的要求，所以有必要重新设计一种高性能的定时器，该定时器重点具有以下一些特点：

（1）具有很高的实时性；

（2）具有较高的灵活性和扩展性；

（3）可以安全的管理较多的定时任务；

（4）支持较多的到期定时任务并发；

（5）可以根据到期待执行的定时任务负载情况自动进行处理能力的动态扩展和收缩。

1 高性能定时器架构

从系统层面看，高性能定时器内部由定时器管理模块和定时器执行模块组成，两个模块分工明确、各司其职、互相配合，共同完成定时任务的新增、管理、到期推送、到期执行和删除的一整套功能。高性能定时器对外可以看成一个处理黑盒，外部不用关心其内部的具体实现，只需要调用其暴露给外部的接口就可以了。

图1 定时任务处理流图

大量的定时任务通过定时器模块暴露出的对外接口加入定时器管理池，由定时器管理模块进行管理和维护，定时器管理模块同时也负责软时钟的维护，当定时器管理池中的定时任务节点到达触发时间点时，定时器管理模块就把该节点定时任务取出来并放入定时器执行池中即进行推送，由定时器执行模块进行抢占式执行该到期定时任务。

图2 时间轮算法

图3 软时钟的处理流程

图4 定时任务的新增流程

1.1 定时器管理模块

定时器管理模块采用分级别的时间轮算法 （Hierarchical Timing Wheel），即把整个时间轮按照不同的时间单位进行分组，然后每组又由多个时间片组成，每个时间片下面又对应一个链表，比如第一组1个时间片（序号为0）表示小于1秒，第二组9个时间片（序号为1-9）分别表示1-9秒，第三组9个时间片（序号为11-19）分别表示10秒-90秒，第四组9个时间片（序号为21-29）分别表示100秒-900秒。

例如一个定时任务要求在加入定时器管理池后15秒钟执行，那么定时器管理模块会根据计算得出该定时任务首先插入第二组的序号为5号时间片的双向链表，同时把任务节点的10s标志置为序号11，当该定时任务加入定时器管理池后，定时器管理模块经过5秒钟后把该定时任务从5号时间片对应的双向链表中取出，然后放入11号时间片对应的双向链表中，然后再经过10秒钟后，定时器管理模块就会再次把该定时任务从11号时间片对应的双向链表中取出，然后放入定时器执行池，由定时器执行模块执行该到期定时任务，至此就完成了该定时任务从新增到执行的全过程。

图5 定时任务的删除流程

图6 到期任务的激活流程

定时器管理模块主要具有以下的功能：

（1）软时钟的维护；

（2）定时任务的新增；

（3）定时任务的删除；

（4）到期任务的推送。

1.1.1 软时钟的维护

首先定时器管理模块内部取系统时间作为基准时间，然后进入循环，循环内按照事先设定的休眠毫秒数值进行预休眠，然后软时钟百毫秒数值+1，接着进行定时器管理池的处理，如果有到期的定时任务，就把该任务的相关信息放入定时器执行池，然后软时钟判断是否到整秒钟，如果到了整秒钟，软时钟的缓存中的秒钟数+1，然后判断是否配置了需要进行时间校正和软时钟时间是否已经到校正的时间了，如果两个条件都满足就取系统时间做参照进行软时钟的缓存中的秒钟数的校正，最后取当前系统时间和基准系统时间进行比较确定需要补休眠的毫秒数值并按此进行补休眠。

1.1.2 定时任务的新增

首先外部调用定时器管理模块的对外新增定时任务的接口，定时器管理模块内部判断定时器任务节点池是否还存在空闲节点，如果存在空闲节点进行互斥加锁，根据该定时任务的具体信息进行计算得到对应的组，对应的时间片等，然后把定时任务放入该组该时间片的链表中，同时把该节点的其他相应组标志位进行赋值，然后互斥解锁，返回结果。

1.1.3 定时任务的删除

首先外部调用定时器管理模块的对外删除定时任务的接口，定时器管理模块内部判断定时器任务节点池中是否存在该任务节点，如果存在该任务节点，则从相应的任务节点队列中删除该任务节点，并把该任务节点放入任务节点池中，并置为空闲状态，最后返回结果。

1.1.4 到期任务的推送

定时器管理模块开始遍历每个时间片，对于每个时间片首先判断该时间片对应的链表是否非空，如果非空就判断该链表的头节点的触发时间是否已经到达，如果到达就把该头节点放入待执行定时任务队列，并从链表中删除，如果该任务是循环任务的话，就把该任务重新加入链表尾部，同时判断新的头节点的触发时间是否已经到达，如果已经到达就重复上面的操作，直至所有的时间片都遍历结束。

1.2 定时器执行模块

到期任务的执行：

图7 到期任务的执行流程

定时器执行模块首先进行互斥加锁，然后判断任务执行池中是否非空，如果有任务的话则从任务执行池中取得任务，同时把任务执行池中的读取位置下移，待处理任务数-1，互斥解锁，最后执行该到期的定时任务。

2 到期任务处理能力自扩展和收缩

传统的定时器对于到期的任务只能串行的进行处理，同一时刻只能执行单个到期任务，如果此到期任务执行比较耗时的话就会引起其他到期任务延迟执行和到期任务大量积压的严重的后果，对于计费系统这种实时性要求很高的场合，这种影响是危害性很大的，所以高性能定时器采用专门的资源监控模块实时监控待处理的到期定时任务队列和任务执行线程池，如果发现队列堵塞且任务的处理线程池中的工作线程都很忙的情况下说明实时处理能力不够就动态增加工作线程以提高任务的处理能力，如果发现待处理队列较空且任务的处理线程池中的工作线程较空闲的情况下说明实时处理能力已经满足就动态减少工作线程以降低任务的处理能力，这样就保证了定时任务的准确性、实时性和高并发性，同时对系统资源的占用也较少，以平衡两者之间的关系。

3 结束语

本文描述了采用分级时间轮的高性能定时器的设计及实现，该定时器能够高性能实时并发处理大量的定时任务。首先我们基于定时任务的管理和到期任务的执行相分离的原则对系统进行了设计，定时任务的数据存储采用双向链表的方式，加快节点的插入和检索。到期任务的数据存储采用环形数组的方式，加快定时任务的插入和检索。

考虑到需要较高的并发性，本架构采用到期任务处理能力自扩展和收缩，有专门的监控模块实时监控到期任务的待处理队列和处理到期任务的执行线程池的情况，并根据情况的变化进行处理能力的动态调整已达到在满足实时性和并发性的情况下，尽可能下的占用系统资源，以减少对系统其他功能模块的影响。