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

Hence, s i,k can be computed with the following recurrent relation:

⎧
⎨

+
h : P h >P i

s (0)
i,k

= B i C h

s ( − 1)
i,k
T h

+1 C h .

(8.4)

1) C i +
h : P h >P i

⎩

s ( )
i,k

= B i +( k −

Since, once started, the task cannot be preempted, the finishing time f i,k can be com-

puted as

f i,k = s i,k + C i . (8.5)

Hence, the response time of task τ i

is given by

R i =max

k∈ [1 ,K i ] {

f i,k −

( k

−

1) T i }

.

(8.6)

Once the response time of each task is computed, the task set is feasible if and only if

∀ i =1 ,...,n R i ≤ D i . (8.7)

Yao, Buttazzo, and Bertogna [YBB10a] showed that the analysis of non-preemptive
tasks can be reduced to a single job, under specific (but not too restrictive) conditions.

Theorem 8.1 (Yao, Buttazzo, and Bertogna, 2010) The worst-case response time of
a non-preemptive task occurs in the first job if the task is activated at its critical instant
and the following two conditions are both satisfied:

1. the task set is feasible under preemptive scheduling;

2. relative deadlines are less than or equal to periods.

Under these conditions, the longest relative start time S i of task τ i is equal to s i, 1 and
can be computed from Equation (8.4) for k =1:

S i
T h

+1 C h .

S i = B i +
h : P h >P i

(8.8)

Hence, the response time R i is simply:

R i = S i + C i . (8.9)