Priority inherance issue

[xi yang]

2009/5/20 Manuel Coutinho <manuel.coutinho at edisoft.pt>:
>
>
>> -----Original Message-----
>> From: xi yang [mailto:hiyangxi at gmail.com]
>> Sent: Wednesday, May 20, 2009 4:59 AM
>> To: Aitor Viana; Joel Sherrill
>> Cc: Manuel Coutinho; rtems-users at rtems.com
>> Subject: Re: Priority inherance issue
>>
>> 2009/5/19 Aitor Viana <aitor.viana.sanchez at esa.int>:
>> > There is prob. a middle ground solution. To have less than 256 levels
>> per
>> > semaphore hashed (hash table)
>> >
>> > regards,
>> >
>> >
>> > Aitor
>> >
>> >
>> > On Tue, May 19, 2009 at 11:37 AM, Manuel Coutinho
>> > <manuel.coutinho at edisoft.pt> wrote:
>> >>
>> >> Hi
>> >>
>> >> 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
>> >> perfect.
>> >>
>> >> 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.
>> Yeah, you are right. with STRICT_ORDER_MUTEX, when thread releases a
>> inherent mutex, the priority of the thread is decreased to the
>> priority before locking this inherent mutex.
>> Here is a problem in some situations, for example.
>>  Thread P with Priority 10 have got SemA,B,C.
>>  Then, thread Q with priority 1 acquires Sem A.
>>  Priority of Thread P will be improved to 1.
>>  At this time, if P wants to release Sem C,
>>  its priority will be decreased to 10 which is the priority before
>> locking Sem C.
>>
>
> Yes, well, just some differences of course, but that is the main problem.
>
>> Is this the problem what you have?
>> >>
>> >> 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.
>> I think there is a more simpler solution. For every inherent mutex, we
>> record two priorities. One is before_improved_priority which is
>> initialized to the priority when get this mutex. The other is
>> after_improved_priority which is initialized to the lowest priority.
>>
>> When a thread T with priority P1 wants to acquire a inherent mutex, it
>> finds that priority improvement is needed and do it like this:
>> before_improved_priority = current holder's priority
>> after_improved_priority = P1
>>
>> When the holder releases a inherent mutex
>> It needs to check
>>
>> {
>> if(current_priority is not higher than before_improved_priority)
>>     return and do nothing
>>
>> if(current_priority does not equal after_improved_priority)
>>     return and do nothing because the priority of holder is improved
>> by thread which waits for other mutex.
>>
>> decrease the holder's priority to before_improved_priority
>> }
>>
>>
>> Then, we are able to make sure that after releases the mutex, the
>> priority of the holder is still equal to the highest priority of
>> threads who wait for mutex which the holder holds.
>>
>>
>> Welcome more comments.
>
> Not sure if your solution works. Perhaps I'm reading it wrong :S.
>
> Suppose the example:
>
> Threads A, B, C and D
> Semaphores S1 and S2
>
> Steps:
>  D obtains S1
>  D obtains S2
>  C tries to obtain S1 and blocks
>  B tries to obtain S2 and blocks
>  A tries to obtain S1 and blocks
>  D releases S1 -> and returns to priority B.priority (think your algorithm
> works well here)
With STRICT_ORDER_MUTEX, D can not release S1 before releasing S2.
Threads must obtain and release mutex in LIFO oder, which means thread
have to obtain M1,M2,...,Mn and release them in Mn,......M2,M1 order.
>  A obtains S1 and releases it
>  D releases S2 -> here, you have S2.before = C.priority and S2.after =
> B.priority but thread D must now return to the initial priority (because it
> no longer holds any semaphores)
>
> I'm not sure I understood the "philosophy" behind your method, so cannot
> really complete it :S
> (but am not saying it is a bad ideia!)
>
> Regards
> Manuel Coutinho
>
>
>