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

In order to realize this idea, each semaphore is assigned a priority ceiling equal to
the highest priority of the tasks that can lock it. Then, a task τ i is allowed to enter a
critical section only if its priority is higher than all priority ceilings of the semaphores
currently locked by tasks other than τ i .

7.7.1 PROTOCOL DEFINITION

The Priority Ceiling Protocol can be defined as follows:

Each semaphore S k is assigned a priority ceiling C ( S k ) equal to the highest
priority of the tasks that can lock it. Note that C ( S k ) is a static value that can be
computed off-line:

C ( S k ) de =ma i {

P i | S k ∈ σ i } . (7.13)

Let τ i be the task with the highest priority among all tasks ready to run; thus, τ i
is assigned the processor.

Let S ∗ be the semaphore with the highest ceiling among all the semaphores cur-
rently locked by tasks other than τ i and let C ( S ∗ ) be its ceiling.

To enter a critical section guarded by a semaphore S k , τ i must have a priority

higher than C ( S ∗ ).If P i ≤ C ( S ∗ ), the lock on S k is denied and τ i is said to be

blocked on semaphore S ∗ by the task that holds the lock on S ∗ .

When a task τ i is blocked on a semaphore, it transmits its priority to the task,
say τ j , that holds that semaphore. Hence, τ j resumes and executes the rest of its
critical section with the priority of τ i . Task τ j is said to inherit the priority of τ i .

In general, a task inherits the highest priority of the tasks blocked by it. That is,
at every instant,

p j ( R k )=max { P j , ma h { P h | τ h is blocked on R k }} . (7.14)

When τ j exits a critical section, it unlocks the semaphore and the highest-priority
task, if any, blocked on that semaphore is awakened. Moreover, the active priority
of τ j is updated as follows: if no other tasks are blocked by τ j , p j is set to the
nominal priority P j ; otherwise, it is set to the highest priority of the tasks blocked
by τ j , according to Equation (7.14).

Priority inheritance is transitive; that is, if a task τ 3 blocks a task τ 2 , and τ 2 blocks
a task τ 1 , then τ 3 inherits the priority of τ 1 via τ 2 .