In detail: does a task inherit the priority ceiling, only when it is executing the critical section or already when it is selected to run the critical section next (after being blocked for example). I could not find the answer to this question in the papers I have read, some of them are:

  • "Real-time synchronization protocols for shared memory multiprocessors" by Rajkumar
  • "Improved Blocking Time Analysis and Evaluation for the Multiprocessor Priority Ceiling Protocol" by Yang et al.
  • "Synchronizations: Shared Resource Access Protocols" by Midonnet et al.

The second paper (Yang et al.) states:

Further, if the queue on ρk is not empty when Ji attempts to release ρk , the head of the queue is granted to lock ρk , otherwise, ρk is released.

My third source (Midonnet et al.) writes:

The tasks in the queue are sorted by priority, the highest priority task being the one which will be able to execute its critical section when RG l is freed

The previous two statements made me believe that the blocked tasks do inherit the priority ceiling immediately when the lock on the shared resource is released, but I'm not sure if this is really what is meant by them.


Consider the following example: Three tasks T1, T2, T3 (with priorities P1 > P2 > P3) run on two processors: T1 on p1 and T2, T3 on p2. T1 and T3 access a global resource R protected by a semaphore using the MPCP. Following timeline:

| t |       p1       |                           p2                          |
|:-:|:--------------:|:-----------------------------------------------------:|
| 1 |     T1 runs    |                        T3 runs                        |
| 2 |  T1 accesses R |                     T3 accesses R                     |
| 3 | T1  acquires R |                    T3 gets blocked                    |
| 4 | T1 executes CS |               T2 gets activated and runs              |
| 5 |  T1 releases R | Does T3 inherit the priority ceiling and preempt T2?  |

At t=5, T1 releases the semaphore on which T3 is blocked. Does T3 inherit the priority ceiling immediately and thus preempt T2 or is T3 placed in a waiting queue of p2 and inherits the priority ceiling once it is scheduled on the given processor and thus is able to execute the critical section?

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.