On Thursday 08 November 2007, you wrote:

Luís Henriques wrote:

quoted

Maybe I didn't completely understood your question, but... if there is a
problem with SMP efficiency (I do not really know, but believe you :) )
with priority ceiling (PC) implementation, this problem should have been
already identified (and possibly solved) in the current PI
implementation, right?

To make it clear: I'm not aware of any efficiency issues with
the current PI implementation :-)


The (potential) efficiency issue with PC on SMP derives from the
dead-lock avoidance mechanism that you mentioned: If a task
locks a resource, then it's priority is raised to the ceiling
(which is typically the highest priority of all task sharing
that resource). Once that happens, no other task (sharing the
same resource) could then lock another resource that potentially
leads to a dead-lock situation.

Example:

* A low priority Task A shall share resources X and Y
   with a high priority Task B.

* Task A shall execute the following fraction of code:

     1. lock(X)
     2. lock(Y)

* Task B shall execute the following fraction of code:

     1. lock(Y)
     2. lock(X)

With PI, this could easily lead to a race condition resulting
in a dead-lock. But with PC, no dead-lock is possible: the very
moment Task A locks X, Task B won't be scheduled any more
(assuming a FIFO scheduling policy), because A would now run
at the same priority as B. If B takes Y, then lower priority A
wouldn't be scheduled anyway, because in a single CPU system,
only the highest priority task will actually run!

Fully agree!  Single CPU systems are great :)

On SMP systems, the situation is completely different, because
you can have two CPUs to run the tasks on: even if Task A running
on CPU 1 is boosted to the ceiling when it takes X, then Task B
on CPU 2 is not affected and could easily lock Y -> deadlock!

Now I see what you mean.  However, I guess the problem here is that, in the 
example you provide you are using nested locks and this is _always_ an issue.  
It is a known problem with the PI protocol.  Good practices in RT 
applications development say you should never do this.  Anyway, the main goal 
of PI and PC protocols is to avoid priority inversion, not dead-locks.

The only solution (i'm aware of) would be that when Task A locks
Y, then CPU 1 needs to inform CPU 2 to un-schedule Task B (if it's
currently running) or to mark Task-B as un-schedulable (if it's
not currently running), respectively. This way, Task B can't take
any shared resources (X or Y) while Task A holds X or Y. When
Task A frees the lock, CPU 1 has to tell CPU 2 to kick Task B again
(if it was put asleep) or to mark it as schedulable, respectivly.

I believe this could actually be implemented _but_ it might not be desirable 
to do it.  An in-deep analysis would be required to check this, but I believe 
the determinism of the system would suffer with this.

Effectivly, all Tasks using PC and sharing the same resources do
not perform any better than on a single CPU system because they
can't run in parallel on different CPUs. Even worse the notable
notification overhead could reduce performance dramatically for
heavyly contended locks!

Now my actual question was if there is any other resource
locking mechanism that inherently (by design) avoids dead-locks
and is proven to work on SMP?

Well... apart for good RT applications design and some schedulabity analysis, 
no, I don't know anything else.  I know there are several academic research 
(probably some implementations too, of course) on distributed systems locking 
mechanisms that deal with this issues but I am not familiar with those.

Note once again that the main goal of PI and PC protocols is not dead-locks 
avoidance but to prevent priority inversion.

quoted

(BTW, what do you think that should be the kernel behaviour when the
ceiling value is violated?  Typical solution in RTOS is to have a fatal
error)

Here's where i'm not exactly sure what you mean:

When you have a some kind of locking mechanism (a mutex, for example) that 
implements the PC protocol, you need to define a ceiling value for it.  This 
ceiling value is defined according to an analysis of your system and 
correspond to the highest priority task that can access this locking 
mechanism.  My question was: sometimes it may not be easy to define this 
value and, in runtime, the ceiling may be violated by a task that accesses 
this mutex.

You mean, if in the example above, a new yet higher priority Task C
would come in (sharing X or Y) and thus the ceiling value would
need to be (dynamically) changed? I don't think that would have
any implications for the case, above.

Well, but if you dynamically change the ceiling value, then we are talking 
about PI, right? :)

Best regards
-- 
Luís Henriques