实时嵌入式系统中高效定时器算法的实现

在实时系统中，如果逻辑和时序出现偏差会引起严重后果。实时系统广泛应用于工厂生产过程控制、办公自动化、通信、航空航天、民用消费等领域。对于不太复杂的实时系统，一般可设计成前后台式或者超循环式。对于大多数实时系统来说，因为有多任务处理和共享资源的要求，则必须有操作系统支持，这时的操作系统就被称为实时操作系统[1]。隐藏在内部的计算机系统称为嵌入式系统，而实时操作系统又是嵌入式的，则被称为嵌入式实时操作系统。

　　嵌入式实时操作系统一般由任务调度管理、时间管理、任务同步和通信、内存管理等几部分组成[1-2]。对于通用操作系统，设置定时在50 ms以下的定时器没有意义的，而实时操作系统由于对时限的要求非常严格，经常设置定时在50 ms以下。因为实时操作系统对时序的偏差依赖性很强，因此作为操作系统时间管理的核心部件??定时器就显得很重要。

　　在通信领域的产品(如大型程控交换机)中，一次业务呼叫需要几个不同的定时。当同时处理的业务呼叫多达上万个时，则需要大规模(如20 000个)的定时器群。如果定时器的计时方法效率较差，则会因定时器个数太多而造成定时处理耗用系统CPU资源过大，影响定时精度，影响呼叫业务处理的及时性，使定时成为影响整体系统性能的“瓶颈”，因此定时器算法的优劣是影响实时系统性能的重要环节。

1 常用定时器算法

　　定时器的时钟源来源于硬件时钟中断。时钟中断每间隔一定时间产生，该时间间隔为最小计时时长，也就是定时器的计时精度。

　　目前关于定时器的算法有两种：

　　（1）简单计时法

　　当每个计时周期到达时，先将所有定时器的计时数减1，然后判断结果是否为0，如果为0，则表示计时时间已到并进行到时处理，否则继续进行计时操作，这种方法称为简单计时法。

　　（2）多队列计时法

　　多队列计时法首先根据系统定时应用特点，将定时器划分成不同时长的队列，目的在于减少每次参与计数的定时器个数(设定定时器时就将计时时长分解为毫秒位、个位、十位、百位、千位等几个部分)；再把定时器插入到最大不为0的位所在的队列，计时就从该队列开始，完成后逐一计以下位，直至计时到毫秒位队列；在该队列计时完成后定时器总计时完毕。[3-5]

　　由于各队列除头定时器外计算的均是相对于上个定时器的时间相对值，计时的时候只需对队列头部时间做减运算便可确定是否有定时器在本次计时到期。

　　综上所述，简单计时法固然方法简单，实现容易，但当定时器数目满载(如20 000个)时，每次计数需所有定时器做减法，每秒需做20万次减法(每个计时周期为100 ms)。而嵌入式系统的CPU资源相当有限，定时器本身的任务不能占用太多的资源，所以如果采用这种方法，就会占用较多的CPU资源。

　　多队列计时法相对简单，计时法更高效，在每次计时周期到来时，只需做与队列次数相同的判断和减法以及可能的报时操作就能基本满足嵌入式系统的定时需求。但该方法也存在很多冗余操作，如空负载时检查所有队列，满负载时要对所有队列做2倍于空负载检查时的加减法操作，真正有效操作只占少部分，而且在队列处理中存在耗费计算资源的排序操作。

2 单循环队列定时器算法

2.1 单循环队列定时器算法原理

　　单循环队列定时器算法所要解决的技术问题是提供一种新的定时器计时方法，解决多队列计时法中存在的冗余操作和排序操作的缺点。该算法可提高定时效率，具有伸缩性，能适应不同规模的嵌入式系统。

　　单循环队列计时原理如下：

　　假定所需的最大定时器数目为M个，则设置M个定时器描述数组。再构造一个循环计时队列缓冲(长度为L)，其元素指示定时器链表队列头标识(ID)和尾ID，通过该ID与定时器缓冲中的相应元素构成虚拟双向链表。每个时钟源(100 ms)到来时，循环计时队列头向后走一位，查找该位所指示的队列中是否存在时间已到定时器，如存在，则取出做相应报时操作和定时器时长与L取余的余数位队列插入操作。对于超过L长度的定时器，因已计算出定时器时长与L相除所得的倍数，每次循环计时队列头经过时，该倍数值得减去1，直至倍数值被减为0，之后的检查就可报时并进行插入操作。

　　新定时器在循环队列中插入位置的计算方法如下：

　　新定时器的插入位置等于当前循环计时队列头位置加新定时器时长与循环队列长度相除的余数再与循环计时队列长度相除取余，并在循环队列所在节点对定时器进行排序操作。

　　循环队列由长度为L的数组和循环指针变量组成，循环队列的长度为L，L的取值遵循如下规律：

　　(1)L与M的大小基本相同，以便当使用的定时器接近M个时，定时器可以随机均匀地分布到循环队列的各数组元素中，使定时器负载比较均衡；如果L太小容易造成倍数值的减操作过多，效率得不到提高；L太大则浪费存储空间。

　　(2)L最好取为2的指数，以便利用移位和与操作来计算倍数值和余数，提高效率，比如，当M为20 000时，L可取为214(即16 384)。

2.2 插入定时器操作的步骤

　　在单循环的队列计时算法中插入定时器操作包括以下步骤：

　　(1)设置所需最大定时器数的定时器描述数组。

　　(2)采用一定长度的数组和循环指针变量组成一个循环计时队列，循环指针变量以循环的方式逐一指向各数组元素。

　　(3)当上层应用程序需要定时器任务时，将所需新的定时器插入循环队列中。

　　(4)在每个计时周期到来时，循环指针变量向后走一位，查询该处的链表队列是否为空，如果为空，则等待下一个计时周期的到来；如不为空，则逐一判断该处链表队列中定时器的描述结构中的倍数值是否为0，如为0则表示该定时器的定时时间到，进行相应的报时操作和再次插入定时器操作，并从该处链表队列中删除该定时器描述数组；如倍数值不为0则将倍数值减1，然后判断下一个定时器。

　　(5)当上层应用程序不再需要定时器时，从循环队列和定时器描述数组中删除该定时器。

　　图1是定时器描述数组和循环队列的示意图。

3 定时器性能的测试

3.1 测试内容及测试步骤

　　定时器测试包括模拟定时器计时运行，统计平均每个计时周期占用CPU时间，并以该指标来量度定时器性能。

　　测试步骤如下：

　　(1)依照算法原理在VxWorks仿真环境下编程[6]。

　　(2)用编程方式实现不同时长的单循环定时器初始设置，可选的范围是1～20 000个计时时长。

　　(3)用多次循环的方法模拟时钟中断，因测试比较的是相对值，所以计时周期的时长不影响对比结果，实际测试时模拟时钟中断并无实际的时间间隔。循环次数要足够多，使得用函数能够测量出CPU时钟周期差别。一般循环次数取1 000 000次。

　　(4)运行程序，让测试程序打印结果。

　　(5)在文档中记录结果。

　　(6)改变循环定时器初始设置，重复步骤3?5。

3.2 测试结果分析

　　表1是多队列算法和单循环队列计时算法的性能比较测试结果。其平均性能效率提高倍数为8.39。

　　表2进行了多队列算法和单循环队列的理论分析和实际结果的综合比较。

4 结论

　　采用我们提出的单循环队列计时法，经过模拟测试，与现有技术相比，定时器在各种负载下的平均性能可提高5倍以上，达到了高性能、高效率、高均衡性、实现简单、可伸缩的效果，节省了嵌入式系统的定时管理所需的计算资源。

5 参考文献

　　[1] 孔祥营, 柏桂枝. 嵌入式实时操作系统VxWorks及其开发环境Tornado [M]. 北京: 中国电力出版社, 2002.

　　[2] Jean J Labrosse. μC/OS-II--源码公开的实时嵌入式操作系统 [M]. 邵贝贝译. 北京: 中国电力出版社, 2001.

　　[3] William Stallings. Operating Systems: Internals and Design Principles [M]. 北京: 电子工业出版社, 2001.

　　[4] 吴林平, 胡仁杰, 徐达银. 软件定时器的实现 [J]. 工业控制计算机, 2002,15(11):46-48.

　　[5] 杨顺昆, 刘斌,陆民燕. Windows NT下几种定时器的实现原理及性能比较 [J]. 测控技术, 2002,21(12):44-46.

　　[6] 葛波, 李京秀, 舒云星. Vxworks通用定时器设计与实现 [J]. 无线电通信技术, 2002,28(3):47-48.

[摘要] 文章提出了一种实时嵌入式系统中高效定时器算法的实现手段：通过采用单循环队列定时器算法解决了在多队列计时算法中存在的冗余操作和排序操作的缺点，使定时器计时方法更有效率，更具有伸缩性，能适应不同规模的嵌入式系统。

[关键词] 定时器；实时操作系统；计时周期；时钟

[Abstract] A highly efficient timer algorithm for the real-time embedded system is proposed. The single circular queue algorithm resolves the defects of multiple circular queue algorithms, such as redundant manipulation and queue manipulation. It enables the timer to work more efficiently and be more flexible to be deployed in embedded systems of different scales.

[Keywords] timer; RTOS; cycle of timing; clock