Implementation of μC/OS-II Task Scheduling Hardware Instructions for Cortex-M3

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 principle of task scheduling with priority first, so that the task with the highest priority among the tasks that enter the ready state can run immediately once it enters 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 - from level 0 to the lowest priority OS_LOWEST_PRIO. The last two are used by the operating system, which are the priorities of the statistical task and the idle task respectively. The μC/OS-II task ready table is shown in Figure 1. The task readiness is also determined based on the two variables OSRdyTb1[] and OSRdyGrp: OSR-dyTb1[] is divided into 8 groups according to task priority (i.e. 8 task priorities in each group). 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.

To make a task enter the ready state and leave the ready state, the two variables OSRdyTb1[] and OSRdyGrp are used to search the OSMapTb1[] table:
① 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 bit of the corresponding element 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. [page]

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[]. According to a certain pattern, there are 128 Os, 64 1s, 32 2s, 16 3s, 8 4s, 4 5s, 2 6s, 1 7, and 1 0 in the table, totaling 256 bytes. The definition of OSUnMapTb1[] is as follows:

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 can be deduced in the same way.
Let's take another 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, and the task scheduling is to find the highest priority task (y=OSUnMapTb1[0x58]). Since OSRdyTb1[3]>OSRdyTb1[4]>OSRdyTb1[6], the result 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 look up 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 the two 32-bit data is searched separately. 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.
In Cotrex-M3, the highest priority task can be located 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. [page]

Assume that in the lower 32 bits of OSRdyTb1[], 000000000000000000000000000001100B indicates that the priority 2 task and the priority 3 task are in the ready state. Now we need to use the instructions RBIT and CLZ to find out the priority 2 task and schedule it to run. After running RBIT, the data becomes: 0011000000000000000000000000000000000000000. After running CLZ, the number of leading zeros is calculated to be 2, indicating that the priority 2 task 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 task communication in μ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, simplifies the code of μC/OS-II, and improves the performance of the processor.