Abstract
The Priority Ceiling Protocol (PCP) of Sha, Rajkumar and Lehoczky is a policy for locking binary semaphores that bounds priority inversion (i.e., the blocking of a job while a lower priority job executes), and thereby improves schedulability under fixed priority preemptive scheduling. We show how to extend the PCP to handle: multiunit resources, which subsume binary semaphores and reader-writer locks; dynamic priority schemes, such as earliest-deadline-first (EDF), that use static “preemption levels”; sharing of runtime stack space between jobs. These extensions can be applied independently, or together.
The Stack Resource Policy (SRP) is a variant of the SRP that incorporates the three extensions mentioned above, plus the conservative assumption that each job may require the use of a shared stack. This avoids unnecessary context switches and allows the SRP to be implemented very simply using a stack. We prove a schedulability result for EDF scheduling with the SRP that is tighter than the one proved previously for EDF with a dynamic version of the PCP.
The Minimal SRP (MSRP) is a slightly more complex variant of the SRP, which has similar properties, but imposes less blocking. The MSRP is optimal for stack sharing systems, in the sense that it is the least restrictive policy that strictly bounds priority inversion and prevents deadlock for rate monotone (RM) and earliest-deadline-first (EDF) scheduling.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
U.S. Department of Defense. 1983. Military Standard Ada Programming Language, ANSI/MILSTD1815A, Ada Joint Program Office.
Baker, T.P., and Scallon, G.L. 1986. An Architecture for Real-Time Software Systems. IEEE Software, 50–59; reprinted in Hard-Real-Time Systems, Washington, DC: IEEE Press (1988).
Baker, T.P. 1989. A Fixed-Point Approach to Bounding Blocking Time in Real-Time Systems. Technical Report, Department of Computer Science, Florida State University, Tallahassee, FL 32306.
Baker, T.P., Malec, C., and Wilson, R. 1989. Practical Tasking. Boeing Aerospace and Electronics Company white paper.
Baker, T.P. 1990. Preemption vs. Priority, and the Importance of Early Blocking. Proceedings of the Seventh IEEE Workshop on Real-Time Operating Systems and Software, Charlottesville, VA (May): 44–48.
Baker, T.P. 1990. A Stack-Based Resource Allocation Policy for Realtime Processes. Proceedings of the IEEE Real-Time Systems Symposium.
Borger, M.W., and Rajkumar, R. 1989. Implementing Priority Inheritance Algorithms in an Ada Runtime System. Technical report, Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PA.
Chen, M.I., and Lin, K.J. 1989. Dynamic Priority Ceilings: A Concurrency Control Protocol for Real-Time Systems. Technical report UIUCDCS-R-89-1511, Department of Computer Science, University of Illinois at Urbana-Champaign.
Coffman, E.G.Jr., and Denning, P.J. 1973. Operating Systems Theory. Englewood Cliffs, NJ: Prentice-Hall.
Garey, M.R., and Johnson, D.S. 1979. Computers and Intractability. New York: W.H. Freeman.
Ghazalie, T. 1990. Improving Aperiodic Response with Deadline Scheduling. Master's Thesis, Florida State University.
Giering, E.W. III, and Baker, T.P. 1989. Toward the Deterministic Scheduling of Ada Tasks. Proceedings of the IEEE Real-Time Systems Symposium, 31–40.
Habermann, A.N., and Nassi, I.R. 1980. Efficient Implementation of Ada Tasks. Technical report, Department of Computer Science, Carnegie Mellon University.
Havender, J.W. 1968. Avoiding Deadlock in Multitasking Systems. IBM Systems Journal 7, 2: 74–84.
Hilfinger, P.N. 1982. Implementation Strategies for Ada Tasking Idioms. Proceedings of the AdaTEC Conference on Ada, Arlington, VA: 26–30.
Holt, R.C. 1971. On Deadlock in Computer Systems. Ph.D. Thesis, TR 71-91, Department of Computer Science, Cornell University.
IEEE Computer Society. 1988. IEEE Standard Portable Operating System Interface for Computer Environments, Washington, DC: IEEE Press.
Leung, J.Y.-T. and Merrill, M.L. 1980. A Note on Preemptive Scheduling of Periodic, Real-Time Tasks. Information Processing Letters 11, 3: 115–118.
Leung, J.Y.-T., and Whitehead, J. 1982. On the Complexity of Fixed-Priority Scheduling of Periodic Real-Time Tasks. Performance Evaluation 2: 237–250.
Liu, C.L., and Layland, J.W. 1973. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. JACM 20.1: 46–61.
Mok, A.K.-L. 1983. Fundamental Design Problems of Distributed Systems for the Hard Real-Time Environment. Ph.D. Thesis, MIT.
Rajkumar, R., Sha, L., Lehoczky, J.P., and Ramamritham, K. 1989. An Optimal Priority Inheritance Protocol for Real-Time Synchronization. Technical report, Carnegie Mellon University (submitted for publication).
Rajkumar, R., Sha, L., and Lehoczky, J.P. 1988. Real-Time Synchronization Protocols for Multiprocessors. Proceedings of the Real-Time System Symposium, IEEE, 259–272.
Sha, L., Lehoczky, J.P., and Rajkumar, R. 1986. Solutions for Some Practical Problems in Prioritized Preemptive Scheduling. Proceedings of the IEEE Real-Time Systems Symposium, 181–191.
Sha, L., Rajkumar, R., and Lehoczky, J.P. 1987. Priority Inheritance Protocols, An Approach to Real-Time Synchronization. Technical report CMU-CS-87-181, Carnegie Mellon University.
Sha, L., Rajkumar, R., and Lehoczky, J. 1988. A Priority Driven Approach to Real-Time Concurrency Control. Technical report, Carnegie Mellon University.
Sprunt, B., Sha, L., and Lehoczky, J. 1989. Aperiodic Task Scheduling for Hard-Real-Time Systems. Real Time Systems 1, 1: 27–60.
Sha, L., Rajkumar, R., and Lehoczky, J. 1989. Mode Change Protocols for Priority-Driven Preemptive Scheduling. Real Time Systems 1, 3: 243–264.
Bic, L., and Shaw, A.C. 1988. The Logical Design of Operating Systems. Englewood Cliffs NJ: Prentice-Hall.
Author information
Authors and Affiliations
Additional information
This work is supported in part by grant N00014-87-J-1166 from the U.S. Office of Naval Research.
Rights and permissions
About this article
Cite this article
Baker, T.P. Stack-based scheduling of realtime processes. The Journal of Real-Time Systems 3, 67–99 (1991). https://doi.org/10.1007/BF00365393
Issue Date:
DOI: https://doi.org/10.1007/BF00365393