Hardware Reference
In-Depth Information
Note that the
U
ski
p
factor represents the net bandwidth really used by periodic tasks,
under the deeply-red condition. It is easy to show that
U
skip
p
≤
U
p
. In fact, according
to Equation (9.25) (setting
S
i
=
∞
),
U
p
can also be defined as
i
T
i
C
i
L
⎧
⎨
⎫
⎬
U
p
=max
L≥
0
.
⎩
⎭
Thus,
U
skip
p
≤
U
p
because
L
T
i
L
T
i
S
i
L
T
i
.
−
≤
The bandwidth saved by skips can easily be exploited by an aperiodic server to ad-
vance the execution of aperiodic tasks. The following theorem ([CB97]) provides a
sufficient condition for guaranteeing a hybrid (periodic and aperiodic) task set.
Theorem 9.7
Given a set of periodic tasks that allow skip with equivalent utilization
U
ski
p
and a set of soft aperiodic tasks handled by a server with utilization factor
U
s
,
the hybrid set is schedulable by EDF if
U
skip
p
+
U
s
≤
1
.
(9.26)
The fact that the condition of Theorem 9.7 is not necessary is a direct consequence
of the “granular” distribution of the spare time produced by skips. In fact, a fraction
of this spare time is uniformly distributed along the schedule and can be used as an
additional free bandwidth (
U
p
−
U
ski
p
) available for aperiodic service. The remaining
portion is discontinuous, and creates a kind of “holes” in the schedule, which can only
be used in specific situations. Whenever an aperiodic request falls into some hole, it
can exploit a bandwidth greater than 1
U
skip
p
−
. Indeed, it is easy to find examples of
U
skip
p
feasible task sets with a server bandwidth
U
s
>
1
−
. The following theorem
([CB97]) gives a maximum bandwidth
U
max
s
above which the schedule is certainly
not feasible.
Theorem 9.8
Given a set
Γ
of
n
periodic tasks that allow skips and an aperiodic
server with bandwidth
U
s
, a necessary condition for the feasibility of
Γ
is
U
s
≤
U
max
s
where
n
C
i
T
i
S
i
U
max
s
=1
−
U
p
+
.
(9.27)
i
=1
Search WWH ::
Custom Search