Hardware Reference
In-Depth Information
Algorithm
: Elastic compression(Γ
,U
d
)
Input
: A task set Γ and a desired utilization
U
d
<
1
Output
: A task set with modified periods such that
U
p
=
U
d
begin
U
min
:=
i
=1
C
i
/T
i
max
;
(1)
if
(
U
d
<U
min
) return(INFEASIBLE);
(2)
for
(
i
:= 1
to
n
)
U
i
0
:=
C
i
/T
i
0
;
(3)
do
(4)
U
f
:= 0;
U
v
0
:= 0;
E
v
:= 0;
(5)
for
(
i
:= 1
to
n
)
do
(6)
if
((
E
i
== 0)or(
T
i
==
T
i
max
))
then
(7)
U
f
:=
U
f
+
U
i
min
;
(8)
else
(9)
E
v
:=
E
v
+
E
i
;
(10)
U
v
0
:=
U
v
0
+
U
i
0
;
(11)
end
(12)
end
(13)
ok
:= 1;
(14)
for
(
each τ
i
∈
Γ
v
)
do
(15)
if
((
E
i
>
0) and (
T
i
<T
i
max
))
then
(16)
U
i
:=
U
i
0
−
(
U
v
0
−
U
d
+
U
f
)
E
i
/E
v
;
(17)
T
i
:=
C
i
/U
i
;
(18)
if
(
T
i
>T
i
max
)
then
(19)
T
i
:=
T
i
max
;
(20)
ok
:= 0;
(21)
end
(22)
end
(23)
end
(24)
while
(
ok
== 0);
(25)
return(FEASIBLE);
(26)
end
Figure 9.29
Algorithm for compressing a set of elastic tasks.
Search WWH ::
Custom Search