Hardware Reference
In-Depth Information
Therefore, a synchronous set of periodic tasks with relative deadlines less than or equal
to periods is schedulable by EDF if and only if
∀
t>
0
dbf
(
t
)
≤
t.
(4.26)
It is worth observing that, for the special case of tasks with relative deadlines equal
to periods, the test based on the processor demand criterion is equivalent to the one
based on the processor utilization. This result is formally expressed by the following
theorem [JS93].
Theorem 4.5 (Jeffay and Stone, 1993)
A set of periodic tasks with relative deadlines
equal to periods is schedulable by EDF if and only if
L
T
i
C
i
≤
n
∀
L>
0
L.
(4.27)
i
=1
Proof.
The theorem is proved by showing that equation (4.27) is equivalent to the
classical Liu and Layland's condition
n
C
i
T
i
≤
U
=
1
.
(4.28)
i
=1
(4.28)
⇒
(4.27). If
U
≤
1, then for all
L
,
L
≥
0,
L
T
i
C
i
≥
L
T
i
C
i
.
n
n
L
≥
UL
=
i
=1
i
=1
To demonstrate (4.28)
⇐
(4.27) we show that
¬
(4.28)
⇒¬
(4.27). That is, we assume
U>
1 and prove that there exist an
L
≥
0 for which (4.27) does not hold. If
U>
1,
then for
L
=
H
=
lcm
(
T
1
,...,T
n
),
H
T
i
C
i
=
H
T
i
C
i
.
n
n
H<HU
=
i
=1
i
=1
4.6.2
REDUCING TEST INTERVALS
In this section we show that the feasibility test expressed by condition (4.26) can be
simplified by reducing the number of intervals in which it has to be verified. We first
observe that
Search WWH ::
Custom Search