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

8.6.1 SELECTION ALGORITHM

First of all, it is worth noting that minimizing the number of EPPs does not necessarily
minimize the overall preemption overhead. In fact, there are cases in which inserting
more preemption points, than the minimum number, could be more convenient to take
advantage of points with smaller cost.

Consider, for instance, the task illustrated in Figure 8.15, consisting of 6 basic blocks,
whose total execution time in non preemptive mode is equal to C N i =20. The num-
bers above each PPP in Figure 8.15(a) denote the preemption cost; that is, the over-
head that would be added to C NP

i if a preemption occurred in that location. Assuming
a maximum non-preemptive interval Q =12, a feasible schedule could be achieved
by inserting a single preemption point at the end of δ 4 , as shown in Figure 8.15(b). In

fact, k =1 b k = 3+3+3+2=11 Q , and ξ 4 + k =5 b k = 3+3+6=12 Q ,

leading to a feasible schedule. This solution is characterized by a total preemption
overhead of 3 units of time (shown by the gray execution area). However, selecting
two EPPs, one after δ 1 and another after δ 5 , a feasible solution is achieved with a
smaller total overhead ξ 1 + ξ 5 =1+1=2, as shown in Figure 8.15(c). In general,
for tasks with a large number of basic blocks with different preemption cost, finding
the optimal solution is not trivial.

≤ ≤

Q =12

1 2 3 3 1

τ i δ 1 δ 2 δ 3 δ 4 δ 5 δ 6

C NP
i

=20

(a) Task with 6 basic blocks.

ξ 4 Overhead = 3

τ i

δ 1 δ 2 δ 3 δ 4 δ 5 δ 6

q 1 =11 q 2 =12

(b) Task with a single preemption point.

ξ 1 ξ 5 Overhead = 2

τ i δ 1 δ 2 δ 3 δ 4 δ 5 δ 6

q 1 =3 q 2 =12 q 3 =7

(c) Task with two preemption points.

Figure 8.15 : the first minimizes

the number of EPPs, while the second minimizes the overall preemption cost.

Two solutions for selecting EPPs in a task with Q =12