Task Scheduling in FreeRTOS

typedef struct tskTaskControlBlock {    volatile StackType_t * pxTopOfStack; // Stack top pointer    ...    ListItem_t xStateListItem; // Task state    UBaseType_t uxPriority; // Task priority    StackType_t * pxStack; // Stack starting address    char pcTaskName[ configMAX_TASK_NAME_LEN ]; // Task name    ...} tskTCB;

typedef struct tskTaskControlBlock * TaskHandle_t;

StackType_t *pxPortInitialiseStack( StackType_t *pxTopOfStack, TaskFunction_t pxCode, void *pvParameters ){  ...  *pxTopOfStack = ( StackType_t ) pxCode + portINSTRUCTION_SIZE;      pxTopOfStack--;  ...}

• Running

When a task is actively executing, it is said to be in the running state. The task is currently using the processor. If the RTOS runs on a single-core processor, then at any given time, only one task can be in the running state.

• Ready

A ready task is one that is capable of executing (it is not blocked or suspended), but is currently not executing because other tasks of equal or higher priority are already in the running state.

• Blocked

If a task is currently waiting for a delay or an external event, it is considered to be in the blocked state. For example, if a task calls vTaskDelay(), it will be blocked (placed in the blocked state) until the delay ends. Tasks can also be blocked waiting for queues, semaphores, event groups, notifications, or semaphore events. A task in the blocked state typically has a “timeout” period, after which it will be unblocked, even if the event it was waiting for has not occurred.

A task in the “blocked” state does not occupy processor time and cannot be selected to enter the running state.

• Suspended

Similar to a task in the “blocked” state, a task in the suspended state cannot be selected to enter the running state, but a task in the suspended state does not have a timeout exit mechanism. Instead, a task will only enter or exit the suspended state when explicitly commanded through vTaskSuspend() and xTaskResume() API calls.

The code definition of task states is as follows, and the current state of a task can be known through the function eTaskGetState().

eTaskState eTaskGetState( TaskHandle_t xTask );/* Task states returned by eTaskGetState. */typedef enum{    eRunning = 0, /* A task is querying the state of itself, so must be running. */    eReady,       /* The task being queried is in a ready or pending ready list. */    eBlocked,     /* The task being queried is in the Blocked state. */    eSuspended,   /* The task being queried is in the Suspended state, or is in the Blocked state with an infinite time out. */    eDeleted,     /* The task being queried has been deleted, but its TCB has not yet been freed. */    eInvalid      /* Used as an 'invalid state' value. */} eTaskState;

However, the TCB does not define such an enum type variable to track the task’s state; instead, it adopts a more flexible method: using ListItem_t xStateListItem; to indirectly represent the task’s state.

xStateListItem indicates which task state list the task is placed under. FreeRTOS maintains the following lists and defines a global pointer to the current task’s TCB.

/* List of tasks in the ready state */static List_t pxReadyTasksLists[ configMAX_PRIORITIES ];/* List of tasks in the blocked state; the reason for defining two lists is not discussed here */static List_t xDelayedTaskList1; static List_t xDelayedTaskList2; /* List of tasks in suspended state */static List_t xSuspendedTaskList; /* Tasks that are ready during the scheduler's suspension will be moved to the ready list when the scheduler resumes.*/static List_t xPendingReadyList; /* Deleted tasks, but their memory has not yet been released.*/static List_t xTasksWaitingTermination;/* Pointer to the current task's TCB */TCB_t * volatile pxCurrentTCB = NULL;

The logic to determine the current task’s state using eTaskGetState is as follows:

1. Compare the handle of the task being queried (which is the TCB pointer) with pxCurrentTCB. If they are equal, it indicates that the task is the currently running task, so its state is eRunning.

if( pxTCB == pxCurrentTCB ){    /* The task calling this function is querying its own state. */    eReturn = eRunning;}

2. If the task being queried is in the blocked list, then its state is eBlocked.

if( ( pxStateList == pxDelayedList ) || ( pxStateList == pxOverflowedDelayedList ) ){    /* The task being queried is referenced from one of the Blocked     * lists. */    eReturn = eBlocked;}

3. If the task being queried is in the suspended list, more information is needed to determine: if the task does not appear in any event list and is not waiting for a notification, it is truly suspended (eSuspended); otherwise, it is blocked (eBlocked). Event lists and notifications seem to be related to events and notifications between tasks, which will not be explored further.

4. If the task being queried is in xTasksWaitingTermination, then its state is eDeleted.

if( ( pxStateList == &xTasksWaitingTermination ) || ( pxStateList == NULL ) ){    /* The task being queried is referenced from the deleted     * tasks list, or it is not referenced from any lists at     * all. */    eReturn = eDeleted;}

5. If none of the above conditions are met, then the task must be in the ready state (eReady).

else{    /* If the task is not in any other state, it must be in the     * Ready (including pending ready) state. */    eReturn = eReady;}

Task Priority Design in FreeRTOS

Each task is assigned a priority ranging from 0 to (configMAX_PRIORITIES – 1), where configMAX_PRIORITIES is defined in FreeRTOSConfig.h.

A lower priority number indicates a lower priority task. The idle task has a priority of zero (tskIDLE_PRIORITY).

The FreeRTOS scheduler ensures that high-priority tasks that are in the ready or running state receive processor (CPU) time before lower-priority tasks that are also in the ready state. In other words, the task that is placed in the running state is always the highest-priority runnable task.

Multiple tasks can share the same priority. If configUSE_TIME_SLICING is set to 1, ready tasks of the same priority will share available processing time using a time-slicing round-robin scheduling scheme.

Task Scheduling Process in FreeRTOS

Task scheduling essentially involves two things:

• Selecting the task to run

• Task switching

# Selecting the Task

How do we select the task to run? Do you remember the ready task list mentioned earlier?

/* List of tasks in the ready state */static List_t pxReadyTasksLists[ configMAX_PRIORITIES ];

configMAX_PRIORITIES indicates the maximum priority of tasks, and each priority corresponds to a task list:

As mentioned in the previous section on task priority design, the task placed in the running state is always the highest-priority runnable task. Therefore, the process of selecting a task is to find the highest-priority task from the ready task list, as shown in the following macro:

#define taskSELECT_HIGHEST_PRIORITY_TASK()                                \
{                                                                         \
    UBaseType_t uxTopPriority = uxTopReadyPriority;                       \
                                                                          \
    /* From high priority to low priority, find the task list that has a task */      \
    while( listLIST_IS_EMPTY( &( pxReadyTasksLists[ uxTopPriority ] ) ) ) \
    {                                                                     \
        configASSERT( uxTopPriority );                                    \
        --uxTopPriority;                                                  \
    }                                                                     \
                                                                          \
    /* Get the task from the task list and point the current task's TCB pointer to it */                    \
    listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB, &( pxReadyTasksLists[ uxTopPriority ] ) ); \
    uxTopReadyPriority = uxTopPriority;                                                   \
} /* taskSELECT_HIGHEST_PRIORITY_TASK */

# Task Switching

What is the essence of task switching? It is allowing the CPU to leave the current task processing function and execute the new task’s processing function; at the same time, it needs to consider that at some later point, when switching back to the old task (after the old task is rescheduled), the old task can resume its state and continue execution.

The specific code for task switching is related to the CPU architecture and may vary in implementation across different CPUs. Here, we take ARM7 as an example.

FreeRTOS\Source\portable\GCC\ARM7_AT91SAM7S\portISR.c

void vPortYieldProcessor( void ){  /* Within an IRQ ISR the link register has an offset from the true return  address, but an SWI ISR does not.  Add the offset manually so the same  ISR return code can be used in both cases. */  __asm volatile ( "ADD    LR, LR, #4" );
  /* Perform the context switch.  First save the context of the current task. */  portSAVE_CONTEXT();
  /* Find the highest priority task that is ready to run. */  vTaskSwitchContext();
  /* Restore the context of the new task. */  portRESTORE_CONTEXT();}

Preempting the CPU:

void vPreemptiveTick( void ){  /* Save the context of the current task. */  portSAVE_CONTEXT();
  /* Increment the tick count - this may wake a task. */  if( xTaskIncrementTick() != pdFALSE )  {    /* Find the highest priority task that is ready to run. */    vTaskSwitchContext();  }
  /* End the interrupt in the AIC. */  AT91C_BASE_AIC->AIC_EOICR = AT91C_BASE_PITC->PITC_PIVR;
  portRESTORE_CONTEXT();}

As can be seen, whether it is proactively yielding the CPU or preempting the CPU, the overall process of task switching is consistent and requires these three steps:

• portSAVE_CONTEXT() saves the context of the current task, as this task may be switched back later.

• vTaskSwitchContext calls taskSELECT_HIGHEST_PRIORITY_TASK() to select a new task.

• portRESTORE_CONTEXT() restores the context of the new task, which will continue running from where it was last interrupted.

Proactively yielding the CPU can be triggered by various blocking operations, such as calling the vTaskDelay function for a delay or waiting for a semaphore, etc.

Preempting the CPU, in this example, is triggered by the chip’s Timer interrupt.

static void prvSetupTimerInterrupt( void ){    ...    AT91F_AIC_ConfigureIt( AT91C_ID_SYS, AT91C_AIC_PRIOR_HIGHEST, portINT_LEVEL_SENSITIVE,         ( void (*)(void) ) vPreemptiveTick );    ...}

# Why can restoring a task’s context switch to that task?

This can be understood by comparing it to interrupt handling. After an interrupt occurs, the response process is to save the context, handle the interrupt, and restore the context, so that it can correctly return to the interrupted position and continue executing. The task context is similar to the interrupt context.

The code for saving and restoring context is in the following file:

FreeRTOS\Source\portable\GCC\ARM7_AT91SAM7S\portmacro.h

The logic for saving the context is to save the return address of the current task, registers (R0-LR), SPSR to the current task’s stack and update the variable recording the stack top in the TCB.

  /* Push the return address of the current task onto the stack */            
"STMDB  R0!, {LR}                      
	"  
  /* Push registers from R0 to LR onto the stack */    
"STMDB  LR,{R0-LR}^                      
	"  
"NOP                            
	"  
"SUB  LR, LR, #60                      
	"  
                                    
  /* Push the SPSR register onto the stack */              
"MRS  R0, SPSR                      
	"  
"STMDB  LR!, {R0}                      
	"  
    /* Update the stack top record in the TCB (after the above operations, the stack top of the current task has changed) */            
"LDR  R0, =pxCurrentTCB                  
	"  
"LDR  R0, [R0]                      
	"  
"STR  LR, [R0]                      
	"  

The logic for restoring the context is the opposite of saving the context: first find the stack top of the task (the TCB has a variable recording the stack top), then restore the SPSR, registers (R0-LR), and the return address of the task from the stack. The last step is to assign the task’s return address to the PC register, completing the task switch.

# Where is the context of a newly created task?

If a task actively yields the CPU or is preempted by a higher-priority task during its execution, its context will be saved to its own stack. Later, if it is rescheduled to run, it will restore its context from the stack.

For a newly created task, where does its context come from when it runs for the first time? The answer lies in the task creation process.

When creating a task, a function is called to initialize the task’s stack, filling it with the information needed for context switching. The implementation of this function is related to the CPU architecture.

FreeRTOS\Source\portable\GCC\ARM7_AT91SAM7S\port.c
StackType_t *pxPortInitialiseStack( StackType_t *pxTopOfStack, TaskFunction_t pxCode, void *pvParameters ){StackType_t *pxOriginalTOS;
  pxOriginalTOS = pxTopOfStack;  pxTopOfStack--;
  *pxTopOfStack = ( StackType_t ) pxCode + portINSTRUCTION_SIZE;      pxTopOfStack--;
  *pxTopOfStack = ( StackType_t ) 0x00000000;  /* R14 */  pxTopOfStack--;    *pxTopOfStack = ( StackType_t ) pxOriginalTOS; /* Stack used when task starts goes in R13. */  pxTopOfStack--;  *pxTopOfStack = ( StackType_t ) 0x12121212;  /* R12 */  pxTopOfStack--;    *pxTopOfStack = ( StackType_t ) 0x11111111;  /* R11 */  pxTopOfStack--;    *pxTopOfStack = ( StackType_t ) 0x10101010;  /* R10 */  pxTopOfStack--;    *pxTopOfStack = ( StackType_t ) 0x09090909;  /* R9 */  pxTopOfStack--;    *pxTopOfStack = ( StackType_t ) 0x08080808;  /* R8 */  pxTopOfStack--;    *pxTopOfStack = ( StackType_t ) 0x07070707;  /* R7 */  pxTopOfStack--;    *pxTopOfStack = ( StackType_t ) 0x06060606;  /* R6 */  ...  ...