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