RESOURCE ACCESS PROTOCOLS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 246

7.9 SCHEDULABILITY ANALYSIS

This section explains how to verify the feasibility of a periodic task set in the presence
of shared resources. All schedulability tests presented in Chapter 4 for independent
tasks can be extended to include blocking terms, whose values depend on the specific
concurrency control protocol adopted in the schedule.

In general, all the extended tests guarantee one task τ i at the time, by inflating its
computation time C i by the blocking factor B i . In addition, all the guarantee tests that
were necessary and sufficient under preemptive scheduling become only sufficient in
the presence of blocking factors, since blocking conditions are derived in worst-case
scenarios that differ for each task and could never occur simultaneously.

Liu and Layland test for Rate Monotonic. A set of periodic tasks with blocking
factors and relative deadlines equal to periods is schedulable by RM if

C h
T h

+ C i + B i
T i

i (2 1 /i ∀ i =1 ,...,n ≤ − 1) . (7.19)

h : P h >P i

Liu and Layland test for EDF. A set of periodic tasks with blocking factors and
relative deadlines equal to periods is schedulable by EDF if

C h
T h

+ C i + B i
T i

∀ i =1 ,...,n ≤ 1 . (7.20)

h : P h >P i

Hyperbolic Test. Using the Hyperbolic Bound, a task set with blocking factors and
relative deadlines equal to periods is schedulable by RM if

C h
T h

+1 C i + B i
T i

+1

∀ i =1 ,...,n ≤ 2 . (7.21)

h : P h >P i

Response Time Analysis. Under blocking conditions, the response time of a generic
task τ i with a fixed priority can be computed by the following recurrent relation:
⎧
⎨ R (0)

i

= C i + B i

R ( s− 1)
i
T h

C h .

+
h : P h >P i

(7.22)

R ( s )
i

⎩ = C i + B i