Implementation of a μC/OS-II Task Scheduling Hardware Instruction

μC/OS-II is a priority-based preemptive multitasking real-time operating system that includes real-time kernel, task management, time management, inter-task communication synchronization (semaphore, mailbox, message queue) and memory management functions. It can make each task work independently without interfering with each other, and it is easy to achieve timely and error-free execution, making the design and expansion of real-time applications easy and greatly simplifying the application design process.

　　1 Analysis of the task scheduling algorithm of μC/OS-II

1.1 Interpretation of the μC/OS-II task ready table

The μC/OS operating system adopts the priority-first task scheduling principle, so that the task with the highest priority among the tasks entering the ready state can run immediately after entering the ready state. The μC/OS operating system implements a clever table lookup algorithm, which can quickly implement the task scheduling principle. How to find the task with the highest priority from the task ready table? In summary:

two variables (OSrdyGrp, OSRdyTb1[]) and two tables (OSMapTb1[], OSUnMaTb1[]).
The μC/OS operating system can support 64 tasks, each of which is assigned a different priority level - from level 0 to the lowest priority OS_LOWEST_PRIO. The last two are used by the operating system, which are the priorities of statistical tasks and idle tasks respectively. The μC/OS-II task ready table is shown in Figure 1. The judgment of task readiness is also completed based on the two variables OSRdyTb1[] and OSRdyGrp: OSR-dyTb1[] is divided into 8 groups according to task priority (that is, each group has 8 task priorities). When the task is in the ready state, the corresponding bit is 1, otherwise it is 0; when any bit in the OSRdyTb1 group is 1, the corresponding OSRdyGrp position is 1. Figure 1 μC/OS-II task ready table

　　The task is put into the ready state and leaves the ready state by searching the OSMapTb1[] table through the two variables OSRdyTb1[] and OSRdyGrp:

① Enter the ready state. The lower 3 bits of the task priority are used to determine the position of the task in the total ready table OSRdyTb1[]. The first 3 bits are used to determine the number of elements in the OSRclyTb1[] array, and both variables are set to 1. ② Leave the ready state. The code clears the corresponding bits of the corresponding elements in the ready task table array OSRdyTb1[] to 0, and the OSRdyGrp variable will only be 0 when all tasks in this group are out of the ready state.         1.2 Searching for high-priority tasks Search the highest priority task from the task ready table, that is, find the lowest bit of 1 from the OSRdyTb1[] variable (corresponding to the highest priority task). μC/OS-II uses a table lookup to find the highest priority task in the ready state. μC/OS-II has a 256-unit data table OSUnMapTb1[]. In the table, there are 128 Os, 64 1s, 32 2s, 16 3s, 8 4s, 4 5s, 2 6s, 1 7, and 1 0, for a total of 256 bytes. The definition of OSUnMapTb1[] is as follows: [page] The code to find the highest priority task in the ready state is as follows: At first glance, this table seems messy, but it is actually very regular. Take "OSUnMapTb1[0]~OSUnMapTb1[15]: 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /*0x00~0x0F*/" as an example: The others are similar. Let's take an example to illustrate: Assume that variable OSRdyGrp = 01011000B, which means that variables OSRdyTb1[3], OSRdyTb1[4], and OSRdyTb1[6] have tasks in the ready state. Task scheduling is to find the highest priority task (y = OSUnMapTb1[0x58]). Since SRdyTb1[3]>OSRdyTb1[4]>OSRdyTb1[6], the result is y = 3. If OSRdyTb1[3] = 1000 0001B, then by looking up the table x = OS-UnMapTb1[OSRdyTb1[3]], we can get x = 0, indicating that the 0th bit in this group of numbers is 1 and is in the optimal state. In this way, prio = (y < 3) + x = (3 < 3) + 0 = 24. Then use this priority value to search the task control block priority table OSTCBPrioTb1[] to get the task control block OS_TCB pointing to the task. 　　2 Hardware Implementation of μC/OS-II Task Scheduling in Cortex-M3 Cortex-M3 uses a reduced instruction set and Thumb-2 instructions, including hardware algorithm instructions (CLZ) based on RTOS, which can be used to find the highest priority task in the ready state. The ready state of the task in μC/OS-II is reflected in the OSRdyTb1[] variable, which is 8 bytes (64 bits) in total, corresponding to 64 tasks. It can be divided into two 32-bit data, and then the task with the highest priority in these two 32-bit data can be found respectively. First search the lower 32 bits. If the lower 32 bits are not zero, find the highest priority task; otherwise, search the upper 32 bits to find the highest priority task. The search result of the upper 32 bits should be added with the value 32. The        highest priority task can be located in Cortrex-M3 through the following two instructions: RBIT and CLZ. RBIT means to rotate a 32-bit data horizontally by 180°; CLZ means to count the number of leading zeros. Assume that in the lower 32-bit data of OSRdyTb1[], 0000000000000000000000000000001100B indicates that the task with priority 2 and the task with priority 3 are in the ready state. Now we need to find the task with priority 2 and schedule it through the instructions RBIT and CLZ. After running RBIT, the data becomes: 00110000000000000000000000000000000000000000. After running CLZ, the number of leading zeros is calculated to be 2, indicating that the task with priority 2 is in the highest ready state. The task scheduling in μC/OS-II is to find the highest priority task by looking up the table twice. The method is as follows: The above code is tested in MDK4.12 software. The system clock uses 8 MHz. Task scheduling according to this method can save 0.5μs. At the same time, it also reduces the 256-byte space used to store OSUnMapTb1[], shortens the code running time, and improves CPU utilization. This method is also applicable to the task communication of μC/OS-II. I will not go into details here. 　　Conclusion This article mainly analyzes the task scheduling algorithm in μC/OS-II, especially explains how the OSUnMapTb1[] table is constructed, and introduces the task scheduling hardware implementation method of μC/OS-II based on the ARM Cortex-M3 processor platform, which simplifies the code of μC/OS-II and improves the performance of the processor.