PCP implementation

[Martin Molnar]

The statements from Vxworks manual are correct. But it is not clearly 
stated whether a task`s priority remains or changes after the task 
releases the mutex with the highest ceiling and still holds another one 
with priority higher than its normal priority. So, I am not sure that 
vxworks do the same thing. Tests would releave it.

What about implementing the changing of task`s priority this way:
-enforce the mutex release rule that PCP mutexes are released in the 
opposite order  of acquisition. I think , it is not a painful restriction.
- for each task, maintain the "resources held set" implemented as stack. 
  Every stack element(record) consists of two fields: the mutex id (to 
control that the mutex relase rule is kept) and task`s priority after 
releasing that mutex.

For better explation, consider the example:
- task`s normal priority is 9.
1. Task acquires mutex 4 ( 4 is the ceiling of mutex). Then,put on the 
stack element(mutex id= 4   priority= current priority=9 ) and change 
task`s current priority to 4.
2.Task acquires mutex 8. Then put on the stack element(mutex id= 8 
priority=current priority= 4 ). Task`s current priority is not changed 
because it is higher than 8.

Example of the stack:
mutex id: 4 8 6 2 1
priority: 9 4 4 4 2

It`s obvious how to release mutexes and change task`s priority.

It is possible to save memory space a little bit if separate stack is 
maintained for mutex ids and for priorities. Mutex ids would be pushed 
on the stack as usual, the current priority is pushed on the priority 
stack only if the ceiling of currently locked mutex is higher than or 
equal to the current priority. When releasing mutexes from the id stack, 
the ceiling of released mutex is compared to the priority on the top of 
priority stack. If the ceiling is higher than or equal to that priority, 
the current priority is set to that priority which is sequentially 
removed from the stack.

For example:
mutex id: 5 4 4 8 6 7 2 1
priority: 9 5 4 4 2

In the book Jane W.S. Liu. Hard Real-Time Computing Systems. Prentice
Hall, 2000  are described two version of PCP: basic and stacked-based.
As far as basic version (classic PCP), when task becomes blocked on a 
mutex, the task holding that mutex inherits its priority if it is 
greater. However, in RTEMS when task locks mutex its priority is changed 
to mutex`s ceiling under certain condition. Simplier but I am not sure 
whether absolutely correct or not.

It think, it would be easy to implement stacked-based PCP. It applies 
Stack resource policy(SRP) which brings advantages. Stack-based PCP 
extends the basic PCP in that it allows the use of multiunit resources 
and allows the sharing of runtime stack-based resources (and support for 
dynamic scheduling but it would require another changes).
It would require to maintain the stack (history) of system ceilings and 
to choose the first task in the highest priority queue whose priority is 
higher than the system ceiling as the next executing task. SRP also 
saves  memory space because there is only one stack and no waiting 
queues( tasks "wait" in ready queue)

Martin















Joel Sherrill wrote:
> Till Straumann wrote:
> 
>> I still consider this a design flaw. However,
>> vxWorks seems to do the same thing. I couldn't
>> test but the manual (semMLib) still (as of
>> vxWorks 5.5 says
>>
>>  "Once the task priority has been
>>   elevated, it remains at the higher level until all
>>   mutual-exclusion  semaphores  that  the task owns
>>   are released; then the task returns to its normal,
>>   or standard, priority."
>>
>> And a little further down:
>>
>>   "The task will return to its normal priority only
>>    after  relinquishing  all of its mutual-exclusion
>>    semaphores that have the inversion-safety option
>>    enabled."
>>
>>
> 
> I'm certainly willing to do something more theoretically correct if
> we can identify an algorithm that is efficient to implement.
> 
> --joel
> 
>> -- Till
>>
>>
>> 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 of PCP/PI 
>>> mutexes
>>> and don't hold them for lengthy periods of time.
>>>
>>> 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,
>>> 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.
>>>
>>> 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
>>>>>
>>>>
>>>
>>
>>
>