Content Overview:

This article begins with how tasks switch, introducing the ready list and priority table in the RTOS kernel, layer by layer unveiling the mystery of the RTOS kernel’s preemptive scheduling method. Only with an in-depth understanding of the kernel can better applications be created.

1. Knowledge Point Review

1.1. Review of Previous Article

The previous article discussed the three major elements of tasks: task control block, task stack, and task entry function, and highlighted three important points to consider when writing RTOS task entry functions.

If you haven’t read the previous article, please do so first as it will help in understanding this article:

• RTOS Internal Skills Training (I) – How Should Tasks Be Written?

1.2. Doubly Circular Linked List

A doubly linked list is a type of linked list, where each node has not only a successor pointer but also a predecessor pointer. The nodes of a doubly linked list look like this:

If you are not familiar with the implementation and use of a doubly circular linked list, be sure to 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 handler.”

2.1. How to Trigger PendSV Exception

In STM32, setting bit 28 of the Interrupt Control and State Register (ICSR) to 1 manually triggers the PendSV exception, as shown:

The underlying function to trigger the exception 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 code may seem a bit difficult. Let’s take a look at what the two values specifically are:

NVIC_INT_CTRL   EQU     0xE000ED04
NVIC_PENDSVSET  EQU     0x10000000

So this piece of assembly code effectively sets bit 28 of the ICSR register (referred to as NVIC_INT_CTRL in the code) to 1, right?

2.2. Implementing Task Switching in Exception Service

In STM32, the PendSV exception handler is named PendSV_Handler, which is weakly defined by default in stm32l4xx_it.c. Therefore, the implementation in tos can directly redefine this function, with the source code located 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 interruptions during the task switching process:

CPSID   I

② “Save the context”: Save the current CPU register values and the value of the PSP stack pointer into the task stack;

③ “Load the context”: Load the values from the current task stack into the CPU registers and the PSP stack pointer;

④ “Enable global interrupts” to allow real-time responses to all system interrupts:

CPSIE   I

Remember these four processes of task switching; deeply researching the meaning of each assembly instruction is not very helpful.

2.3. When Does the CPU Respond 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. This raises a question:

Compared to GPIO interrupts, timer interrupts, and serial port interrupts, is the priority of the PendSV exception higher or lower?

Imagine the following situation:

① The CPU is happily running task 1…

② At this moment, you press a button, generating a GPIO interrupt. The CPU receives it and immediately runs to execute the interrupt handler…

③ During the processing, a PendSV exception occurs in the system. Upon receiving it, the CPU sarcastically remarks: “I just came from a normal task to handle the interrupt, and I haven’t finished processing yet. Now you want me to execute the next normal task? Have you lost your mind?” After saying that, it continues processing the interrupt…

Therefore, regardless of how high the priority of a task is, it is still lower than an interrupt. “The system’s PendSV exception priority must be set to the lowest” to avoid task switching in external interrupt service functions.

The register to set the PendSV exception priority is as follows, with values ranging from 0 to 255:

In tos, the PendSV exception priority is set during the scheduling startup, with the following source code:

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 a collection of several doubly linked lists and 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 the 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, default is 10:

#define TOS_CFG_TASK_PRIO_MAX           10u

The node type k_list_t is a type of doubly linked list node:

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:

② “A priority table used to indicate the priorities currently being 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 quite precise; if the maximum priority is less than or equal to 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 a uint8_t type:

typedef uint8_t             k_prio_t;

This member indicates the highest priority of tasks currently existing in the system, defaulting to the maximum priority defined by the system.

3.2. How Many Ready Lists Are There in the System?

So, how many ready lists are there in the system?

Indeed, the answer is: “There is only one ready list.”

Declared in tos_global.h for use across all files in the kernel:

/* ready queue of tasks                         */
extern readyqueue_t         k_rdyq;

Defined in tos_global.c:

readyqueue_t        k_rdyq;

“Remember its name, it is called k_rdyq”, where k stands for kernel, and rdyq is the abbreviation for ready queue, which will appear frequently later.

3.3. Initializing the Ready List

Now that we know what the ready list looks like, initializing it becomes very simple; all standard 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;
    }
}

The first step sets the initial value of the highest priority member to the currently configured maximum priority of the system;

The second step initializes each doubly linked list node;

The third step initializes 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 there?

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 task’s priority in the ready list.”

② “Record this priority in the priority table.”

Determine if 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, 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 a priority of 2, the priority table will look like this:

③ “Mount the task’s 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 the doubly linked list, this pend_list node is added to the tail of the list obtained in step 1, as shown:

5. Preemptive Scheduling

5.1. Scheduling Rules

Having understood the above three sections, preemptive scheduling becomes a natural step.

Similarly, here is the source code for preemptive scheduling, located 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();
}

From the source code, we can see that preemptive scheduling actually consists of two steps:

① Get the pointer to the task control block of the highest priority task in the ready list;

② Start the context switch;

In summary, the rule of preemptive scheduling is:

“Whenever scheduling conditions are met, switch to the task with the highest priority in the ready list to run.”

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 present in the system, allowing easy access to the task list mounted at the highest priority. The source code for this function 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 find the base address of the corresponding task control block?

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 of this article.

6. What is the Use of the Priority Table?

The purpose of the priority table is:

“To obtain the highest priority currently in the ready list when removing a task from it.”

The preemptive scheduler does not care about the current state of the task; it always seeks the highest priority task in the scheduling list.

Therefore, when a task needs to actively suspend itself, it must be removed from the ready list, with the source code 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, with the source code 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 task’s current priority in the ready list;

② Disconnect the task control block from this doubly linked list (the task is not deleted);

③ If the list becomes empty after disconnection, it indicates that there are no tasks of this 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.”

At this point, the function of the priority table becomes evident. As mentioned earlier, the priority table records the priorities of tasks currently present in the ready list, allowing the highest priority to be obtained by traversing and querying the priority table, 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

Having discussed so much, it’s very necessary to summarize the key points to note:

① “In the RTOS kernel, task switching is initiated by manually triggering the PendSV exception, and the 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 in external interrupt handling functions.”

③ “The rule of preemptive scheduling in the RTOS kernel is to always find the highest priority task in the ready queue to run.”

Of course, with the rule of preemptive scheduling, the physical body of an RTOS kernel is barely held up. When to schedule is the soul of an RTOS kernel. In the next article, I will meet you all again. I am Mculover666, a small coder who loves playing with boards.

“To receive more exciting articles and resource pushes, please subscribe to my WeChat public account: ‘mculover666’.”