Hardware Reference
In-Depth Information
Theorem 4.4 (Bini and Buttazzo, 2004)
A set of fully preemptive periodic tasks can
be scheduled by a fixed priority algorithm if and only if
∀
i
=1
,...,n
∃
t
∈TS
i
:
W
i
(
t
)
≤
t.
(4.23)
An advantage of Equation (4.23) is that it can be formulated as the union of a set
of simpler conditions, leading to a more efficient guarantee test, named the Hyper-
planes test [BB04]. The test has still a pseudo-polynomial complexity, but runs much
quicker than the response time analysis in the average case. Moreover, a novel fea-
ture of this test is that it can be tuned using a parameter to balance acceptance ratio
versus complexity. Such a tunability property is important in those cases in which
the performance of a polynomial time test is not sufficient for achieving high proces-
sor utilization, and the overhead introduced by exact tests is too high for an online
admission control.
Another advantage of this formulation is that Equation (4.23) can be manipulated to
describe the feasibility region of the task set in a desired space of design parameters,
so enabling sensitivity analysis [BDNB08], which determines how to change task set
parameters when the schedule is infeasible.
4.6
EDF WITH CONSTRAINED DEADLINES
Under EDF, the analysis of periodic tasks with deadlines less than or equal to periods
can be performed using the
processor demand
criterion. This method has been de-
scribed by Baruah, Rosier, and Howell in [BRH90] and later used by Jeffay and Stone
[JS93] to account for interrupt handling costs under EDF.
4.6.1
THE PROCESSOR DEMAND APPROACH
In general, the processor demand of a task
τ
i
in an interval [
t
1
,t
2
] is the amount of
processing time
g
i
(
t
1
,t
2
) requested by those instances of
τ
i
activated in [
t
1
,t
2
] that
must be completed in [
t
1
,t
2
]. That is,
g
i
(
t
1
,t
2
)=
C
i
.
r
i,k
≥t
1
,d
i,k
≤t
2
Search WWH ::
Custom Search