From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_00,INVALID_DATE, MSGID_SHORT autolearn=no autolearn_force=no version=3.4.4 Path: utzoo!attcan!uunet!husc6!bloom-beacon!mit-eddie!bbn!rochester!pt.cs.cmu.edu!sei!sei.cmu.edu!lrs From: lrs@sei.cmu.edu (Lui Sha) Newsgroups: comp.lang.ada Subject: On Priority Scheduling and Priority Inversion Keywords: Ada, Priority Scheduling, Priority Inversion Message-ID: <5595@aw.sei.cmu.edu> Date: 26 May 88 22:42:50 GMT Sender: netnews@sei.cmu.edu List-Id: 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