Hardware Reference
In-Depth Information
The following lemma provides a simple guarantee test for verifying the feasibility of
a task set consisting of hard and soft tasks.
Lemma 6.6
Given a set of
n
periodic hard tasks with processor utilization
U
p
and a
set of
m
CBSs with processor utilization
U
s
=
i
=1
U
s
i
, the whole set is schedulable
by EDF
if
and
only if
U
p
+
U
s
≤
1
.
The isolation property allows us to use a bandwidth reservation strategy to allocate
a fraction of the CPU time to soft tasks whose computation time cannot be easily
bounded. The most important consequence of this result is that soft tasks can be
scheduled together with hard tasks without affecting the a priori guarantee, even in the
case in which the execution times of the soft tasks are not known or the soft requests
exceed the expected load.
In addition to the isolation property, the CBS has the following characteristics.
The CBS behaves as a plain EDF algorithm if the served task
τ
i
has parameters
(
C
i
,T
i
) such that
C
i
≤
Q
s
and
T
i
=
T
s
. This is formally stated by the following
lemma.
Lemma 6.7
A hard task
τ
i
with parameters (
C
i
,T
i
) is schedulable by a CBS
with parameters
Q
s
≥
C
i
and
T
s
=
T
i
if and only if
τ
i
is schedulable with EDF.
Proof.
For any job of a hard task we have that
r
i,j
+1
−
Q
s
.
Hence, by definition of the CBS, each hard job is assigned a deadline
d
i,j
=
r
i,j
+
T
i
r
i,j
≥
T
i
and
c
i,j
≤
Q
s
, each
job finishes no later than the budget is exhausted; hence the deadline assigned to
a job is never postponed and is exactly the same as the one used by EDF.
and it is scheduled with a budget
Q
s
≥
C
i
. Moreover, since
c
i,j
≤
The CBS automatically reclaims any spare time caused by early completions.
This is due to the fact that whenever the budget is exhausted, it is always imme-
diately replenished at its full value and the server deadline is postponed. In this
way, the server remains eligible and the budget can be exploited by the pending
requests with the current deadline.
This is the main difference with respect to the
processor capacity reserves
proposed by Mercer et al. [MST93, MST94a].
Knowing the statistical distribution of the computation time of a task served by a
CBS, it is possible to perform a QoS guarantee based on probabilistic deadlines
(expressed in terms of probability for each served job to meet a deadline). Such
a statistical analysis is presented by Abeni and Buttazzo [AB98, AB04].
Search WWH ::
Custom Search