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

7.7.4 IMPLEMENTATION CONSIDERATIONS

The major implication of the Priority Ceiling Protocol in kernel data structures is that
semaphores queues are no longer needed, since the tasks blocked by the protocol can
be kept in the ready queue. In particular, whenever a task τ i is blocked by the protocol
on a semaphore S k , the task τ h that holds S k inherits the priority of τ i and it is assigned
to the processor, whereas τ i

returns to the ready queue. As soon as τ h unlocks S k , p h

is updated and, if p h becomes less than the priority of the first ready task, a context

switch is performed.

To implement the Priority Ceiling Protocol, each semaphore S k has to store the identi-
fier of the task that holds the lock on S k and the ceiling of S k . Moreover, an additional
field for storing the task active priority has to be reserved in the task control block. It is
also convenient to have a field in the task control block for storing the identifier of the
semaphore on which the task is blocked. Finally, the implementation of the protocol
can be simplified if the system also maintains a list of currently locked semaphores,
ordered by decreasing priority ceilings. This list is useful for computing the maximum
priority ceiling that a task has to overcome to enter a critical section and for updating
the active priority of tasks at the end of a critical section.

If the kernel data structures are extended as described above, the primitives pc wait
and pc signal for realizing the Priority Ceiling Protocol can be defined as follows.

pc wait(s)

Find the semaphore S ∗ having the maximum ceiling C ∗ among all the semaphores
currently locked by tasks other than the one in execution ( τ exe ).

C ∗ , transfer P exe to the task that holds S ∗ , insert τ exe in the ready
queue, and execute the ready task (other than τ exe ) with the highest priority.

If p exe ≤

If p exe >C ∗ , or whenever s is unlocked, lock semaphore s , add s in the list of
currently locked semaphores and store τ exe

in s.holder .

pc signal(s)

Extract s from the list of currently locked semaphores.

If no other tasks are blocked by τ exe , set p exe = P exe , else set p exe to the highest
priority of the tasks blocked by τ exe .