Hardware Reference
In-Depth Information
where
next r
i
(
t
) identifies the time greater than
t
at which the next periodic instance
of task
τ
i
will be activated. If periodic tasks are synchronously activated at time zero,
then
next r
i
(
t
)=
t
T
i
T
i
.
(6.4)
Since
I
a
and
I
f
can be computed in
O
(
n
), the overall complexity of the deadline
assignment algorithm is
O
(
Nn
), where
N
is the maximum number of steps performed
by the algorithm to shorten the initial deadline assigned by the TB server. We now
show that
f
k
is the real worst-case finishing time if it coincides with the deadline
d
k
.
f
k
=
f
k
f
k
=
d
k
.
Lemma 6.5
In any feasible schedule,
only if
Proof.
Assume that there exists a feasible schedule
σ
where
f
k
=
d
k
,but
f
k
>f
k
.
Since
f
k
is the time at which
J
k
and all the periodic instances with deadline less than
d
k
end to execute,
f
k
>f
k
would imply that
f
k
coincides with the end of a periodic
instance having deadline less than
f
k
=
d
k
, meaning that this instance would miss its
deadline. This is a contradiction; hence, the lemma follows.
6.7.1
AN EXAMPLE
The following example illustrates the deadline approximation algorithm. The task set
consists of two periodic tasks,
τ
1
and
τ
2
, with periods 3 and 4, and computation times
1 and 2, respectively. A single aperiodic job
J
k
arrives at time
t
=2, requiring 2 units
of computation time. The periodic utilization factor is
U
p
=5
/
6, leaving a bandwidth
of
U
s
=1
/
6 for the aperiodic tasks.
When the aperiodic request arrives at time
t
=2, it receives a deadline
d
k
=
r
k
+
C
k
/U
s
=14, according to the TBS algorithm. The schedule produced by EDF using
this deadline assignment is shown in Figure 6.10.
By applying Equations (6.2) and (6.3) we have
I
a
(2
,
14)
=
c
2
(2)
=
1
I
f
(2
,
14)
=
3
C
1
+2
C
2
=7
,
and, by Equation (6.1), we obtain
f
k
d
k
t
+
C
k
+
I
a
+
I
f
=
=
=12
.
Search WWH ::
Custom Search