Clock beat management mechanism based on μC/OS-II

    In order to effectively manage the clock beat and ensure the real-time performance of the system, μC/OS-III not only adds a dedicated system task to manage the clock beat, but also adopts a hash table mechanism to further reduce the time spent on the clock beat processing process. This article discusses the shortcomings of μC/OS-II in clock beat management and introduces the efficient clock beat management mechanism in μC/OS-III.

    In an embedded real-time operating system (RTOS), a task can suspend itself for a period of time by calling a delay function (such as the OSTimeDly() function in μC/OS). During the delay, the task will release the CPU usage right, that is, the delayed task does not occupy precious CPU resources. The delayed task is tracked and managed by the clock beat service. When the task delay ends and is ready to run, the clock beat service will resume the task. The clock beat service runs periodically, and its operation is triggered by the periodic clock beat interrupt, which can be generated by the hardware timer.

    In μC/OS-III, the clock beat service is completed in the clock beat interrupt service program. Each clock beat service will traverse the entire task list and decrement the delay counters of all delayed tasks. When the number of tasks is large, the clock beat service processing time is very long, which will cause the interrupt delay time and task delay time to become very long, affecting the real-time performance of the system.

    In μC/OS-III, the clock beat service is no longer completed in the clock beat interrupt service program, but in a clock beat task. Moreover, by using the hash table mechanism to manage delayed tasks, each clock beat service only needs to process a very small number of delayed tasks, which greatly reduces the time spent on the clock beat service and improves the real-time performance of the system.

    In addition, in μC/OS series RTOS, the clock beat service will not only track delayed tasks, but also those waiting tasks with a specified timeout limit. That is, when the specified timeout limit expires, the clock beat service will resume the task even if the event the task is waiting for does not occur.

    1 Clock beat management mechanism in μC/OS-II

    In μC/OS-II, each clock beat service will traverse the entire task list and process each task in turn. If the delay count of the currently processed task is 0, then skip the task and continue to process the next task; otherwise, reduce the delay count of the current task by 1, and then determine whether the delay count after reduction is 0. If it is 0, it means that the task delay has ended or the waiting has timed out. Since μC/OS-Ⅱ allows other tasks to call the OSTaskSuspend() function to force the delayed task to be suspended, in this case, not only do you need to wait until the task delay ends, but you also need other tasks to call the OSTaskResume() function to release the forced suspension state of the task before the task can enter the ready state. Therefore, when the delay count decreases to 0, it is also necessary to determine whether the task is forced to be suspended. Only when the task is not forced to be suspended can the task enter the ready state; otherwise, set the delay count to 1 to maintain the delayed state of the task. The main code and comments of the μC/OS-II clock beat service function are as follows:

    In μC/OS-II, since each clock tick service must traverse all tasks, its execution time may be very long when there are many tasks. In addition, since the clock tick service function OSTimeTick ( ) is called and executed by the clock tick interrupt service routine OSTicidSR(), when the execution time of OSTimeTick() is very long, the execution time of the clock tick interrupt service routine is also very long. When the interrupt service routine is executed, all tasks cannot be executed. In this case, the real-time performance of the system will be very poor.

    2 Clock beat management mechanism in μC/OS-III

    In response to the problems of μC/OS-II clock beat service, μC/OS-III mainly made two improvements: 1) Use clock beat tasks to perform clock beat processing; 2) Use clock beat wheel to classify and manage delayed tasks and waiting tasks with specified timeout limits.

    2.1 Clock beat task

    In μC/OS-III, a system task is added, namely the clock tick task OS_TickTask(). This task is one of the two system tasks that are always created in μC/OS-III. The clock tick task is responsible for processing delay tasks and waiting tasks with specified timeout limits. In this way, μC/OS-III puts the clock tick processing work into the task-level code. The relationship between the clock tick interrupt service routine and the clock tick task is shown in Figure 1.

    Whether in μC/OS-II or μC/OS-III, a hardware timer (or other peripherals that can generate periodic frequency of the clock beat interrupt depends on the performance of the processor used and the application requirements. The higher the clock beat interrupt frequency, the higher the delay accuracy of the system and the higher the processing power required of the processor.
    Every time a clock beat interrupt is generated, the CPU will jump to the clock beat interrupt service routine (ISR) for execution. The clock beat ISR will call the OSTimeTick() function. As mentioned earlier, the clock beat ISR of μC/OS-II will also call the OSTimeTick() function. At this point, μC/OS-II and μC/OS-III seem to be the same, but in fact, the OS TimeTick() function in μC/OS-III is very different from the OSTimeTick() function in μC/OS-II. The OSTimeTick() function in μC/OS-III mainly completes the following operations: sending a signal to the clock beat task, calling the OS_SchedRoundRobin() function, and sending a signal to the timer task. Among them, the latter two points are not related to the management of the clock beat and will not be introduced in detail here. The streamlined OSTimeTick() function is shown in the following code, in which only the code related to the clock beat management is retained.
    
    In μC/OS-III, the OSTimeTick() function does not need to traverse the task list, but only sends a signal to the clock beat task through the OSTaskSemPost() function. The clock beat task is in the state of waiting for the signal most of the time. Every time the signal is received, the clock beat task will resume running, call the OS_TiekListUpdate() function to process the delayed task, and then enter the state of waiting for the signal again. The code is as follows:
    
    
    Compared with the clock beat management method of μC/OS-II, μC/OS-III uses a dedicated clock beat task to process the clock beat, which can greatly reduce the execution time of the clock beat interrupt service program.

    In order to improve the processing speed of the clock tick, μC/OS-III uses a hash table mechanism to manage all delayed tasks and waiting tasks with a specified timeout limit. These tasks are recorded in the clock tick list (TICk List ) . The clock tick list consists of two parts: an array called the clock tick wheel (OSCfg_TickWheel[]) and a clock tick counter (OSTick CTR ), as shown in Figure 2.

    Each task in the clock tick list has a delayed end time or a waiting timeout limit, which is assumed to be TM. For example, when the clock tick counter value is OSTickCtr, a task calls OSTimeDly() to delay dly clock ticks, then the delayed end time TM of the task is equal to OSTickCtr+dly. Then, by performing a modulo operation with TM and the number of entries in the clock tick wheel (OS_CFG_TICK_WHEEL_SIZE), a remainder I (I=TM%OS_CFG_TICK_WHEEL_SIZE) can be obtained. Then, the delayed task will be placed in the task list pointed to by the first entry in the clock tick wheel.

    Each entry in the clock beat wheel has three members: ".NbrEntriesMax", ".NbrEntries" and ".FirstPtr". Among them, ".FirstPtr" points to the task list corresponding to the entry. All delayed tasks or waiting tasks with a specified timeout period assigned to the entry will be placed in the task list. ".NbrEntries" and ".NbrEntries Max" record the current number of tasks and the historical maximum number of tasks in the task list respectively. In the task list, tasks are sorted according to the delay end time or timeout period, and tasks with earlier end time are placed at the front of the list.

    By adopting the hash table mechanism, in each clock beat service, only the task list pointed to by a specific table item of the clock beat wheel needs to be processed, because the tasks that are delayed or waiting for timeout during the clock beat service must be in the task list pointed to by the table item, and the index number of the table item is equal to OSTickCtr%OS_CFG_TICK_WHEEL_SIZ E. In addition, since the tasks in the task list pointed to by each table item are sorted in the order of the delay end time and the waiting timeout limit, when processing the current task list, it is possible to judge whether the task delay end time or waiting timeout limit is equal to the current value of OSTickCtr from the task at the head of the list. If it is equal, it means that the task delay has ended or the waiting timeout has expired, and then the next task is judged; if it is not equal, it means that the task delay has not ended or the waiting timeout has not expired, and it also means that the tasks behind the list cannot be delayed or waited for timeout, so the processing of the task list can be ended immediately.

    Due to the use of the hash table mechanism, the clock beat service in μC/OS-III only needs to determine the delayed end time or timeout limit of a very small number of tasks in most cases to see whether it is equal to the current value of the clock beat counter. This is obviously much more efficient than the clock beat service in μC/OS-II that needs to traverse the entire task list.

    Conclusion

    The clock beat service in μC/OS-II has two shortcomings: one is that it needs to traverse the entire task list, and the other is that it needs to process the clock beat in the clock beat interrupt service program. When there are many tasks in the system, it will affect the real-time performance of the system, which is an imperfection for a real-time embedded operating system. In μC/OS-III, by adding a clock beat system task and using a hash table mechanism, these two problems are well solved, and the real-time performance of the system can be ensured even when there are many tasks in the system.