PCP implementation

Till Straumann strauman at slac.stanford.edu
Mon Mar 27 19:34:11 UTC 2006

Joel Sherrill wrote:

> Till Straumann wrote:
>> I agree and I consider this a major design flaw.
>> Indeed: by looking at the source code and testing
>> your example I can confirm the documented
>> behavior.
>> Note that priority-inheriting binary semaphores
>> exhibit the same flaw.
>> When surrendering a priority-ceiling or -inheriting
>> mutex the executing task priority should be changed
>> to the highest priority (ceiling or inherited) of all currently
>> held mutexes.
> This is the designed and documented behavior.  To implement otherwise
> would require maintaining information on the set of held resources and
> analyzing that set each time a mutex is released.  The current design is
> an engineering tradeoff assuming that you don't nest lots

lots = 'more than 1'

> of PCP/PI mutexes
> and don't hold them for lengthy periods of time.

This is pretty strict. It is easy to imagine applications that violate this

> I recently thought about this and think  the "resources held set" 
> could be
> cheaply maintained but how you determine the appropriate priority when
> you release a mutex is still painful.  Even if you maintain the set as a
> stack/LIFO and imposed and enforced the rule that
> PCP/PI mutexes were released in the opposite order of acquisition,

stack approach would be easier but I don't like the necessary restriction.
It's easy to imagine situations where this restriction is not acceptable.

> I still think you would have to scan the set when you released a mutex
> to find out what the highest priority to inherit is.

You could keep the 'resources held list' sorted according to priority.
This makes releasing a semaphore cheaper/faster but OTOH,
the set would have to be re-ordered every  time another task
takes a member of the set. In some cases this might be better as
the extra time is spent when the resource is unavailable anyways.
Hard to argue the general case, however.

-- Till

> Any thoughts on an efficient way to implement the set management
> required is appreciated.  I have trouble seeing it as something that is
> constant order execution time.
> --joel
>> -- Till
>> Martin Molnar wrote:
>>> Hi,
>>> Could anybody explain me how exactly Priority Ceiling Protocol (PCP) 
>>> is implemented in RTEMS? I think it works differently than PCP 
>>> described in technical books.
>>> Example:
>>> 1.Task1 (current priority 10) obtains the mutex SEM1 and its 
>>> priority is raised to the mutex ceiling (9).
>>> 2.Task1 ( current priority 9) obtains the mutex SEM2 and its 
>>> priority is raised to the mutex ceiling (5).
>>> 3.Task1 ( current priority 5) releases the mutex SEM2. I would 
>>> expect the priority to be changed to value 9. However, the priority 
>>> remains unchanged. From RTEMS documentation: Only when the task 
>>> releases ALL of the binary semaphores it holds will its priority be 
>>> restored to the normal value.
>>> I am not sure, whether RTEMS PCP(and also Priority Inheritance 
>>> Protocol) is correct. Because,now Task1 can block for example TAsk2 
>>> with priority 6.
>>> Thanks for explanation
>>>  Martin Molnar

More information about the users mailing list