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

τ 1 τ 2 τ n

Figure 7.16 Deadlock among n tasks.

however, by the transitivity of the protocol, task τ n would inherit the priority of τ 1 ,
which is assumed to be higher than P n . This contradicts Lemma 7.6, and hence the
theorem follows.

Theorem 7.4 (Sha, Rajkumar, Lehoczky) Under the Priority Ceiling Protocol, a task
τ i can be blocked for at most the duration of one critical section.

Proof. Suppose that τ i is blocked by two lower-priority tasks τ 1 and τ 2 , where
P 2 <P 1 <P i . Let τ 2 enter its blocking critical section first, and let C 2 be the
highest-priority ceiling among all the semaphores locked by τ 2 . In this situation, if
task τ 1 >C 2 . Moreover, since we enters its critical section we must have that P 1

C 2 . This means that

assumed that τ i can be blocked by τ 2 , we must have that P i ≤

C 2

P i ≤ <P 1 . This contradicts the assumption that P i >P 1 . Thus, the theorem

follows.

7.7.3 BLOCKING TIME COMPUTATION

The evaluation of the maximum blocking time for each task can be computed based
on the result of Theorem 7.4. According to this theorem, a task τ i can be blocked for
at most the duration of the longest critical section among those that can block τ i . The
set of critical sections that can block a task τ i

is identified by the following lemma.

Lemma 7.8 Under the Priority Ceiling Protocol, a critical section z j,k (belonging

to task τ j and guarded by semaphore S k ) can block a task τ i only if P j <P i and

C ( S k ) ≥ P i .

Proof. Clearly, if P j ≥ P i , τ i cannot preempt τ j and hence cannot be blocked on z j,k .

Now assume P j <P i and C ( S k ) <P i , and suppose that τ i is blocked on z j,k .We