Hardware Reference
In-Depth Information
the following utilization:
U
d
+
U
f
)
E
i
E
v
∀
τ
i
∈
U
i
=
U
i
0
−
(
U
v
0
−
Γ
v
(9.38)
where
U
v
0
=
τ
i
∈
Γ
v
U
i
0
(9.39)
U
f
=
τ
i
∈
Γ
f
U
i
min
(9.40)
E
v
=
τ
i
∈
Γ
v
E
i
.
(9.41)
If there are tasks for which
U
i
<U
i
min
, then the period of those tasks has to be fixed
at its maximum value
T
i
max
(so that
U
i
=
U
i
min
), sets Γ
f
and Γ
v
must be updated
(hence,
U
f
and
E
v
recomputed), and Equation (9.38) applied again to the tasks in Γ
v
.
If there is a feasible solution, that is, if the desired utilization
U
d
is greater than or
equal to the minimum possible utilization
U
min
=
i
=1
C
i
T
i
max
, the iterative process
ends when each value computed by Equation (9.38) is greater than or equal to its
corresponding minimum
U
i
min
. The algorithm
2
for compressing a set Γ of
n
elastic
tasks up to a desired utilization
U
d
is shown in Figure 9.29.
DECOMPRESSION
All tasks' utilizations that have been compressed to cope with an overload situation
can return toward their nominal values when the overload is over. Let Γ
c
be the subset
of compressed tasks (that is, the set of tasks with
T
i
>T
i
0
), let Γ
a
be the set of
remaining tasks in Γ (that is, the set of tasks with
T
i
=
T
i
0
), and let
U
d
be the current
processor utilization of Γ. Whenever a task in Γ
a
voluntarily increases its period, all
tasks in Γ
c
can expand their utilizations according to their elastic coefficients, so that
the processor utilization is kept at the value of
U
d
.
Now, let
U
c
be the total utilization of Γ
c
, let
U
a
be the total utilization of Γ
a
after
some task has increased its period, and let
U
c
0
be the total utilization of tasks in Γ
c
at
their nominal periods. It can easily be seen that if
U
c
0
+
U
a
≤
U
lub
, all tasks in Γ
c
can return to their nominal periods. On the other hand, if
U
c
0
+
U
a
>U
lub
, then the
release operation of the tasks in Γ
c
can be viewed as a compression, where Γ
f
=Γ
a
and Γ
v
=Γ
c
. Hence, it can still be performed by using Equations (9.38), (9.40) and
(9.41) and the algorithm presented in Figure 9.29.
2
The actual implementation of the algorithm contains more checks on tasks' variables, which are not
shown here in order to simplify its description.
Search WWH ::
Custom Search