In online scheduling, decisions are taken based on a set of pre-defined rules represented as priorities. Following are the algorithms which come under the online RTOS scheduling.

1. Event Driven: EDF (Earliest Deadline First)

It is priority based scheduling also called a list time to go or deadline given scheduling. It uses a dynamic strategy for scheduling the processes. In this algorithm, queue searches for those processes which are having minimum execution time at the time of scheduling the events. Event means the current task finishes or new task releases.

EDF is an optimal scheduling algorithm meaning it is possible for the process to schedule, then it is surely scheduled by EDF. This algorithm is based on preemption. In preemptive uni-processors, if the collection of jobs are independent, each one is having arrival time, fulfillment of execution requirements, and deadline. Then there is surety of job-completion within a deadline.

EDF ensures that all deadlines don't go beyond 100% of total CU utilization. But Sometimes the system can be overloaded. So, there would be a number of processes that can miss the deadline and this count is unpredictable. This is the disadvantage of RTOS due to this most applications uses Rate Monolithic Scheduling i.e. Fix priority scheduling.

Example:

Following table shows the number of task sets we have to complete using parameters like the capacity of each task for execution, deadline and period of execution of the task.

First of all, it is important to know the LCM of the period of tasks. The total number of units on the performance line.

LCM (05, 10, 20) = 20 Units. So, plotting 20 number of units on performance line.

Now, concentrate on the deadline. The earliest deadline should be considered first. Here, it is 4(T2). Therefore we will plot capacity of 2 for the deadline 4 and period 5 on task T2. See in the figure below.

Next early deadline is 7 i.e. T1. So, we will now plot capacity of 3 for deadline 7 and period 20.
The last deadline is 8 for task T3 having the capacity of 2 and the period is 10 units.

Now, we should follow the deadlines. Whichever having a less deadline will execute first. T2 has the lowest deadline will execute first. So this deadline is achieved with the capacity of 2. Next deadline lower than T2 is T1 will execute. T1 has to execute 3 units. After that T1 will not participate in scheduling. Because it completed it’s 3 units of the capacity of execution. Our next target is T3. It will execute with 2 units. Next deadline is 9 which is completed by T2.

From 9 to 10, no deadline available. So, the next deadline is 10 to 14. T2 will execute once in this patch (shown in the figure below). Next deadline is 18. So T3 will execute from 12 to 14.

At last, only one deadline remains to schedule i.e. 19th which is for T2. So, again from 14 to 15 no deadline available. So we have to schedule in slot 15 to 17 i.e. 2 units.

Now, if you will observe the completed diagram, T2 is completed before 4 in the first slot, that is true.

Next deadline is 8 as T3 is completed before it. T2 is completed before next deadline i.e. 9. On so on.

This is the way we use the earliest deadline first algorithm.

Advantages of EDF

1. No need to define the priorities offline.
2. EDF has less context switching.
3. It tries to utilize the processes maximum i.e. up to 100%

Disadvantages of EDF

1. EDF has a high overhead.
2. Control over the execution of processes is less.
3. Less predictable.

2. Rate monotonic Scheduling

Rate monotonic scheduling is a fixed priority driven algorithm. In this algorithm, Rate = 1/Period i.e. if the period is less, then priority is high and if the period is high, priority is less.

It is a static priority scheduling algorithm i.e. task with the highest static priority and the shortest period of time is run-able immediately and preempt all other tasks.

Now see the example below. (Deadline is a priority)

First of all, it is important to know the LCM of the period of tasks. The total number of units on the performance line.

LCM (05, 10, 20) = 20 Units.

So, plotting 20 number of units on performance line.

The second thing is the priority. We will get the priority by the deadline. Least deadline has the highest priority. So, T2 will goes the highest priority. T2>T1>T3 like that.

T1 has to execute 3 units from 0 to 20 but the deadline is 7 so it has to complete 3 units before 7. For T2, it has to execute 2 units over 0 to 20 but must complete 2 units before 4 because of its deadline. Now coming to the T3, it has to execute 2 units but the deadline is 9. So execute 2 units before 9.

Now, consider the highest priority which is T2 execute 2 units before 4 deadlines, so it's complete. Now the second priority is T1 has to execute 3 units and deadline is 7, so as T1 has to execute 3 units and move out of the executing As total capacity is completed, thus scheduling will take place only in T2 and T3, thus T2 executes again 2 units now its time of T3 to execute 2 units before deadline 9 and so on.

After doing so, consider the highest priority which is T2. So start executing T2 first which will execute for 2 units before deadline 4. The second priority is T1 which has to execute 3 units and the deadline is 7. See in the figure below. Now at 5, T2 will start again because of the highest priority. So, execute T2 for 2 units from 5 to 7. Now the priority goes to T1 but T1 is already completed.

Now scheduling will take place only between T2 and T3. T2 will again execute 2 units. Then T3 will execute. At 10, T2 will come again because of its period. Now from 10 to 20 T3 has to execute. T3 also completed its execution and move out of scheduling. From 15, T2 will execute for completion.

A complete plotted graph is given below.

Deadline monotonic scheduling

1. LCM(20,5,10) = 20 units

2. Priority: High to Low $T_2 \gt T_1 \gt T_3$

Advantages of RMS

1. It processes good transient overload handling.

Disadvantages of RMS

1. It is difficult to support the aperiodic and sporadic task.

2. RMS is not optimal when task periods are deadlines differ.