Skip to content

The scheduler

The scheduling of tasks

In FreeRTOS tasks are simply functions which return nothing (i.e. they return "void" in C) and which have a void pointer as the only parameter (a void pointer is a pointer to something. "Void" means that this something can be anything: a string, a number, a data structure, an arbitrary memory location). With this void pointer the user has the opportunity to give the task any parameters at start-up since an arbitrarily complex object can sit at the indicated memory location. Of course later we will see more possibilities of how to provide a RUNNING tasks with input data.

Often tasks are once created and then run forever. This means their implementation contains an infinite loop in which they perform their job.

The scheduler has to decide when which task in the system starts running. For this it provides several "scheduling algorithms" from which the user can choose.

States of tasks and Priorities and the Idle task

A task can be in one of three states

  • Running : The task is currently running. Only one task can be in this state for each processor core. Ready : The task is currently not running but is in the list of tasks which are ready to be selected by the scheduling algorithm.
  • Blocked : Tasks which are not ready to run but wait for some event to occur before they resume activity are in this state. Events which can move tasks back to the Ready state are task notification events, arrival of data in a message queue, semaphore events, or timer events. All of these will be discussed later but their names might give you an idea what they are doing.
  • Suspended : In this state a task cannot be elected for running. The only way to bring a task into this state is via a dedicated API call of FreeRTOS (i.e. a specific function of the FreeRTOS system has to be called). And the only way to get back to the Ready state is via another dedicated function call.

Every task has a priority attached to it. This priority is always used in the various scheduler algorithms to decide which task to move into the Running state next. In FreeRTOS always the task with the highest priority is chosen to be moved in the Running state (We see later how the various algorithms differ.) Priorities are numbers where low numbers have lower priorities than higher numbers. In FreeRTOS there must be always one task (per core) in the Running state. Since situations might occur that there is no user task in the Ready state it might happen that the scheduler has no task to choose for scheduling. For this reason there exists a so called "Idle" task provided by the FreeRTOS system which has priority 0 and is put into the Running states if no other user task is able to run. The "Idle" task is also performing some cleanup in the system. If an application is deleting tasks during its life time (often applications do NOT need this feature) then the idle tasks is cleaning up the memory resources which where blocked for this task. (I.e. the memory which was allocated to hold the information about the task is given back to the system and can be used for something else.) Hence it is important to design a program which is deleting tasks in a way that the idle task is getting some running time every now and then (in computer jargon you say: you must make sure to not starve the Idle task.)

The following figure summarizes the states and their possible transitions in a diagram:

State_Diagram

The idle tasks supports hooks which can be programmed by the user. In computer jargon a hook is a function which can be programmed by the user in case it is wanted. This function is executed every time something specific happens. In case of the idle task the hook is always executed when the idle task is put into the Running state. This can be useful to do things like measuring spare processing time or place processor in low power mode). Hooks must not block or suspend or take a long time to execute since the Idle task should never take a lot of CPU resources.

Prioritized Pre-emptive Scheduling with Time-Slicing

The probably most commonly used algorithm is called preemptive scheduling with time-slicing. To implement the "Time-Slicing" part of the algorithm (explained below) the scheduler divides the time into fixed size periods called "Ticks" (typically some 10ms. Slices shorter than 1ms should be avoided since then the CPU resources used to do the scheduling become significant in the system.(This is valid for the controllers available today i.e. in 2024)). There are three different situations in which the scheduler needs to decide which task to run:

  • When the running task is entering Blocked or Suspended state. This might happen any time during the execution of a task. The scheduler then chooses the highest priority task in Ready state to run next. If there are more than one task with the same priority the task which has not run for the longest period is chosen to run next.

  • When a Blocked task of higher priority than the running task is moved to the Ready state. This can happen due to an interrupt in the system which interrupts shortly the running task and creates and event which moves a Blocked task to Ready state. A typical scenario is a task which has put itself into the Blocked state to wait for data from some hardware Peripheral. If data arrives the hardware transfers the data into a dedicated memory (e.g. a FIFO: First in First Out memory. This is a memory which is written by the hardware and has to be read by the microcontroller on the other side.) of the microcontroller and then issues an interrupt to tell the system that new data needs to be processed (i.e. read out of the FIFO to avoid that the FIFO memory overflows when more data arrives).

  • At then end of each Tick (i.e. time-slice). When a task is running at the end of each time slice the scheduler looks at the list of tasks in the Ready state and chooses the one with the highest priority to move into the Running state (this of course can also be the same task which was running in the previous time-slice). If there are multiple tasks with equal priority in the Ready state and if that priority is the highest priority in the list of tasks ready to run, then the Scheduler chooses the tasks in a Round-Robin manner so that they are equally often selected to run. This mechanism is referred to as "Time-Slicing".

The fact that a running state can be interrupted any time when a higher priority task is moved to the Ready state is called pre-emptive scheduling.

This algorithm is chosen with the following two FreeRTOS parameters set to '1' in the configuration file:

configUSE_PREEMPTION 1 configUSE_TIME_SLICING 1

Prioritized Pre-emptive Scheduling without Time-Slicing

This algorithm is very similar to the algorithm described in the previous section the only difference being the absence of Time-Slicing. This means that a running task is only removed from the Running state if there is a higher priority task in the Ready state. This can lead to the scenario that two tasks which have equal priority get very different running times. Since this situation might be undesirable care has to be taken when tasks with the same priorities exist with this algorithm and this algorithm is considered an advanced feature which requires experience and care to master. The advantage of this algorithm might be much less task switching than in the previous algorithm.

This algorithm is chosen with the following two FreeRTOS parmeters set to '1':

configUSE_PREEMPTION   1
configUSE_TIME_SLICING 0

Tasks with identical priority might get largly different amount of CPU time.

Co-operative Scheduling

Finally there is the co-operative scheduling algorithm where tasks are never pre-empted. A new task is only chosen if the running tasks goes into the blocked state or if it gives up it's time slice by calling the function taskYield(). This algorithm is used with the following configuration parameters:

configUSE_PREEMPTION   0
configUSE_TIME_SLICING {don't care}