精华内容
下载资源
问答
  • 基于时间种子的软件定时器算法的实现,包含了设置软件定时器,杀死定时器,暂停定时器,重置定时器处置的所有方法!
  • 本文在对μC/OS-II定时器算法分析的基础上,对定时精度和处理器占用情况进行了分析与测试,其结果在实时系统的设计与应用中具有借鉴意义。
  • 这一篇文章系统的梳理主流定时器算法实现的差异以及应用地方。 定时器介绍 程序里的定时器主要实现的功能是在未来的某个时间点执行相应的逻辑。在定时器模型中,一般有如下几个定义。 interval:间隔时间,即...

    这一篇文章系统的梳理主流定时器算法实现的差异以及应用地方。

    1. 定时器介绍

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

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

    StartTimer:添加一个定时器任务

    StopTimer:结束一个定时器任务

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

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

    链表

    排序链表

    最小堆

    时间轮

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

    1. 定时器实现方法

    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 时间轮实现

    时间轮示意图如下:

    系统梳理主流定时器算法实现的差异以及应用
    图2 时间轮

    时间轮的数据结构是数组 + 链表。 他的时间轮为数组,新增和删除一个任务,时间复杂度都是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 最小堆的数组表示

    1. 定时器不同实现对比

    3.1 时间复杂度对比

    系统梳理主流定时器算法实现的差异以及应用

    图5 不同实现时间复杂度

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

    3.2 使用场景来看

    在任务量小的场景下:最小堆实现,可以根据堆顶设置超时时间,数组存储结构,节省内存消耗,使用最小堆可以得到比较好的效果。而时间轮定时器,由于需要维护一个线程用来拨动指针,且需要开辟一个bucket数组,消耗内存大,使用时间轮会较为浪费资源。在任务量大的场景下:最小堆的插入复杂度是O(lgN), 相比时间轮O(1) 会造成性能下降。更适合使用时间轮实现。在业界,服务治理的心跳检测等功能需要维护大量的链接心跳,因此时间轮是首选。

    更多免费技术资料及视频
    系统梳理主流定时器算法实现的差异以及应用

    展开全文
  • 软件定时器算法

    2017-05-04 23:31:00
    说明:软件定时器不是定时器,是应用于操作系统中的一种定时回调功能函数的算法算法结构:本软件定时器,包含一个链表,一个定时器任务。 void updateSystemTime(void)函数要在定时器溢出中断中被调用。 timer_...

    说明:软件定时器不是定时器,是应用于操作系统中的一种定时回调功能函数的算法。 算法结构:本软件定时器,包含一个链表,一个定时器任务。 void updateSystemTime(void)函数要在定时器溢出中断中被调用。

    • timer_callback.h头文件
    #ifndef _TIMER_CALLBACK_H_
    #define _TIMER_CALLBACK_H_
    #include "board.h"
    
    
    #define LIST_OK 0
    #define ERR_LIST_EMPTY 1
    #define ONLY_ONE 0
    
    extern u32 system_time;
    
    #define	GET_TICK(tick)	\
    	do {		\
    		tick = system_time;	\
    	} while (tick != system_time)
    	
    //#define NULL 0
    
    typedef struct{
      u32 tick_temp;
      u32 tick_begin;
    }TICK;
            
              
    typedef void (*timer_callback_function)(void*);
    typedef struct callback_timer_type{
            unsigned char timer_index;
    	unsigned char mode;
    	unsigned long long time;
    	unsigned long long start_time;
    	timer_callback_function func;
    }callback_timer;
    
    typedef callback_timer DataType;
    
    typedef struct node_l{
    	DataType data_t;
    	struct node_l *next_node;
    }nodelist;
    
    
    
    void node_test(void );
    void createNodeList(void);
    void addNode(nodelist* L);
    u8 rmNode(nodelist* L);
    int getNodeNum(void);
    void timer_task(void);
    void callback_TimerInit(void );
    u32 getSystemTime(void);
    void updateSystemTime(void);
    #endif
    
    • timer_callback.c源文件
    #include "timer_callback.h"
    #include "stdlib.h"
    //#include "string.h"
    #include "stdio.h"
    #include "board.h"
    
    /*定义一个链表头指针*/
    nodelist *nl;
    /*系统时间,单位ms*/
    u32 system_time=0;
    
    void createNodeList()
    {
        nl = NULL;
    }
    void addNode(nodelist* L)
    {
    	nodelist* tp;
    	tp = nl;
        if(nl==NULL)
        {
            nl=(nodelist*)malloc(sizeof(nodelist));
            *nl=*L;
            nl->next_node=NULL;
            return;
        }
    	while(tp->next_node!=NULL)
        {
            tp=tp->next_node;
        }
        tp->next_node=(nodelist*)malloc(sizeof(nodelist));
        *(tp->next_node)=*L;
        tp->next_node->next_node=NULL;
    }
    u8 rmNode(nodelist* L)
    {
      nodelist *tp,*tp_head;
      tp = nl;
      while(tp!=NULL)
      {
        if(tp==nl)
        {
          /*根据索引号删除*/
          if(nl->data_t.timer_index==L->data_t.timer_index)
          {
            nl=nl->next_node;
            free(tp);
            tp=nl;
          }
          else
          {
            tp_head=nl;
          }
        }
        else
        {
          /*根据索引号删除*/
          if(tp->data_t.timer_index==L->data_t.timer_index)
          {
            tp_head->next_node=tp->next_node;
            free(tp);
            tp=tp_head->next_node;
          }
          else
          {
            tp_head=tp;
            tp=tp->next_node;
          }
        }
      }
      return LIST_OK;
    }
    int getNodeNum()
    {
        int num=0;
        nodelist* tp;
        tp=nl;
        while(tp!=NULL)
        {
            num++;
            tp=tp->next_node;
        }
        return num;
    }
    void timer_task()
    {
        nodelist* tp;
    	nodelist* rm_temp;
        tp=nl;
        if(nl!=NULL)
        {
            if((nl->data_t.time)<(system_time-nl->data_t.start_time))
            {
                (nl->data_t.func)(NULL);
                if(nl->data_t.mode==ONLY_ONE)
                {
    					/*记录要删除节点*/
    					rm_temp=nl;
    					
    					nl=nl->next_node;
    					/*删除节点*/
    					free(rm_temp);
                }
                else
                {
                    nl->data_t.start_time=system_time;
                }
            }
        }
        else
        {
            return;
        }
        while(tp->next_node!=NULL)
        {
            if((tp->next_node->data_t.time)<(system_time-tp->next_node->data_t.start_time))
            {
                (tp->next_node->data_t.func)(NULL);
                if(tp->next_node->data_t.mode==ONLY_ONE)
                {
                	  /*记录要删除节点*/
    				  rm_temp=tp->next_node;
    
                    tp->next_node=tp->next_node->next_node;
    		     	  /*删除节点*/
    				  free(rm_temp);
    										
                    if(tp->next_node==NULL)
                    {
                        return;
                    }
                }
                else
                {
                    tp->next_node->data_t.start_time=system_time;
                }
            }
            tp=tp->next_node;
        }
    }
    
    void callback_TimerInit()
    {
      //timer4Init();
    }
    
    
    u32 getSystemTime(void)
    {
      return system_time;
    }
    
    void updateSystemTime(void)
    {
      system_time++;
    }
    
    

    转载于:https://my.oschina.net/u/2345008/blog/892806

    展开全文
  • 在定时算法中尽量采用一个定时器,轮询不同的定时需求。 例子: 各家商户的订单,需要设置不同的订单超时时间。 一般做法是每个订单都生成一个相应超时时间的定时器定时器到了后自动超时。但是同时多个定时器,...

    在定时算法中尽量采用一个定时器,轮询不同的定时需求。

    例子:

    各家商户的订单,需要设置不同的订单超时时间。

    一般做法是每个订单都生成一个相应超时时间的定时器,定时器到了后自动超时。但是同时多个定时器,这样会造成内存占用太多。

    建议:

    只生成一个定时器(以秒为单位),可以将多个商户的订单分成不同的队列,设置队列id和队列超时时间,定时器去轮询所有的队列,如果订单生成时间加上超时时间超过当前时间即为超时。

    转载于:https://www.cnblogs.com/jlj9520/p/10761079.html

    展开全文
  • μC/OS-II操作系统是建立在微内核基础上的实时操作系统,抢占式多任务、微内核、移植性好等特点,使其在诸多领域都有较好的应用。
  •  关于定时器有很多种,有基于升序的定时器时间链表,但是这种链表存在效率的不足,就是当插入定时器的时候时间复杂度是O(n).今天,我们来认识一下高性能定时器时间轮。  如上图所示,就是一个时间轮的基本轮廓。一...

    l 时间轮的概念

       关于定时器有很多种,有基于升序的定时器时间链表,但是这种链表存在效率的不足,就是当插入定时器的时候时间复杂度是O(n).今天,我们来认识一下高性能定时器时间轮。

       如上图所示,就是一个时间轮的基本轮廓。一个轮子上有很多槽slot,每一个槽指向一个定时器链表,这个链表是无序的。时间轮每转动一步就会指向下一个槽,其实也可以理解为一个滴答时间成为时间轮的槽间隔si (slot interval)。它实际上就是心跳时间。如果该时间轮有n个槽,因此它运转一周的时间是n*si.

       如果现在指针指向槽cs,我们此时要添加一个定时器时间为ti的定时器,则该定时器将被插入槽ts对应的链表

                                   Ts = (cs+ti/si)%N

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

    显然要提高时间轮的精度,就要使si(slot interval)足够小,要提高其执行效率则要N要足够大。


    转自:http://wenku.baidu.com/link?url=q6N4azyNaZMxGyr6ScqVtpb8EWqHudQCjHshZru6d-7QLI41uiqYQYWXjWrE5-Y8CIaZmWoQQd3CdNZyEk-zhF3tiSYfH2T7n3_mmuD8bei

    进阶 分层时间轮模型: http://www.tuicool.com/articles/yeeua2n

    时间轮实现和规范接口:http://blog.csdn.net/mindfloating/article/details/8033340

    游戏后台之高效定时器-时间轮http://blog.csdn.net/soft2967/article/details/9274691
     

    展开全文
  • 内核中经常要用到各种定时器。比如nanosleep()系统调用,让当前进程睡眠一段时间,再把它唤醒。即在expires时刻(以时钟滴答为单位),自动调用wake_up_process。最直接的思路是定义一个定时器,里面有function...
  • 内核中经常要用到各种定时器。比如nanosleep()系统调用,让当前进程睡眠一段时间,再把它唤醒。即在expires时刻(以时钟滴答为单位),自动调用wake_up_process。 最直接的思路是定义一个定时器,里面有function...
  • stm32 定时器中断算法

    2018-09-06 01:16:13
    stm32 定时器中断算法,s曲线七段法,可以根据自己应用实例进行更改
  • 本文对μC/OS-II V2.86中新增的用于管理软件定时器定时器轮进行了重新规划,并对处理算法进行了重新设计,有效提高了软件定时器的到期命中率,验证表明,新改进的算法在同等负载下可降低CPU的负载率约9%左右。...
  • 详细描述了Linux下的定时器的原理,实现
  • Linux中定时器算法实现定时器的作用 定时器在操作系统中起到了举足轻重的作用。在做IO操作时,需要超时机制保证任务不处于无休止的等待状态;在延时处理时,可以通过“闹表”进行相对准点的唤醒操作。在多任务...
  • linux定时器时间轮算法详解

    千次阅读 2021-01-05 14:49:27
    linux高并发编程|红黑树实现定时器|时间轮实现定时器 linux多线程环境下海量定时任务的定时器设计 时间轮实现 Linux定时器分为低精度定时器和高精度定时器两种类型,内核对其均有实现。本文讨论的是我们在应用程序...
  • Linux定时器分为低精度定时器和高精度定时器两种类型,内核对其均有实现。本文讨论的是我们在应用程序开发中比较常见的低精度定时器。作为常用的基础组件,定时器常用的几种实现方法包括:基于排序链表实现、基于小...
  • js算法定时器

    2021-03-28 14:47:04
    定时器核心:要结束定时器的话,毫秒之后就输出才能结束定时器. function count(start, end) { console.log(start); var a=setInterval(function() { if(start<end) { console.log(++start);
  • 内核通过时间轮算法实现一个精度固定的定时器,这个精度由时钟中断和软频率 HZ 决定。定时器运作的基本流程: 在每次(时间)中断触发后,执行各种软中断,其中包括定时器软中断。 检查时间轮中的定时器是否超时...
  • C8051单片机定时器定时值的算法

    热门讨论 2012-06-10 09:49:03
    以C80518020单片机为例子,介绍了单片机定时器初始值的算法,可以帮助处学这!
  • 提高单片机定时器精度的算法

    千次阅读 2015-10-18 21:29:16
    定时器误差产生的主要原因:定时器产生溢出中断时,CPU正在执行指令,从溢出中断出现到CPU响应成为中断响应时间。 定时器工作方式:定时/计数器有方式0~方式3共4种工作方式。常用的为定时方式1,若定时/计数值计满...
  • 常用的定时器实现算法有两种:红黑树和时间轮(timing wheel)。 在Linux2.6的代码中,kernel/timer.c文件实现了一个通用定时器机制,使用的是时间轮算法。 每一个CPU都有一个struct tvec_base结构,代表这个CPU...
  • STC单片机定时器(1T_12T)初值计算器

    热门讨论 2011-11-21 10:57:36
    STC单片机定时器(1T_12T)初值计算器,支持1T定时器算法
  • 目录 写在前面 我对定时器作用的理解 这个小定时器涉及的算法思想 设计这个定时器 定时器的细节 单例模式 谈一谈此定时器缺点 写在前面 我一直很想写出一个好用的网络库,可以作为本科毕业前送给自己的礼物,由于我...
  • 最近在一个项目中想做一个定时器队列,而定时器的插入超时是随机的,这意味着如果在如果定时器管理队列在队列中插入的是几乎均匀分布,思前想后如果用链表来管理这个时间队列当定时器密集超时,那么链表插入效率必然...
  • 上一篇热文《构建企业级业务高可用的延时消息中台》引起了大家的讨论,评论里讨论除了时间轮算法外的其他高性能算法实现延迟消息的定时器。这一篇文章系统的梳理主流定时器算法实现的差异以及应用地方...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 41,883
精华内容 16,753
关键字:

定时器算法