Hardware Reference
In-Depth Information
Therefore, the deadline
d
a
of
J
a
can be replaced by the minimum between
d
a
and
C
b
) without changing the problem. Let
d
a
be the new deadline of
J
a
. Then,
(
d
b
−
d
a
=min(
d
a
,d
b
−
C
b
)
.
The algorithm that modifies the deadlines can be implemented in
O
(
n
2
) and can be
described as follows:
1. For any terminal node of the precedence graph, set
d
i
=
d
i
.
2. Select a task
J
i
such that its deadline has not been modified but the deadlines of
all immediate successors
J
k
have been modified. If no such task exists, exit.
3. Set
d
i
=min[
d
i
,
min(
d
k
−
C
k
:
J
i
→
J
k
)].
4. Return to step 2.
PROOF OF OPTIMALITY
The transformation algorithm ensures that if a feasible schedule exists for the modified
task set
J
∗
under EDF, then the original task set
J
is also schedulable; that is, all tasks
J
∗
is schedulable, all
in
J
meet both precedence and timing constraints. In fact, if
modified tasks start at or after time
r
i
and are completed at or before time
d
i
. Since
r
i
≥
and
d
i
≤
J
∗
implies that
r
i
d
i
, the schedulability of
J
is also schedulable.
To show that precedence relations in
are not violated, consider the example illus-
trated in Figure 3.16, where
J
1
must precede
J
2
(i.e.,
J
1
→
J
J
2
), but
J
2
arrives before
J
1
and has an earlier deadline. Clearly, if the two tasks are executed under EDF, their
precedence relation cannot be met. However, if we apply the transformation algorithm,
the time constraints are modified as follows:
r
1
d
1
=
r
1
=min(
d
1
,d
2
−
C
2
)
r
2
d
2
=max(
r
2
,r
1
+
C
1
)
=
d
2
This means that, since
r
2
>r
1
,
J
2
cannot start before
J
1
. Moreover,
J
2
cannot
preempt
J
1
because
d
1
<d
2
and, based on EDF, the processor is assigned to the task
with the earliest deadline. Hence, the precedence relation is respected.
d
j
. This
means that, if
J
i
is in execution, then all successors of
J
i
cannot start before
r
i
because
J
j
,wehave
r
i
≤
r
j
and
d
i
≤
In general, for any pair of tasks such that
J
i
≺
Search WWH ::
Custom Search