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

[Nick Garnett <nickg at ecoscentric dot com>]

"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