Priority inherance issue

Manuel Coutinho manuel.coutinho at
Tue May 19 09:37:56 UTC 2009


I've already placed up for discussion, but it was thought that by activating
strict order mutex would solve this.
Just tried to test in RTEMS 4.9.2 with strict order and the result is not

So, the issue is that when using semaphore priority inherence protocol, the
taskA priority (task which holds the semaphore) must be equal to the highest
priority of the task blocked on any of the semaphores that taskA holds.

Currently, this does not happen in RTEMS.

My guess to solve this issue, is that when a semaphore is released, the new
priority of the calling thread (lets call it thread A) must be searched
through a list (or chain) of all the threads blocked on other semaphores
that thread A holds.

Of course, also, if a thread which is blocked on semaphore is deleted, it
has to be removed from that list.

The list has some design compromises. It would be good that insertions and
deletions took O(1), but to make this the list has to be ordered by threads
priority. This can be done by a vector with 256 positions, just like the
thread ready queue. But this can cause a great overhead in terms of memory
-> each mutex needs an additional 256 * 4 bytes (1 KiB) for this list.
I would propose that the list be composed by a chain with the chain handler,
ordered by priority. This would make insertions O(n) but when a semaphore is
released the priority would be quick to obtain. Deletions would also be O(n)
with this solution, but it is not expected that there would be too many
threads deletions at all during the execution of a real-time system (at
least, hard real-time).

What do you think?
Is this an issue worth solving?
Is my "solution" in fact a solution? If so, is it a good approach?

Kind Regards
Manuel Coutinho

More information about the users mailing list