LIMITED PREEMPTIVE SCHEDULING - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 277

For a generic task, the worst-case execution time q of a NPR composed of the consec-
utive basic blocks δ j ,δ j +1 ,...,δ k can be expressed as

k

q = ξ j− 1 + b , (8.38)

= j

conventionally setting ξ 0 =0. Note that the preemption overhead is included in q .
Since any NPR of a feasible EPP selection has to meet the condition q

≤ Q , we must

have

k

ξ j− 1 + b ≤ Q.

(8.39)

= j

Now, let C k be the WCET of the chunk of code composed of the first k basic blocks
- that is, from the beginning of δ 1 until the end of δ k - including the preemption
overhead of the EPPs that are contained in the considered chunk. Then, we can express
the following recursive expression:

k

C k = C j− 1 + q = C j− 1 + ξ j− 1 +

b . (8.40)

= j

Note that since δ N is the last BB, the worst-case execution time C i of the whole task

is equal to C N .

τ i

The algorithm for the optimal selection of preemption points is based on the equations
presented above and its pseudo-code is reported in Figure 8.16. The algorithm eval-
uates all the BBs in increasing order, starting from the first one. For each BB δ k , the
feasible EPP selection that leads to the smallest possible C k

is computed as follows.

is given by the sum of the BB lengths k For the first BBs, the minimum C k

=1 b
as long as this sum does not exceed Q . Note that if b 1 >Q , there is no feasible PPP
selection, and the algorithm fails. For the following BBs, C k needs to consider the cost
of one or more preemptions as well. Let Prev k be the set of the preceding BBs δ j≤k
that satisfy Condition (8.39), i.e., that might belong to the same NPR of δ k . Again, if
ξ k− 1 + b k >Q , there is no feasible PPP activation, and the algorithm fails. Otherwise,
the minimum C k is given by

⎧
⎨

⎫
⎬

k

C k =min
δ j ∈Prev k

C j− 1 + ξ j− 1 +

b .

(8.41)

⎩ ⎭

= j