专栏首页架构之美基于Linux内核的时间轮算法设计实现【附代码】

基于Linux内核的时间轮算法设计实现【附代码】

首先声明,本文内容参考了以下博客文章,向这三篇文章的作者表示感谢。

  1. https://www.cnblogs.com/arnoldlu/p/7078262.html
  2. https://blog.csdn.net/HELPLEE601276804/article/details/36717979
  3. https://www.cnblogs.com/lsgxeva/p/8072468.html

1. 时间轮算法基本思想

对于一个复杂的软件系统,定时器的对任务的管理和调度至关重要,通常定时器的管理已成为一个复杂系统的重要基础设施。

定时器有很多种(一文完全理解定时器实现技术),基于升序的定时器时间链表是一种最直接的实现方式:即按照定时器时间到的时间顺序依次存放在一个链表中进行管理。但是这种链表存在效率的不足,就是当插入定时器的时候时间复杂度是O(n). 因此需要一种更高效地管理定时器的数据结构和算法,这里结合Linux内核中基于时间轮的定时器管理器的具体实现,介绍一种基于时间轮的定时器管理算法。图1为时间轮的基本结构:

图1 定时器基本结构

图1所示的是一个时间轮的基本结构。时间轮分为N个(例如8个)时间槽slot,每时间槽指向一个定时器链表,这个链表里包含多个定时器,这个链表的定时器Timeout时间相同,因此链表里的定时器无须排序。

时间轮每一个滴答时间转动一格,会指向下一个时间槽。这里的滴答时间取决于时间轮的具体实现,可以是系统的一个时钟时间,也可以是一个毫秒,一秒钟等。

如果记时间轮的一个滴答时间为si(slot interval),即时间轮每转动一个槽的时间为si,如果有N个槽,那么时间轮转动一圈的时间为N * si。

如果时间轮开始转动的起始时间为ts,那么当有个定时器Timeout时间为t的定时器要加入到时间轮,那么应该将这个定时器放到哪个时间槽对应的链表呢?可以用下面的公式计算:

((t - ts)/ si) % N

以图1为例,如果时间轮一个滴答时间为1秒,假设时间轮开始转动时间为0,那么一个定时器Timeout=6s的定时器应该加到6号时间槽对应的链表里,一个定时器Timeout=7s的定时器应该加到7号槽对应的链表里。

那么时间轮该如何检查定时器是否时间到呢?同样地,如果时间轮开始转动的起始时间为ts,当前时间为tc,则计算

((tc - ts)/ si) % N

计算结果则为定时器时间到的那个时间槽对应编号,这个时间槽对应的链表里的定时器全部时间到。

聪明的读者马上会想到一个问题:那么一个定时器Timout=8s的定时器会加到0号槽,岂不是和定时器Timeout=0s(马上时间到)的定时器放到一个槽里了?这是因为图1所示的时间轮刻度只要8个(即只能管理8种不同Timout的定时器),因此为了解决这种问题,需要增加N的值。

增加N的值更聪明的办法是采用多级时间轮,即在图1所示的时间轮外面再环绕一个时间轮,假设外面时间轮的刻度为8,即外轮的时间槽也是8个,每个时间槽也对应一个链表。同时定义时间轮的转动规则:当里面的时间轮转动1圈(8格),外面的时间轮转动1格。可以看到,采用这种方式,二级时间轮可以管理(8*8=64)种不同Timeout的定时器。

在二级时间轮的结构下,一个定时器Timeout=t的定时器怎么加入时间轮呢?还是假设二级时间轮都有8个槽,假设时间轮的起始时间为ts,则采用如下算法将Timeout=t的定时器加入时间轮:

1)计算t-ts/si;

2)如果t-ts/si < 8,则以t-ts/si的低3位作为索引加入内轮;

3)如果t-ts/si>= 8(当然要小于64,否则又溢出),则以t-ts/si的高3位作为索引加入外轮;

二级时间轮检查时间到的算法与单机时间轮类似,不同的地方就是当内轮的所有时间槽都时间到后,要把外轮的时间槽链表迁移到内轮。

综上所述:基于排序链表的定时器使用唯一的链表来管理所有定时器,所以插入定时器的数目越多,效率就会越低,而时间轮则是利用哈希表的思想,将定时器散列到不同的链表中,这样每条链表上的数据就会显著少于原来排序链表的数目。插入操作的效率基本不受定时器数目的影响(不需要排序,直接散列到一个链表上)。因此插入定时器的时间复杂度和定时器数量n无关,为O(1)。

显然要提高时间轮的精度,就要使si(slot interval)足够小,要提高其执行效率则要N要足够大。如果最里面一级时间轮的槽采用n1为二进制编码,外面一级时间轮采用n2位二进制编码,则总共可以管理的时间范围为0 ~ 2(n1+n2) – 1。以上面的例子为例,如果二级时间轮都是3位二进制编码(8个时间槽),那么总共可以管理的时间范围为0 ~ 63,即64种Timeout的定时器。

Linux内核采用多级时间轮。定义了5个链表数组(每个数组里面包含多个定时器链表):tv1-tv5都是一个链表数组,其中tv1的数组大小为TVR_SIZE(256,8位编码), tv2、tv3、tv4、tv5的数组大小为TVN_SIZE(64,6位编码)。可以看到一共是32位编码,总共可以管理的时间范围为0 ~ 232 – 1。

这5个数组就好比是5个齿轮,它们随着滴答时间的增长而不停地转动,每次只需处理第一个齿轮的某一个齿节,低一级的齿轮转动一圈,高一级的齿轮转动一个齿,同时自动把即将到期的定时器迁移到上一个齿轮中,所以低分辨率定时器通常又被叫做时间轮:time wheel。事实上,它的实现是一个很好的空间换时间软件算法。参考Linux的实现,具体代码如下:

首先定义如下宏:

2. 定时器的添加

要加入一个新的定时器,按以下步骤进行处理:

1)计算定时器到期时间和当前cpu定时器所经历过的毫秒数的差值,记为idx

2)根据idx的值,选择该定时器应该被放到tv1--tv5中的哪一个链表数组中,可以认为tv1-tv5分别占据一个32位数的不同比特位,tv1占据最低的8位,tv2占据紧接着的6位,然后tv3再占位,以此类推,最高的6位分配给tv5。最终的选择规则如下表所示:

确定链表数组后,接着要确定把该定时器放入数组中的哪一个链表中,如果时间差idx小于256,按规则要放入tv1中,因为tv1包含了256个链表,所以可以简单地使定时器的expires的低8位作为数组的索引下标,把定时器链接到tv1中相应的链表中即可。如果时间差idx的值在256--18383之间,则需要把定时器放入tv2中,同样的,使用定时器的expires的8--14位作为数组的索引下标,把定时器链接到tv2中相应的链表中,。定时器要加入tv3tv4 tv5使用同样的原理。经过这样分组后的定时器,在后续的tick事件中,系统可以很方便地定位并取出相应的到期定时器进行处理。代码如下:

3. 定时器到期处理

系统中的定时器按到期时间有规律地放置在tv1--tv5各个链表数组中,其中tv1中放置着在接下来的256个滴答时间(如毫秒)即将到期的定时器列表。系统滴答值一直在随着系统的运行而动态地增加,原则上是每个tick事件会加1,定时器加入tv1中使用的下标索引是定时器到期时间expires的低8位,所以假设当前的滴答值是0x34567826,则马上到期的定时器是在tv1.vec[0x26]中,如果这时候系统加入一个在滴答值0x34567828到期的定时器,他将会加入到tv1.vec[0x28]中,运行两个tick后,系统滴答的值会变为0x34567828,很显然,在每次tick事件中,定时器系统只要以当前滴答值的低8位作为索引,取出tv1中相应的链表,里面正好包含了所有在该滴答值到期的定时器列表。

那什么时候处理tv2--tv5中的定时器?每当当前系统滴答值的低8位为0值时,这表明当前系统滴答值的第8-13位有进位发生,这6位正好代表着tv2,这时只要按当前系统滴答值的第8-13位的值作为下标,移出tv2中对应的定时器链表,然后用第2节的步骤把它们重新加入到定时器系统中来,因为这些定时器一定会在接下来的256个tick期间到期,所以它们肯定会被加入到tv1数组中,这样就完成了tv2往tv1迁移的过程。同样地,当当前系统滴答值的第8-13位为0时,这表明当前系统滴答值的第14-19位有进位发生,这6位正好代表着tv3,按当前系统滴答值的第14-19位的值作为下标,移出tv3中对应的定时器链表,然后用第2节的步骤把它们从新加入到定时器系统中来,显然它们会被加入到tv2中,从而完成tv3到tv2的迁移,tv4,tv5的处理可以以此作类推。具体地,定时器时间到需要实现下面二个函数:check和cascade,其中cascade完成时间轮的从外轮向里轮的进位。

基于Linux内核的时间轮实现代码,可以在应用程序层面实现一个基于时间轮的管理器。部分代码如下所示:

TimerManager 类的定义如下:

本文分享自微信公众号 - 架构之美(beautyArch),作者:辜希武

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一文完全理解定时器实现技术

    上一篇热文《构建企业级业务高可用的延时消息中台》引起了大家的讨论,评论里讨论除了时间轮算法外的其他高性能算法实现延迟消息的定时器。这一篇文章系统的梳理主流定时器...

    孙玄@奈学教育
  • 10个常见的软件架构模式

    想知道如何设计大型企业级的系统吗?在开始主要的代码开发之前,我们必须选择一种合适的体系架构,它将为我们提供所需的功能和质量属性。因此,在将它们应用到我们的设计之...

    孙玄@奈学教育
  • 分布式柔性事务之事务消息详解

    在 《柔性事务之TCC详解》 和《柔性事务之Saga详解》两文中我们详细剖析了柔性事务的第一个分支补偿型事务。在《刚性事务总结和柔性事务概述》中我们介绍过的柔性...

    孙玄@奈学教育
  • FreeRTOS 软定时器实现

    考虑平台硬件定时器个数限制的, FreeRTOS 通过一个 Daemon 任务(启动调度器时自动创建)管理软定时器, 满足用户定时需求. Daemon 任务会在...

    orientlu
  • Qt多种定时器

      使用startTimer开启定时器,使用killTimer(int id)接口来关闭指定的定时器。 启动定时器后会在对应间隔时间触发timerEvent事...

    Qt君
  • 18.5.13日报

    1,找到帧率低的原因了,wkeWake里做的帧率限制。打开后,并且调整每帧的sleep之类,帧率基本和chrome差不多

    龙泉寺扫地僧
  • 巧用SDK,帮你减少开发时间

    已经介绍过很多次NXP的SDK在开发中的应用,但多是基于KV系列和K系列的芯片,最近一个小项目用的是Kinetis KE02系列,该系列已经在SDK中支持,如...

    用户1605515
  • 单片机捕捉功能

    输入捕捉:具有此功能的一个管脚,定时器在内部时钟的作用下在运行,此时管脚来了个中断,假如上升沿吧。在中断的作用下,定时器停止工作,此时可以读出定时器的数值,读出...

    用户4645519
  • iOS中的CADisplayLink定时器 原

        说到定时器,在iOS中最常用的为NSTimer类,其实CADisplayLink类在某些场景下使用,要比NSTimer类更加适合。首先CADisplay...

    珲少
  • jquery_12js基础_定时器

    在html页面开发中,我们有时会用到定时器,比如时间倒数,商品的限时抢购等,都会使用到js的定时器。那么这个定时器怎么使用?下面我们来看一下。

    用户1730674

扫码关注云+社区

领取腾讯云代金券