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

8.4.1 FEASIBILITY ANALYSIS

In the presence of non-preemptive intervals, a task can be blocked when, at its arrival, a
lower priority task is running in non-preemptive mode. Since each task can be blocked
at most once by a single lower priority task, B i is equal to the longest non-preemptive
interval belonging to tasks with lower priority. In particular, the blocking factor can
be computed as

B i =max

j : P j <P i {

q j − 1 } . (8.19)

Note that under the floating model one unit of time must be subtracted from q j to
allow the non-preemptive region to start before τ i . Under the activation-triggered
model, however, there is no need to subtract one unit of time from q j , since the non-
preemptive interval is programmed to be exactly q j from the task arrival time. Then
schedulability can be checked through the response time analysis, by Equation (7.22),
or through the workload analysis, by Equation (7.23). Note that under the floating
model the analysis does not need to be carried out within the longest Level- i active
period. In fact, the worst-case interference on τ i

occurs in the first instance assuming

that τ i can be preempted an epsilon before its completion.

On the other hand, the analysis is more pessimistic under the activation-triggered
model, where non-preemptive intervals are exactly equal to q i units and can last until
the end of the task. In this case, the analysis does not take advantage of the fact that
τ i cannot be preempted when higher periodic tasks arrive q i units (or less) before its
completion. The advantage of such a pessimism, however, is that the analysis can be
limited to the first job of each task.

8.4.2 LONGEST NON-PREEMPTIVE INTERVAL

When using the deferred preemption method, an interesting problem is to find the
longest non-preemptive interval Q i for each task τ i that can still preserve the task set
schedulability. More precisely, the problem can be stated as follows:

Given a set of n periodic tasks that is feasible under preemptive scheduling,
find the longest non-preemptive interval of length Q i for each task τ i ,so
that τ i can continue to execute for Q i units of time in non-preemptive mode,
without violating the schedulability of the original task set.

This problem has been first solved under EDF by Baruah [Bar05], and then under fixed
priorities by Yao et al. [YBB09]. The solution is based on the concept of blocking
tolerance β i , for a task τ i , defined as follows: