The unexamined life is not worth living.
Life without examination is not worth living.
– Socrates
1, Principle overview
RT thread is not only an embedded real-time operating system (RTOS), but also an excellent Internet of things operating system. Compared with the bare metal polling scheduling algorithm, its thread (task) scheduling algorithm is a priority based full preemptive multithreading scheduling algorithm. This algorithm greatly enhances the real-time response of the system and greatly expands the application scenario of the system.
When scheduling tasks each time, the scheduling algorithm always selects the ready task with the highest priority to execute, so as to ensure that the tasks with high priority get the most timely response.
Next, we will explain the principle and implementation of the scheduling algorithm in detail.
Note: the version based on RT thread is RT-Thread v4.0.5 released , which was released on December 31, 2021.
First, a bidirectional linked list array RT is defined in RT thread_ thread_ priority_ Table, which is used to mount ready threads. The code is as follows:
/* Double List structure*/
struct rt_list_node
{
struct rt_list_node *next; /**< point to next node. */
struct rt_list_node *prev; /**< point to prev node. */
};
typedef struct rt_list_node rt_list_t; /**< Type for lists. */
rt_list_t rt_thread_priority_table[RT_THREAD_PRIORITY_MAX]; //Thread priority bidirectional linked list array
In fact, it implements the following structure:
Where RT_ THREAD_ PRIORITY_ Max represents the number of priorities configured by the system. The scheduling algorithm of RT thread only supports RT_ THREAD_ PRIORITY_ Max < = 256, this number is absolutely enough for most project requirements. And rt_thread_priority_table[RT_THREAD_PRIORITY_MAX] the array is from 0 to RT_ THREAD_ PRIORITY_ The array elements of MAX-1 correspond to the priority of tasks from 0 to RT_THREAD_PRIORITY_MAX-1.
When a thread is ready, the thread will be mounted to the position of the rt_thread_priority_table element corresponding to its priority. Suppose there are two threads, thread1 with priority 0 and thread2 with priority 1. When they enter the ready state and wait for scheduling, the effect is as follows:
At this point, the problem arises. When the tasks are in the ready state and mounted on the rt_thread_priority_table, how can we find the one with the highest priority among all ready tasks?
First of all, we think that we can start from position 0 in the rt_thread_priority_table. Once we find a mounted thread in which position, it means that there is a corresponding task ready under the priority and the thread can be executed. The next time you schedule a task, you can start searching from 0 according to the steps just now. This is a way to solve the problem.
But think about it carefully. If the highest priority in the ready task is relatively low, such a search algorithm will almost traverse it, which is obviously time-consuming and does not match the word "real-time" in the real-time operating system (RTOS).
In order to schedule tasks more efficiently, RT thread uses the mapping of rt_thread_ready_table. In short, it is to maintain a table recording ready tasks. By looking up this table, we can know which task has the highest priority in the current ready tasks, and then directly execute the tasks under this priority.
Specifically, the number of bits in the rt_thread_ready_table corresponds to the priority one by one. When a bit in the table is 1, it means that there are tasks ready under this priority.
RT thread is a multi task scheduling system. Due to the trigger of external conditions, each task should often switch between ready state and non ready state (corresponding to the data structure: the bidirectional pointer of the task is inserted or separated from rt_thread_priority_table). Therefore, the mapped thread ready table should also be updated at any time according to the status of the tasks, Corresponding to this table is nothing more than clearing the corresponding bit of this table to 0 when there are no tasks under a certain priority. When there are tasks attached under this priority, the position of this ready table to 1.
Through this table, we can find the task with the highest priority in the time complexity of O(1), and realize the rapid scheduling of the task with the highest priority. When switching the status of tasks, update the contents of this table in real time to ensure that the corresponding results of rt_thread_ready_table and rt_thread_priority_table are correct.
Next, it's time to show the code. It may consume some brain cells.
2, Implementation details
Let's take a look at the code implementation of rt_thread_ready_table:
/* Thread priority ready group, when RT_ THREAD_ PRIORITY_ When Max < = 32, each bit directly corresponds to 32 priorities, otherwise it is mapped to RT respectively_ thread_ ready_ table)*/ rt_uint32_t rt_thread_ready_priority_group; #if RT_THREAD_PRIORITY_MAX > 32 /* Maximum priority level, 256 */ rt_uint8_t rt_thread_ready_table[32];//Corresponding 32 * 8 (bits) = 256 priorities #endif
According to RT_ THREAD_ PRIORITY_ Different from the macro definition of Max, there are two ways to implement the rt_thread_ready_table:
-
When the priority number is less than or equal to 32, a 32-bit variable RT is defined_ thread_ ready_ priority_ Group can implement the thread ready table, which is the simplest to implement and saves space and time (the search efficiency will be improved). Therefore, if you do not need too many priorities, it is recommended to set the number of priorities to less than or equal to 32.
-
Corresponding to RT_ THREAD_ PRIORITY_ In the case of Max > 32, you can imagine that the purpose is to want a variable with a data length of 256 bits. However, at present, most MCU running RTOS are 32 bits, so this compromise can only be adopted here, which is equivalent to double mapping to achieve the coveted variable with a data length of 256 bits.
Before talking about how to use and update the rt_thread_ready_table, let's take a look at the structure of a specific priority task, which is related to the scheduling algorithm. The following is the definition of the structure of the task thread. I delete irrelevant variables, leaving only all relevant variables:
/**
* Thread structure
*/
struct rt_thread
{
.......
rt_list_t tlist; /**< the thread list Used to mount in the thread priority table*/
/* priority */
rt_uint8_t current_priority; /**< current priority Current priority*/
rt_uint8_t init_priority; /**< initialized priority initial priority */
#if RT_THREAD_PRIORITY_MAX > 32
rt_uint8_t number; //Mark as yes_ thread_ ready_ Which element in table [32]
rt_uint8_t high_mask; //The mask corresponding to the specific element, which is used to speed up the operation
#endif
rt_uint32_t number_mask; //rt_ thread_ ready_ priority_ The mask corresponding to group, which is used to speed up the operation
.......
};
typedef struct rt_thread *rt_thread_t;
A brief mention of the role of the mask here is to facilitate the subsequent operation of the thread priority ready table. For example, suppose there is a task with a priority of 20, the mask of its corresponding thread structure is as follows:
For RT_ THREAD_ PRIORITY_ MAX <= 32:
number_mask = 1<<20(priority); number_mask: 000100000000000000000000 is to make number_ The 19th bit of the mask is 1.
Anyway, why set number_ What about the mask variable? When using this variable, directly use 1 < < priority instead of number_ Isn't mask OK? In fact, it's not impossible. If it is used in this way, it needs to carry out one more displacement operation. In fact, it is also a strategy of exchanging space for time. It pays the price of a variable to obtain faster operation speed, which increases the speed of scheduling tasks of the real-time system, and is also conducive to the real-time performance of the system.
For RT_ THREAD_ PRIORITY_ Max > 32, the principle is the same, so I won't repeat it.
How does RT thread initialize the above variables?
In the initialization function of a thread (whether dynamically creating a thread or statically initializing a thread), operations are performed according to the passed priority parameters, which are mainly used for initialization:
rt_err_t _thread_init(...,priority)
{
......
/* priority init */
RT_ASSERT(priority < RT_THREAD_PRIORITY_MAX);
thread->init_priority = priority;
thread->current_priority = priority;
thread->number_mask = 0;
#if RT_THREAD_PRIORITY_MAX > 32
thread->number = 0;
thread->high_mask = 0;
#endif
......
}
When starting a thread, update the data corresponding to the thread:
rt_err_t rt_thread_startup(rt_thread_t thread)
{
......
/* calculate priority attribute */
#if RT_THREAD_PRIORITY_MAX > 32
thread->number = thread->current_priority >> 3; /* It's equivalent to dividing by 8 to get the corresponding array */
thread->number_mask = 1L << thread->number; /* Get the mask corresponding to the array position */
thread->high_mask = 1L << (thread->current_priority & 0x07); /* Mask specific to the corresponding array element */
#else
thread->number_mask = 1L << thread->current_priority; /* Mask */
#endif
......
}
Now that everything is ready, let's see how the scheduler operates the priority ready table when scheduling tasks.
2.1. How to find the highest priority in the current ready task
In fact, it is to find the position of the priority ready table closest to the previous 1. This table will be used to obtain the highest priority every time the task is scheduled, and then the highest priority thread ready at this time will be obtained according to the highest priority.
//This function is used to get the highest priority task that is currently ready
static struct rt_thread* _scheduler_get_highest_priority_thread(rt_ubase_t *highest_prio)
{
......
#if RT_THREAD_PRIORITY_MAX > 32
register rt_ubase_t number;
//The result is an array RT_ thread_ ready_ Which element of table
number = __rt_ffs(rt_thread_ready_priority_group) - 1;
//Shifting 3 bits to the right means * 8. Get the base address of the array, and finally add the position in the group to get the real priority
highest_ready_priority = (number << 3) + __rt_ffs(rt_thread_ready_table[number]) - 1;
#else
//Get specific priorities directly
highest_ready_priority = __rt_ffs(rt_thread_ready_priority_group) - 1;
#endif /* RT_THREAD_PRIORITY_MAX > 32 */
......
}
Let's focus on here__ rt_ffs() function, which realizes the function of obtaining the lowest position of 1 in the incoming 32-bit variable, that is, the so-called implementation of finding the lowest non-0 bit of the byte. This function can find the lowest priority under the time complexity of O(1). It uses the bitmap search algorithm, which is still very sophisticated. Due to the limited space, please move to this article: Bitmap scheduling algorithm analysis of RT thread (latest version).
2.2. How to update the thread readiness list when the task is ready?
If a task is ready, the thread ready table is updated according to the priority of the task_ thread_ ready_ Corresponding position of table.
//This function is used to add a new task to the ready state
void rt_schedule_insert_thread(struct rt_thread *thread)
{
......
#if RT_THREAD_PRIORITY_MAX > 32
rt_thread_ready_table[thread->number] |= thread->high_mask; //Let the specific position 1 of the corresponding priority group indicate that it is ready
#endif
rt_thread_ready_priority_group |= thread->number_mask; //Set the grouping position of the corresponding priority to 1
......
}
2.3. How to update the thread ready list when the task is out of the ready state?
When a task is out of the ready state (deleted, suspended, etc.), we also need to update the thread ready table rt_thread_ready_table. Since RT thread supports multiple tasks with the same priority, we are updating the thread ready table rt_thread_ready_table needs to consider whether other tasks under this priority are still ready.
//This function is used to remove a task from the ready state
void rt_schedule_remove_thread(struct rt_thread *thread)
{
......
if (rt_list_isempty(&(rt_thread_priority_table[thread->current_priority])))//It indicates that there are no other ready tasks under this priority
{
#if RT_THREAD_PRIORITY_MAX > 32
rt_thread_ready_table[thread->number] &= ~thread->high_mask;//Let the specific position of the corresponding priority group be 0, indicating that it is out of the ready state
if (rt_thread_ready_table[thread->number] == 0)//When each bit of the array element is 0, it can be set to 0, because the group may have other tasks ready
{
rt_thread_ready_priority_group &= ~thread->number_mask;//Clear the corresponding position of the table to 0
}
#else
rt_thread_ready_priority_group &= ~thread->number_mask; //Clear the corresponding position of the table to 0
#endif /* RT_THREAD_PRIORITY_MAX > 32 */
}
......
}
3, Some useful suggestions
- Due to code implementation, RT_THREAD_PRIORITY_MAX must be configured to be less than or equal to 256, otherwise the system will work abnormally.
- In addition to idle tasks, each priority task should have an operation to give up CPU usage (temporarily out of the ready state, such as using delay), so that threads with lower priority can have the opportunity to execute.
- If the chip used has limited resources (RAM, ROM, etc.), it is recommended to use RT as much as possible_ THREAD_ PRIORITY_ The max setting should be smaller, preferably less than or equal to 32, which not only saves resources, but also speeds up the scheduling speed.
4, References
- Bitmap scheduling algorithm analysis of RT thread (latest version)
- RT thread Document Center - thread management
For more articles, please pay attention to the official account number:
