Priority Inversion

[brosgol@AJPO.SEI.CMU.EDU (Ben Brosgol)]

The phenomenon of priority inversion can be illustrated by the following
example.  On a uniprocessor system, there is a high priority task H, a
medium priority task M, and a low priority server task L.  At some point
in program execution, imagine that H is running, M is suspended, and
L is suspended at a place other than an accept for its service entry.
Now H issues a call on this service entry from L.  If L were ready to
accept this entry, it would assume H's high priority and execute the accept.
But L is not ready; thus H is suspended and M is run instead, thereby
blocking the high-priority task from receiving its service.

This problem was presented last year by Lui Sha (Carnegie-Mellon Univ) at
the International Workshop on Real-Time Ada Issues, at Moretonhampstead.
A summary of the issue was published in SIGAda's Ada Letters, Volume VII,
Number 7 (Nov-Dec '87), pages 30-32: "Priority Inversion in Ada" by
Dennis Cornhill and Lui Sha.
Full proceedings of the Moretonhamstead workshop were published as a
special issue of Ada Letters, Volume VII, Number 6 and were mailed
to SIGAda members.
An extended summary of the workshop, including an example of the
priorrity inversion problem, was published in Ada Letters, Volume VIII,
Number 1 (Jan-Feb '88), pages 91-107: "International Workshop on Real-Time
Ada Issues: Summary Report" by Ben Brosgol.

If you happen to have missed these issues because you're not a member
of SIGAda, that situation is easily remedied; send me a message that
includes your mailing address, and I'll send you an application form.

By the way, one solution that was proposed for the priority inversion
problem was to have priority inherited at the time the entry is called,
rather than waiting till the rendezvous starts.  Of course if the
called server task is itself suspended on a call of an entry for another
low priority task, then the inheritance of the high priority would have
to be passed on in a transitive fashion.

Note that if an implementor wants to support such a priority inheritance
approach but would rather not tinker with the language-defined semantics
of Ada priority (such changes tend to be frowned upon) it is legitimate
to supply an implementation-defined dynamic priorities package that has
the desired effect.  Just let all tasks have the same Ada priority;
thus the language rules will not interfere with inheritance of the
implementation-provided priority on entry calls.

-Ben Brosgol, Alsys Inc. / SIGAda Chair