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.
Think of EDF as a personal assistant, who helps you prioritize your tasks based on their urgency. Each task is assigned a deadline, and your assistant ensures that the task with the closest deadline is handled first. This way, you never miss a deadline and always complete the most critical task first. The EDF algorithm works in much the same way, helping real-time systems prioritize tasks based on their deadlines and execute them on time.
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 id; // Task ID
int arrival_time; // Task Arrival Time
int deadline_time; // Task Deadline Time
int execution_time; // Task Execution Time
bool executed;
};
// setting priority to tasks by sorting deadline time
bool set_priority(EDF a, EDF b)
{
return a.deadline_time < b.deadline_time;
}
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;
}
//showing output of tasks set
cout << “___________________________________________” << endl;
cout << “Tasks Set” << endl;
cout << “______________________________________________” << endl;
cout << “Task ID Arrival Execution Deadline ” << endl;
cout << “______________________________________________” << endl;
for (int i = 0; i < MAX; i++) {
cout << e[i].id << ” “
<< e[i].arrival_time << ” “
<< e[i].execution_time << ” “
<< e[i].deadline_time << ” “
<< endl;
}
cout << “______________________________________________” << endl;
//Built-in function to sort an array (Here I have used it to sort deadline time of tasks)
cout << endl;
cout << “Sorting tasks deadlines…” << 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 << “Task ID Arrival Execution Deadline ” << endl;
cout << “______________________________________________” << endl;
for (int i = 0; i < MAX; i++) {
cout << e[i].id << ” “
<< e[i].arrival_time << ” “
<< e[i].execution_time << ” “
<< e[i].deadline_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 {
// tasks that missed their deadline
//cout << “Task ” << e[i].id << ” missed its deadline” << endl;
remaining_time = e[i].deadline_time – time;
e[i].execution_time -= remaining_time;
time = e[i].deadline_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.
- Finally, the code iterates through the task array and checks if each task can be executed within its deadline time. If a task can be executed, its execution time is added to the current time, and the task is marked as executed. If a task cannot be executed within its deadline, the code calculates the remaining time until the deadline and updates the task’s execution time accordingly. The task is then marked as partially executed.
- Note that the constant “MAX” at the start of the program represents the maximum number of tasks that can be scheduled. This is flexible you can execute any number of tasks.
This is the implementation of the Earliest Deadline First (EDF) in C++, which is a CPU scheduling algorithm used in real-time operating systems. The EDF schedules tasks based on their deadlines, with the task having the earliest deadline being executed first. Hence, this EDF scheduling algorithm code in C++ is flexible and can be easily modified to suit different scheduling requirements.
