Optimality of EDF

Optimality of EDF

Theorem

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

Proof:

We show that any feasible schedule of J can be systematically transformed into an EDF schedule.

Suppose parts of two jobs Ji and Jk are executed out of EDF order.

This situation can be corrected by performing a “swap”:

If we inductively repeat this procedure, we can eliminate all out-of-order violations.

The resulting schedule may still fail to be an EDF schedule because it has idle intervals where some job is ready:

Such idle intervals can be eliminated by moving some jobs forward:

Corollary

When preemption is allowed and jobs do not contend for resources, the LRT 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 feasible schedules of J exist.

Optimality of LST

When preemption is allowed and jobs do not contend for resources, the LST (MLF) 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 feasible schedules of J exist.

J1, 1(0,1)

J2, 1(0,2)

J3, 5(0,5)

ST = deadline – current time – (remaining time to execute the job)

At, t=0, slacktime (ST),

for J1 = 1 – 0 – (1 – 0) = 0

for J2 = 2 – 0 – (1 – 0) = 1

for J3 = 5 – 0 – (5 – 0) = 0

At t = 1, ST for J1 = 1 – 1 – (1 -1) = 0

J2 = 2 – 1 – (1 - 0) = 0

J3 = 5 – 1 – (5- 0) = -1

Example

Show that given jobs are LST optimal.

J1, 3(0,6) , J2, 2(5,8), J3, 2(2,7)

Solution:

At time t = 0, slack time, ST for

J1 = 6 – 0 – (3 – 0) = 3

J2 = 8 – 0 – (2 – 0) = 6

J3 = 7 – 0 – (2- 0) = 5

At time t = 1, ST for

J1 = 6 – 2 – (3 – 2) = 3

J2 = 8 – 1 – (2 – 0) = 5

J3 = 7 – 1 – (2 – 0) = 4

At time t = 2, ST for

J1 = 6 – 2 – (3 – 2) = 3

J2 = 8 – 2 – (32– 0) = 4

J3 = 67– 2 – (2 – 0) = 3

At time 3 = 0, ST for

J1 = 6 – 3 – (3 – 3) = 3

J2 = 8 – 3 – (2 – 0) = 4

J3 = 7 – 2 – (2 – 0) = 3

At time t = 4, ST for

J1 = 6 – 4 – (3 – 3) = 2

J2 = 8 – 4 – (2 – 0) = 2

J3 = 7 – 4 – (2 – 1) = 2

At time t = 5, ST for

J1 = 6 – 5 – (3 – 3) = 1

J2 = 8 – 5 – (2 – 1) = 2

J3 = 7– 5 – (2 – 1) = 1

At time t = 6, ST for

J1 = 6 – 6 – (3 – 0) = 0

J2 = 8 – 6 – (2 – 1) = 1

J3 = 7 – 6 – (2 – 2) = 1

Non- Optimality of EDF and LST

The system shown in this ï¬Âgure has three independent, nonpreemptable jobs J1, J2, andJ3. Their release times are 0, 2 and 4, respectively, and are indicated by the arrows above the schedules. Their execution times are 3, 6, and 4; and their deadlines are 10, 14, and 12, respectively.

Here, J3 doesn’t meet deadline. So, it is non-optimal.

Now, using EDF

It is also non-optimal because it contains slack time.

The example in Figure below shows that the EDF algorithm is not optimal for scheduling preemptable jobs on more than one processor (here, we have two processors, J1>J2>J3). The system in this ï¬Âgure also contains three jobs, J1, J2, andJ3. Their execution times are 1, 1, and 5 and their deadlines are 1, 2, and 5, respectively. The release times of all three jobs are 0. The system has two processors.

References

Liu, Jane W. S. Real Time Systems. Integre Technical Publishing Co., Inc, January 10, 2000. Print.