EARLIEST DEADLINE FIRST (EDF) SCHEDULING ALGORITHM

Earliest deadline first (EDF) is dynamic priority scheduling algorithm for real time embedded systems. Earliest deadline first selects a task according to its deadline such that a task with earliest deadline has higher priority than others. It means priority of a task is inversely proportional to its absolute deadline. Since absolute deadline of a task depends on the current instant of time so every instant is a scheduling event in EDF as deadline of task changes with time. A task which has a higher priority due to earliest deadline at one instant it may have low priority at next instant due to early deadline of another task. EDF typically executes in preemptive mode i.e. currently executing task is preempted whenever another task with earliest deadline becomes active.

EARLIEST DEADLINE FIRST (EDF) SCHEDULING ALGORITHM

EDF is an optimal algorithm which means if a task set is feasible then it is surely scheduled by EDF. Another thing is that EDF does not specifically take any assumption on periodicity of tasks so it is independent of Period of task and therefore can be used to schedule aperiodic tasks as well. If two tasks have same absolute deadline choose one of them randomly. you may also like to read

• Scheduling Algorithms in RTOS
• Rate monotonic scheduling Algorithm 

Example of EARLIEST DEADLINE FIRST (EDF) SCHEDULING ALGORITHM

An example of EDF is given below for task set of table-2.

Table 2. Task set

U= 1/4 +2/6 +3/8 = 0.25 + 0.333 +0.375 = 0.95 = 95%

As processor utilization is less than 1 or 100% so task set is surely schedulable by EDF.

Figure 2. Earliest deadline first scheduling of task set in Table -2

1. At t=0 all the tasks are released, but priorities are decided according to their absolute deadlines so T1 has higher priority as its deadline is 4 earlier than T2 whose deadline is 6 and T3 whose deadline is 8, that’s why it executes first.
2. At t=1 again absolute deadlines are compared and T2 has shorter deadline so it executes and after that T3 starts execution but at t=4 T1 comes in the system and deadlines are compared, at this instant both T1 and T3 has same deadlines so ties are broken randomly so we continue to execute T3.
3. At t=6 T2 is released, now deadline of T1 is earliest than T2 so it starts execution and after that T2 begins to execute. At t=8 again T1 and T2 have same deadlines i.e. t=16, so ties are broken randomly an T2 continues its execution and then T1 completes. Now at t=12 T1 and T2 come in the system simultaneously so by comparing absolute deadlines, T1 and T2 has same deadlines therefore ties broken randomly and we continue to execute T3.
4. At t=13 T1 begins it execution and ends at t=14. Now T2 is the only task in the system so it completes it execution.
5. At t=16 T1 and T2 are released together, priorities are decided according to absolute deadlines so T1 execute first as its deadline is t=20 and T3’s deadline is t=24.After T1 completion T3 starts and reaches at t=17 where T2 comes in the system now by deadline comparison both have same deadline t=24 so ties broken randomly ant we T continue to execute T3.
6. At t=20 both T1 and T2 are in the system and both have same deadline t=24 so again ties broken randomly and T2 executes. After that T1 completes it execution. In the same way system continue to run without any problem by following EDF algorithm.

Transient Over Load Condition & Domino Effect in Earliest deadline first

Transient over load is a short time over load on the processor. Transient overload condition occurs when the computation time demand of a task set at an instant exceeds the processor timing capacity available at that instant. Due to transient over load tasks miss their deadline. This transient over load may occur due many reasons such as changes in the environment, simultaneous arrival of asynchronous jobs, system exception. In real time operating systems under EDF, whenever a task in Transient overload condition miss its deadline and as result each of other tasks start missing their deadlines one after the other in sequence, such an effect is called domino effect. It jeopardizes the behavior of the whole system. An example of such condition is given below.

Figure 3. Domino effect under Earliest deadline first

As in the above figure at t=15 T1 misses it deadline and after that at t=16 T4 is missing its deadline then T2 and finally T3 so the whole system is collapsed. It is clearly proved that EDF has a shortcoming due to domino effect and as a result critical tasks may miss their deadlines. The solution of this problem is another scheduling algorithm that is least laxity first (LLF). It is an optimal scheduling algorithm. Demand bound function ad Demand bound analysis are also used for schedualability analysis of given set of tasks.

Advantages of EDF over rate monotonic

• No need to define priorities offline
• It has less context switching than rate monotonic
• It utilize the processor maximum up to 100% utilization factor as compared to rate monotonic

Disadvantages of EDF over rate monotonic

• It is less predictable. Because response time of tasks are variable and response time of tasks are constant in case of rate monotonic or fixed priority algorithm.
• EDF provided less control over the execution
• It has high overheads