lrs@sei.cmu.edu (Lui Sha) (05/27/88)
On Priority Scheduling and Priority Inversion (sha@sei.cmu.edu)
It has been almost a year since the priority inversion problem was raised in
the First International Workshop on Real-Time Ada Issues. However, it is still
a topic of interests in info-ada and I would like to share my thoughts on
this subject.
I have discussed these issues with many people and have learned a great deal
from them, especially John Goodenough of SEI who has helped me to appreciate
the subtlety in language design and Douglass Locke of IBM who has helped me to
appreciate the complexity of building a real-time system.
-----------------
Q: What is priority inversion?
A: Priority scheduling requires priority assignments to be observed in
allocating resources, logical and physical. For example, the CPU should not
be given to a low priority task if a high priority task needs to use it.
PRIORITY INVERSION occurs when a low priority task is given or is using a
resource needed by a higher priority task.
Priority inversion cannot be completely eliminated. For example, when a low
priority task is in a critical region, the higher priority task which needs
the shared data must wait. Nonetheless, the duration of priority inversion
must be tightly bounded in order to ensure a high degree of responsiveness and
schedulability of a real-time system. Schedulability is a measure of resource
utilization under which all the deadlines of periodic tasks can be met.
Responsiveness measures the priority weighted response time of the system to
aperiodic events. Priority inversion degrades both measures.
Controlling priority inversion is a system level problem. Tasking model,
runtime support, program design and hardware architecture should all be part
of the solution, not part of the problem. For example, if the hardware permits
only FIFO queues for data I/O channels, no software efforts alone can save the
day. What will happen is "hurry-up at the CPU and miss the deadline at I/O".
By the same token, in a distributed system, if the token ring or bus performs
FIFO, end to end deadlines can be missed at the communication level.
Priority assignment must be observed at the system level for all forms of
resource allocations. Consistency is a key to predictability and determinism.
-------------------
Q. Is priority inversion an Ada language deficiency or a program design
error?
A. While program design errors can cause unnecessary priority inversion, the
Ada language rules do not consistently enforce a prioritized scheduling
discipline. Ada mandates that priority assignments be observed in the
allocation of a hardware resource: CPU, while ignoring priority in logical
resource allocation: an entry ignores the priorities of tasks on its queue,
and a selective wait statement is not required to select the highest priority
task waiting at an open select alternative. The priority of a calling task is
ignored until the call is accepted. This set of rules not not ensure
either fairness needed by a time sharing system or responsiveness
and schedulability needed by a real-time system.
In short, independent of how Ada is used, its rules do not consistently
enforce a priority scheduling discipline, and hence, it is reasonable to say
the language rules are deficient.
-----------------------
Q. If revised Ada enforces a consistent set of rules that support priority
scheduling, can we use Ada for time sharing applications where fairness is
important?
A. Yes. We can either assign equal priority or raise the priority of a task
that has waited for a long time, a commonly used practice. Of course, the
revised Ada must permit the change of a task's priority.
-----------------------
Q. What exactly is the "priority inheritance" rule?
A: priority inheritance is a basic rule in priority scheduling. It says that
when a lower priority task blocks higher priority tasks, it should execute at
the highest priority of the blocked tasks. The Ada rule of taking the max of
the priorities of the caller and server during rendezvous is a form of
priority inheritance, except that it is a bit too late. It should be done at
the time of the entry call, not waiting until the call is accepted. Priority
inheritance ensures that the waiting time of a high priority task to lower
priority tasks is a function of critical section durations (durations of entry
calls in Ada). When a high priority task is blocked by a low priority task,
failure to observe this rule can lead to serious priority inversion.
Based upon the priority inheritance rule, a family of real-time
synchronization protocols have been developed. For example, the priority
ceiling protocol is one which ensures the freedom from deadlocks and ensures a
high priority task will be blocked at most once by lower priority tasks until
it either completes or suspends (e.g. I/O). These real-time synchronization
protocols allow tasks to interact in a predictable fashion.
(For details, Readers are referred to "The Priority Ceiling Protocol: A Method
for Minimizing the Blocking of High Priority Ada Tasks", by John Goodenough
and Lui Sha, to appear in the Proceedings of the 2nd International
Workshop on Real-Time Ada Issues". For its applications, see Douglass Locke's
and John Goodenough's paper in the same proceedings. For a formal treatment
of this subject, see "Priority Inheritance Protocols: An Approach to Real-Time
Synchronization, by Lui Sha, Ragunathan Rajkumar, and John Lehoczky, Technical
Report, Department of CS, CMU, 1987.)
-----------------
Q. Priority inheritance seems a good idea, should Ada mandate its
implementation?
A. No. There can be embedded applications in which called tasks always have
priorities higher than callers and thus this rule is not needed. Furthermore,
there is a family of priority inheritance protocols to be chosen by
applications. While Ada should NOT mandate the implementation of the priority
inheritance rule, Ada should PERMIT the implementation of this rule when an
application needs it. At this point in time, implementing any priority
inheritance protocol will result in "illegal" Ada.
The fundamental issue here is that we must understand that real-time
scheduling algorithms and the runtime scheduler are part of the real-time
applications. Different real-time applications have different timing
constraints and require a different set of real-time scheduling algorithms.
Ada should permit the selection of scheduling algorithms just as it
permits the selection of computation algorithms.
Hence, Ada should mandate the implementation of a consistent set of low level
priority scheduling mechanisms upon which a consistent set of real-time
scheduling algorithms/rules needed by an application can be implemented. (For
details, see "Scheduling Mechanisms for Prioritized Preemptive Scheduling", by
Sha and Rajkumar, to appear in the proceeding of 2nd International Workshop
on Real-time Ada Issues.)
While Ada should not mandate the implementation of any particular
algorithm/rule in priority scheduling, Ada can provide a default package of a
scheduler consisting of commonly used scheduling rules, just like Text-IO is
for the convenience of users for the management of I/O.
---------------
Q. Is it sufficient to avoid the priority inversion problem for task
rendezvous if the server is given a priority higher than all the
callers.
A. It can be part of the solution if giving the server a priority higher than
all its callers is acceptable to the application. It can be considered as a
static approximation of the priority inheritance rule. Like the priority
inheritance rule, it requires the support of priority queueing and priority
select to make it complete in the avoidance of priority inversion for task
rendezvous. To illustrate this point, consider that we have a server task to
handle I/O. When the server is suspended for I/O completion, the entry queues
of the server can be filled. If the high priority server selects calling
tasks in an arbitrary fashion and in a FIFO order, serious priority inversion
can occur.
---------------
Q. Since high priority server plus priority queue and priority select can
avoid priority inversion in task rendezvous, why don't we leave Ada
definitions alone? We can use entry families to simulate a priority queue. In
addition, we can modify the runtime so that a server selects the highest
priority caller. There is a loophole here: priority select is one form of
arbitrary select, isn't it?
A. When you need a loophole to get the job done, the rules are wrong. In
addition, it is difficult to preclude the possibility that a high priority
task may need to call a lower priority task. The Ada rule of taking the max of
the priorities of the caller and server anticipates this problem. In fact, if
we want to write a simple periodic task in existing Ada, we run into the
problem right away. For example,
- - - - - - - - - -
"loop
do work
read clock
-- can be preempted right here
delay until the beginning of next period
end loop"
is incorrect because the task can be preempted after reading the clock and
before the execution of the delay statement. This leads to delayed initiation
of next period. Hence, we need a high priority driver task.
"loop
worker.start
delay worker's period
end loop"
and the worker
"loop
accept start
do work
end loop"
-- some more code is needed to make it actually work without drift, but
-- that is not the point.
- - - - - - - - - -
As we can see, it does not make sense to let the worker have priority higher
than the driver. This is just an example which illustrates that it may not
always be sensible to make the called task to have a priority higher than the
callers. From an application point of view, if getting the work done means
fighting the rules of Ada, the rules should be changed. Ada should be part of
the solution, not part of the problem.
--------------------
Q. Consider the producer and consumer problem. We have three tasks. A high
priority producer task, a buffer task of low priority and a low priority
consumer task. At some point, the buffer is full and the guard is closed. In
the mean time, the low priority consumer is preempted by medium priority
tasks. Can the priority inheritance rule help?
A. Yes, it can. However, we must realize that in the terminology of real-time
system design we are dealing with the problem of transient overload on a given
resource. During a transient overload, something has to be given up in order
to get the system timing behavior predictable. We have two options to get the
high priority producer going. We can either give up old data or some
schedulability. The former solution is the generally the preferred solution in
most real-time applications. In this case, the buffer task inherits the
priority of the producer and when it runs, it deletes the old data to open up
the guard. In the latter solution, we speed up the consumer by letting it
inherit the priority of the producer. When the producer is blocked, instead
of deleting old data we let the consumer inherit the producer's priority.
This can be done either via a pragma to inform the runtime what to do when the
producer is blocked or let the buffer task give a call to the consumer to pass
data. This call allows buffer task's inherited priority to be inherited by the
consumer. This, in turn, allows the consumer to preempt the medium priority
tasks and accept the data. The reason that the latter solution pays a
schedulability price is that now the producer entry call time must include the
consumer execution time. In schedulability analysis for Ada tasking, blocking
time is measured in terms of the duration of entry calls. And blocking time
represents a schedulability loss in the equations of schedulability analysis.
-------------------
Q: Is priority inheritance harmful for fault tolerance? Specifically,
suppose that a server is sick and has difficulty to make its way to the accept
statement. Bad things would happen if the "sick server" inherits the priority
of a high priority caller.
A: Yes, if we cannot detect the fault of "sick server" in time and raise its
priority, many bad things could happen. Because raising the priority of a
faulty process is inconsistent with the principle of fault confinement. At
this point, I don't know any good solution to this problem. All I know is that
when temporarily raising the priority of a sick server is harmful, giving a
permanently high priority to a sick server can be fatal. I think that we
should pay more attention to the problem of the interplay between scheduling
algorithms and fault tolerant techniques.
--------------------
Q: Why should Ada support priority scheduling in the first place?
A: The importance of priority scheduling is that by far it is the most matured
discipline in real-time scheduling. There is a large body of results which
give us closed form solutions to problems like:
* Periodic and aperiodic deadlines;
* maintaining stability under transient overload;
* the problems of mode changes and the control of jitters;
* synchronization and communication media scheduling, ...
Once the real-time scheduling algorithms and synchronization protocols are
employed, as long as we observe the resource utilization bounds on CPU, I/O
drivers and communication media, the timing constraints will be guaranteed.
Even if there is a transient overload, the tasks missing deadlines will be in
a pre-defined order. In other words, these analytical solutions allow
programmers to reason about the timing correctness and robustness at a high
level of abstraction and with confidence. Furthermore, these algorithms belong
to the family of static scheduling algorithms which can be efficiently
implemented. However, these results will not hold unless priority inversion
is tightly bounded. And this is why the priority inversion problem was raised
in the 1st International Workshop on Real-Time Ada Issues.
Ada manages complexity by means of abstractions and it embodies many sound
software engineering principles. Analytical scheduling algorithms abstract
away the complex problem of scheduling the resources from the applications.
Together, they allow us to reason about the logical correctness and timing
correctness abstractly. In my opinion, Ada and analytical real-time
scheduling approach is a marriage in heaven. After all, Ada means software
engineering and the very meaning of engineering means building things on the
foundation of science. But like any marriage there will be some problems. So
let's iron out the wrinkles and make the marriage work.
---------------
Lui Sha