brosgol@AJPO.SEI.CMU.EDU (Ben Brosgol) (05/12/88)
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
firth@sei.cmu.edu (Robert Firth) (05/14/88)
Priority Inversion ================== Ben Brosgol explained (correctly) the problem of priority inversion in these terms: A server task of low priority - SERVER(L) - is approaching an accept statement. Queued on its entry is a high priority task CALLER(H). Hoever, an unrelated task of medium priority - RANDOM(M) - prempts SERVER, and so CALLER stays blocked. Hence, RANDOM(M) is being given the processor at the expense of CALLER(H). Here is another example: We have CALLER(H) queued behind CALLER(L) on the entry queue of SERVER(L), which is in rendezvous. The priority of the rendezvous is, of course, L. Again, RANDOM(M) preempts, so suspending SERVER, and holding up CALLER(H) on the entry queue. One proposed solution is to have a SERVER inherit the priority of a CALLER at the moment the entry is called. This doesn't work, of course, for reasons we shall see. Consider now this example: the SERVER(L) is a resource allocator allocating buffers, and so is suspended on the usual select statement "accept CLAIM_BUFFER... or accept RELEASE_BUFFER...". A high-priority task CALLER(H) calls the CLAIM_BUFFER entry, but unfortunately SERVER has run out of buffers, the guard is closed, and CALLER(H) blocks. Now over in the blue corner, another task RUMPLESTILTSKIN(L) is closing fast on a RELEASE_BUFFER call that will give back a buffer. But, as you might guess, RANDOM(M) preempts, suspending poor RUMPLE(L), and so, indirectly, blocking CALLER(H). Priority inversion! The thing about this last example is that there is no way the Ada runtime can detect what is going on, and so no magic "solution" can be achieved by tweaking the language semantics. The only recourse is that you really shouldn't write code that way. So we observe, that the priority mechanism of Ada still requires the user to take some care in writing the code. But the same sort of care also solves the other inversion examples. For example, the rule "give a server a priority no lower than its highest-priority user" guarantees there will be no inversions such as the ones given above. This is a simple, obvious, and, I submit, largely acceptable rule. Again, it requires the user to understand the language semantics and use them with care. However, isn't it better to change the language to remove the possibility of priority inversion, or, at any rate, of some priority inversions? Maybe; the problem is that the proposed solutions are wrong. Consider again CALLER(H) blocked on entry of SERVER(L), in turn preempted by RANDOM(M). Suppose we now raise the server's priority. Suppose further that SERVER is rather sick, and in fact will never reach the accept statement. Then, CALLER(H) still will never unblock; all we have achieved is to allow SERVER(L) indefinitely to shut out RANDOM(M), and this of course is a priority inversion. And how can the Ada runtime possibly know whether a given server will indeed reach the accept? Hence, with either current Ada or Ada as changed, a programmer can always code priority inversions, even in the cases the changes are intended to exclude. I conclude that priority inversion is not a language design error; it is a program design error. Given that there are simple design rules that will in most cases avoid the problem, I see no reason to further complicate Ada runtimes - they are surely complicated enough. The root cause of the trouble is that word "priority". It has an English meaning, and an Ada meaning. People who take the English meaning and ingore the Ada meaning tend to go wrong - for instance, they give the highest priority to the task that is psychologically "most important". Priority is merely a number that controls a comparison somewhere in a scheduler; it is a last-resort way of deciding which task to run when the user has not fully synchronized the tasks. Just because the language provides the word priority, the user is not absolved from the responsibility of understanding tasking semantics, and of careful design of real-time algorithms. Likewise, just because the language Fortran contains the word REAL, the user is not absolved from the responsibility of understanding the semantics of floating-point arithmetic, and of careful design of numerical algorithms. Robert Firth