Analysis and Testing of μC/OS-II Software Timer

introduction

μC/OS-II operating system is a real-time operating system based on a microkernel. Its features of preemptive multitasking, microkernel, and good portability make it widely used in many fields.

In μC/OS-II 2.83 and later versions, a major change is the addition of support for software timers. This makes the μC/OS real-time operating system more functional and more convenient for application development and porting. In a real-time operating system, a good software timer implementation requires high precision, low processor overhead, and less memory resources. Based on the analysis of the μC/OS-II timer algorithm, this paper analyzes and tests the timing accuracy and processor occupancy. The results are of reference significance in the design and application of real-time systems.

1 Timer Implementation Architecture

In the μC/OS-II operating system, the delay function of the task and the software timer function both require a hardware counter to support the underlying layer. The hardware counter decrements at a fixed frequency, and when the count reaches 0, it triggers a clock interrupt. This specific periodic interrupt is called a "clock beat". Whenever a clock beat arrives, the system will jump to the clock beat function OSTimTick() after saving the scene and adding 1 to the interrupt nesting count, and then add 1 to the software counter and traverse the task control block to determine whether the task delay has expired.

μC/OS-II does not perform timer expiration judgment and processing in OSTim Tick(), but creates a timer management task OSTmr_Task() with a higher priority than all other tasks in the application, and performs timer expiration judgment and processing in this task. The clock beat function sends a signal to this high-priority task through a semaphore. This method shortens the execution time of the interrupt service program, but also makes the response of the timer expiration processing function affected by the restoration of the scene and task switching when the interrupt exits. The software timer function implementation code is stored in the tmr.c file. When porting, you only need to enable the timer and set the relevant parameters of the timer in the os_cfg.h file.

2 Analysis of software timer algorithm of μC/OS-II

The implementation method of software timer in μC/OS-II is to group the timers according to the timing time, so that only some timers are compared each time the clock beat arrives, shortening the time of each processing. However, this requires dynamic maintenance of a timer group. The maintenance of the timer group only occurs each time the timer expires, and the removal and reinsertion of the timer from the group does not need to be sorted. This is a more efficient algorithm that reduces the operation time required for maintenance.

2.1 Data structures required for timer management

Once the timer is established, a timer control block (OS_TMR) is assigned. The timer control block is the basic unit of timer management, containing basic information such as the timer name, timing time, position in the linked list, usage status, usage method, and the time callback function and its parameters.
In the μC/OS-II software timer, three types of linked list maintenance are implemented:

OSTmrTbl[OS_TMR_CFG_MAX]: Statically allocates the RAM space required for the timer control block in the form of an array and stores all established timer control blocks.

OSTm RF reeLiSt: is the head pointer of the idle timer control block linked list. In the idle timer control block (OS_TMR), the OSTmrnext and OSTmrPrev pointers point to the previous and next idle control blocks respectively, organizing the idle control block bidirectional linked list. When establishing a timer, search for the idle timer control block from this linked list.

OSTmrWheelTbl[OS_TMR_CFG_WHEEL_SIZE]: Each element of this array is a group of enabled timers. The element records the pointer to the first timer control block in the group and the number of timer control blocks. In the running timer control block (OS_TMR), the two pointers OSTmrnext and OSTmrPrev also organize the bidirectional linked list of the timer control blocks in the group. The schematic diagram of the data structure required for timer management is shown in Figure 1.

[page]

2.2 Principle of software timer implementation

The macro OS_TMR_CFG_WHEEL_SIZE defines the size of the OSTmr-WheelTbl[] array, and this value is also the basis for timer grouping. Grouping is done according to the remainder of the timer's expiration value divided by OS_TMR_CFG_WHEEL_SIZE: timers with different remainders are placed in different groups; timers with the same remainder are placed in the same group, connected by a bidirectional linked list. In this way, different timer control blocks with remainder values ​​of 0 to OS_TMR_CFG_WHEEL_SIZE-1 correspond to different groups of array elements OSTmr- WheelTbl[0] to OSTmrWheelTbl[OS_TMR_CFGWHEEL_SIZE-1]. Each time the clock beat arrives, the clock number OSTmrTime value is increased by 1, and then the remainder operation is also performed. Only the group of timers with the same remainder may expire, so only this group of timers is judged. This method is more efficient than looping to judge all timers. As the number of clocks accumulates, the processed packets also cycle from 0 to OS_TMR_CFG_WHEEL_SIZE-1.

The semaphore wakes up the timer management task. After calculating the current group to be processed, the program traverses all control blocks in the group and compares the current OSTmr-Time value with the expiration value in the timer control block. If they are equal (i.e., the timer expiration callback function is called; if they are not equal, the next timer control block in the group is determined. This operation is repeated until the end of the group linked list. The process of the timer management task is shown in Figure 2. The value of OS_TMR_CFG_WHEEL_SIZE is recommended to be 2 to the power of N, so that the remainder can be calculated using shift operations to shorten the processing time.

2.3 Timer removal and insertion operations

After the timer's expiration processing function returns, the timer control block must be removed and reinserted from the linked list. Before insertion, the group where the timer will be located next time it expires needs to be recalculated. The calculation formula is as follows:

The OSTmrTime value when the timer expires next time = the timer timing value + the current OSTmrTime value

New group = OSTmrTime value when the timer expires next time% OS_TMR_CFG_WHEEL_SIZE

3 Timer Accuracy and Jitter

In the μC/OS-II operating system, all functions related to timing are based on the system's clock beats. The number of clock beats per second of the system determines the minimum time that the system can distinguish, and the timing value can only be a multiple of the minimum time. The number of clock beats per second is defined by the macro OS_TICKS_PER_SEC in the os_cfg.h. file. For different applications, the clock beat is generally selected in the range of 10 to 100 times/s. The corresponding clock interrupt time interval is 100 to 10 ms, that is, the minimum resolution unit of time is 10 ms. The higher the processor's processing power, the larger the number of clock beats per second. The ARM9 processor was used in the following data test. When the minimum operating frequency is 250 Hz, the clock beat is set to 200 times/s, which can perform normal multi-task scheduling. In this test environment, the minimum resolution time is 5 ms.

Jitter refers to the phenomenon that the timer callback function starts executing earlier or later than the specified time. Jitter always exists in the timer. The following mainly analyzes two types of jitter and their impact on timing accuracy. The first jitter situation is shown in Figure 3.

T1: The time when the CPU responds to the clock interrupt, searches for the interrupt number, saves the interrupt scene and jumps to the clock interrupt handler OSTimTick.

T2: Execution time of OSTimTick() function. This function determines whether the task delay has expired.

T3: The time to restore the scene, exit the interruption and perform task context switching.

T4: The timer management task OSTmr_Task() determines whether the timer has expired.

After T4: When the timer expires, the callback function starts to execute. [page]

When the CPU operating frequency is fixed, the execution time of T1 and T3 is relatively fixed, and they are generally implemented in assembly language and run faster. The time of T2 and T4 will increase with the increase of the number of tasks and software timers. The timer timing value is randomly selected during the test. The time in Table 1 is the maximum value observed when the number of timers is 1 and 5 under different processor frequencies. Among them, T=T1+T2+T3+T4.

From the test data, we can see that if a timer expires, the timer callback function can be executed after a delay of several μs. Compared with the minimum resolution time of ms, the impact of jitter on the accuracy of the time is very small. With the increase of processor frequency and the enhancement of processing power, this jitter time can be further reduced. The second jitter situation is shown in Figure 4.

When the next clock beat is about to arrive (such as time A in Figure 4), a timer is turned on. Because the minimum time that the system can distinguish is the interval between clock beats, the current clock beat number recorded when the timer is turned on is 1. Assume that the timing value of the timer is a clock beat interval. After the timer is turned on, the second clock beat arrives soon. From the analysis of situation 1, it can be seen that the callback function of this timer will be executed soon. Time B indicates the first execution of this timer callback function. Times C and D are the second and third execution times of the callback function, and these two times are relatively accurate.

Therefore, the time from when the timer is turned on to when the callback function starts to execute has a larger jitter than the timing value. If the clock beat interval at this time is 5 ms, the maximum error of this jitter is 5 ms. The jitter in this case can only be reduced by increasing the number of clock beats per second. Therefore, in data acquisition or other timer applications, pay attention to the processing of the first time after the timer is turned on to avoid making wrong judgments.

4 Impact of timer management tasks on operating system performance

The running of the timer management task reduces the number of tasks that can be established by the application by 1. This task requires the highest priority in the system, so it must run every time a clock interrupt occurs, which will inevitably consume a certain amount of CPU resources. The counting formula for the CPU running time (set as M) occupied by the software timer function is:

M = timer management task to determine whether the timer has expired + timer callback function execution time + timer control block removal and reinsertion time + time to switch to the second lowest priority task

First, the statistics task built into μC/OS-II is used to test the CPU resource usage of the timer management task. Three tasks are enabled in the system during the test: the timer management task, the statistics task, and the idle task. The timer expiration callback function is executed in the timer management task, which increases the running time of the management task. In order to only test the overhead of the system timer management function, the timer callback function is set to a no-op during the test. Because the statistics task requires that the statistics task initialization function OSStatInit() must be called in the first and only task established during initialization, necessary changes must be made in the timer management task to ensure that the timer management function is enabled only after the statistics task is initialized. The test timer is statically created in the main function.

After testing, it was found that when the number of timers increased from 1 to 8, the CPU usage rate remained at 1%. This shows that after the system turns on the timer management function, the increased load is very small. On the other hand, because the statistical task calculates the CPU usage rate by integer division and discards the remainder, the counts of 0 to (OSIidleCtrMax/100-1) cannot be distinguished, so the statistical task cannot accurately reflect the CPU usage of the timer management task.

In order to obtain more accurate measurement results, the "processor utilization" indicator is used to test the management task overhead.

Processor occupancy = CPU running time occupied by software timer function (M) / CPU running time

When a certain clock beat arrives, it is assumed that no timer expires under this clock beat, that is, the "timer callback function execution time" and "timer control block removal and reinsertion time" are 0. If the timers created in the current system happen to be in the same group, the management task must compare the expiration value of each timer. This is the highest CPU occupancy rate of the timer management task when no timer expires. In the test, the timer expiration value is set to a multiple of 8 plus 1, and it is statically created in the main() function. Make all timer control blocks in the same group, when OSTime is also a multiple of 8 plus 1, it forms the worst running condition of the timer management task when no timer expires. [page]

The test environment is: ARM9 (400 MHz), the minimum resolution time of the timer is 5 ms (this value is used as the "CPU running time" in calculation), and the minimum resolution time of the hardware timer is 0.02μs. Read the hardware timer calculation time, and the test results are listed in Table 2.

From the test data, we can see that when the number of timers is 8, the processor occupancy rate is much less than 1%. For each additional timer, the running time of the timer management task increases by about 6.5μs, the processor occupancy rate increases by about 0.01%, and the task switching time remains unchanged. This is tested under extreme conditions of construction, and the time in actual application is less than this value.

The "timer control block removal and reinsertion time" is 0.22μs at 400 MHz. When a timer expires during a certain clock beat processing, the worst case is that the timer control block that expires is at the end of the linked list, and the callback function of the expired timer is executed only after the judgment of the entire linked list is completed. Assuming that the number of timers is 8 and the last timer in the linked list expires first, the processor utilization rate at the clock beat when the timer expires is: (0.34μs+0.22μs+0.82μs+timer callback function execution time)/5 ms=(1.38μs+timer callback function execution time)/5 ms.

in conclusion

This paper analyzes the algorithm and jitter problem of μC/OS-II software timer and tests it on a specific platform, which better reflects the accuracy of the timer and the occupation of processor resources. The test results are highly reliable and provide a reliable basis for the development of software timer applications under μC/OS-II.