Hardware Reference
In-Depth Information
Let
δ
∗
(
δ
k
) be the basic block for which the rightmost term of Expression (8.41) is
minimum
⎧
⎨
⎫
⎬
k
C
j−
1
+
ξ
j−
1
+
δ
∗
(
δ
k
)=
min
δ
j
∈Prev
k
b
.
(8.42)
⎩
⎭
=
j
If there are many possible BBs minimizing (8.41), the one with the smallest index is
selected. Let
δ
Prev
(
δ
k
) be the basic block preceding
δ
∗
(
δ
k
), if one exists. The PPP at
the end of
δ
Prev
(
δ
k
) - or, equivalently, at the beginning of
δ
∗
(
δ
k
) - is meaningful for
the analysis, since it represents the last PPP to activate for minimizing the preemption
overhead of the first
k
basic blocks.
A feasible placement of EPPs for the whole task can then be derived with a recur-
sive activation of PPPs, starting with the PPP at the end of
δ
Prev
(
δ
N
), which will
be the last EPP of the considered task. The penultimate EPP will be the one at the
beginning of
δ
Prev
(
δ
Prev
(
δ
N
)), and so on. If the result of this recursive lookup of
function
δ
Prev
(
k
) is
δ
1
, the start of the program has been reached. A feasible place-
ment of EPPs has therefore been detected, with a worst-case execution time, including
preemption overhead, equal to
C
N
. This is guaranteed to be the placement that mini-
mizes the preemption overhead of the considered task, as proved in the next theorem.
Theorem 8.3 (Bertogna et al., 2011)
The PPP activation pattern detected by proce-
dure
SelectEPP
(
τ
i
,Q
i
)
minimizes the preemption overhead experienced by a task
τ
i
,
without compromising the schedulability.
The feasibility of a given task set is maximized by applying the
SelectEPP
(
τ
i
,Q
i
)
procedure to each task
τ
i
, starting from
τ
1
and proceeding in task order. Once the
optimal allocation of EPPs has been computed for a task
τ
i
, the value of the overall
WCET
C
i
=
C
N
can be used for the computation of the maximum allowed NPR
Q
i
+1
of the next task
τ
i
+1
, using the technique presented in Section 8.5.
The procedure is repeated until a feasible PPP activation pattern has been produced
for all tasks in the considered set. If the computed
Q
i
+1
is too small to find a feasible
EPP allocation, the only possibility to reach schedulability is by removing tasks from
the system, as no other EPP allocation strategy would produce a feasible schedule.
Search WWH ::
Custom Search