FreeRTOS Scheduler

An RTOS embedded application is structured of independent tasks, each one with its own context with no dependency on other tasks. Just a task can be executed at any point in time. The FreeRTOS scheduler is responsible for managing task execution in an embedded system by determining which task should run at any given moment based on their priority, states, and scheduling policy.

By default, FreeRTOS uses a fixed-priority preemptive scheduling policy, with round-robin time-slicing of equal-priority tasks:

  • Fixed priority means that all tasks are assigned a specific priority level and will retain that priority throughout their execution. The scheduler ensures that tasks are executed based on this fixed priority, and it will not alter the priority of a task unless a task with a lower priority needs to be handled. In such cases, the scheduler may adjust the execution order, but the priority itself remains constant. This ensures that tasks with higher priority always take precedence. The scheduler uses priority inheritance to ensure the correct task is executed according to its fixed priority.
  • Preemptive scheduling means that tasks with higher priority are always given preference for execution. For instance, if a low-priority task is currently running and an ISR changes the state of a high-priority task to “ready”, the scheduler will immediately stop the low-priority task and execute the high-priority task. The scheduler will continue executing the high-priority task until it finishes, and then return to the previously interrupted low-priority task if no other higher-priority tasks are waiting to be executed.
  • Round-robin scheduling applies when multiple tasks have the same priority. In this case, these tasks take turns to enter in the “running” state. Each task gets a proportional amount of CPU time, allowing all tasks at the same priority level to be executed in rotation without a task blocked in the running satate and consuming all the CPU time.
  • Time-sliced scheduling is a specific type of round-robin scheduling where the scheduler switches between tasks of the same priority at each system tick. This means that the CPU time is distributed evenly between tasks, with the scheduler ensuring that all tasks are executed for a certain time slice before moving on to the next task in line.

Scheduler manages the task execution according to the state of each task. The task contains a parameter that indicates the current state of the task, this state indicates to the scheduler if need to run a task, if there are running, stopped or paused. Mainly the task contains 4 states. Ready, Running, Blocked, and suspended.

The scheduler always needs to execute at least one task, when there isn't a task running then the system automatically creates the Idle task with the lowest priority this means that the Idle task just will run when there are no tasks in “Ready“ or “Running“ states, ensuring that this task executes when the system is not running a crucial task. The main purpose is to free memory when the system deletes a kernel object. It also can be used to enter in low-power modes to save energy when the system is in idle state.

Take a look at the Task section, which explains in more detail the task state and idle task.

Memory management

The RAM memory in most microcontrollers are divided in three sections, static, stack, and heap.

  • The static memory is used to store the global variables and variables defined as static, these variables will retain their value at any time during execution.
  • Stack memory is used for automatic allocations of variables, storing all the variables created during the execution of the function and deleted when the function ends. Efficient for managing short-lived variables and function call management.
  • Heap memory used for dynamic memory allocation, the programmer needs to allocate and deallocate variables when consider is necessary. This section plays a crucial role in memory management, ensuring the efficiency of the RAM.

To make FreeRTOS as easy to use as possible, the kernel objects are not statically allocated in run-time. Objects are allocated dynamically using the heap space in memory. FreeRTOS uses RAM for kernel objects created and frees RAM each time these objects are deleted.

The RTOS kernel needs RAM each time a task, queue, mutex, semaphore, timer, or event is created, the RAM can automatically be dynamically allocated from the FreeRTOS API functions that use internally similar functions from the standard C library malloc(), and free(). These standard functions are not thread-safe and are not deterministic, the time taken can differ from call to call.

To get around this problem, FreeRTOS keeps the memory allocation API in its portable layer. The portable layer is outside of the source files that implement the core RTOS functionality, allowing an application-specific implementation appropriate for the real-time system being developed to be provided. When the RTOS kernel requires RAM, instead of calling malloc(), it instead calls pvPortMalloc(). When RAM is being freed, instead of calling free(), the RTOS kernel calls vPortFree().

When a task is created, the RTOS systems allocate it in the heap memory section, one part of the allocated memory is the TCB (Task Control Block) which contains all the info about the task created, the other section is reserved as a local stack that is similar to the global stack but is reserved just for the Task.

The local variables created in a function task are stored in the task’s local stack memory. It is important to calculate the predicted stack usage to set the appropriate parameter in the task creation function.

FreeRTOS allows the creation of statics objects, whether it is preferable to use static or dynamic memory allocation is dependent on the application, and the preference of the code writer.

FreeRTOS allows the creation of static tasks, which allocate all the tasks and their TCB (Task Control Block) directly in stack memory instead of heap memory. This is useful for systems with limited heap memory or for applications that require deterministic memory allocation, leading to more predictable and stable system behavior. Others objects as software timers, queues, semaphores, and mutex, can be created using the Stack section.

System Tick

The heartbeat of a FreeRTOS system is called the system tick. FreeRTOS configures the system to generate a periodic tick interrupt, known as the tick rate. The user can configure the tick interrupt frequency, which is typically in the millisecond range. This interval is defined by the “configTICK_RATE_HZ“ macro in the FreeRTOSConfig.h file.

When a task enters blocked mode, it specifies the maximum time it will wait to be “woken up.” The FreeRTOS Kernel measures this time using a tick count variable. Each time the tick ISR executes, it increments the tick count value. This allows the kernel to measure time with a resolution determined by the timer interrupt frequency.

Each time the tick count is incremented, the real-time kernel must check if it is time to unblock or wake a task. If a task is woken or unblocked during the tick ISR and has a higher priority than the interrupted task, the tick ISR should switch to the newly woken/unblocked task. This effectively means interrupting one task but returning to another.

When the SysTick timer generates an interrupt, the FreeRTOS tick handler (xPortSysTickHandler) is called. This handler performs several critical functions:

void xPortSysTickHandler( void )
{
    SEGGER_SYSVIEW_TickCnt++;                       /* increments the tick counter */
    uint32_t ulPreviousMask;                        /* declares a variable to store the previous interrupt mask state */

    ulPreviousMask = portSET_INTERRUPT_MASK_FROM_ISR(); /* sets the interrupt mask to prevent other interrupts occur while this ISR is executing and stores the previous mask state */
    traceISR_ENTER();                               /* marking the entry point of the ISR */
    {
        /* Increment the RTOS tick. */
        if( xTaskIncrementTick() != pdFALSE )       /* If the tick increment results in a context switch being required (a higher priority task is ready to run), 
                                                       the function returns pdTRUE */
        {
            traceISR_EXIT_TO_SCHEDULER();           /* If a context switch is needed, this trace macro marks the exit point of the ISR to the scheduler. */
            /* Pend a context switch. */
            portNVIC_INT_CTRL_REG = portNVIC_PENDSVSET_BIT;   /* Set a bit in the NVIC to leave a context switch pending */
        }
        else                                        /* If no context switch is needed */
        {
            traceISR_EXIT();                        /* macro marks the exit point of the ISR */
        }
    }
    portCLEAR_INTERRUPT_MASK_FROM_ISR( ulPreviousMask );  /* restores the previous interrupt mask state, allowing interrupts to occur again */
}

Systick Functionality

Observe the image, suppose that 2 tasks are created with the same priority. At T0 the Idle task is running waiting for a task to be in the ready state. At T1 When the systick interrupt is triggered, both tasks are now in a ready state, and the systick calls the function xPortSysTickHandler which is in charge of decide if the scheduler needs to switch the context, in this case, it is needed and the function sets the PendSV register to indicate to the NVIC to change the context. At T2 observe that Task1 is executed, At T3 when the systick executes again, will notice that there are other task ready to execute with the same priority, and then the function calls to the NVIC to switch the context again. At T4 Task 2 starts running to finish at T5.

Change of context

The NVIC (Nested Vectored Interrupt Controller) manages interrupts and system exceptions in Cortex-M processors. Each interrupt has its own priority, determining the order in which it is executed by the NVIC.

To handle the change of context, it is important to understand that PendSV is a system exception of the processor, that indicates to the NVIC that there is a pending context switch. This register is typically used with RTOS systems to change context when needed. To set PendSV, you need to set bit 28 of the NVIC to 1b1, notifying to the NVIC that a change context is pending. PendSV usually has a low priority, so the processor will first execute any pending interrupts with higher priority and then process the system event.

The NVIC constantly monitors the priorities of all pending interrupts. If the PendSV interrupt has a higher priority than the currently running task or interrupt, the NVIC will call the xPortPendSVHandler function responsible for saving data of the current task into the stack to be executed at the same point where it was interrupted. This mechanism allows the RTOS to efficiently manage task timing, ensuring that high-priority tasks receive CPU time.

To understand the context switch process, take a look at the xPortPendSVHandler function in the port.c file of the FreeRTOS source code.

void xPortPendSVHandler( void )
{
    /* This is a naked function. */

    __asm volatile
    (
        "	.syntax unified						\n"
        "	mrs r0, psp							\n"
        "										\n"
        "	ldr	r3, pxCurrentTCBConst			\n"/* Get the location of the current TCB. */
        "	ldr	r2, [r3]						\n"
        "										\n"
        "	subs r0, r0, #32					\n"/* Make space for the remaining low registers. */
        "	str r0, [r2]						\n"/* Save the new top of stack. */
        "	stmia r0!, {r4-r7}					\n"/* Store the low registers that are not saved automatically. */
        " 	mov r4, r8							\n"/* Store the high registers. */
        " 	mov r5, r9							\n"
        " 	mov r6, r10							\n"
        " 	mov r7, r11							\n"
        " 	stmia r0!, {r4-r7}					\n"
        "										\n"
        "	push {r3, r14}						\n"
        "	cpsid i								\n"/* Disable all the interrupts */
        "	bl vTaskSwitchContext				\n"/* Change context */
        "	cpsie i								\n"/* Enable all the interrupts */
        "	pop {r2, r3}						\n"/* lr goes in r3. r2 now holds tcb pointer. */
        "										\n"
        "	ldr r1, [r2]						\n"
        "	ldr r0, [r1]						\n"/* The first item in pxCurrentTCB is the task top of stack. */
        "	adds r0, r0, #16					\n"/* Move to the high registers. */
        "	ldmia r0!, {r4-r7}					\n"/* Pop the high registers. */
        " 	mov r8, r4							\n"
        " 	mov r9, r5							\n"
        " 	mov r10, r6							\n"
        " 	mov r11, r7							\n"
        "										\n"
        "	msr psp, r0							\n"/* Remember the new top of stack for the task. */
        "										\n"
        "	subs r0, r0, #32					\n"/* Go back for the low registers that are not automatically restored. */
        " 	ldmia r0!, {r4-r7}					\n"/* Pop low registers.  */
        "										\n"
        "	bx r3								\n"/*Return to the restored task*/
        "										\n"
        "	.align 4							\n"
        "pxCurrentTCBConst: .word pxCurrentTCB	  "
    );
}

The function is written using the assembly code of the ARM Cortex M. Firstly the function gets the address of the task control block of the task to be interrupted (line 10 - 11). Then, it clears the data from register r0, which contains the stack pointer, to free up space for new data (line 13). After the function stores the low and high ranges of the registers to ensure the full state of the processor’s registers is saved (lines 14-20).

At this point, it is possible to change the context. First, the function disables the interrupts and calls the function vTaskSwitchContext which changes the stack pointer to the new task to be executed. Finally, when the functions end enable the interrupts (line 22-25).

When the task need to be restored, first recover the necessary values from the TCB and then modify the stack pointer to point the high range registers and next the low range registers (line 26-40). Finally, scheduler returns to the restored task using r3 which contains the return address.

In FreeRTOS some functions allows to switch the context to another task, some of the most important are:

  • taskYield() this function forces a switch context, allowing to the scheduler choose another task to be executed.
  • vTaskDelay() suspends the current task for a specific number of ticks, this allows to execute another task.
  • xTaskResumeFromISR() Resume a task from an ISR, that can cause a change of context if this task has a high priority.

 

Two interrupts are needed for a context switch, the SysTick, which has a high priority, and the PendSV, which has a low priority in the NVIC. This setup ensures efficient and predictable task management in real-time operating systems. SysTick maintains system timing and scheduling. The PendSV, used for context switching, should have a lower priority to prevent unnecessary preemption, ensuring that higher-priority interrupts or tasks execute first.

Interrupt Handling

When an interrupt is generated, the RTOS system pauses the current execution and runs the ISR function. This interruption is executed asynchronously, meaning there is no need to wait for the systick handler interrupt to be executed. When the NVIC receives the signal of an interrupt or event, the process of context saving occurs automatically by the logic of the processor, the code is not visible as the context switch of the FreeRTOS port of PendSV exception. After all the register of the current process is saved, then the NVIC executes the corresponding ISR function.

When working with hardware interrupts in an RTOS, several aspects need to be considered:

An ISR should never block itself. Avoid calling blocking functions or functions that wait for resources. An ISR must execute as quickly as possible and cannot wait for resources.
An ISR must be as short as possible and avoid complex processes. The time spent inside an ISR is critical; if the ISR takes unnecessary time, it can delay the execution of other important interrupts or tasks.
After the ISR completes, the processor restores the saved context from the stack and resumes the interrupted process.

Deferred Interrupt Handling

A Deferred Interrupt refers to a mechanism where a task is triggered by a standard ISR (Interrupt Service Routine). The task is unblocked when the ISR executes, and the interrupt has a mechanism to trigger the task after the ISR completes its function. The deferred task should have a high priority to ensure it executes immediately after the interrupt routine finishes. This guarantees that all necessary processing is done continuously and without gaps, just as if all the processing had been performed within the ISR itself.

Deferred Interrupt Functionality

When to use it?

To avoid system instability and ensure that other high-priority tasks or interrupts can execute, deferred interrupts are used. This approach prevents the system from spending excessive time in ISRs (Interrupt Service Routines), which can delay the execution of application tasks and potentially cause system instability.

Deferred interrupts are particularly useful when an interrupt needs to perform prolonged operations or actions that are not deterministic.

For example, if an interrupt requires complex data processing or communication with external devices, it can be deferred to a task that runs immediately after the ISR completes. This ensures that the system remains responsive and that high-priority tasks are not delayed by lengthy ISR execution.

To execute the deferred task after the ISR, the interrupt function needs to be configured to change the context to the deferred task when the interrupt ends. This ensures that the logic of the interrupt is executed immediately after the ISR execution by the task unblocked.

Let's take an ISR callback of the binary semaphore example as an illustration:

void WWDG_IRQHandler( void )                                /* Callback of the interrupt */
{ 
    /* Interruption Vector */
    BaseType_t xTaskWoken = pdFALSE;                        
    xSemaphoreGiveFromISR( xBinSemaphore, &xTaskWoken );    /* Release semaphore */
    portEND_SWITCHING_ISR(xTaskWoken);                      /* Change context if xTaskWoken=pdTRUE */
}

Let's focus on the function portEND_SWITCHING_ISR(xTaskWoken), and its parameter. The function indicates to the system to change context and execute the task with high priority after the ISR interrupt, if the process of the function xSemaphoreGiveFromISR to give the semaphore is successfully done, then the xTaskWoken parameter will change to pdTRUE that indicates the system will execute the deferred task that will have the high priority. On the other hand, if the ISR cannot give the semaphore, then the xTaskWoken parameter maintains the pdFALSE value and the system will return to the task interrupted by the ISR.

The disadvantage of using deferred interruptions is the greater consumption of resources, which implies that more tasks than necessary are created for each interruption, can lead to greater consumption of system resources such as memory and CPU time.

While the deferred interrupts help to maintain the ISR function as short as possible they can introduce latency in handling the actual interrupt, this because the deferred process is handled by a lower priority task, this implies that the task can not run immediately if there are another task with a high priority of if a new interruption is generated after the task can run.

Task Control Block (TCB)

In FreeRTOS, the Task Control Block (TCB) is a crucial data structure used to store and manage the information of every task created. Each task has its own TCB, which contains all the information the kernel needs to manage the task. For example, the TCB stores the variables used inside the task, the task’s priority, and an ID to identify it among other tasks. Additionally, the TCB contains pointers to the task’s stack and state information, such as the task’s context. This context includes the CPU registers, stack pointer, and program counter, which are used to switch to another task stopping the current execution, and later used to restore the execution of the task from the interrupted point.

The TCB is defined in tasks.c, here are the most common parameters of TCB structure :

/*
 * Task control block.  A task control block (TCB) is allocated for each task,
 * and stores task state information, including a pointer to the task's context
 * (the task's run time environment, including register values)
 */
typedef struct tskTaskControlBlock              /* The old naming convention is used to prevent breaking kernel aware debuggers. */
{
    volatile StackType_t * pxTopOfStack;        /*< Points to the location of the last item placed on the tasks stack.  THIS MUST BE THE FIRST MEMBER OF THE TCB STRUCT. */

    ListItem_t xStateListItem;                  /*< The list that the state list item of a task is reference from denotes the state of that task (Ready, Blocked, Suspended ). */
    ListItem_t xEventListItem;                  /*< Used to reference a task from an event list. */
    UBaseType_t uxPriority;                     /*< The priority of the task.  0 is the lowest priority. */
    StackType_t * pxStack;                      /*< Points to the start of the stack. */
    char pcTaskName[ configMAX_TASK_NAME_LEN ]; /*< Descriptive name given to the task when created.  Facilitates debugging only. */ /*lint !e971 Unqualified char types are allowed for strings and single characters only. */

    #if ( ( portSTACK_GROWTH > 0 ) || ( configRECORD_STACK_HIGH_ADDRESS == 1 ) )
        StackType_t * pxEndOfStack;             /*< Points to the highest valid address for the stack. */
    #endif
    #if ( configUSE_MUTEXES == 1 )
        UBaseType_t uxBasePriority;             /*< The priority last assigned to the task - used by the priority inheritance mechanism. */
    #endif

} tskTCB;
  • Stack Management: The Task Control Block (TCB) stores the stack’s start address in pxStack, and the current top of the stack in pxTopOfStack, also stores a pointer to the end of the stack inpxEndOfStack to check for stack overflow if it grows up to the higher addresses. If the stacks grow down to the lower addresses then the stack overflow is compared with the current top stack and the start memory pxStack.
  • Task Priority: The TCB holds the task’s initial priority in uxPriority and uxBasePriority. Tasks are assigned a priority at creation, which can be changed. If priority inheritance then it uses uxBasePriority to remember the original priority while the task is temporarily elevated to the "inherited" priority.
  • Scheduling Lists: Each task has two list items (xStateListItem and xEventListItem) for scheduling. Instead of pointing directly to the TCB, FreeRTOS uses these list items to manage tasks more efficiently.
  • Task States: Tasks can be in one of four states: running, ready to run, suspended, or blocked. FreeRTOS tracks task states by placing tasks in corresponding lists. As a task changes from one state to another, FreeRTOS simply moves it from one list to another, as their state changes.