Hardware Reference
In-Depth Information
It follows that
k
2
C
ape
=
C
k
k
=
k
1
k
2
=
[
d
k
−
max(
r
k
,d
k−
1
)]
U
s
k
=
k
1
≤
[
d
k
2
−
max(
r
k
1
,d
k
1
−
1
)]
U
s
≤
(
t
2
−
t
1
)
U
s
.
The main result on TBS schedulability can now be proved.
Theorem 6.3 (Spuri, Buttazzo)
Given a set of
n
periodic tasks with processor uti-
lization
U
p
and a TBS with processor utilization
U
s
, the whole set is schedulable by
EDF
if
and
only if
U
p
+
U
s
≤
1
.
Proof.
1 and suppose there is an overflow at time
t
. The
overflow is preceded by a period of continuous utilization of the processor. Further-
more, from a certain point
t
on (
t
<t
), only instances of tasks ready at
t
or later
and having deadlines less than or equal to
t
are run. Let
C
be the total execution time
demanded by these instances. Since there is an overflow at time
t
, we must have
If
. Assume
U
p
+
U
s
≤
t
<C.
t
−
We also know that
t
C
i
+
C
ape
n
t
−
C
≤
T
i
i
=1
n
t
t
−
t
)
U
s
≤
C
i
+(
t
−
T
i
i
=1
t
)(
U
p
+
U
s
)
.
≤
(
t
−
Thus, it follows that
U
p
+
U
s
>
1
,
Search WWH ::
Custom Search