Hardware Reference
In-Depth Information
3.5.2
EDF WITH PRECEDENCE CONSTRAINTS
( 1
|
PREC, PREEM
|
L MAX )
The problem of scheduling a set of n tasks with precedence constraints and dynamic
activations can be solved in polynomial time complexity only if tasks are preemptable.
In 1990, Chetto, Silly, and Bouchentouf [CSB90] presented an algorithm that solves
this problem in elegant fashion. The basic idea of their approach is to transform a set
J
J of independent tasks by an adequate modification
of timing parameters. Then, tasks are scheduled by the Earliest Deadline First (EDF)
algorithm. The transformation algorithm ensures that
of dependent tasks into a set
J
is schedulable and the prece-
J is schedulable. Basically, all release
times and deadlines are modified so that each task cannot start before its predecessors
and cannot preempt their successors.
dence constraints are obeyed if and only if
MODIFICATION OF THE RELEASE TIMES
The rule for modifying tasks' release times is based on the following observation.
Given two tasks J a and J b , such that J a
J b (that is, J a is an immediate predecessor
of J b ), then in any valid schedule that meets precedence constraints the following
conditions must be satisfied (see Figure 3.14):
s b
r b
(that is, J b
must start the execution not earlier than its release
time);
s b
r a + C a
(that is, J b must start the execution not earlier than the minimum
finishing time of J a ).
C a
J a
>
s
r
b
b
C b
J b
>
s b
r+
C a
r
r
s
d a
d b
a
b
b
Figure 3.14
If J a → J b , then the release time of J b can be replaced by
max( r b ,r a +
C a )
.
 
Search WWH ::




Custom Search