FOR FREE YEAR SOLVED

Earliest Deadline First (EDF) Scheduling

EDF scheduling process and example

Scheduling As its name suggests, this policy always selects the process with the earliest deadline.

It dynamically assigns priorities to real-time processes according to deadline and changes process priorities during execution based on initiation times. As a result, it can achieve higher CPU utilization than Rate-Monotonic Scheduling (RMS). 

The earlier the deadline, the higher the priority; the later the deadline, the lower the priority. 

The EDF policy is also very simple: It assigns priorities in order of deadline. The highest-priority process is the one whose deadline is nearest in time, and the lowest priority process is the one whose deadline is farthest away. Clearly, priorities must be recalculated at every completion of a process. However, the final step of the OS during the scheduling procedure is the same as for RMS — the highest-priority ready process is chosen for execution.

To clear the concept better way looks at the example.

Period: Processes always occur at regular intervals of time which is called the period.

Deadline: The time by which operation of the process must complete.

Execution time: Time required to execute the process i.e. CPU time. 

Example1. (Earliest Deadline First (EDF) Scheduling)

In this example1, deadline is not mentioned so we can assume here period and the deadline is the same.

Now hyper period is either given the question or we can calculate by LCM of periods of all process.

So, here hyper period is LCM (3, 4, 8) = 24. 

Algorithm:

For each time unit

 {

  For each ready process

 {

  Process with closed deadline will execute first

 }

}

Periodic Task Timing Diagram: 

a) Initially at time unit 0, all processes are ready to execute, but P1 has the nearest deadline compare to P2, P3 so, first P1 assign for 1 unit.

b) Now at time unit 1, only P2 and P3 are ready processes and P2 has the nearest deadline compare to P3, so here P2 has been assigned for 1 unit. 

c) Now at time unit 2 only ready process is P3. So, we assign P3 for 1 unit (though the execution time of P3 is 2), because as we know at every time unit we check which is the earliest deadline.

d) Now after 1 unit of P3, at time unit of 3 ready processes are P1 and P3. Here P1 is the earliest deadline compare to P3, so we assign P1 for 1 unit.

e) Now after completion of P1 (1 unit), at time unit 4, the ready processes are P2 and P3. And P2 has the nearest deadline compared to P3 so, we assign P2 for 1 unit.

f) Now after P2 finished (1 unit), at time unit 5 only the P3 process is ready, so we assign the rest 1 unit for P3 at the first period.

In the same way, we complete all the processes as per the given period. 

Calculation for CPU utilization

Process P1: 1x8 = 8 (Process P1 runs 1 unit for 8 times in the total period)

Process P2: 1x6= 6 (Process P2 runs 1 unit for 6 times in the total period)

Process P3: 2x3= 6 (Process P3 runs 2 units for 3 times in the total period)

CPU Utilization= 20/24 = 0.8333 means 83.33%