uCOS-II软件定时器管理算法.doc

1、C/OS-II 软件定时器管理算法分析及改进摘要：软件定时器是常用于内核设计和应用程序设计的一项基础软件措施。本文对 C/OS-II V2.86 中新增的用于管理软件定时器的定时器轮进行了重新规划，并对处理算法进行了重新设计，有效提高了软件定时器的到期命中率，验证表明，新改进的算法在同等负载下可降低 CPU 的负载率约 9%左右。1、概述软件定时器是一种软件措施，通过它可以使一项特定的任务在给定的时间段后被执行。软件定时器广泛地应用于内核设计和应用程序设计中，例如，一个进程使用软件定时器等待其他的进程完成特定的动作,以使任务间的操作同步等，因此，对软件定时器的高效实现对提升系统的响应效率是至关

2、重要的。作为一种基础的软件措施，C/OS-II1的 V2.86 版本中增加了对软件定时器的支持。使用 C/OS-II 提供的软件定时器，应用程序可以方便地完成特定的定时任务。本文对C/OS-II 的软件定时器的实现机制进行简要分析，然后提出了对 C/OS-II 的软件定时器的实现进行改进的方法。 2、C/OS-II 软件定时器的实现机制及算法分析2.1 C/OS-II 软件定时器的核心数据结构C/OS-II 实现软件定时器的核心数据结构是 OS_TMR，其定义如下：typedef struct os_tmr INT8U OSTmrType; /*应该设置为 OS_TMR_TYPE*/OS_TM

3、R_CALLBACK OSTmrCallback; /* 指定时间到达时要执行的回调函数 */void *OSTmrCallbackArg; /*传递给回调函数的参数*/void *OSTmrNext; /*软件定时器链表管理指针*/void *OSTmrPrev;INT32U OSTmrMatch; /* 当 OSTmrTime = OSTmrMatch 时表示定时器时间到*/INT32U OSTmrDly; /* 对于周期性定时器，再次启动定时器前的延时时间*/INT32U OSTmrPeriod; /*对于周期性定时器，时钟周期的长度*/INT8U OSTmrOpt; /* 选项 (如

4、OS_TMR_OPT_xxx 等) */INT8U OSTmrState; /*定时器的状态*/ OS_TMR;每个 OS_TMR 结构的实例定义了一个软件定时器，多个软件定时器通过结构中的 OSTmrNext 和 OSTmrPrev 构成一个定时器双向链表。为了提高对软件定时器的管理效率，C/OS-II 引入了“定时器轮”数据结构，所谓定时器轮，是将定时器实例中的 OSTmrMatch 域的值参照某一个预先设计的数（称为轮数）进行求余运算，并根据求余结果将定时器进行分组以改善对到期定时器的命中率。定时器轮数缺省配置如下:typedef struct os_tmr_wheel OS_TMR *

5、OSTmrFirst; /*指向第一定时器的指针*/INT16U OSTmrEntries; /* 该定时器轮中的定时器项数 */ OS_TMR_WHEEL;缺省配置下，C/OS-II 定义的轮数为 8，因此，C/OS-II 的定时器轮为如下的一个数组：OS_TMR_WHEEL OSTmrWheelTbl8;例如，在某一个特定的时刻,此处假设时刻 5，系统中有定时时间为2ticks、4ticks 、5ticks 、32ticks 、161ticks、357ticks 的软件定时器，那么，这些定时器将在时钟滴答分别为 7、9、10、37、166、362 时到期，则此时系统的定时器轮的实例如图 1

6、所示：2.2 C/OS-II 软件定时器的处理算法分析C/OS-II 对定时器的超时处理在一个称为“uC/OS-II Tmr”的任务中进行,该任务是通过信号量 OSTmrSemSignal 来激活。基于以上定义的定时器轮，C/OS-II 对定时器的处理算法如下：static void OSTmr_Task (void *p_arg)for(;)等待 OSTmrSemSignal 信号量并获得 OSTmrWheelTbl 的访问权；STmrTime = OSTmrTime+1，并对 8 求余后得到对应的定时器轮项索引 index;for OSTmrWheelTblindex定时器轮中的每一个定时

7、器 ptmr，doif (OSTmrTime = ptmr-OSTmrMatch) 执行 ptmr 软件定时器中的回调函数；对于单次定时器，从定时器轮中删除该时钟；对于周期性定时器，则重置该定时器的 OSTmrMatch 值；释放对 OSTmrWheelTbl 的访问权；2.3 C/OS-II 的定时器处理算法的效率分析 采用上面的例子，对 C/OS-II 的定时器处理算法效率进行一个简单的分析：在下一次时钟滴答，也就是时钟滴答 6 时，没有定时器到期，而 for 循环必须对每个时钟进行检查，类似的情况还发生在自时钟到达 10 以后的多个检查中。根据系统中的定时器的数量，这种无谓的检查将占用大

8、量的 CPU 时间。3、对 C/OS-II 的定时器管理算法的改进3.1 改进以后的数据结构设计对 C/OS-II 的定时器管理算法进行改进的主要目标是：要么不对定时器进行检查，要检查则一定有定时器到期2。为了达到这个设计目标，需要对 C/OS-II 的定时器轮进行重新设计。采用同样的 OS_TMR 数据结构和 OS_TMR_WHEEL 定时器轮结构，但是，对定时器轮的每一个项的功能进行重新规划：（1）定时器轮的第 1 项到第 7 项，即 OSTmrWheelTbl1到 OSTmrWheelTbl7的定时器轮，分别表示将在此后的第 1 个时钟滴答到第 7 个时钟滴答将到期的定时器项，此时，每个

9、定时器结构的 OSTmrMatch 中的值表示需要经过多少个时钟滴答该定时器项将到期。在同一个定时器轮中的多个定时器项通过 OSTmrNext 和 OSTmrPrev 指针构成双向链表。（2）定时器轮的第 0 项，表示将至少需要经过 8 个时钟滴答才到期的定时器，并通过OSTmrNext 和 OSTmrPrev 指针将这些定时器构成双向链表。 针对上面的同一个例子，按照此规划形成的新的定时器轮如图 2 所示：3.2 改进的处理算法对定时器的超时处理仍然在“uC/OS-II Tmr”任务中进行,该任务还是通过信号量OSTmrSemSignal 来激活，因此，对于基于该接口调用的应用程序可以不做任

10、何修改即可正常运行。基于新规划的定时器轮，对定时器的处理算法如下：static void OSTmr_Task (void *p_arg)STmrTime = 0；for(;)等待 OSTmrSemSignal 信号量并获得 OSTmrWheelTbl 的访问权；STmrTime = OSTmrTime+1；if (OSTmrTime OSTmrMatch = ptmr-OSTmrMatch 8;/已经经过了 8 个时钟滴答；if (ptmr-OSTmrMatch = 0) /到期定时值正好是 8 的倍数执行 ptmr 软件定时器中的回调函数；对于单次时钟，从定时器轮中删除该定时器；对于周期性

11、时钟重置该定时器的 OSTmrMatch 值；continue;if (ptmr-OSTmrMatch OSTmrMatch 的值将 ptmr 插入到相应的 OSTmrWheelTbl定时器轮中；STmrTime = 0； /重新计数滴答；释放对 OSTmrWheelTbl 的访问权；3.3 改进的处理算法的效率分析通过对改进以后的算法进行分析可以发现：在每一个时钟滴答，如果对应的定时器轮的 OSTmrFirst 指针不为 NULL，则在该时钟滴答有到期的定时器，需要调用对应的回调函数。通过对定时器轮进行重新规划，避免了不必要的定时器到期检查，从而可节省 CPU时间，提高了运行效率。4、结束语针对本文提出的改进算法，本文在基于 ARM7 核的 LPC2210 为 MCU 的开发板 34上对改进以后的处理算法进行了测试，测试中建立了 1000 个软件定时器，在其他负载相同的情况下，通过 C/OS-II 的统计任务对 CPU 的使用率进行了统计分析，统计发现 CPU的负载率降低了约 9%。本文创新点：对 C/OS-II 的定时器轮进行了重新规划，使得在每个时钟滴答对软件定时器进行处理时有效提高了到期定时器的命中率，进而降低了 CPU 的负载率