Follow+Star Public Number, don’t miss wonderful content
Source | McuLover666
1. Knowledge Point Consolidation
1.1. Knowledge Point Consolidation
The three major elements of a task: task control block, task stack, task entry function, here you can refer to the article:
-
How to write RTOS tasks?
1.2. Doubly Circular Linked List
A doubly linked list is a type of linked list, distinguished by the fact that each node has both a successor pointer and a predecessor pointer, the nodes of a doubly linked list look like this:
If you are not familiar with the implementation and usage of doubly circular lists, please read this article first:
-
Implementation and Use of Doubly Circular Linked List in TencentOS-tiny
2. How Tasks Switch
In the RTOS kernel, the principle of switching from one task to the next is:
“Manually trigger the PendSV exception, and implement task switching in the PendSV exception service function”.
2.1. How to Trigger PendSV Exception
In STM32, set bit 28 of the Interrupt Control and State Register (ICSR) to 1 to manually trigger the PendSV exception, as shown:
The underlying function to trigger exceptions in tos is port_context_switch, implemented in arch\arm\arm-v7m\cortex-m4\armcc\port_s.S as follows:
GLOBAL port_context_switch
port_context_switch
LDR R0, =NVIC_INT_CTRL
LDR R1, =NVIC_PENDSVSET
STR R1, [R0]
BX LR
At first glance, this assembly looks a bit difficult; let’s take a look at the specific values:
NVIC_INT_CTRL EQU 0xE000ED04
NVIC_PENDSVSET EQU 0x10000000
So the assembly code above is actually completing the operation of setting bit 28 of the ICSR register (which is NVIC_INT_CTRL in the code) to 1, right?
2.2. Implementing Task Switching in Exception Service
In STM32, the PendSV exception service function is named PendSV_Handler, and a weak definition is provided by default in stm32l4xx_it.c, so the implementation in tos can directly redefine this function, with the source code in arch\arm\arm-v7m\cortex-m4\armcc\port_s.S, the main steps are four:
① “Disable global interrupts” (except NMI and HardFault) to prevent interruption during task switching:
CPSID I
② “Save the context”: Save the values of the current CPU register set and the value of the PSP stack pointer to the task stack;
③ “Load the context”: Load the values from the current task stack into the CPU register set and the PSP stack pointer;
④ “Enable global interrupts” to respond to all system interrupts in real time:
CPSIE I
Just remember these four processes for task switching; delving into what each assembly instruction means is not very useful or helpful.
2.3. When the CPU Responds to PendSV Exception
We all know that “high-priority interrupts can interrupt low-priority interrupts”, which is an important guarantee of system real-time performance, so a question arises:
Compared to GPIO interrupts, timer interrupts, and serial interrupts, is the PendSV exception priority higher or lower?
Imagine this situation:
① The CPU is happily running task 1…
② At this moment, you press a button, generating a GPIO interrupt, and the CPU immediately runs to execute the interrupt handler…
③ During the processing, a PendSV exception occurs, and the CPU receives it and sarcastically says: “I just came from a normal task to handle an interrupt, and haven’t finished processing, now you want me to execute the next normal task, are you crazy?” After saying that, it continues to handle the interrupt…
Therefore, no matter how high the priority of the task is, it is not as high as an interrupt, “the priority of the system’s PendSV exception must be set to the lowest” to avoid task switching during external interrupt service functions.
The register to set the PendSV exception priority is as follows, the value can be from 0-255:
In tos, the priority of the PendSV exception is set when starting the scheduler, with the source code as follows:
NVIC_SYSPRI14 EQU 0xE000ED22
NVIC_PENDSV_PRI EQU 0xFF
Similarly, the assembly code to set the PendSV exception priority to the lowest is as follows:
; set pendsv priority lowest
; otherwise trigger pendsv in port_irq_context_switch will cause a context switch in irq
; that would be a disaster
MOV32 R0, NVIC_SYSPRI14
MOV32 R1, NVIC_PENDSV_PRI
STRB R1, [R0]
3. Ready List
3.1. What Does the Ready List Look Like?
The ready list is actually many doubly linked lists + a priority table, its type is defined in tos_sched.h, as follows:
typedef struct readyqueue_st
{
k_list_t task_list_head[TOS_CFG_TASK_PRIO_MAX];
uint32_t prio_mask[K_PRIO_TBL_SIZE];
k_prio_t highest_prio;
} readyqueue_t;
① “Each priority is assigned a head node of a doubly linked list to mount the tasks of that priority”.
TOS_CFG_TASK_PRIO_MAX is the maximum task priority, configured in tos_config.h, the default is 10:
#define TOS_CFG_TASK_PRIO_MAX 10u
The node type k_list_t is a doubly linked list node type:
typedef struct k_list_node_st
{
struct k_list_node_st *next;
struct k_list_node_st *prev;
} k_list_t;
After all doubly linked list nodes are initialized, each doubly node’s next pointer points to itself (orange line), and the prev pointer also points to itself, as shown:
② “Used to indicate the priority currently used by the system”.
The size of the priority table is determined by the macro definition K_PRIO_TBL_SIZE:
#define K_PRIO_TBL_SIZE ((TOS_CFG_TASK_PRIO_MAX + 31) / 32)
This definition is more particular; if the maximum priority does not exceed 32, the value of this macro will be 1, and a uint32_t type variable can be used, with each priority represented by one bit.
After initialization, the priority table looks like this:
③ “Highest priority indicator member”.
The member highest_prio in the ready list is of type k_prio_t, which is actually of type uint8_t:
typedef uint8_t k_prio_t;
This member indicates the highest priority of the tasks currently existing in the system, and the default is the maximum priority defined by the system.
3.2. How Many Ready Lists Are in the System?
That’s right, the answer is: “There is only one ready list”.
Declared in tos_global.h, convenient for use in all files of the entire kernel:
/* ready queue of tasks */
extern readyqueue_t k_rdyq;
Defined in tos_global.c:
readyqueue_t k_rdyq;
“Remember its name, it’s called k_rdyq”, where k stands for kernel and rdyq is an abbreviation for ready queue, it will appear frequently later.
3.3. Initializing the Ready List
Once you know what the ready list looks like, initializing the ready list becomes very simple, it’s all routine operations, implemented in tos_sched.c:
__KNL__ void readyqueue_init(void)
{
uint8_t i;
k_rdyq.highest_prio = TOS_CFG_TASK_PRIO_MAX;
for (i = 0; i < TOS_CFG_TASK_PRIO_MAX; ++i) {
tos_list_init(&k_rdyq.task_list_head[i]);
}
for (i = 0; i < K_PRIO_TBL_SIZE; ++i) {
k_rdyq.prio_mask[i] = 0;
}
}
Step ① is to set the initial value of the highest priority member to the highest priority configured for the system;
Step ② is to initialize each doubly linked list node;
Step ③ is to initialize all values of the priority table to 0.
4. How Tasks Are Mounted to the Ready List
At the end of the task creation API, the function readyqueue_add_tail is called to add the task to the ready list, so how is the task actually mounted?
The source code implementation of this function is as follows:
__KNL__ void readyqueue_add_tail(k_task_t *task)
{
k_prio_t task_prio;
k_list_t *task_list;
task_prio = task->prio;
task_list = &k_rdyq.task_list_head[task_prio];
if (tos_list_empty(task_list)) {
readyqueue_prio_mark(task_prio);
}
tos_list_add_tail(&task->pend_list, task_list);
}
① “Get the head node corresponding to the priority of the task in the ready list”.
② “Record this priority in the priority table”.
Determine whether this priority appears for the first time in the system; if so, set the corresponding bit in the priority table to 1 to indicate that a task of this priority exists in the system, and reassign the highest priority member in the ready list (note: the lower the priority value, the higher the priority):
__STATIC_INLINE__ void readyqueue_prio_insert(k_prio_t prio)
{
k_rdyq.prio_mask[K_PRIO_NDX(prio)] |= K_PRIO_BIT(prio);
}
__STATIC_INLINE__ void readyqueue_prio_mark(k_prio_t prio)
{
readyqueue_prio_insert(prio);
if (prio < k_rdyq.highest_prio) {
k_rdyq.highest_prio = prio;
}
}
For example, when we create a task with priority 2, the priority table will look like this:
③ “Mount the task control block’s pend list node to the tail of the doubly linked list obtained in step 1”.
The pend_list member in the task control block is also a doubly linked list node:
/**
* task control block
*/
struct k_task_st {
//……
k_list_t pend_list; /**< when we are ready, our pend_list is in readyqueue; when pend, in a certain pend object's list. */
//……
};
Using a doubly linked list to add this pend list node to the tail of the doubly linked list obtained in step 1, after adding it, as shown:
5. Priority Preemptive Scheduling
5.1. Scheduling Rules
Understanding the above three sections, the priority preemptive scheduling becomes a natural conclusion.
Similarly, let’s first look at the source code of priority preemptive scheduling in tos_syc.c:
__KNL__ void knl_sched(void)
{
TOS_CPU_CPSR_ALLOC();
if (unlikely(!tos_knl_is_running())) {
return;
}
if (knl_is_inirq()) {
return;
}
if (knl_is_sched_locked()) {
return;
}
TOS_CPU_INT_DISABLE();
k_next_task = readyqueue_highest_ready_task_get();
if (knl_is_self(k_next_task)) {
TOS_CPU_INT_ENABLE();
return;
}
cpu_context_switch();
TOS_CPU_INT_ENABLE();
}
In the source code, it can be seen that priority preemptive scheduling is actually two steps:
① Get the pointer to the task control block of the highest priority task in the ready list;
② Start context switching;
To summarize, the rule of priority preemptive scheduling is:
“Whenever scheduling conditions are met, switch to the highest priority task in the ready list to start running”.
5.2. How to Get the Highest Priority Task
Don’t forget that there is a member in the ready list called highest_prio, which indicates the highest priority currently existing in the system, making it easy to obtain the linked list of the highest priority task, the function source code is as follows:
__KNL__ k_task_t *readyqueue_highest_ready_task_get(void)
{
k_list_t *task_list;
task_list = &k_rdyq.task_list_head[k_rdyq.highest_prio];
return TOS_LIST_FIRST_ENTRY(task_list, k_task_t, pend_list);
}
However, it should be noted that what is mounted on the ready list is the pend list node in the task control block, as shown:
Knowing the address of the pend list node in the task control block, how do we determine the base address of the task control block it belongs to?
Actually, it is obtained through the macro TOS_LIST_FIRST_ENTRY, for specific usage, please refer to the second article I mentioned at the beginning.
6. What is the Use of the Priority Table?
The purpose of the priority table is:
“To obtain the highest priority in the current ready list when removing a task from the ready list”.
The priority preemptive scheduler is indifferent to everything, it doesn’t care what the current state of the task is, it always looks for the highest priority task in the scheduling list.
So when a task needs to actively suspend, it must be removed from the ready list, the source code is as follows:
__API__ k_err_t tos_task_suspend(k_task_t *task)
{
TOS_CPU_CPSR_ALLOC();
//A bunch of parameter checks omitted
TOS_CPU_INT_DISABLE();
if (task_state_is_ready(task))
{
// kill the good kid
readyqueue_remove(task);
}
task_state_set_suspended(task);
TOS_CPU_INT_ENABLE();
knl_sched();
return K_ERR_NONE;
}
The core function to remove from the ready list is readyqueue_remove, the source code is as follows:
__KNL__ void readyqueue_remove(k_task_t *task)
{
k_prio_t task_prio;
k_list_t *task_list;
task_prio = task->prio;
task_list = &k_rdyq.task_list_head[task_prio];
tos_list_del(&task->pend_list);
if (tos_list_empty(task_list)) {
readyqueue_prio_remove(task_prio);
}
if (task_prio == k_rdyq.highest_prio) {
k_rdyq.highest_prio = readyqueue_prio_highest_get();
}
}
① Get the head node of the current priority in the ready list;
② Disconnect the task control block from that doubly linked list (but do not delete the task);
③ If the linked list becomes empty after disconnection, it indicates that there are no tasks of that priority in the ready list, and the corresponding bit in the priority table will be cleared;
④ “Re-obtain the highest priority in the ready list”.
This is when the role of the priority table is reflected; as mentioned earlier, the priority table records the priorities of the tasks currently existing in the ready list, so it can be used to traverse and find the highest priority, which is then assigned to the indicator member in the ready list.
The source code is as follows:
__STATIC__ k_prio_t readyqueue_prio_highest_get(void)
{
uint32_t *tbl;
k_prio_t prio;
prio = 0;
tbl = &k_rdyq.prio_mask[0];
while (*tbl == 0) {
prio += K_PRIO_TBL_SLOT_SIZE;
++tbl;
}
prio += tos_cpu_clz(*tbl);
return prio;
}
7. Summary
After discussing so much content, it is very necessary to summarize the key points:
① “The RTOS kernel starts a switch by manually triggering the PendSV exception, and task switching is implemented in the PendSV exception service function”.
② “The priority of the PendSV exception in the RTOS kernel is set to the lowest to avoid task switching during external interrupt handler functions”.
③ “The so-called priority preemptive scheduling rule in the RTOS kernel is to always find the highest priority task from the ready queue to run”.
Of course, with the priority preemptive scheduling rule, it barely supports the physical body of an RTOS kernel, but when to schedule is the soul of an RTOS kernel.
