定时器及时间轮

定时器的基本模型

  • StartTimer(Interval, TimerId, ExpiryAction)  注册一个时间间隔为 Interval 后执行ExpiryAction 的定时器实例,其中返回 TimerId 以区分在定时器系统中的其他定时器实例。

  • StopTimer(TimerId)  根据 TimerId 找到注册的定时器实例并执行 Stop 。

  • PerTickBookkeeping()  在一个 Tick 内,定时器系统需要执行的动作,它最主要的行为就是检查定时器系统中,是否有定时器实例已经到期。

  • ExpiryProcessing()  在定时器实例到期之后,执行预先注册好的 ExpiryAction 行为。

  • Single-Shot Timer  定时器,从注册到终止,仅仅只执行一次。

  • Repeating Timer  定时器,在每次终止之后,会自动重新开始。本质上,可以认为Repeating Timer 是在 Single-Shot Timer 终止之后,再次注册到定时器系统里的Single-Shot Timer,因此在支持 Single-Shot Timer 的基础上支持 Repeating Time并不算特别的复杂。

时间轮定时器:

时间轮是基于一个循环链表(实际上就是个数组,通过下标控制)的数据结构。所以也因此得名WheelTimer。

时间轮算法的复杂程度跟分级层数有关,最简单的就是一层的,复杂一点的就是分层时间轮(Hierarchical Timing Wheels)。

对于一层的时间轮,添加/删除/取消任务的复杂度是O(1),过期/执行任务时,最差情况是O(n)(类似HashMap中的hash冲突,退化成链表),平均O(1)(和HashMap类似,格子越多,分散的越均匀,但是占用的空间也就越多)。

简单时间轮示意图:

   

时间轮中的相关术语:

    • tick:时间格,时间轮中的一格,一个格子代表一段时间;
    • tickDuration: 间隔,每一格代表的时长;
    • ticksPerWheel: 格数,时间轮总共有多少格.
    • newTimeout: 定时任务被分配到的超时时间

时间轮上的每个tick都可以存放多个任务,并使用一个List保存tick上的任务。轮到哪个tick就执行哪个tick上的任务。任务通过取模来决定放入哪个tick。

如果一个tick用时1s(tickDuration),而总共有60个tick,那么走完一圈用时差不多是60 * 1s

当前指针指向的tick1,如果需要调度一个2s后需要执行的任务,那么需要等待2个tick。所以任务应该被放在第3个tick中。假设一个任务需要1min30s后执行,那么任务应该是落在指针走完后1圈后的第31个tick中。

 

原文地址:https://www.cnblogs.com/tongyishu/p/11797071.html