Priority scheduling based on deadline are:

  1. Earliest deadline first (EDF)
  2. Least slack time first (LST)

Earliest deadline first (EDF):

It is a type of the priority scheduling algorithms assign priority to jobs based on deadline. In this approach, earlier the deadline gets higher the priority. Simply, it just requires knowledge of deadlines.

Least Slack Time first (LST):

Suppose a job J i has deadline d i, execution time e i, and was released at time r i then at time t < d

i:

  • Remaining execution time t rem = e i - (t – r i)
  • Slack time t slack = d i – t – t rem

In this approach, priority to jobs be assigned based on slack time .The smaller the slack time jobs gets higher the priority then next higher slack time and so on. It is more complex for implementation and requires knowledge of execution times and deadlines properly. Knowing the actual execution time is often difficult a priori, since it depends on the data, need to use worst case estimate. For example

Job J1 of example is released at time 0 and has its deadline at time 6 and execution time 3. Hence its slack is 3 at time 0. The job starts to execute at time 0. As long as it executes its slack remains 3 because at any time before its completion its slack is 6 - t - (3 – t).

Suppose J1 is preempted at time 2 by J3 which executes from time 2 to 4. During this interval the slack of J1 decreases from 3 to 1. At time 4 the remaining execution time of J1 is 1, so its slack is 6 - 4 - 1 = 1. The LST algorithm assigns priorities to jobs based on their slacks. The smaller the slack, the higher the priority.

Optimality of EDF and LST:

These algorithms are optimal only when they always produce a feasible schedule if one exists.

It is constraints on a single processor as long as preemption is allowed and jobs do not contend for resources.

Optimality of EDF (Proof):

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 jobs with arbitrary release times and deadlines on a processor if and only if J has feasible schedules

Proof:

To show the optimality of EDF, we have to require to show any feasible schedule can be transformed into another an EDF schedule

If J i is scheduled to execute before J k, but J i’s deadline is later than J k’s such that there exist two conditions:

  • The release time of J k is after the J i completes that means they’re already in EDF order.
  • The release time of J k is before the end of the interval in which J i executes

This is always possible to swap J i and J k since J i’s deadline is later than J k’s such that

We can move any jobs following idle periods forward into the idle period then

The result is an EDF schedule.

When deadline of J i’s is earlier than J k’s there is no possibility to generate the other feasible schedule and EDF failed to produce a feasible schedule. Hence the optimality of EDF is verified.

Latest-Release-Time (LRT) Algorithm:

The Latest-Release-Time algorithm treats release times as deadlines and deadlines as release times and schedules jobs backwards, starting from the latest deadline of all jobs, in a priority-driven manner, to the current time. The ‘priorities’ are based on the later the release time, the higher the ‘priority’. Because it may leave the processor idle when there are jobs awaiting execution, the LRT algorithm is not a priority-driven algorithm. For example

In the following example, the number next to the job is the execution time and the feasible interval follows it.

The latest deadline is 8, so time starts at 8 and goes back to 0. At time 8, J2 is “ready” and is scheduled. At time 7, J3 is also “ready” but because J2 has a later release time, it has a higher priority, so J2 is scheduled from 7 to 6.

When J2 “completes” at time 6, J1 is “ready” however J3 has a higher priority so is scheduled from 6 to 4.

Finally J1 is scheduled from 4 to 1.

The following corollary states that the LRT algorithm is also optimal under the same conditions that the EDF algorithm is optimal. Its proof follows straightforwardly from the proof of EDF.

“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”.