Analysis of the highest priority level search method in UC/OS-II-EEWORLD

Collect

UC/OS-II is a commonly used embedded real-time operating system that supports up to 64 tasks. Since the operating system is a priority-preemptive real-time system, it is important to find the task with the highest priority.

In UC/OS-II, bitmap method is used for representation, that is, each bit represents a task, so an 8-bit number can be composed of an array containing 8 elements. When the task is ready, the corresponding bit will be set to 1. Usually, OSRdyTbl[i], 0=

Since the smaller the priority number is in UC/OS-II, the higher the priority is, we need to know the highest priority in the actual scheduling process. Originally, there are only 64 bits, which can be implemented by simple query, but we know that the query time is different for different priority numbers, which means that our real-time system has a certain delay. The implementation in UC/OS-II shows a certain superiority, and the query time is the same for different priority levels, which further improves the real-time performance. Its implementation method is mainly based on the table lookup method. The specific table design ideas are as follows. According to the above analysis, we only need to know the rows and columns separately to know the finite level number. Then finding the highest priority row number and the highest priority column number will achieve the highest priority search.

The idea of implementation is as follows:

Because OSRdyGrp has 8 bits, there are 256 possible situations. Through OSRdyGrp, we can know the most prioritized row i. Similarly, OSRdyTbl[i] is also 8 bits, so there are also 8 bits, a total of 256 situations. Through it, we can also know the most prioritized column j. Therefore, we can also make judgments based on the same table.

The table design process is as follows:

Since OSRdyGrp has 256 cases, we only need to know the lowest bit that is 1 to know the optimal row number. For example, OSRdyGrp = 98 (d) = 1100010 (b), the lowest bit that is 1 is bit1, so we can know from OSRdyGrp that the highest priority number is in group 1, that is, find row number 1. The same method can also be applied to finding the optimal column.

Therefore, the table can be designed as follows:

INT8U const OSUnMapTbl[256] = {
/* 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f */
0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x00 to 0x0F */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x10 to 0x1F */
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x20 to 0x2F */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x30 to 0x3F */
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x40 to 0x4F */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x50 to 0x5F */
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x60 to 0x6F */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x70 to 0x7F */
7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x80 to 0x8F */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x90 to 0x9F */
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xA0 to 0xAF */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xB0 to 0xBF */
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xC0 to 0xCF */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xD0 to 0xDF */
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xE0 to 0xEF */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 /* 0xF0 to 0xFF */
};

According to the table above, we can find the row with the highest priority number corresponding to each OSRdyGrp value, and also find the column with the highest priority number corresponding to each OSRdyTbl[i] value. Then, according to the equation TaskPrior = 8*i+j=（i<<3）+j, we can determine i and j respectively.

Right now:

i = OSUnMapTbl[OSRdyGrp] ;// Find the row number

j = OSUnMapTbl[OSRdyTbl[i]]; //Find the column number

TaskPrior = 8*i+j=（i<<3）+j; //Find the highest priority number.

The combination of the above bitmap and table lookup method can effectively solve the priority management problem of UC/OS-II.

Extension: If the higher the priority number, the higher the finite level, the same principle of combining the bitmap method with the table lookup can be used. The only difference is the content of the table. In that case, the bit value corresponding to the highest bit being 1 should be selected. In this way, the highest priority number that is ready can be found quickly.

Keywords：UCOS-II Reference address：Analysis of the highest priority level search method in UC/OS-II

Previous article：Magical Uses of Void * Pointers
Next article：Discussion on Task Suspension in uC/OS-II

Popular Resources
Popular amplifiers