Hardware Reference
In-Depth Information
As another example, if tasks are allowed to change their frequency and
τ
3
reduces its
period to 50, no feasible schedule exists, since the utilization would be greater than 1:
10
20
+
10
40
+
15
50
=1
.
05
>
1
.
Note that a feasible schedule exists for
T
1
=22,
T
2
=45, and
T
3
=50. Hence, the
system can accept the higher request rate of
τ
3
by slightly decreasing the rates of
τ
1
and
τ
2
. Task
τ
3
can even run with a period
T
3
=40, since a feasible schedule exists
with periods
T
1
and
T
2
within their range. In fact, when
T
1
=24,
T
2
=50, and
T
3
=40,
U
p
=0
.
992. Finally, note that if
τ
3
requires to run at its minimum period
(
T
3
=35), there is no feasible schedule with periods
T
1
and
T
2
within their range,
hence the request of
τ
3
to execute with a period
T
3
=35must be rejected.
U
p
=
Clearly, for a given value of
T
3
, there can be many different period configurations
that lead to a feasible schedule; thus one of the possible feasible configurations must
be selected. The elastic approach provides an efficient way for quickly selecting a
feasible period configuration among all the possible solutions.
THE ELASTIC MODEL
The basic idea behind the elastic model is to consider each task as flexible as a spring
with a given rigidity coefficient and length constraints. In particular, the utilization of
a task is treated as an elastic parameter, whose value can be modified by changing the
period within a specified range.
Each task is characterized by four parameters: a computation time
C
i
, a nominal pe-
riod
T
i
0
(considered as the minimum period), a maximum period
T
i
max
, and an elastic
coefficient
E
i
≥
0, which specifies the flexibility of the task to vary its utilization for
adapting the system to a new feasible rate configuration. The greater
E
i
, the more
elastic the task. Thus, an elastic task is denoted as
τ
i
(
C
i
,T
i
0
,T
i
max
,E
i
)
.
In the following,
T
i
will denote the actual period of task
τ
i
, which is constrained to be
in the range [
T
i
0
,T
i
max
]. Any task can vary its period according to its needs within
the specified range. Any variation, however, is subject to an
elastic
guarantee and is
accepted only if there is a feasible schedule in which all the other periods are within
their range.
Under the elastic model, given a set of
n
periodic tasks with utilization
U
p
>U
max
,
the objective of the guarantee is to compress tasks' utilization factors to achieve a new
desired utilization
U
d
≤
U
max
such that all the periods are within their ranges.
Search WWH ::
Custom Search