Sources of unbounded priority inversions in real-time systems and a comparative study of possible solutions

ABSTRACT

In the design of real-time systems, tasks are often assigned priorities. Preemptive priority driven schedulers are used to schedule tasks to meet the timing requirements. Priority inversion is the term used to describe the situation when a higher priority task's execution is delayed by lower priority tasks. Priority inversion can occur when there is contention for resources among tasks of different priorities. The duration of priority inversion could be long enough to cause tasks to miss their deadlines. Priority inversion cannot be completely eliminated. However, it is important to identify sources of priority inversion and minimize the duration of priority inversion. IN the paper we present a comprehensive review of the problem of and solutions to unbounded priority inversion.

REFERENCES

• 1: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 2: Lui Sha , John B. Goodenough, Real-Time Scheduling Theory and Ada, Computer, v.23 n.4, p.53-62, April 1990 [doi>10.1109/2.55469]
• 3: Lui Sha , Ragunathan Rajkumar , John P. Lehoczky, Real-Time Computing with IEEE Futurebus+, IEEE Micro, v.11 n.3, p.30-33, 95-100, May 1991
• 4: L. Sha , R. Rajkumar , J. P. Lehoczky, Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, v.39 n.9, p.1175-1185, September 1990 [doi>10.1109/12.57058]
• 5: J. B. Goodenough , L. Sha, The priority ceiling protocol: A method for minimizing the blocking of high priority Ada tasks, Proceedings of the second international workshop on Real-time Ada issues, p.20-31, June 01-03, 1988, Moretonhampstead, Devon, England
• 6: [6] R. Rajkumar, L. Sha, and J.P. Lehoczky, "Real-Time Synchronization Protocols for Multiprocessors," Proc. IEEE Real-Time Systems Symposium, 1988, pp. 259-269.
• 7: [7] T. Baker, "Stack Based Scheduling of Real-Time Resources", Technical Report, Department of Computer Science, Florida State University, Tallahassee, FL 32306, April 1990.
• 8: [8] M.I. Chen and K.J. Lin, "Dynamic Priority Ceilings: A Concurrency Control Protocol for Real-Time Systems.", Technical Report, Department of Computer Science, University of Illinoise at Urbana-Champaign, 1989.
• 9: [9] Draft Ada 9x Project Report: Ada 9x Mapping Document Vol. II, December 1991.
• 10: [10] Tread Extension to Portable Operating System Standard, IEEE P1003.4a, Draft 5, IEEE 1990.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance