RTOS Scheduling Algorithms

We already introduced the basic concepts of real-time operating systems (RTOS) and now we will take a deeper look into one of the most important things when designing an embedded system using an RTOS – the scheduling of the tasks and the algorithms that are used.

Scheduling Process

Scheduling is the process of deciding which task should be executed at any point in time based on a predefined algorithm. The logic for the scheduling is implemented in a functional unit called the scheduler. The scheduling process is not present only in RTOS, it can be found in one form or another even in simple “bare-bone” applications.

Different RTOS distributions may support a variety of scheduling algorithms. It is important that we choose the algorithm before the development of the user application starts. Like many things in the engineering field, there is not a universal algorithm that is suitable for every use case. There are always trade-offs. In this case, they are mainly related to speed (response times), implementation complexity, etc. The chosen algorithm should always enable the timing requirements of the tasks to be met.

Types of Scheduling Algorithms

There are many scheduling algorithms that can be used for scheduling task execution on a CPU. They can be classified into two main types: preemptive scheduling algorithms and non-preemptive scheduling algorithms.

Preemptive Scheduling

Preemptive scheduling allows the interruption of a currently running task, so another one with more “urgent” status can be run. The interrupted task is involuntarily moved by the scheduler from running state to ready state. This dynamic switching between tasks that this algorithm employs is, in fact, a form of multitasking. It requires assigning a priority level for each task. A running task can be interrupted if a task with a higher priority enters the queue.

As an example let’s have three tasks called Task 1, Task 2 and Task 3. Task 1 has the lowest priority and Task 3 has the highest priority. Their arrival times and execute times are listed in the table below.

In Fig. 1 we can see that Task 1 is the first to start executing, as it is the first one to arrive (at t = 10 μs ). Task 2 arrives at t = 40μs and since it has a higher priority, the scheduler interrupts the execution of Task 1 and puts Task 2 into running state. Task 3 which has the highest priority arrives at t = 60 μs. At this moment Task 2 is interrupted and Task 3 is put into running state. As it is the highest priority task it runs until it completes at t = 100 μs. Then Task 2 resumes its operation as the current highest priority task. Task 1 is the last to complete is operation.

Non-preemptive Scheduling (a.k.a Co-Operative Scheduling)

In non-preemptive scheduling, the scheduler has more restricted control over the tasks. It can only start a task and then it has to wait for the task to finish or for the task to voluntarily return the control. A running task can’t be stopped by the scheduler.

If we take the three tasks specified in the table from the previous chapter and schedule them using a non-preemptive algorithm we get the behavior shown in Fig. 2. Once started, each task completes its operation and then the next one starts.

The non-preemptive scheduling can simplify the synchronization of the tasks, but that is at the cost of increased response times to events. This reduces its practical use in complex real-time systems.

Popular Scheduling Algorithms

We will now introduce some of the most popular scheduling algorithms that are used in CPU scheduling. Not all of them are suitable for use in real-time embedded systems. Currently, the most used algorithms in practical RTOS are non-preemptive scheduling, round-robin scheduling, and preemptive priority scheduling.

First Come, First Served (FCFS)

FCFS is a non-preemptive scheduling algorithm that has no priority levels assigned to the tasks. The task that arrives first into the scheduling queue (i.e enters ready state), gets put into the running state first and starts utilizing the CPU. It is a relatively simple scheduling algorithm where all the tasks will get executed eventually. The response time is high as this is a non-preemptive type of algorithm.

Shortest Job First (SJF)

In the shortest job first scheduling algorithm, the scheduler must obtain information about the execution time of each task and it then schedules the one with the shortest execution time to run next.

SJF is a non-preemptive algorithm, but it also has a preemptive version. In the preemptive version of the algorithm (aka shortest remaining time) the parameter on which the scheduling is based is the remaining execution time of a task. If a task is running it can be interrupted if another task with shorter remaining execution time enters the queue.

A disadvantage of this algorithm is that it requires the total execution time of a task to be known before it is run.

Priority Scheduling

Priority scheduling is one of the most popular scheduling algorithms. Each task is assigned a priority level. The basic principle is that the task with the highest priority will be given the opportunity to use the CPU.

In the preemptive version of the algorithm, a running task can be stopped if a higher priority task enters the scheduling queue. In the non-preemptive version of the algorithm once a task is started it can’t be interrupted by a higher priority task.

Of course, not all tasks can have unique priority levels and there will always be tasks that have the same priority. Different approaches can be used for handling the scheduling of those tasks (e.g FCFS scheduling or round-robin scheduling).

Round-Robin Scheduling

Round-robin is a preemptive type of scheduling algorithm. There are no priorities assigned to the tasks. Each task is put into a running state for a fixed predefined time. This time is commonly referred to as time-slice (aka quantum). A task can not run longer than the time-slice. In case a task has not completed by the end of its dedicated time-slice, it is interrupted, so the next task from the scheduling queue can be run in the following time slice. A pre-emptied task has an opportunity to complete its operation once it’s again its turn to use a time-slice.

An advantage of this type of scheduling is its simplicity and relatively easy implementation.

.