In this article, you will learn about real time embedded systems scheduling algorithms, types of real time scheduling algorithms, online and offline scheduling algorithms of real time embedded systems. In real time operating systems(RTOS) most of the tasks are periodic in nature. Periodic data mostly comes from sensors, servo control, and real-time monitoring systems. In real time operating systems, these periodic tasks utilize most of the processor computation power. A real-time control system consists of many concurrent periodic tasks having individual timing constraints.
These timing constraints include release time (ri), worst case execution time(Ci), period (ti) and deadline(Di) for each individual task Ti. Real time embedded systems have time constraints linked with the output of the system. The scheduling algorithms are used to determine which task is going to execute when more than one task is available in the ready queue. The operating system must guarantee that each task is activated at its proper rate and meets its deadline. you may also like to read about
To ensure this, some periodic scheduling algorithms are used. There are basic two type of scheduling algorithms,
Offline Scheduling Algorithm
Offline scheduling algorithm selects a task to execute with reference to a predetermined schedule, which repeats itself after specific interval of time. For example, if we have three tasks Ta, Tb and Tc then Ta will always execute first, then Tb and after that Tc respectively.
Online Scheduling Algorithm
In Online scheduling a task executes with respect to its priority, which is determined in real time according to specific rule and priorities of tasks may change during execution. The online line scheduling algorithm has two types. They are more flexible because they can change the priority of tasks on run time according to the utilization factor of tasks.
Fixed priority algorithms
In fixed priority if the kth job of a task T1 has higher priority than the kth job of task T2 according to some specified scheduling event, then every job of T1 will always execute first then the job of T2 i.e. on next occurrence priority does not change. More formally, if job J(1,K) of task T1 has higher priority than J(2,K) of task T2 then J(1,K+1) will always has higher priority than of J(2,K+1) . One of best example of fixed priority algorithm is rate monotonic scheduling algorithm.
Dynamic priority algorithms
In dynamic priority algorithm, different jobs of a task may have different priority on next occurrence, it may be higher or it may be lower than the other tasks. One example of a dynamic priority algorithm is the earliest deadline first algorithm.
Processor utilization factor (U)
For a given task set of n periodic tasks, processor utilization factor U is the fraction of time that is spent for the execution of the task set. If Si is a task from task set then Ci/Ti is the time spent by the processor for the execution of Si . Similarly, for the task set of n periodic tasks
processor utilization is greater than one then that task set will not be schedulable by any algorithm. Processor utilization factor tells about the processor load on a single processor. U=1 means 100% processor utilization. Following scheduling algorithms will be discussed in details in next articles: