# Earliest Deadline First (EDF) Scheduling Algorithm Code in C++

The Earliest Deadline First (EDF) scheduling algorithm is a dynamic priority scheduling algorithm that is commonly used in real-time systems. In this algorithm, tasks are assigned deadlines, and the task with the earliest deadline is given the highest priority. This algorithm ensures that the most critical task is executed first and prevents task delay. Implementing EDF in code can be a bit challenging, especially if you are a newbie to programming. In this post, we will walk you through the EDF scheduling algorithm code in C++, breaking down complex concepts into simple, understandable steps. So sit back, grab a cup of coffee, and get ready to take your real-time task management to the next level!

Let’s get started with the definition of the Earliest Deadline First (EDF) CPU scheduling algorithm and how it works.

## EDF Scheduling Algorithm

Earliest Deadline First (EDF) is a dynamic priority scheduling algorithm that is commonly used in real-time systems to manage tasks and ensure that the tasks which have an earlier deadline are executed first. The EDF algorithm is based on the idea that tasks have deadlines and that the task with the earliest deadline should be given the highest priority.

As in EDF the arrival of the tasks is not the same hence preemption will take place and assign the processor to the task having an earlier deadline. Thus by dynamically assigning the priority of tasks based on their deadlines, the EDF algorithm ensures that no task is left waiting for too long. This makes EDF an effective solution for real-time systems where missing deadlines can have serious consequences.

### Example

Let’s take a set of five tasks as shown in the table below. At time t = 0, the tasks J1 and J2 arrived, since in EDF the priority will be given to the task that has the earliest deadline, in this case, the processor will be assigned to J1.

 J1 J2 J3 J4 J5 ai 0 0 2 3 6 Ci 1 2 2 2 2 di 2 5 4 10 9 At time t = 1, task J1 completes its execution. Then at time t = 2, J2 starts its execution, but after completing one unit execution J3 arrives. Since the deadline for J3 is earlier so it will preempt J2. Note that at time t = 3, J4 arrives but it will not preempt J3 because the deadline of J3 is earlier than J4, so J3 will continue its execution. At time t = 4, J3 completes its execution and the processor will be assigned to J2, which will complete the one-unit execution that was left before. At time t = 5, J4 starts its execution but is preempted by J5 at time t = 6 because J5 has an earlier deadline. Task J4 will resume its execution at time t = 8 when J5 is completed.

Hence in the above example, all the tasks meet their deadlines at in this case the maximum lateness (Lmax) = 0.

## EDF implementation in C++

Here is the EDF scheduling algorithm code in C++ programming language.

```#include <iostream>
#include <algorithm>
using namespace std;

const int MAX = 3;

struct EDF {
int arrival_time; // Task Arrival Time
int execution_time; // Task Execution Time
bool executed;
};
bool set_priority(EDF a, EDF b)
{
}
int main() {
srand(time(NULL));
int time = 0;// Time starts at 0
int remaining_time;

EDF e[MAX];

cout << "-----EDF Algorithm-----" << endl << endl;

//Getting tasks details from rand function
for (int i = 0; i < MAX; i++) {
cout << "Getting Tasks " << i+1 << " Details: " << endl;

e[i].id = i+1;

e[i].arrival_time = 0 + rand() % 5;

e[i].execution_time = 1 + rand() % 5;

e[i].deadline_time = e[i].execution_time + (rand() % 10);

e[i].executed = false;
}
cout << "___________________________________________" << endl;
cout << "Tasks Set" << endl;
cout << "______________________________________________" << endl;
cout << "______________________________________________" << endl;

for (int i = 0; i < MAX; i++) {
cout << e[i].id << "            "
<< e[i].arrival_time << "             "
<< e[i].execution_time << "            "
<< endl;
}
cout << "______________________________________________" << endl;

//Built-in function to sort an array (Here I have used it to sort deadline time of tasks)

cout << endl;

sort(e, e + MAX, set_priority);
//showing output of tasks set (details entered by user)
cout << "___________________________________________" << endl;
cout << "Tasks Set After Sorting" << endl;
cout << "______________________________________________" << endl;
cout << "______________________________________________" << endl;

for (int i = 0; i < MAX; i++) {
cout << e[i].id << "            "
<< e[i].arrival_time << "             "
<< e[i].execution_time << "            "
<< endl;
}
cout << "______________________________________________" << endl;

for (int i = 0; i < MAX; i++) {

if (time + e[i].execution_time <= e[i].deadline_time) {

cout << "Task " << e[i].id << " executed from time " << time << " to time " << time + e[i].execution_time << endl;
time += e[i].execution_time;
e[i].executed = true;

}
else {
//cout << "Task " << e[i].id << " missed its deadline" << endl;
e[i].execution_time -= remaining_time;
cout << "Task " << e[i].id << " partially executed " << endl;
e[i].executed = false;
}
}

cout << "______________________________________" << endl;
cout << "Program Ended" << endl;
return 0;
}
```

### Output ## Code Explanation

• The program takes random value input for ai (arrival time), Ci (execution time or computation time), and di (deadline) by using the built-in function rand(). Note that we’ve added execution time while getting random values for the deadline so that the deadline must be in increasing order.
• Define a boolean function that sorts the tasks based on their deadlines.
• Now come to the main function, we’ve declared a variable ‘time‘ and initialized it with 0. This variable keeps track of the current time.