[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: The dangers of priority inheritance

Oyvind Teig pointed us at:
  The dangers of priority inheritance http://www.cs.nmt.edu/~yodaiken/articles/priority.ps

An interesting paper. If I can be so bold as to summarise, what he says in essence is:

* the "simple priority inheritance protocol" (SPI) (which, incidentally, is an algorithm not a communications protocol in my lexicon) only works in the simple case of acquiring one semaphore. When tasks acquire several semaphores, the situation becomes far more complex and SPI doesn't work. Priority inversion or deadlock may still result.

* a more complex approach called basic priority inheritance (BPI) can also fail under more difficult conditions, the author asserts. I guess it is substantially more compute-intensive than SPI too.

* he postulates that a far simpler solution is to prevent any thread holding a semaphore from being pre-empted. He says that this is the same as using monitors. (Is it? He does not define monitors in his paper so I'm not quite sure).

It is interesting that he favours clearer abstractions in order to avoid getting mired up in complex systems for which the analysis is too daunting to attempt (I paraphrase using his words).

If I can quote Peter Welch's comments (on the java-threads mailing list):

My hard real-time rule is: don't communicate with a lower priority process [i.e. thread]
*unless* you don't have any real-time guarantees to deliver.  Removing the
double negatives, this means feel free to communicate with a lower priority
process (and maybe get blocked) if you currently have no real-time service

General design pattern: give the high-priority real-time servicing process
an equal-priority buddy process.  When you need to communicate with a lower
priority process, get your buddy to do it.  Your buddy is listening out for
you - so you won't be blocked communicating with your buddy.  Your buddy
then gets blocked (maybe) communicating with the lower-priority process but
no matter - you are still alive and servicing.  You need to remember not
to communicate with your buddy until he communicates back to you to say
that he's dealt with the lower-priority process.  If you really need to
do that, you'll need some more buddies.

What I don't need with the above pattern is any priority raising.  My high
priority buddy can get stuck communicating with a low priority process.
Fine - my buddy hasn't got anything else to do!  That low-priority process
is doing background computation that is not time-critical (else it wouldn't
be low-priority).  The last thing I want is for its priority to be raised
to mine so that it competes with me - I've got real-time duties to service!
My buddy needs to be equal-priority with me so that he will succeed as soon
as the low-priority process is ready to communicate with him *and* so that
he gets my attention when that's been done.

Richard Beton B.Sc. C.Phys. M.Inst.P.
Roke Manor Research Limited (http://www.roke.co.uk/)
ICQ: 56840977. Homepage: http://www.beton.freeserve.co.uk/
------------------------- Standard Disclaimer Applies -------------------------