Hardware Reference
In-Depth Information
Lemma 6.4
Let
σ
be a feasible schedule of task set
, in which an aperiodic job
J
k
is
assigned a deadline
d
k
, and let
f
k
be the finishing time of
J
k
in
σ
.If
d
k
is substituted
with
d
k
=
f
k
, then the new schedule
σ
' produced by EDF is still feasible.
T
Proof.
Since
σ
remains feasible after
d
k
is substituted with
d
k
=
f
k
and all other
deadlines are unchanged, the optimality of EDF [Der74] guarantees that
σ
' is also
feasible.
The process of shortening the deadline can be applied recursively to each new dead-
line, until no further improvement is possible, given that the schedulability of the
periodic task set must be preserved. If
d
k
is the deadline assigned to the aperiodic
request
J
k
at step
s
and
f
k
is the corresponding finishing time in the current EDF
schedule (achieved with
d
k
), the new deadline
d
s
+
k
is set at time
f
k
. At each step, the
schedulability of the task set is guaranteed by Lemma 6.4.
The algorithm stops either when
d
k
=
d
s−
k
or after a maximum number of steps
defined by the system designer for bounding the complexity. Note that the exact eval-
uation of
f
k
would require the development of the entire schedule up to the finishing
time of request
J
k
, scheduled with
d
k
. However, there is no need to evaluate the exact
value of
f
k
to shorten the deadline. Rather, the following upper bound can be used:
f
k
=
t
+
C
k
+
I
p
(
t, d
k
)
,
(6.1)
where
t
is the current time (corresponding to the release time
r
k
of request
J
k
or to
the completion time of the previous request),
C
k
is the worst-case computation time
required by
J
k
, and
I
p
(
t, d
k
) is the interference on
J
k
due to the periodic instances in
the interval [
t
,
d
k
).
f
k
is an upper bound for
f
k
because it identifies the time at which
and all the periodic instances with deadline less than
d
k
J
k
end to execute. Hence,
f
k
.
f
k
≤
The periodic interference
I
p
(
t, d
k
) in Equation (6.1) can be expressed as the sum of
two terms,
I
a
(
t, d
k
) and
I
f
(
t, d
k
), where
I
a
(
t, d
k
) is the interference due to the cur-
rently active periodic instances with deadlines less than
d
k
, and
I
f
(
t, d
k
) is the future
interference due to the periodic instances activated after time
t
with deadline before
d
k
. Hence,
I
a
(
t, d
k
)=
τ
i
active, d
i
<d
k
c
i
(
t
)
(6.2)
and
max
0
,
d
k
−
1
C
i
,
n
next r
i
(
t
)
T
i
I
f
(
t, d
k
)=
−
(6.3)
i
=1
Search WWH ::
Custom Search