Hardware Reference
In-Depth Information
Theorem 3.2 (Horn) Given a set of n independent tasks with arbitrary arrival times,
any algorithm that at any instant executes the task with the earliest absolute deadline
among all the ready tasks is optimal with respect to minimizing the maximum lateness.
This result can be proved by an interchange argument similar to the one used by Jack-
son. The formal proof of the EDF optimality was given by Dertouzos in 1974 [Der74]
and it is illustrated below. The complexity of the algorithm is O ( n ) per task, if the
ready queue is implemented as a list, or O ( n log n ) per task, if the ready queue is
implemented as a heap.
3.3.1
EDF OPTIMALITY
The original proof provided by Dertouzos [Der74] shows that EDF is optimal in the
sense of feasibility. This means that if there exists a feasible schedule for a task set
J
, then EDF is able to find it. The proof can easily be extended to show that EDF
also minimizes the maximum lateness. This is more general because an algorithm
that minimizes the maximum lateness is also optimal in the sense of feasibility. The
contrary is not true.
Using the same approach proposed by Dertouzos, let σ be the schedule produced by
a generic algorithm A and let σ EDF be the schedule obtained by the EDF algorithm.
Since preemption is allowed, each task can be executed in disjointed time intervals.
Without loss of generality, the schedule σ can be divided into time slices of one unit
of time each.
To simplify the formulation of the proof, let us define the following
abbreviations:
identifies the task executing in the slice [ t, t +1). 1
σ ( t )
E ( t )
identifies the ready task that, at time t , has the earliest deadline.
t E ( t )
is the time (
t ) at which the next slice of task E ( t ) begins its execution
in the current schedule.
If σ
= E ( t ). As illustrated
in Figure 3.4, the basic idea used in the proof is that interchanging the position of
σ ( t ) and E ( t ) cannot increase the maximum lateness. If the schedule σ starts at time
t =0and D is the latest deadline of the task set ( D =ma i {
= σ EDF , then in σ there exists a time t such that σ ( t )
d i }
) then σ EDF
can be
obtained from σ by at most D transpositions.
1 [a,b) denotes an interval of values x such that a ≤ x<b .
Search WWH ::




Custom Search