Hardware Reference
In-Depth Information
Proof.
The theorem is proved by showing that for any type of service, SS exhibits
an execution behavior equivalent to one or more periodic tasks. Let
t
A
be the time at
which
C
s
is full and SS becomes active, and let
t
I
be the time at which SS becomes
idle, such that [
t
A
,t
I
] is a continuous interval during which SS remains active. The
execution behavior of the server in the interval [
t
A
,t
I
] can be described by one of the
following three cases (see Figure 5.19):
1. No capacity is consumed.
2. The server capacity is totally consumed.
3. The server capacity is partially consumed.
Case 1.
If no requests arrive in [
t
A
,t
I
], SS preserves its capacity and no replen-
ishments can be performed before time
t
I
+
T
s
. This means that at most
C
s
units of aperiodic time can be executed in [
t
A
,t
I
+
T
s
]. Hence, the
SS behavior is identical to a periodic task
τ
s
(
C
s
,T
s
) whose release time
is delayed from
t
A
to
t
I
. As proved in Chapter 4 for RM, delaying the
release of a periodic task cannot increase the response time of the other
periodic tasks; therefore, this case does not jeopardize schedulability.
Case 2.
If
C
s
is totally consumed in [
t
A
,t
I
], a replenishment of
C
s
units of time
will occur at time
t
A
+
T
s
. Hence, SS behaves like a periodic task with
period
T
s
and execution time
C
s
released at time
t
A
.
Case 3.
If
C
s
is partially consumed in [
t
A
,t
I
], a replenishment will occur at time
t
A
+
T
s
, and the remaining capacity is preserved for future requests. Let
C
R
be the capacity consumed in [
t
A
,t
I
]. In this case, the behavior of
the server is equivalent to two periodic tasks,
τ
x
and
τ
y
, with periods
T
x
=
T
y
=
T
s
, and execution times
C
x
=
C
R
and
C
y
=
C
s
−
C
R
,
such that
τ
x
is released at
t
A
and
τ
y
is delayed until
t
I
. As in Case 1,
the delay of
τ
y
has no schedulability effects.
Since in any servicing situation SS can be represented by one or more periodic tasks
with period
T
s
and total execution time equal to
C
s
, the contribution of SS in terms of
processor utilization is equal to
U
s
=
C
s
/T
s
. Hence, from a schedulability point of
view, SS can be replaced by a periodic task having the same utilization factor.
Since SS behaves like a normal periodic task, the periodic task set can be guaranteed
by the same schedulability test derived for the Polling Server. Hence, a set Γ of
n
Search WWH ::
Custom Search