Hardware Reference
In-Depth Information
idle
τ
i
τ
k
deadline miss
τ
ov
τ
m
t
t
1
2
Figure 4.12
Interval of continuous utilization in an EDF schedule before a deadline miss.
If
. We show the sufficiency by contradiction. Assume that the condition
U<
1 is
satisfied and yet the task set is not schedulable. Let
t
2
be the first instant at which
a deadline is missed and let [
t
1
,t
2
] be the longest interval of continuous utilization,
before
t
2
, such that only instances with deadline less than or equal to
t
2
are executed
in [
t
1
,t
2
] (see Figure 4.12 for explanation). Note that
t
1
must be the release time of
some periodic instance. Let
C
p
(
t
1
,t
2
) be the total computation time demanded by
periodic tasks in [
t
1
,t
2
], which can be computed as
t
2
−
C
i
.
n
C
p
(
t
1
,t
2
)=
r
k
≥t
1
,d
k
≤t
2
t
1
C
k
=
(4.15)
T
i
i
=1
Now, observe that
t
2
−
C
i
n
n
t
1
t
2
−
t
1
C
p
(
t
1
,t
2
)=
≤
C
i
=
t
2
−
t
1
)
U.
T
i
T
i
i
=1
i
=1
Since a deadline is missed at
t
2
,
C
p
(
t
1
,t
2
) must be greater than the available processor
time (
t
2
−
t
1
); thus, we must have
(
t
2
−
t
1
)
<C
p
(
t
1
,t
2
)
≤
(
t
2
−
t
1
)
U.
That is,
U>
1, which is a contradiction.
Search WWH ::
Custom Search