## State and Prove Optimal Earliest Deadline First (EDF) Algorithm,

Real Time System Notes | Sixth Semester,

BSc.CSIT | Tribhuvan University (TU)

**State and prove optimal EDF algorithm**

**State:**

When preemption is allowed and jobs do not contend for resources, the EDF algorithm can produce a feasible schedule of a set J of jobs with arbitrary release times and deadlines on a processor if and only if J has feasible schedules.

**Proof:**

Any feasible schedule of J can be systematically transformed into an EDF schedule.

Suppose that in a schedule, parts of J_{i} and J_{k} are scheduled in interval I_{1} and I_{2} respectively. The deadline d_{i} of J_{i} is later than the deadline d_{k} of J_{k}, but I_{1} is earlier than I_{2}.

**Case (I)**

Release time (r_{k}) of J_{k} may be later than the end of I_{1}

J_{k} cannot be scheduled in I_{1}

So, the two jobs are already scheduled on EDF basis in these intervals.

**Case (II)**

Release time (r_{k}) of J_{k} is before end of I_{1}.

We assume r_{k} is no later than beginning of I_{1}

To transform the given schedule we swap J_{i} and J_{k}.

If I_{1} is shorter than I_{2}, we move the portion of J_{k} that fits in I_{1} forward to I_{1} and move entire portion of J_{i} scheduled in I_{1} backward to I_{2} after J_{k}.

If I_{1} is longer than I_{2}, we move the entire portion of J_{k} scheduled in I_{2} to I_{1} and place it before J_{i} and move the portion of J_{i} that fits in I_{2} to the interval.

- We repeat this transformation for every pair of jobs that are not scheduled on EDF basis according to given non-EDF schedule until no pair exists.
- The schedule obtained after this transformation may still not be an EDF schedule if some interval is left idle while there are jobs ready for execution but are scheduled in later interval.
- We can eliminate such an idle interval by moving one or more of these jobs forward into the idle interval and leave the interval where jobs were scheduled idle.
- We repeat this process if necessary until the processor never idles when there are jobs ready for execution.

Hence, the fact that preemptive EDF can always produce a feasible schedule as long as feasible schedule exists follows straightforward from the fact that every feasible schedule can be transformed into a preemptive EDF schedule.

If the algorithm fails to produce feasible schedule, then no feasible schedule exists.