Anonymous user menu

EDF: Earliest Deadline First Scheduling algorithm. Can an

EDF: Earliest Deadline First Scheduling algorithm.

Can anybody explain the statement in bold?

EDF can guarantee that all deadlines are met provided that the total CPU utilization is not more than 100%. Compared to fixed priority scheduling techniques like rate-monotonic schedulingEDF can guarantee all the deadlines in the system at higher loading.

However, when the system is overloaded, the set of processes that will miss deadlines is largely unpredictable (it will be a function of the exact deadlines and time at which the overload occurs.) This is a considerable disadvantage to a real-time systems designer. The algorithm is also difficult to implement in hardware and there is a tricky issue of representing deadlines in different ranges (deadlines must be rounded to finite amounts, typically a few bytes at most). If a modular arithmetic is used to calculate future deadlines relative to now, the field storing a future relative deadline must accommodate at least the value of the (("duration" {of the longest expected time to completion} * 2) + "now"). Therefore, EDF is not commonly found in industrial real-time computer systems.

 

Also, I read that if a set of processes cannot be scheduled by rate monotonic algorithm, then they can not be scheduled by any other algorithm. How can we say that?

2Comments
Dhrupit Dave @dhrupitdave
8 Oct 2014 05:55 pm

It tries to explain that EDF is not practical for industrial use.

Why? Because it is tough to find out the deadline(when to end the task) and even if we choose it with modular arithmetic(the residue method of finding the remainder) it we can not get the longest expected deadline to accommodate the task.

 

Parimal Andhalkar @parimal_andhalkar
10 Nov 2014 09:21 pm

it can be asked in gate exam  ? 

is EDF is equivalent to SJF  ???