It suddenly dawned on me; I realized that I had a strong feeling for FreeRTOS after seeing a lot of assembly code during Keli’s debugging, running so fast that we didn’t even notice the frequent task switching.
1. The Essence of Multitasking Execution
1.1 Core Concepts
On a single-core MCU, multitasking does not truly execute in parallel; instead, it achieves “time slicing” through rapid task switching.
1.2 Basic Principles
For the hardware characteristics of the MCU, a single-core MCU still executes one instruction at a time in sequence; however, the RTOS periodically interrupts through the system timer to save/restore task states. Due to the extremely high switching frequency (usually 1ms), users perceive multiple tasks as running “simultaneously”.
2. Time Slicing Mechanism
2.1 Time Slicing Diagram
Time Axis: |----1ms----|----1ms----|----1ms----|----1ms----|----1ms----|
Task Execution: [ Task A executes ] [ Task B executes ] [ Task C executes ] [ Task A executes ] [ Task B executes ]
Interrupt: ↑SysTick ↑SysTick ↑SysTick ↑SysTick ↑SysTick
State: [Save A] [Save B] [Save C] [Save A] [Save B]
[Load B] [Load C] [Load A] [Load B] [Load C]
2.2 System Timer (SysTick) Configuration
// Typical SysTick configuration
#define configTICK_RATE_HZ 1000 // 1000Hz = 1ms time slice
#define configCPU_CLOCK_HZ 100000000 // 100MHz CPU
// SysTick initialization
SysTick_Config(configCPU_CLOCK_HZ / configTICK_RATE_HZ); // Trigger every 1ms
2.3 Characteristics of Time Slices
| Feature | Description |
|---|---|
| Time Slice Length | Usually 1ms, configurable |
| Interrupt Frequency | 1000Hz (1ms interval) |
| Switching Overhead | Tens of CPU cycles |
| User Perception | No perception, tasks seem to run in parallel |
3. Detailed Process of Task Switching
3.1 Four Steps of Task Switching
Step 1: System Timer Interrupt Trigger
/**
* @brief SysTick interrupt handler
* @note Triggered every 1ms, the starting point of task scheduling
*/
void xPortSysTickHandler(void)
{
uint32_t ulPreviousMask;
ulPreviousMask = portSET_INTERRUPT_MASK_FROM_ISR();
{
/* Increment system tick counter */
if( xTaskIncrementTick() != pdFALSE )
{
/* Task switch needed, trigger PendSV interrupt */
portNVIC_INT_CTRL_REG = portNVIC_PENDSVSET_BIT;
}
}
portCLEAR_INTERRUPT_MASK_FROM_ISR( ulPreviousMask );
}
Step 2: PendSV Interrupt Context Switching
/**
* @brief PendSV interrupt handler (ARM Cortex-M series assembly code)
*/
xPortPendSVHandler:
/* 1. Save current task's CPU registers to task stack */
mrs r0, psp ; Get current task stack pointer (PSP)
ldr r3, =pxCurrentTCB ; Get current TCB address
ldr r2, [r3] ; Load current TCB pointer
stmdb r0!, {r4-r11} ; Save registers R4-R11 to stack
str r0, [r2] ; Save new stack pointer to TCB
/* 2. Call C language task scheduler */
push {r3, r14} ; Protect registers
cpsid i ; Disable interrupts
bl vTaskSwitchContext ; Call task scheduler
cpsie i ; Enable interrupts
pop {r2, r3} ; r2=new TCB address, r3=return address
/* 3. Restore new task's context */
ldr r1, [r2] ; Get new task TCB
ldr r0, [r1] ; Get new task's stack pointer
ldmia r0!, {r4-r11} ; Restore registers R4-R11 from stack
msr psp, r0 ; Set new stack pointer
bx r3 ; Return, continue executing new task
Step 3: Task Scheduler Selects Next Task
/**
* @brief Task switching context function
*/
void vTaskSwitchContext( void )
{
if( uxSchedulerSuspended != ( UBaseType_t ) 0U )
{
/* Scheduler is suspended, task switching not allowed */
xYieldPendings[ 0 ] = pdTRUE;
}
else
{
/* Record task run time statistics */
#if ( configGENERATE_RUN_TIME_STATS == 1 )
{
ulTotalRunTime[ 0 ] = portGET_RUN_TIME_COUNTER_VALUE();
if( ulTotalRunTime[ 0 ] > ulTaskSwitchedInTime[ 0 ] )
{
pxCurrentTCB->ulRunTimeCounter +=
( ulTotalRunTime[ 0 ] - ulTaskSwitchedInTime[ 0 ] );
}
ulTaskSwitchedInTime[ 0 ] = ulTotalRunTime[ 0 ];
}
#endif
/* Check for stack overflow */
taskCHECK_FOR_STACK_OVERFLOW();
/* Select the highest priority ready task */
taskSELECT_HIGHEST_PRIORITY_TASK();
/* Platform-specific task switch post-processing */
portTASK_SWITCH_HOOK( pxCurrentTCB );
}
}
4. Task Scheduling Algorithms
4.1 General Algorithm vs Hardware Optimized Algorithm
| Algorithm Type | Time Complexity | Applicable Platforms | Pros and Cons |
|---|---|---|---|
| General Algorithm | O(n) | All platforms | Good compatibility, but slower |
| Hardware Optimized | O(1) | ARM supporting CLZ instruction | Extremely fast, hardware accelerated |
4.2 General Task Selection Algorithm
/**
* @brief General task selection algorithm (linear search)
*/
#define taskSELECT_HIGHEST_PRIORITY_TASK() \
do { \
UBaseType_t uxTopPriority = uxTopReadyPriority; \
\
/* Find the highest priority queue with ready tasks */ \
while( listLIST_IS_EMPTY( &( pxReadyTasksLists[ uxTopPriority ] ) ) != pdFALSE ) \
{ \
configASSERT( uxTopPriority ); \
--uxTopPriority; \
} \
\
/* Select the next task from the task list of that priority (time slice round-robin) */ \
listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB, &( pxReadyTasksLists[ uxTopPriority ] ) ); \
uxTopReadyPriority = uxTopPriority; \
} while( 0 )
4.3 Hardware Optimized Version (O(1) Time Complexity)
/**
* @brief Hardware optimized task selection algorithm
*/
#if ( configUSE_PORT_OPTIMISED_TASK_SELECTION == 1 )
/* Bit manipulation macros */
#define portRECORD_READY_PRIORITY( uxPriority, uxReadyPriorities ) \
( uxReadyPriorities ) |= ( 1UL << ( uxPriority ) )
#define portRESET_READY_PRIORITY( uxPriority, uxReadyPriorities ) \
( uxReadyPriorities ) &= ~( 1UL << ( uxPriority ) )
/* Use CLZ instruction to quickly find the highest priority */
#define portGET_HIGHEST_PRIORITY( uxTopPriority, uxReadyPriorities ) \
uxTopPriority = ( 31UL - ( ( uint32_t ) __CLZ( ( uxReadyPriorities ) ) ) )
#endif /* configUSE_PORT_OPTIMISED_TASK_SELECTION */
4.4 Working Principle of CLZ Instruction
/**
* @brief Example of CLZ instruction
* CLZ = Count Leading Zeros
*/
// Example: Assume uxReadyPriorities = 0x00000110
// (binary: 00000000 00000000 00000001 00010000)
// CLZ(0x00000110) = 28 (28 leading zeros)
// Highest priority = 31 - 28 = 3
uint32_t uxReadyPriorities = 0x00000110; // Tasks of priority 0 and 8 are ready
uint32_t uxTopPriority = 31 - __CLZ(uxReadyPriorities); // Result: uxTopPriority = 8
5. Multitasking State Management
5.1 Core Structure of Task Control Block (TCB)
/**
* @brief Task Control Block structure definition (simplified version)
*/
typedef struct tskTaskControlBlock
{
volatile StackType_t *pxTopOfStack; /* Stack top pointer - must be the first member */
ListItem_t xStateListItem; /* State list item */
ListItem_t xEventListItem; /* Event list item */
UBaseType_t uxPriority; /* Task priority */
StackType_t *pxStack; /* Stack bottom pointer */
char pcTaskName[ configMAX_TASK_NAME_LEN ]; /* Task name */
#if ( configGENERATE_RUN_TIME_STATS == 1 )
configRUN_TIME_COUNTER_TYPE ulRunTimeCounter; /* Run time counter */
#endif
#if ( configUSE_TASK_NOTIFICATIONS == 1 )
volatile uint32_t ulNotifiedValue[ configTASK_NOTIFICATION_ARRAY_ENTRIES ];
volatile uint8_t ucNotifyState[ configTASK_NOTIFICATION_ARRAY_ENTRIES ];
#endif
} tskTCB;
typedef tskTCB TCB_t;
5.2 Task State Definitions
/**
* @brief Task state enumeration
*/
typedef enum
{
eRunning = 0, /* Running state - task is executing on CPU */
eReady, /* Ready state - task can run, waiting for scheduling */
eBlocked, /* Blocked state - task is waiting for an event or delay */
eSuspended, /* Suspended state - task is explicitly suspended */
eDeleted, /* Deleted state - task has been deleted */
eInvalid /* Invalid state */
} eTaskState;
5.3 Task List Management
/**
* @brief Task list definition
*/
/* Ready task list - grouped by priority */
PRIVILEGED_DATA static List_t pxReadyTasksLists[ configMAX_PRIORITIES ];
/* Delayed task lists */
PRIVILEGED_DATA static List_t xDelayedTaskList1;
PRIVILEGED_DATA static List_t xDelayedTaskList2;
PRIVILEGED_DATA static List_t * volatile pxDelayedTaskList;
PRIVILEGED_DATA static List_t * volatile pxOverflowDelayedTaskList;
/* Suspended task list */
#if ( INCLUDE_vTaskSuspend == 1 )
PRIVILEGED_DATA static List_t xSuspendedTaskList;
#endif
/* Current TCB pointer */
#if ( configNUMBER_OF_CORES == 1 )
PRIVILEGED_DATA TCB_t * volatile pxCurrentTCB = NULL;
#else
PRIVILEGED_DATA TCB_t * volatile pxCurrentTCBs[ configNUMBER_OF_CORES ] = { NULL };
#endif