高效软件定时器的设计

摘要

软件定时器在协议栈等很多场景都有广泛的应用，有时候会有大量的定时器同时处于工作状态，它们的超时时间各异，要高效的保证每个定时器都能够较为准确的超时并执行到其回调函数并不是一件易事。本文分析嵌入式实时操作系统Nucleus的定时器方案，它巧妙的管理了一条按照相对时间来排序的双向链表，避免每次tick中断都要遍历链表检查超时和更新剩余时间，实现了一种相当高效的软件定时器。

数据结构分析

结构体TM_TCB来表示动态创建的定时器，其定义如下

typedef struct TM_TCB_STRUCT

{

/*Nucleus的定时器分为应用定时器和task内置两种type  */

INT                 tm_timer_type;             

/* 剩余时间，可动态改变  */

UNSIGNED            tm_remaining_time;     

/*tm_information指向TM_APP_TCB，其保存了超时函数等定时器参数  */    

VOID               *tm_information;            

struct TM_TCB_STRUCT

                       *tm_next_timer,           /* Next timer in list    */

                       *tm_previous_timer;     /* Previous timer in list*/

} TM_TCB;

每个字段都有注释，和本文相关的字段已经标红。

定时器结构体TM_TCB之间使用双向循环链表的方式组织在一起,即tm_next_timer和tm_previous_timer指针。Nucleus里有个TM_TCB    *TMD_Active_Timers_List全局指针，其指向该链表的头部，管理着所有处于激活状态的定时器。

假设当前系统里没有定时器，我们的应用在初始化时要连续创建和激活5个周期性的定时器，其周期超时时间为：5,8,8,12,20（单位都是tick）.

假设是按照顺序创建，那么链表的形成过程如下所示（方框里的数字就是TM_TCB的tm_remaining_time）：

 // 第2个定时器会在8个tick之后超时，相对于前一个，它的超时时间多3

 // 第4个定时器会在12个tick之后超时，相对于前一个，它的超时时间多4

 

        //第1个定时器会在12个tick之后超时

    // 第3个定时器会在20个tick之后超时，相对于前一个，它的超时时间多8

 

        //链表重新排序，并更新当前插入的定时器的下一个元素的相对时间

总之，无论创建的顺序如何，结果链表组织方式和顺序都是一样的

 

时间的递减怎么记录/span>

需要引入一个重要的全局变量

UNSIGNED TMD_Timer

它记录了当前距离超时最近的定时器的剩余时间。例如在上面的例子里，当前TMD_Timer值为5。Nucleus的底层实现了一个中断处理函数INT_Timer_Interrupt，它是由硬件定时器触发的，当有处于激活状态的timer时，每个tick触发一次，在这个函数里，会对TMD_Timer减1并判断是否为0，如果为0，说明有定时器超时，开始激活TMD_HISR，其回调函数就是用于处理所有定时器超时的入口。

有定时器超时了以后会发生什么/span>

假设现在已经过了5个tick（这个5个tick里，不需要对定时器链表有任何的操作），那么首节点的超时函数会被执行，首节点被从链表头部摘除,TMD_Timer会被改写为下一个首节点的剩余时间重新计数，即3.且链表会更新成（蓝色表示新插入的节点，棕色表示受影响的节点）：

 

再过2个tick，下个节点超时，以此类推。

 

动态加入定时器

前面创建几个定时器的时候都是同时创建的，如果不是同时创建会怎么样/span>

如上面的分析，回到整个用例开始的时候，在5个定时器组成的链表建立好之后，在接下来的5个tick内，没有定时器会超时，同时链表里的数据也不会有任何更新。

假设在3个tick之后，需要加入一个新的定时器，超时时间为10，应该怎么办/span>

如果继续按照上面组织链表的办法，10 = 5 + 3 + 2，应该放在第4位，且相对前一个定时器的超时时间加2，如下所示：

但是请注意，当前已经距离开始时间已经过去了3个tick,第一个定时器会在2个tick后超时，第二和第三个会在5秒后超时，所以如果按照这种方式，新加入的这个定时器在7个tick后就超时了，这显然是不正确的。

这个地方还是需要TMD_Timer，它记录了当前距离超时最近的定时器的剩余时间，也就是等于当前正确的链表首节点的剩余时间（开始是5，过了3个tick之后，变成了2）

正确的做法是先更新头节点的剩余时间之后，再插入新的节点，更新完之后的链表如下所示

这样，链表里的每个定时器节点都会有正确的超时时间了

 

每个tick触发一次，在这个函数里，会对TMD_Timer减1并判断是否为0，如果为0，说明有定时器超时，开始激活TMD_HISR

这是一个反复比较的过程，每个tick的中断里，会做不多的数字累加和比较操作，这个定时器中断的操作可以省下来。每次链表头节点更新的时候，可以启动一个硬件定时器，将其超时时间设置为TMD_Timer，时间一到，就代表着头节点已超时，而不用反复的在每个tick都做着重复的工作

来源：亦大乐谍