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

factors of tasks that do not use nested critical sections. In this case, in fact, Lemma 7.2
guarantees that no transitive inheritance can occur; thus, the analysis of all possible
blocking conditions is simplified.

Using the terminology introduced in Section 7.3, in the absence of transitive blocking,
the set γ i of critical sections that can block a task τ i can be computed as follows:

1. The set of semaphores that can cause direct blocking to τ i , shared by the lower-
priority task τ j ,is

σ dir
i,j

= σ i ∩ σ j .

2. The set of semaphores that can cause push-through blocking to τ i , shared by the
lower-priority task τ j ,is

=
h : P h >P i

σ pt
i,j

σ h ∩ σ j .

3. The set of semaphores that can block τ i (either directly or by push-through),

shared by the lower-priority task τ j ,is

=
h : P h ≥P i

σ pt
i,j

= σ dir σ i,j

i,j ∪

σ h ∩ σ j .

4. The set of the longest critical sections used by τ j that can block τ i (either directly

or by push-through) is then

γ i,j = { Z j,k | ( P j <P i ) and ( R k ∈ σ i,j } .

5. The set of all critical sections that can block τ i (either directly or by push-

through) is

=
j : P j <P i

γ i γ i,j .

6. B i is then given by the largest sum of the lengths of the α i critical sections in
γ i . Note that since τ i cannot be blocked twice by the same task or by the same
semaphore, the sum should contain only terms δ j,k referring to different tasks

and different semaphores.

Unfortunately, even without considering nested resources, the exact computation of
each blocking factor requires a combinatorial search for finding the largest sum among
all possible α i durations. A simpler upper bound, however, can be computed according
to the following algorithm: