Hardware Reference
In-Depth Information
9.3.2
SCHEDULABILITY ANALYSIS
Although a reservation is typically implemented using a server characterized by a
budget
Q
k
and a period
T
k
, there are cases in which temporal isolation can be achieved
by executing tasks in a static partition of disjoint time slots.
To characterize a bandwidth reservation independently on the specific implementation,
Mok et al. [MFC01] introduced the concept of
bounded delay partition
that describes
a reservation by two parameters: a bandwidth
α
k
and a delay Δ
k
. The bandwidth
α
k
measures the fraction of resource that is assigned to the served tasks, whereas the
delay Δ
k
represents the longest interval of time in which the resource is not available.
In general, the minimum service provided by a resource can be precisely described
by its
supply function
[LB03, SL03], representing the minimum amount of time the
resource can provide in a given interval of time.
Definition 9.4
Given a reservation, the
supply function
Z
k
(
t
)
is the minimum amount
of time provided by the reservation in every time interval of length
t
≥
0
.
The supply function can be defined for many kinds of reservations, as static time
partitions [MFC01, FM02], periodic servers [LB03, SL03], or periodic servers with
arbitrary deadline [EAL07]. Consider, for example, that processing time is provided
only in the intervals illustrated in Figure 9.18, with a period of 12 units. In this case,
the minimum service occurs when the resource is requested at the beginning of the
longest idle interval; hence, the supply function is the one depicted in Figure 9.19.
0
3
6
9
12
15
18
21
24
Figure 9.18
A reservation implemented by a static partition of intervals.
For this example we have
α
k
=0
.
5 and Δ
k
=3. Once the bandwidth and the delay
are computed, the supply function of a resource reservation can be lower bounded by
the following
supply bound function
:
def
=max
sbf
k
(
t
)
{
0
,α
k
(
t
−
Δ
k
)
}
.
(9.13)
represented by the dashed line in Figure 9.19. The advantage of using such a lower
bound instead of the exact
Z
k
(
t
) is that a reservation can be expressed with just two
parameters.
Search WWH ::
Custom Search