Hardware Reference
In-Depth Information
The new test can be compared with the Liu and Layland one in the task utilization
space, denoted as the U-space. Here, the Liu and Layland bound for RM is represented
by a
n
-dimensional plane that intersects each axis in
U
lub
(
n
)=
n
(2
1
/n
1). All
points below the RM surface represent periodic task sets that are feasible by RM. The
new bound expressed by equation (4.10) is represented by a
n
-dimensional hyperbolic
surface tangent to the RM plane and intersecting the axes for
U
i
=1(this is the reason
why it is referred to as the hyperbolic bound). Figure 4.11 illustrates such bounds for
n
=2. Notice that the asymptotes of the hyperbole are at
U
i
=
−
1. From the plots,
we can clearly see that the feasibility region below the H-bound is larger than that
below the LL-bound, and the gain is given by the dark gray area.
−
U
2
1
U
lub
(2)
H-bound
EDF-bound
LL-bound
U
lub
(2)
1
U
1
Figure 4.11
Schedulability bounds for RM and EDF in the utilization space.
It has been shown [BBB03] that the hyperbolic bound is tight, meaning that, if not
satisfied, it is always possible to construct an unfeasible task set with those utiliza-
tions. Hence, the hyperbolic bound is the best possible test that can be found using the
individual utilization factors
U
i
as a task set knowledge.
Moreover, the gain (in terms of schedulability) achieved by the hyperbolic test over
the classical Liu and Layland test increases as a function of the number of tasks, and
tends to
√
2 for
n
tending to infinity.
Search WWH ::
Custom Search