Introduction to multitasking and scheduling in Embedded systems

This will be a short introduction into multitasking in embedded systems.

First what is multitasking?

Multitasking is the ability to execute more than one task or processes in a fashion that is seemingly simultaneous. and note here that it is said seemingly simultaneous this means that it is not actually simultaneous and this is because in small to medium embedded systems we only use one processor and the processor can execute only one task at a time. So how can we execute multiple task while having one processor?

The answer is by dividing the CPU time between all the tasks we need to execute with a very high rate that it gives us humans the illusion that every thing is executing at the same time. Now we know what is multitasking but how can we actually do it in code? the answer to this is by using what is called a scheduler.

what is a scheduler?

A scheduler is a part of operating system that is responsible for selecting which task to be executed by the CPU next to ensure that each task meet it's deadline. But on what basis does the scheduler chooses next task to be executed? The scheduler chooses which task to be executed next based on the scheduler algorithm used in implementing the scheduler there are many algorithms used in scheduling and i will explain the most common and important ones.

scheduling algorithms

Most famous scheduling algorithms used in embedded systems are.

1-Clock driven algorithm

2-Round-Robin algorithm

3-Priority-driven algorithm

Now i will discuss how each algorithm work and the advantage of each one.

Clock driven algorithm

In the clock-driven scheduling, scheduling decisions are made at specific time instants, which are typically chosen before the system begins execution.It usually works for deterministic systems where tasks have hard deadlines and all task parameters are not changing during system operation.That time instants is usually called frames where major cycle of the algorithm consists of an integer number multiple of the frame size.to choose the right frame size we should follow three rules

1-when we select a frame size, it should be big enough to allow every task to complete its execution inside a frame

2-the chosen frame size should divide the major cycle size.

3-When we choose the frame size, we should also need to ensure that it allows every task instance to meet its deadline. This constraint imposes that there is at least one full frame between the arrival of a task instance and its deadline.

after following these rules we will have the right major cycle time and the right frame size which we could use to assign and schedule our tasks.

Round-Robin Algorithm

The round-robin approach is a time-sharing scheduling algorithm. In the round-robin scheduling, a time slice is assigned to each task in a circular order. Tasks are executed without priority. There is an FIFS (first-in-first-service) queue that stores all tasks in the ready state. Each time, the task at the head of the queue is removed from the queue and dispatched for execution. If the task is not finished within the assigned time slice, it is placed at the tail of the FIFS queue to wait for its next turn. The round-robin scheduling algorithm is simple to implement. It is fair to all tasks in using the processor.The major drawback is that it delays the completion of all tasks and may cause tasks to miss their deadlines. It is not a good option for scheduling tasks with hard deadlines.

Priority-Driven Algorithm

In priority driven algorithm scheduling decision is made when a new task instance is released or when a task instance is completed.it is considered online scheduling where scheduling is done at run time. Priority is assigned to each task and always task with higher priority that is ready is allowed to run and have the CPU for itself.

Priority assignment for tasks in this algorithm is divided into two types

1-fixed-priority algorithm

2-Dynamic-priority algorithm

Fixed-priority algorithm

As the name implies in fixes priority algorithm each task is given a priority which is fixed that's mean that task's priority doesn't change during run time. the most famous algorithm used in fixed priority scheduling is rate monotonic algorithm.

Rate monotonic algorithm

In rate monotonic algorithm each task is assigned a priority based on it's period where task with less period is assigned a higher priority.Scheduling periodic tasks based on the rate monotonic algorithm is relatively easy: when a new task instance is released, if the processor is idle, it executes the task; if the processor is executing another task, then the scheduler compares their priorities. If the new task’s priority is higher, then it preempts the task in execution and executes on the processor.The preempted task is placed in the queue of ready tasks.

Dynamic priority driven algorithm

In dynamic priority driven algorithm each task's priority could change during runtime based on a certain task parameter one of the algorithm used in dynamic priority algorithm is Earliest deadline first algorithm(EDF).

Earliest deadline-first algorithm(EDF)

A scheduler following the (EDF) algorithm always schedules the task whose absolute deadline is the earliest for execution. A task’s priority is not fixed. It is decided at runtime based on how close it is to its absolute deadline.

Scheduler types

According to the used algorithm in scheduling we could divide schedulers into two main types co-operative and preemptive schedulers

co-operative scheduler

This type of scheduler where tasks cooperate with each other to give each other the CPU control this is done when a task either run to it's completion or when the task time slice finishes. this type of scheduler use clock-driven algorithm and round-robin algorithm for scheduling tasks

Advantage of co-operative scheduler

since in this type of scheduling each task execution is predictable at any instance the system is said to be more deterministic,reliable and safe so that is why this type of scheduling is used with time-triggered architecture in safety critical applications.

preemptive schedulers

In this type of scheduler tasks is allowed to preempt each other based on their priority where higher priority task that is ready is always allowed to run and preempt the execution of the running task. algorithms used in this type is fixed-priority driven and dynamic-priority driven.

Advantage of preemptive schedulers

Preemptive schedulers will increase the system response and give a better multitasking illusion for the user but this comes with a trade off with other parameters as we will see in the disadvantages of the preemptive scheduler.

Disadvantage of preemptive schedulers

since each task could preempt the other context switching should occur before the new task is loaded by context switch we mean saving the task's used CPU registers inside the tasks stack so when it comes back for execution there will be no faults that type of context switching adds time overhead while using preemptive scheduler. now we know what is multitasking and how can we achieve them using schedulers and we know schedulers types and algorithms but we haven't answered a question yet which is when the scheduler itself is called?

Scheduler calling

scheduler is normally called from two places in the code and they are interrupt service routine (ISR) and the task it self this is know as interrupt level scheduling and task level scheduling

Interrupt level scheduling

In interrupt level scheduling the scheduler is called at the end of execution of the ISR and so instead of returning from ISR back to where the program where interrupted the scheduler is called instead to see which task to load.

Task level scheduling

In task level scheduling scheduler is called from inside the task based on type of scheduler used if we are using a cooperative without time slicing or preemptive without time slicing each task has to call the scheduler by itself and the end of it's execution in case of preemptive with time slicing at the end of each task's time slice an interrupt fires at which the scheduler is called from inside it.