μ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

3 定时器精度与抖动
    在μC／OS-II操作系统中，与定时相关的功能均基于系统的时钟节拍。系统每秒的时钟节拍数决定了这个系统能分辨的最小时间，定时值只能为最小时间的倍数。每秒的时钟节拍数由os_cfg．h．文件中的宏OS_TICKS_PER_SEC定义。对于不同的应用，该时钟节拍一般在10～100次／s的范围内选取。其对应的时钟中断的时间间隔为100～10 ms，即时间的最小分辨单位为10 ms。处理器处理能力越高，每秒的时钟节拍数也相应地越大。下面的数据测试中使用了ARM9处理器。最低运行频率为250 Hz时，时钟节拍设为200次／s，可进行正常的多任务调度。该测试环境下，最小分辨时间为5 ms。
    抖动是指定时器回调函数开始执行的时间与规定的时间相比，或提前或推后的现象。在定时器中抖动总是存在的。下面主要分析2种抖动情况及其对定时精度的影响。第1种抖动情况如图3所示。

    T1：CPU响应时钟中断，搜索中断号，保存中断现场并跳到时钟中断处理程序OSTimTick的时间。
    T2：OSTimTick()函数的执行时间。该函数中对任务延时是否到期进行了判断。
    T3：恢复现场，退出中断并进行任务上下文切换的时间。
    T4：定时器管理任务OSTmr_Task()判断定时器是否到时的时间。
    T4之后：定时器到时回调函数开始执行。[page]

    由测试数据可知，若有定时器到时，则经过几个μs的延时，定时器回调函数就可以执行。与ms级的定时最小分辨时间相比，其抖动对到时准确性的影响是非常小的。随着处理器频率的提升和处理能力的加强，这个抖动时间还可以进一步缩小。第2种抖动情况如图4所示。

    当下一个时钟节拍快到来时(如图4中A时刻)，一个定时器被开启了。因为系统能分辨的最小时间即时钟节拍的间隔时间，所以定时器开启时记录的当前时钟节拍数为1，假设定时器的定时值就是一个时钟节拍间隔。定时器开启后，第2个时钟节拍马上就到了，由情况1的分析可知，这个定时器的回调函数很快就会被执行。B时刻表示这个定时器回调函数第一次执行。C、D时刻为回调函数的第2次与第3次执行时刻，这两次到时是比较准确的。
    因此，定时器从开启到回调函数开始执行的时间与定时值相比是有较大抖动的。若此时的时钟节拍间隔为5 ms，则这个抖动的误差最大即5 ms。这种情况下的抖动只能通过提高每秒的时钟节拍数来减小。因此，在数据采集或其他定时器的应用中，要留意定时器开启后第一次到时的处理，以免进行错误的判断。

4 定时器管理任务对操作系统性能的影响
    定时器管理任务的运行使应用程序可建立的任务数减1。该任务要求是系统中的最高优先级，因此每次有时钟中断发生它都要运行，必然会消耗掉一定的CPU资源。软件定时器功能所占用的CPU运行时间(设为M)的计数公式为：
    M=定时器管理任务判断定时器是否到时的时间+定时器回调函数执行时间+定时器控制块移除
    与再插入时间+切换到次低优先级任务的时间
    首先，采用μC／OS-II中自带的统计任务测试定时器管理任务对CPU资源的占用情况。测试时系统中开启3个任务：定时器管理任务、统计任务和Idle任务。定时器到时回调函数在定时器管理任务中执行，增加了管理任务运行时间。为仅测试系统定时器管理功能的开销，测试时将定时回调函数置为空操作。因统计任务要求必须在初始化时建立第一个也是唯一的一个任务中调用统计任务初始化函数OSStatInit()，所以需在定时器管理任务中进行必要改动，以保证在统计任务初始化后才开启定时器的管理功能。测试用定时器在main函数中静态创建。
    测试后发现，当定时器数由1增加到8时，CPU的使用率一直是1％。这说明系统开启定时器管理功能后，增加的负荷很小。另一方面因为统计任务计算CPU使用率时是整数相除、余数舍弃，这就使得0～(OSIidleCtrMax／100-1)的计数是不能被分辨的，因此统计任务不能准确地反应定时器管理任务对CPU的使用情况。
    为了得到更准确的测量结果，采用“处理器占用率”这一指标对管理任务开销进行测试。
    处理器占用率=软件定时器功能所占用的CPU运行时间(M)／CPU运行时间
    当某一时钟节拍到来时，假设这一时钟节拍下无定时器到时，即“到时定时器回调函数执行时间”和“定时器控制块移除与再插入时间”为0。若当前系统中所创建的定时器正好在同一个分组中，则管理任务须对每个定时器的到时值进行比较，此时为无定时器到时时定时器管理任务对CPU的最高占用率。测试中，将定时器的到时值设定为8的倍数加1，在main()函数中静态创建。使所有定时器控制块在同一分组中，当OSTime也是8的倍数加1时，就形成了无定时器到时时定时器管理任务的最坏运行情况。
    测试环境为：ARM9(400 MHz)，定时器最小分辨时间为5 ms(该值作为计算时的“CPU运行时间”)，硬件计时器的最小分辨时间为0．02μs。读硬件计时器计算时间，测试结果如表2所列。

    由测试数据可知建立定时器数为8时，处理器占用率远小于1％。每增加一个定时器，定时器管理任务的运行时间约增加6．5μs，处理器的占用率约增加0．01％，任务的切换时间不变。这是在构建的极端情况下测试的，实际应用中的时间要小于这个值。
    “定时器控制块移除与再插入时间”在400 MHz下测试为0．22μs。某一时钟节拍处理时，若有定时器到时，则最坏情况是这个到时的定时器控制块在链表的最后，只有执行完整个链表的判断后才开始执行该到时定时器的回调函数。假设定时器数为8，且链表中最后一个定时器先到时，则该定时器到时的这个钟节拍下处理器利用率为：(0．34μs+0．22μs+0．82μs+定时器回调函数执行时间)／5 ms=(1．38μs+定时器回调函数执行时间)／5 ms。

结 论
    本文对μC／OS-II软件定时器的算法及抖动问题进行了分析，并在特定平台上进行了测试，较好地反映出了该定时器的精度和对处理器资源的占用情况。测试结果可信度高，为在μC／OS-II下的软件定时器应用开发提供了可靠的依据。