Hardware Reference
In-Depth Information
Algorithm: SelectEPP
(
τ
i
,
Q
i
)
Input:
for task
τ
i
Output:
The set of EPPs for task
τ
i
(1)
{
C
i
,T
i
,D
i
,Q
i
}
begin
;
C
0
:= 0;
Prev
k
:=
{
δ
0
}
//
Initialize variables
(2)
for
(
k
:= 1
to
N
)
do
//
For all PPPs
(3)
Remove from
Prev
k
all
δ
j
violating (8.39);
(4)
if
(
Prev
k
=
∅
)
then
(5)
return
(INFEASIBLE);
(6)
end
(7)
Compute
C
k
using Equation (8.41);
(8)
Store
δ
Prev
(
δ
k
);
(9)
Prev
k
:=
Prev
k
∪{
δ
k
}
;
(10)
end
(11)
δ
j
:=
δ
Prev
(
δ
N
);
(12)
while
(
δ
j
=
∅
)
do
(13)
Select the PPP at the end of
δ
Prev
(
δ
j
);
(14)
δ
j
←
δ
Prev
(
δ
j
);
(15)
end
(16)
return
(FEASIBLE);
(17)
end
(18)
Figure 8.16
Algorithm for selecting the optimal preemption points.
8.7
ASSESSMENT OF THE APPROACHES
The limited preemption methods presented in this chapter can be compared under
several aspects, such as the following
Implementation complexity.
Predictability in estimating the preemption cost.
Effectiveness in reducing the number of preemptions.
Search WWH ::
Custom Search