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

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

[Stanko Vuleta]

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?
 
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?
 
Thanks,
 
Stanko Vuleta

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

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

[Nick Garnett]

"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

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

[Nick Garnett]

"Stanko Vuleta" <vuleta@nimcatnetworks.com> writes:

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

Consider the following scenario:

Tl locks M1 and attempts to lock M2. M2 is already owned by Tm, so Tl
has to wait, there is no priority donation at this point. Now Th
runs and attempts to lock M1. It cannot, since Tl owns it, so it
donates it priority to Tl. Tl must in turn now donate this new
priority to Tm, to prevent Tm blocking Th. This then has to be
repeated for any mutex that Tm may be waiting for.

These sorts of situations are fairly rare, which is why the simple
algorithm is acceptable in most cases.

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

I'm not sure that would help much.


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

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

[Stanko Vuleta]

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