一种风铃式定时器算法研究与实现
2016-10-13邵延峰
邵延峰
一种风铃式定时器算法研究与实现
邵延峰
(中国电子科技集团公司第五十四研究所,河北石家庄050081)
基于软件实现的定时器可以减少对硬件和系统资源的占用。风铃式软件定时器算法采用首尾指针追赶机制,解决了定时器的资源管理问题;借鉴风铃外形,利用来自硬件或系统的一个定时触发和双向链表操作,通过对风铃串间隔计算及风铃串上定时器的挂接和删除,实现了定时器的启动、停止和超时等操作。性能测试结果表明,该算法的定时精度和误差符合预期,而且该算法对外接口简单易操作,还可为系统中的其他软件提供定制化服务。
定时器;双向链表;资源管理;定时触发
引用格式:邵延峰.一种风铃式定时器算法研究与实现[J].无线电工程,2016,46(5):90-94.
0 引言
在通信协议软件中,定时器的使用无处不在。使用定时器可以进行通信协议的状态保护、定时监控或事件维持等。为了防止程序无限制地运行,造成死循环,还会设置看门狗以便在软件故障时复位系统,其本质也是定时器。
定时器的实现可以采用硬件和软件2种方式实现。硬件方式是利用硬件计时并以中断方式通知,其缺点是定时到时可反馈的信息比较少,并且难以支持同时实现数十个甚至上百个定时器。采用软件方式可直接利用操作系统定义的定时器函数,但其占用系统资源较多,不断涉及到系统的任务切换,在多个定时器同时使用时尤为明显,所带信息也多以函数参数形式实现,可反馈信息量有限。而降低大量定时器在系统内的插入、删除和超时等操作开销,是关系系统性能高低的重要技术[1]。
本文基于双向链表和定时触发的思路实现了一个风铃式的软件定时器[2-3],可作为嵌入式实时操作系统的一个单独任务执行,达到代码精简,算法优化,占用硬件或系统资源少,对系统处理能力影响小的效果[4]。
1 总体设计
1.1 定时器资源管理设计
软件系统中每一个定时器都会占用一部分内存资源,定时器越多,其占用的内存就会越多,所以定时器也是一种资源,要进行管理以解决资源的占用和释放。需要时申请,不需要时或超时后要释放,避免内存不断泄露。
描述一个定时器主要由标识和属性组成,定时器标识和定时器属性一一对应。标识具有唯一性,一个标识代表一个定时器。通常以连续的从0开始的阿拉伯数字作为每个定时器的唯一标识,根据最大的阿拉伯数字即可知道定时器的数量(其数值+1)。定时器属性主要由双向指针、使用者标识和一些自定义信息组成,其中双向指针、使用者标识为必选信息。双向指针用于在双向链表中的插入和删除,使用者标识用于定时器超时后通知,自定义信息可由使用者根据自己情况任意定义。
申请者申请定时器成功后,会获得一个定时器标识,该标识具有随机性。释放时基于使用者提供的定时器标识进行定时器回收。为此主要利用一个数组和2个指针实现了定时器资源的管理,如图1所示。
图1 定时器资源管理
数组的大小决定了定时器的数量。在初始状态,初始化数组值、定时器标识值和数组下标值相等,首尾指针都指向数组的基地址。当申请定时器时,首指针所指定时器标识被申请并且该指针前移一格。当释放定时器时,定时器标识放入尾指针所指位置并且该指针同样前移一格。图1中示例为0和1号定时器先后被申请,然后1号定时器被先释放。
任何一个指针指向数组尾部,都要重新指向数组基地址。首指针到尾指针之间的定时器记录还未被申请的定时器。当首指针追上尾指针时,表示定时器已申请耗尽。
1.2 风铃式定时器架构设计
现实中的风铃由顶层的圆环和多个等间隔的多个风铃串组成,每个风铃串由于铃铛数量不同而长短不一。风铃式定时器借鉴这种理念,将圆环上的串间隔等同于最小定时精度,串越多则间隔越多,一圈可代表的时间就越长。假设1个串间隔为100 ms,间隔为100,则一圈即可定时长度为10 s。
同时将风铃串上的风铃比喻为定时器,每个串上的定时器可通过双向链表操作实现挂接和卸除,如图2所示。
图2 风铃式定时器架构
每过一个定时精度,当前串下的定时器就意味着超时了,需要停止定时并将超时消息发给使用者,同时,使用者在启动定时器时留存的各种自定义信息也可原样返回给使用者。
启动一个定时器,就是将定时器挂上相应风铃串的过程。首先计算要启动的定时器需要多少个定时间隔,然后将定时器挂到当前串后相应间隔的风铃串的头部上。
停止一个定时器,即将定时器从风铃串上取下来的过程。基于使用者提供的定时器标识,可以索引到定时器的属性。利用属性中提供的双向链表指针即可进行链表的节点删除操作,也就完成了定时器的停止工作。
1.3 数据结构设计
定时器的数据结构主要包括定时器数量、定时精度、定时长度、定时器及定时器属性的数据设计。
1.3.1 定时器数量及标识声明
该值定义了定时器最大数量,通过更改该数值可以增加定时器数量。
该数组用于存储定时器标识。
该数据结构用于定时器资源的管理。其首尾指针主要指向TimerIdIdxArray。
1.3.2 定时间隔及风铃串头指针声明
#define TIMING_PERIMETER10
定义了定时圆周间隔数量,通过更改该数值可以增加一圈的最大定时长度。如果定时精度为100 ms,则风铃转一圈为100 ms*10=1 s。
该结构数组定义了每个风铃串的头指针。
1.3.3 定时器属性声明
上述数据结构描述了定时器属性。正如前述,双向指针、使用者标识为必选信息。双向指针用于风铃串上定时器的插入和删除,使用者标识用于定时器超时后通知,自定义信息可由使用者根据自己情况任意定义。新增的圈数为可选项,通过该值可增加定时长度。风铃转一圈后,该值-1,只有该值为0时,才可认为定时器超时。
2 定时器触发源
风铃式定时器能够运行,定时触发是必不可少的。定时触发源主要采用系统时钟之外的一个定时中断,是一种辅助时钟[5]。常用的触发源主要有以下几种:
①硬件中断。由硬件提供1个定时中断,每次中断产生就调用一次风铃,风铃就转动一个间隔。其缺点就是在中断处理函数中需要进行过多的软件处理。
②硬件中断结合信号量。同样利用1个硬件的定时中断,每次中断发送一个信号量给定时任务。定时任务收到信号量后调用一次风铃,风铃就转动一个间隔。该方法简化了中断处理函数的工作量。
③利用操作系统的任务延迟功能。一般情况下,嵌入式实时操作系统会提供任务延迟功能,通过调用该函数,相应的软件任务就会在规定tick数量后(一般情况下60 ticks=1 s)被执行一次。
利用该功能,规定时间内风铃也会被调用一次,即转动一个间隔。其前提需要确保系统时钟非常准确,即60 ticks时长确实是现实中的1 s。
④利用操作系统的定时函数加信号量。在操作系统中申请一个系统定时器,启动操作系统定时器时需要指明一个函数作为参数,用于超时后被调用。该函数再重新启动定时器并发送信号量。通过这种无限迭代的方式实现了定时触发源的获取。与硬件中断结合信号量不同之处是利用系统定时器产生软件中断,其前提仍然需要确保系统时钟非常准确。
上述4种方式可根据实际工程情况进行选择。常见的是②和③。触发源②定时比较精准,触发源③实现比较简单。
3 软件实现
3.1 定时器的初始化
定时器初始化主要包括定时器标识、定时器属性和风铃圈的初始化。
3.1.1 定时器标识初始化
3.1.2 定时器属性初始化
3.1.3 风铃圈初始化
上述操作让每个风铃串首尾指针首先指向自身。3.2 定时器的申请和释放
定时器申请就是要从存储定时器标识的数组中申请定时器。其主要操作如下:
定时器释放就是将定时器标识重新放入存储定时器标识的数组中,以备再次申请。其主要操作如下:
3.3 定时器的启动和停止
定时器启动和停止就是将定时器挂接到相应风铃串的过程。为此需要计算定时时长在当前位置之后的多少个间隔,然后基于双向链表操作将定时器挂接到相应的风铃串上。其主要操作如下:
/*iActiveList记录了当前位置,iTimingLen为定时时长,iTimingDelay记录了当前位置之后的多少个定时间隔*/
iTimingDelay=(iActiveList+iTimingLen)%TIMING_ PERIMETER;
/*将申请的定时器对应的定时器属性挂接到对应的风铃串上*/
pTmpTimer=pHeadTimer+iTimerId;
InsertElement((Q_Struc_T*)pTmpTimer,&Timing ListHead[iTimingDelay]);
定时器停止就是将定时器从相应风铃串删除的过程。其主要操作就是基于定时器属性的双向指针将其从风铃串中删除。
/*基于定时器标识定位指针*/
pFreeTimer=pHeadTimer+iFreeTimerId;
/*从定时链表中删除*/
DequeueElement((Q_Struc_T*)pFreeTimer);
3.4 定时器超时
每经过一个定时触发时间,后移一个定时间隔后对应的风铃串就变为当前风铃串,其上的所有定时器(风铃)就被认为超时。将定时器从当前风铃串上逐一删除,并可利用定时器属性上的信息通知使用者。
4 性能测试和结果分析
在操作系统VxWorks 5.5和处理器PPC 860的测试环境下[6],采用硬件的一个100 ms定时中断做为触发源。从图3中调用系统函数sysClkRateGet可以看到,系统时钟默认1 s=60 ticks。为避免频繁打印,软件程序每隔1 s(10*100 ms)打印一次并输出当前的系统tick值。相邻输出的tick的差值正好是60 ticks。说明触发源和系统时间进行了精确校准,即100 ms=6 ticks。
图3 时间校准
调用函数StartTiming分别在100 ms和1 s精度下(函数的第5个参数为1表示100 ms精度,为2表示1 s精度,第6个参数是时长),进行了10 s的定时测试,如图4所示。由图4可以看到,申请和启动定时在1 tick时间内即可完成。2次定时分别用时602 ticks和603 ticks,与理论用时600 ticks相差<6 ticks,即误差<100 ms,符合预期。
图4 100 ms和1 s精度下10 s定时测试
同样调用函数StartTiming分别在100 ms和1 s精度下进行了1 min的定时测试,如图5所示。
图5 100 ms和1 s精度下1 min定时测试
由图5可以看到,申请和启动定时仍在1 tick时间内完成。2次定时分别用时 3 605 ticks和3 602 ticks,与理论用时3 600 ticks相差<6 ticks,即误差同样<100 ms,符合预期。
通过性能测试,验证了定时器的申请、启动效率都没有给定时精准度造成影响。而且由于定时的基本触发源为100 ms,无论采用100 ms还是1 s定时精度,定时误差都不会超过100 ms(即6 ticks)。实际应用中,考虑到可容忍误差,该定时器多用于1 s以上到分钟级的定时。
5 结束语
定时器作为一种资源有可能被多个软件重复性地申请和释放,从避免双向链表中断的角度考虑,建议在申请和释放定时器操作时增加信号量互斥操作。此外,使用者只需根据自己实际情况修改宏定义的数值就可调整定时器数量和定时长度,接口简单且易操作。
风铃式定时器由于其占用硬件及系统资源少,对外接口简单、独立性强和软件量少等特点,已被笔者多次应用到通信协议栈和监控项目的开发中,取得了良好的工程实践效果。此外,使用首尾指针前后追赶实现定时器管理的方法,不仅效率高,还可被抽象出来应用于具有唯一标识的各种资源管理中去。
[1] 窦志斌.基于C语言的高性能LTE RLC层设计与实现[J].无线电工程,2014,44(12):11-13.
[2] 潘金贵,顾铁成,李成法,等.算法导论[M].北京:机械工业出版社,2012.
[3] 严蔚敏,吴伟民.数据结构<C语言版>[M].北京:清华大学出版社,2000.
[4] 李 光.大型有限状态机系统中的定时器设计[J].无线电工程,2005,35(6):54-56.
[5] 山 清.VxWorks下基于辅助时钟的通用定时器设计[J].电子科技,2014,27(3):126-128.
[6] 孔祥营,柏桂枝.嵌入式实时操作系统VxWorks及其开发环境[M].北京:中国电力出版社,2002.
Research and Implementation of a Wind Bell Timer Algorithm
SHAO Yan-feng
(The 54th Research Institute of CETC,Shijiazhuang Hebei 050081,China)
A timer based on software can reduce hardware and OS resource occupation.The algorithm of Wind Bell timer uses a head pointer and a tail pointer to solve the problem of resource management.The appearance of a wind bell is used for reference.The algorithm uses a period trigger and double-linked list.It realizes the operation of timer by calculating the interval of wind bell bunch and adding the timer to the wind bell bunch or deleting it.The performance test result shows that its timing precision and timing error meet the expectation.Moreover,the algorithm’s interface for user is simple and easy for operating.It can also provide customized service for other modules.
timer;double-linked list;resource management;period trigger
TP319
A
1003-3106(2016)05-0090-05
10.3969/j.issn.1003-3106.2016.05.23
2016-01-21
邵延峰 男,(1973—),硕士,高级工程师。主要研究方向:通信网络安全。