一文读懂定时器实现技术

发布时间:2023-09-07  

1. 定时器介绍

程序里的定时器主要实现的功能是在未来的某个时间点执行相应的逻辑。在定时器模型中,一般有如下几个定义。

interval:间隔时间,即定时器需要在interval时间后执行

StartTimer:添加一个定时器任务

StopTimer:结束一个定时器任务

PerTickBookkeeping: 检查定时器系统中,是否有定时器实例已经到期,相当于定义了最小时间粒度。

常见的实现方法有如下几种:

链表

排序链表

最小堆

时间轮

接下来我们一起看下这些方法的具体实现原理。


2. 定时器实现方法

2.1 链表实现

链表的实现方法比较粗糙。链表用于存储所有的定时器,每个定时器都含有interval 和 elapse 两个时间参数,elapse表示当前被tickTimer了多少次。当elapse 和interval相等时,表示定时器到期。

在此方案中,添加定时器就是在链表的末尾新增一个节点,时间复杂度是 O(1)。

如果想要删除一个定时器的话,我们需要遍历链表找到对应的定时器,时间复杂度是O(n)。

此方案下,每隔elapse时间,系统调用信号进行超时检查,即PerTickBookkeeping。每次PerTickBookkeeping需要对链表所有定时器进行 elapse++,因此可以看出PerTickBookkeeping的时间复杂度是O(N)。

可以看出此方案过于粗暴,所以使用场景极少。


2.2 排序双向链表实现

排序双向链表是在链表实现上的优化。优化思路是降低时间复杂度。

首先,每次PerTickBookkeeping需要自增所有定时器的elapse变量,如果我们将interval变为绝对时间,那么我们只需要比较当前时间和interval时间是否相等,减少了对每个定时器的操作。


如果不需要对每个定时器进行操作,我们将定时器进行排序,那么每次PerTickBookkeeping都只需要判断第一个定时器,时间复杂度为O(1)。

相应的,为了维持链表顺序,每次新增定时器需要进行链表排序时间复杂度为 O(N)。

每次删除定时器时,由于会持有自己节点的引用,所以不需要查找其在链表中所在的位置,所以时间复杂度为O(1),双向链表的好处。

图片

图1 双向链表实现示意图


2.3 时间轮实现

时间轮的数据结构是数组 + 链表。

他的时间轮为数组,新增和删除一个任务,时间复杂度都是O(1)。

PerTickBookkeeping每次转动一格,时间复杂度也是O(1)。


2.4 最小堆实现

最小堆是堆的一种, (堆是一种二叉树), 指的是堆中任何一个父节点都小于子节点, 子节点顺序不作要求。

二叉排序树(BST)指的是: 左子树节点小于父节点, 右子树节点大于父节点, 对所有节点适用

图片

图3 最小堆

树的基本操作是插入节点和删除节点。对最小堆而言,为了将一个元素X插入最小堆,我们可以在树的下一个空闲位置创建一个空穴。如果X可以放在空穴中而不被破坏堆的序,则插入完成。否则就执行上滤操作,即交换空穴和它的父节点上的元素。不断执行上述过程,直到X可以被放入空穴,则插入操作完成。

因此我们可以知道最小堆的插入时间复杂度是O(lgN)。

最小堆的删除和插入逻辑基本类似,如果不做优化,时间复杂度也是O(lgN),但是实际实现方案上,做了延迟删除操作,时间复杂度为O(1)。

延迟删除即设置定时器的执行回调函数为空,每次最小堆超时,将触发pop_heap,pop会重新调整最小堆,最终删除的定时器将调整到堆顶,但是回调函数不处理。

可以看到PerTickBookkeeping只处理堆顶定时器,时间复杂度O(1)。

最小堆可以使用数组来进行表示,数组中,当前下标n的左子节点为2N + 1,当前下标n的右子节点小标为2N + 2。

图片

图4 最小堆的数组表示


3. 定时器不同实现对比

3.1 时间复杂度对比

图片

图5 不同实现时间复杂度

从上面的介绍来看,时间轮的时间复杂度最小、性能最好。


3.2 使用场景来看

在任务量小的场景下:最小堆实现,可以根据堆顶设置超时时间,数组存储结构,节省内存消耗,使用最小堆可以得到比较好的效果。而时间轮定时器,由于需要维护一个线程用来拨动指针,且需要开辟一个bucket数组,消耗内存大,使用时间轮会较为浪费资源。

在任务量大的场景下:最小堆的插入复杂度是O(lgN), 相比时间轮O(1) 会造成性能下降。更适合使用时间轮实现。


在业界,服务治理的心跳检测等功能需要维护大量的链接心跳,因此时间轮是首选。


文章来源于:电子工程世界    原文链接
本站所有转载文章系出于传递更多信息之目的,且明确注明来源,不希望被转载的媒体或个人可与我们联系,我们将立即进行删除处理。

我们与500+贴片厂合作,完美满足客户的定制需求。为品牌提供定制化的推广方案、专属产品特色页,多渠道推广,SEM/SEO精准营销以及与公众号的联合推广...详细>>

利用葫芦芯平台的卓越技术服务和新产品推广能力,原厂代理能轻松打入消费物联网(IOT)、信息与通信(ICT)、汽车及新能源汽车、工业自动化及工业物联网、装备及功率电子...详细>>

充分利用其强大的电子元器件采购流量,创新性地为这些物料提供了一个全新的窗口。我们的高效数字营销技术,不仅可以助你轻松识别与连接到需求方,更能够极大地提高“闲置物料”的处理能力,通过葫芦芯平台...详细>>

我们的目标很明确:构建一个全方位的半导体产业生态系统。成为一家全球领先的半导体互联网生态公司。目前,我们已成功打造了智能汽车、智能家居、大健康医疗、机器人和材料等五大生态领域。更为重要的是...详细>>

我们深知加工与定制类服务商的价值和重要性,因此,我们倾力为您提供最顶尖的营销资源。在我们的平台上,您可以直接接触到100万的研发工程师和采购工程师,以及10万的活跃客户群体...详细>>

凭借我们强大的专业流量和尖端的互联网数字营销技术,我们承诺为原厂提供免费的产品资料推广服务。无论是最新的资讯、技术动态还是创新产品,都可以通过我们的平台迅速传达给目标客户...详细>>

我们不止于将线索转化为潜在客户。葫芦芯平台致力于形成业务闭环,从引流、宣传到最终销售,全程跟进,确保每一个potential lead都得到妥善处理,从而大幅提高转化率。不仅如此...详细>>