μC/OS-II timer algorithm analysis and testing

Introduction
The μC/OS-II operating system is a real-time operating system based on a microkernel. Its features such as 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, both the task delay function and the software timer function require a hardware counter support at the bottom layer. The hardware counter decrements at a fixed frequency, and when the count reaches 0, the clock interrupt is triggered. 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 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 program, 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, and only needs to be in os_cfg. h file to enable the timer and set the timer's related parameters.

2 Analysis of the software timer algorithm of μC/OS-II
The implementation method of software timer in μC/OS-II is to group 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 relatively efficient algorithm that reduces the operation time required for maintenance.
2.1 Data structure 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, which contains 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, the maintenance of three types of linked lists is 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 the established timer control blocks.
OSTmrFreeLiSt: is the pointer to the head of the free timer control block linked list. In the idle timer control block (OS_TMR), the two pointers OSTmrnext and OSTmrPrev point to the previous and next free control blocks respectively, organizing a bidirectional linked list of free control blocks. When establishing a timer, search for the free 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.

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. The timers are grouped according to the remainder of the timer expiration value divided by OS_TMR_CFG_WHEEL_SIZE: timers with different remainders are placed in different groups; timers with the same remainder are in the same group and 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 groups also cycle from 0 to OS_TMR_CFG_WHEEL_SIZE-1.
The semaphore wakes up the timer management task, and 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 flow 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 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 when it next expires needs to be recalculated. The calculation formula is as follows:
OSTmrTime value when the timer next expires = timer timing value + current OSTmrTime value
New group = OSTmrTime value when the timer next expires % 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 clock beat. The number of system clock beats per second 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 processing power, the larger the number of clock beats per second. The ARM9 processor is used in the following data test. When the minimum operating frequency is 250 Hz, the clock beat is set to 200 times/s, and normal multi-task scheduling can be performed. In this test environment, the minimum resolution time is 5 ms.
Jitter refers to the phenomenon that the time when the timer callback function starts to execute is either 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 type of jitter 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: The execution time of the OSTimTick() function. This function determines whether the task delay has expired.
T3: The time to restore the scene, exit the interrupt and switch the task context.
T4: The time when the timer management task OSTmr_Task() determines whether the timer has expired.
After T4: The callback function starts to execute when the timer expires. [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 (as shown in 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. Time 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 the timer being turned on to the callback function starting to execute has a larger jitter compared with 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 the application of data acquisition or other timers, pay attention to the processing of the first time after the timer is turned on to avoid making wrong judgments.

4 Impact of the timer management task on the performance of the operating system
The operation 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 occupied by the software timer function (set as M) is:
M = the time for the timer management task to determine whether the timer has expired + the execution time
of the timer callback function + the time to remove and reinsert the timer control block + the 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 occupation of the timer management task. During the test, three tasks are enabled in the system: timer management task, statistics task, and Idle task. The timer expiration callback function is executed in the timer management task, which increases the management task running time. In order to test only 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 timer for the test is statically created in the main function.
After the test, it was found that when the number of timers increased from 1 to 8, the CPU usage rate remained at 1%. This shows that the increased load after the system turned on the timer management function was very small. On the other hand, because the statistical task calculates the CPU usage rate by integer division and discards the remainder, the counts from 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 occupancy rate" indicator is used to test the management task overhead.
Processor occupancy rate = CPU running time occupied by the 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. At this time, it 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 is created statically in the main() function. All timer control blocks are placed in the same group. When OSTime is also a multiple of 8 plus 1, the worst running condition of the timer management task when no timer expires is formed.
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" during 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, it can be seen that when the number of established timers is 8, the processor occupancy rate is far 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 the extreme conditions of the construction, and the time in actual application should be less than this value.
The "timer control block removal and reinsertion time" was tested to be 0.22μs at 400 MHz. When a clock beat is processed, if a timer expires, 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.

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 credible and provide a reliable basis for the development of software timer applications under μC/OS-II.