Priority inherance issue

[Manuel Coutinho]

> -----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)
  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