Hardware Reference
In-Depth Information
Algorithm: interchange
{
for
(t=0 to D-1)
{
if
(
σ
(
t
)
{
σ
(
t
E
)=
σ
(
t
);
σ
(
t
)=
E
(
t
);
=
E
(
t
))
}
}
}
Figure 3.5
Transformation algorithm used by Dertouzos to prove the optimality of EDF.
The algorithm used by Dertouzos to transform any schedule
σ
into an EDF schedule
is illustrated in Figure 3.5. For each time slice
t
, the algorithm verifies whether the
task
σ
(
t
) scheduled in the slice
t
is the one with the earliest deadline,
E
(
t
). If it is,
nothing is done, otherwise a transposition takes place and the slices at
t
and
t
E
are
exchanged (see Figure 3.4). In particular, the slice of task
E
(
t
) is anticipated at time
t
,
while the slice of task
σ
(
t
) is postponed at time
t
E
. Using the same argument adopted
in the proof of Jackson's theorem, it is easy to show that after each transposition the
maximum lateness cannot increase; therefore, EDF is optimal.
By applying the interchange algorithm to the schedule shown in Figure 3.4a, the first
transposition occurs at time
t
=4. At this time, in fact, the CPU is assigned to
J
4
,
but the task with the earliest deadline is
J
2
, which is scheduled at time
t
E
=6.Asa
consequence, the two slices in gray are exchanged and the resulting schedule is shown
in Figure 3.4b. The algorithm examines all slices, until
t
=
D
, performing a slice
exchange when necessary.
To show that a transposition preserves the schedulability, note that at any instant each
slice in
σ
can be either anticipated or postponed up to
t
E
. If a slice is anticipated, the
feasibility of that task is obviously preserved. If a slice of
J
i
is postponed at
t
E
and
σ
is feasible, it must be (
t
E
+1)
≤
d
E
, being
d
E
the earliest deadline. Since
d
E
≤
d
i
for any
i
, then we have
t
E
+1
≤
d
i
, which guarantees the schedulability of the slice
postponed at
t
E
.
Search WWH ::
Custom Search