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.
