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

blocked

τ 0

τ i

b

τ k

a

Figure 7.15 An absurd situation that cannot occur under the Priority Ceiling Protocol.

Lemma 7.6 If a task τ k is preempted within a critical section Z a by a task τ i that
enters a critical section Z b , then, under the Priority Ceiling Protocol, τ k cannot inherit
a priority higher than or equal to that of task τ i until τ i completes.

Proof. If τ k inherits a priority higher than or equal to that of task τ i before τ i

completes, there must exist a task τ 0 blocked by τ k , such that P 0 ≥ P i . This situation

is shown in Figure 7.15. However, this leads to the contradiction that τ 0 cannot be
blocked by τ k . In fact, since τ i enters its critical section, its priority must be higher
than the maximum ceiling C ∗ of the semaphores currently locked by all lower-priority
tasks. Hence, P 0 ≥ >C ∗ . But since P 0 >C ∗ , τ 0 P i cannot be blocked by τ k , and

the lemma follows.

Lemma 7.7 The Priority Ceiling Protocol prevents transitive blocking.

Proof. Suppose that a transitive block occurs; that is, there exist three tasks τ 1 , τ 2 ,
and τ 3 , with decreasing priorities, such that τ 3 blocks τ 2 and τ 2 blocks τ 1 . By the
transitivity of the protocol, τ 3 will inherit the priority of τ 1 . However, this contradicts
Lemma 7.6, which shows that τ 3 cannot inherit a priority higher than or equal to P 2 .

Thus, the lemma follows.

Theorem 7.3 The Priority Ceiling Protocol prevents deadlocks.

Proof. Assuming that a task cannot deadlock by itself, a deadlock can only be formed
by a cycle of tasks waiting for each other, as shown in Figure 7.16. In this situation,