RE: [ECOS] Is priority inheritance implemented the right way in eCOS?

["Stanko Vuleta" <vuleta at nimcatnetworks dot com>]

Nick, 

Thanks for giving a detailed answer.

I understand the reasons for choosing the simpler implementation.  The
one part that I did not understand was:
"When a thread attempts to lock a mutex, and finds it already owned, it
must attempt to donate its priority to the owning thread. If that thread
is itself already waiting for another mutex we must repeat the process,
and so on until we reach the end of the chain."

I may be missing something but I don't see why is this necessary. 
Scenario: Let Tl, Tm and Th be threads with low, medium and high
priority.  Tl owns mutex M1 and Th owns mutex M2.  Tl is waiting for a
mutex owned by Th. 
Tm attempts to lock mutex M1.  It donates its priority to Tl.  It is not
necessary to go down the chain here and do anything with M2 or Th.  If
Tl continues to be blocked because it is waiting on M2 let it be so -
its newly heightened priority (medium) is not supposed to be higher than
high anyway.  Although it may appear that Tm is blocked where it should
not be, this is not so.  Tm is not supposed to get CPU time anyway
because Th should be running - it is the higher priority task.

Further:
I agree that the business with keeping a linked lists of mutexes owned
by each thread adds to latency uncertainty and the complexity.  I would
argue here to limit maximum number of mutexes owned by a thread to a
configurable number like, say 4.  It would make things deterministic
again and it would decrease processing time.

You argument that the problem should be avoided by more careful design
is the same one used by the well known company I already mentioned.  I
am not arguing that your points are not correct, but am instead arguing
hat an RTOS build for the real world should not impose such restrictions
on design.  In the database example I gave, you are in effect asking
that any code calling the flash driver does not use mutexes.  This is
difficult to achieve in the best of times, let alone in realistic
environment when design is done by different people at different times
working at different pieces of code.  This is why the "well known
company" was forced to fix this in their latest release.

Anyhow, this problem seems a very good candidate for enriching the eCOS
configuration set so people can choose if they are willing to pay the
small price in performance to have a more deterministic behaviour.  

Aside from all this, cudos to the people starting and contributing to
the eCOS project. 

Cheers,

Stanko Vuleta

> -----Original Message-----
> From: nickg@xl5.calivar.com [mailto:nickg@xl5.calivar.com] On 
> Behalf Of Nick Garnett
> Sent: May 27, 2005 12:09 PM
> To: Stanko Vuleta
> Cc: ecos-discuss@sources.redhat.com
> Subject: Re: [ECOS] Is priority inheritance implemented the 
> right way in eCOS?
> 
> "Stanko Vuleta" <vuleta@nimcatnetworks.com> writes:
> 
> > I am doing a bit of research in eCOS and I couldn't find 
> the answer to 
> > the following question: how is priority inheritance 
> implemented in eCOS?
> 
> The sources are available, the answer is in there, in 
> particular the following comment in sched.cxx:
> 
>     // A simple implementation of priority inheritance/ceiling
>     // protocols.  The simplification in this algorithm is that we do
>     // not reduce our priority until we have freed all mutexes
>     // claimed. Hence we can continue to run at an artificially high
>     // priority even when we should not.  However, since nested
>     // mutexes are rare, the thread we have inherited from is likely
>     // to be locking the same mutexes we are, and mutex claim periods
>     // should be very short, the performance difference between this
>     // and a more complex algorithm should be negligible. The most
>     // important advantage of this algorithm is that it is fast and
>     // deterministic.
>     
> The documentation also makes reference to this issue.
> 
> 
> > An explanation: a very well known RTOS that has the majority of the 
> > market share nowdays implements priority inheritance in a 
> simple way 
> > which gets you high benchmarks when measuring scheduling 
> latency but 
> > renders your RTOS "pseudo-real-time" since end result is that low 
> > priority tasks can end up stealing CPU time from the high 
> priority ones.
> > Further explanation in words of Tod Litwin picked up from a 
> discussion
> > list: 
> >  
> > "The problem is that when the low-priority task releases the mutex, 
> > the task's elevated priority won't necessarily be lowered 
> back to its 
> > proper level right away. This only occurs if the task is 
> still holding 
> > other inversion-protected mutexes.
> > The
> > priority will only be returned to its proper level when the 
> last such 
> > mutex is released by the task. Until that time it's 
> priority will not 
> > be lowered at all, no matter how many times and through how many 
> > mutexes it's priority needed to be raised through priority 
> > inheritance. (Note that if the task is holding only one 
> > inversion-protected mutex at a time, there is no problem.) "
> >  
> > An example of how bad this can be, think of e.g. data base code: as 
> > soon as a database function is entered, we obtain a semaphore 
> > protecting the database.  A bit later we decide to read/write to 
> > flash.  We obtain another semaphore protecting the flash.  The 
> > conditions for the above problem have been met.
> >  
> > BTW, this is documented as such in their API and the latest 
> version of 
> > the RTOS in question has the problem fixed.
> >  
> > Finally, the question: does eCOS lower the priority of the 
> task with 
> > inherited priority as soon as the particular semaphore is 
> released or 
> > does it wait for all the semaphores it owns to be released?
> 
> The current implementation of priority inheritance in eCos 
> only lowers the thread's priority when it releases the last 
> held mutex.
> 
> To understand why I chose to implement this simplified 
> algorithm, consider what must be done for the complete 
> algorithm. Each thread must have a list of all the mutexes it 
> holds, currently we only keep a count. When a thread attempts 
> to lock a mutex, and finds it already owned, it must attempt 
> to donate its priority to the owning thread. If that thread 
> is itself already waiting for another mutex we must repeat 
> the process, and so on until we reach the end of the chain. 
> When a thread unlocks a mutex it must search the list of 
> mutexes it still holds for a new inherited priority.
> 
> There are a number of drawbacks to this. It is complicated, 
> hard to get right, hard to write tests for and prone to being 
> broken by a ill-considered patch. It adds more fields to the 
> thread and mutex data structures.
> 
> The most important drawback is that it is non-deterministic. 
> Each lock and unlock operation needs to touch some unknown 
> number of other mutexes and threads.
> 
> One must also consider the ways in which mutexes should be used.
> Holding a mutex for a long period is not the intended usage 
> pattern. Mutexes should be locked for very short periods, 
> long enough only to manipulate some shared data. Gatekeeping 
> for long-lived critical regions should be done with binary 
> semaphores, or a mutex/condvar pair. It is seldom a good idea 
> to execute such regions at an inherited high priority.
> 
> Given the intended usage pattern, the current implementation 
> is a sufficient approximation to the complete algorithm, 
> particularly in the context of a small embedded OS. I also 
> decided that it was much more important that these operations 
> be deterministic.
> 
> We do provide priority ceiling protocol, which many consider 
> a better priority inversion mechanism. It is certainly more 
> predictable and deterministic. One could consider our current 
> priority inheritance implementation as a kind of "priority 
> ceiling by discovery".
> 
> Of course this is an open source project, and the code is 
> structured to allow an alternative implementation of priority 
> inheritance to be implemented. Anybody is at liberty to 
> write, test, document, contribute and then maintain a 
> complete implementation.
> 
> 
> -- 
> Nick Garnett                                     eCos Kernel Architect
> http://www.ecoscentric.com                The eCos and RedBoot experts
> 
> 
> 
> 

--
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss