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