Hardware Reference
In-Depth Information
8.6
SELECTING PREEMPTION POINTS
When a task set is not schedulable in non-preemptive mode, there are several ways to
split tasks into subtasks to generate a feasible schedule, if one exists. Moreover, as
already observed in Section 8.1, the runtime overhead introduced by the preemption
mechanism depends on the specific point where the preemption takes place. Hence,
it would be useful to identify the best locations for placing preemption points inside
each task to achieve a feasible schedule, while minimizing the overall preemption cost.
This section illustrates an algorithm [BXM + 11] that achieves this goal.
Considering that sections of code exist where preemption is not desirable (e.g., short
loops, critical sections, I/O operations, etc.), each job of τ i is assumed to consist of
a sequence of N i non-preemptive Basic Blocks (BBs), identified by the programmer
based on the task structure. Preemption is allowed only at basic block boundaries; thus
each task has N i
1 Potential Preemption Points (PPPs), one between any two con-
secutive BBs. Critical sections and conditional branches are assumed to be executed
entirely within a basic block. In this way, there is no need for using shared resource
protocols to access critical sections.
The goal of the algorithm is to identify a subset of PPPs that minimizes the overall
preemption cost, while achieving the schedulability of the task set. A PPP selected
by the algorithm is referred to as an Effective Preemption Point (EPP), whereas the
other PPPs are disabled. Therefore, the sequence of basic blocks between any two
consecutive EPPs forms a Non-Preemptive Region (NPR). The following notation is
used to describe the algorithm:
N i
denotes the number of BBs of task τ i , determined by the N i
1 PPPs defined
by the programmer;
p i
denotes the number of NPRs of task τ i , determined by the p i
1 EPPs selected
by the algorithm;
δ i,k
denotes the k -th basic block of task τ i ;
b i,k
denotes the WCET of δ i,k without preemption cost; that is, when τ i is executed
non-preemptively;
ξ i,k
denotes the worst-case preemption overhead introduced when τ i
is preempted
at the k -th PPP (i.e., between δ k
and δ k +1 );
q i,j
denotes the WCET of the j -th NPR of τ i , including the preemption cost;
q max
i
denotes the maximum NPR length for τ i :
p i
q max
i
=max
{
q i,j }
j =1 .
Search WWH ::




Custom Search