State and Prove Optimal Earliest Deadline First (EDF) Algorithm,Real Time System Notes | Sixth Semester,BSc.CSIT | Tribhuvan University (TU)
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 Ji and Jk are scheduled in interval I1 and I2respectively. The deadline di of Ji is later than the deadline dk of Jk, but I1 is earlier than I2.
Any feasible schedule of J can be systematically transformed into an EDF schedule.
Suppose that in a schedule, parts of Ji and Jk are scheduled in interval I1 and I2respectively. The deadline di of Ji is later than the deadline dk of Jk, but I1 is earlier than I2.
Case (I)
Release time (rk) of Jk may be later than the end of I1
Jk cannot be scheduled in I1
So, the two jobs are already scheduled on EDF basis in these intervals.
Release time (rk) of Jk may be later than the end of I1
Jk cannot be scheduled in I1
So, the two jobs are already scheduled on EDF basis in these intervals.
Case (II)
Release time (rk) of Jk is before end of I1.
We assume rk is no later than beginning of I1
Release time (rk) of Jk is before end of I1.
We assume rk is no later than beginning of I1
To transform the given schedule we swap Ji and Jk.
If I1 is shorter than I2, we move the portion of Jk that fits in I1 forward to I1 and move entire portion of Ji scheduled in I1 backward to I2 after Jk.
If I1 is shorter than I2, we move the portion of Jk that fits in I1 forward to I1 and move entire portion of Ji scheduled in I1 backward to I2 after Jk.
If I1 is longer than I2, we move the entire portion of Jk scheduled in I2 to I1 and place it before Ji and move the portion of Ji that fits in I2 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.
If the algorithm fails to produce feasible schedule, then no feasible schedule exists.
No comments:
Post a Comment