Priority inherance issue

[Manuel Coutinho]

> -----Original Message-----
> From: xi yang [mailto:hiyangxi at gmail.com]
> Sent: Wednesday, May 20, 2009 10:10 AM
> To: Manuel Coutinho
> Cc: Aitor Viana; Joel Sherrill; rtems-users at rtems.com
> Subject: Re: Priority inherance issue
> 
> 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.

Yes, you are right.
But was not thinking about this specific case of strict order.

But actually, think the same problem occurs. Just make D obtain first S2 and
then S1.

But couldn't there be a more general solution?

I've being researching this issue on the net, and more and more I get the
felling that "simple priority inherence" should not be used. Should use
priority ceiling instead since it is much simpler and deterministic to
implement and gives better schedulability results (high priority thread is
blocked for a lesser time because of low priority threads). The only
downside is that the programmer has to know the ceiling priority. But think
in hard real-time system this is not an big issue.

And also, mixing "simple priority inherence" with priority ceiling could
cause problems...

(I use "simple priority inherence" between commas because, in the
literature, priority inherence is divided into "simple priority inherence"
and priority ceiling protocols)

Well...this is my opinion now...

Regards
Manuel Coutinho

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