μC／OS-II定时器算法分析与测试

引 言
μC／OS-II操作系统是建立在微内核基础上的实时操作系统，抢占式多任务、微内核、移植性好等特点，使其在诸多领域都有较好的应用。
在μC／OS-II 2．83及其以后的版本中，一个较大的变化就是增加了对软件定时器的支持。这使得μC／OS实时操作系统的功能更加完善，在其上的应用程序开发与移植也更加方便。在实时操作系统中一个好的软件定时器实现要求有较高的精度、较小的处理器开销，且占用较少的存储器资源。本文在对μC／OS-II定时器算法分析的基础上，对定时精度和处理器占用情况进行了分析与测试，其结果在实时系统的设计与应用中具有借鉴意义。

1 定时器实现架构
在μC／OS-II操作系统内部，任务的延时功能及软件定时器功能，都需要底层有一个硬件的计数器支持。硬件计数器以固定的频率递减，计数到0时，触发时钟中断。这个特定的周期性的中断称为"时钟节拍"。每当有时钟节拍到来时，系统在保存现场和中断嵌套计数加1后都会跳到时钟节拍函数OSTimTick()中，进行软件计数器加1和遍历任务控制块，以判断任务延时是否到时。
μC／OS-II中并未在 OSTim Tick()中进行定时器到时判断与处理，而是创建了一个高于应用程序中所有其他任务优先级的定时器管理任务OSTmr_Task()，在这个任务中进行定时器的到时判断和处理。时钟节拍函数通过信号量给这个高优先级任务发信号。这种方法缩短了中断服务程序的执行时间，但也使得定时器到时处理函数的响应受到中断退出时恢复现场和任务切换的影响。软件定时器功能实现代码存放在tmr．c文件中，移植时需只需在os_cfg．h文件中使能定时器和设定定时器的相关参数。

2 μC／OS-II的软件定时器算法分析
μC／OS-II中软件定时器的实现方法是，将定时器按定时时间分组，使得每次时钟节拍到来时只对部分定时器进行比较操作，缩短了每次处理的时间。但这就需要动态地维护一个定时器组。定时器组的维护只是在每次定时器到时时才发生，而且定时器从组中移除和再插入操作不需要排序。这是一种比较高效的算法，减少了维护所需的操作时间。
2．1 定时器管理所需的数据结构
一旦定时器被建立，一个定时器控制块(OS_TMR)就被赋值了。定时器控制块是定时器管理的基本单元，包含定时器的名称、定时时间、在链表中的位置、使用状态、使用方式，以及到时回调函数及其参数等基本信息。
在μC／OS-II软件定时器中实现了3类链表的维护：

OSTmrTbl[OS_TMR_CFG_MAX]：以数组的形式静态分配定时器控制块所需的RAM空间，并存储所有已建立的定时器控制块。
OSTmrFreeLiSt：为空闲定时器控制块链表头指针。空闲态的定时器控制块(OS_TMR)中，OSTmrnext和OSTmrPrev两个指针分别指向空闲控制块的前一个和后一个，组织了空闲控制块双向链表。建立定时器时，从这个链表中搜索空闲定时器控制块。
OSTmrWheelTbl[OS_TMR_CFG_WHEEL_SIZE]：该数组的每个元素都是已开启定时器的一个分组，元素中记录了指向该分组中第一个定时器控制块的指针，以及定时器控制块的个数。运行态的定时器控制块(OS_TMR)中，OSTmrnext和OSTmrPrev两个指针同样也组织了所在分组中定时器控制块的双向链表。定时器管理所需的数据结构示意图如图1所示。

2．2 软件定时器实现原理
宏OS_TMR_CFG_WHEEL_SIZE定义了OSTmr-WheelTbl[]数组的大小，同时这个值也是定时器分组的依据。按照定时器到时值与OS_TMR_CFG_WHEEL_SIZE相除的余数进行分组：不同余数的定时器放在不同分组中；相同余数的定时器处在同一组中，由双向链表连接。这样，余数值为0～OS_TMR_CFG_WHEEL_SIZE-1的不同定时器控制块，正好分别对应了数组元素OSTmr-WheelTbl[0]～OSTmrWheelTbl[OS_TMR_CFGWHEEL_SIZE-1]的不同分组。每次时钟节拍到来时，时钟数OSTmrTime值加1，然后也进行求余操作，只有余数相同的那组定时器才有可能到时，所以只对该组定时器进行判断。这种方法比循环判断所有定时器更高效。随着时钟数的累加，处理的分组也由0～OS_TMR_CFG_WHE EL_SIZE-1循环。
信号量唤醒定时器管理任务，计算出当前所要处理的分组后，程序遍历该分组中的所有控制块，将当前OSTmr-Time值与定时器控制块中的到时值相比较。若相等(即到时)，则调用该定时器到时回调函数；若不相等，则判断该组中下一个定时器控制块。如此操作，直到该分组链表的结尾。定时器管理任务的流程如图2所示。OS_TMR_CFG_WHEEL_SIZE的取值推荐为2的N次方，以便采用移位操作计算余数，缩短处理时间。

2．3 定时器移除和插入操作
定时器的到时处理函数返回后，都要进行该定时器控制块在链表中的移除和再插入操作。插入前需要重新计算定时器下次到时时所处的分组。计算公式如下：
定时器下次到时的OSTmrTime值=定时器定时值+当前OSTmrTime值
新的分组=定时器下次到时的OSTmrTime值％OS_TMR_CFG_WHEEL_SIZE