Fixed priority pre-emptive scheduling: An historical perspective

• Aarts, E. H. L. and Korst, J. 1988.Simulated Annealing and Boltzman Machines. Wiley-Interscience.

• Ada9X. 1993. “Ada 9X Reference Manual (Draft Version 4.0)”. Ada 9X Mapping/Revision Team, Intermetrics.

• Agrawal, G., Chen. B., Zhao, W. and Davari, S. 1991. “Architectural Impact of FDDI Network on Scheduling Hard Real-Time Traffic”.IEEE Workshop on Architectural Aspects of Real-Time Systems.

• Audsley, N. C. 1993. “Flexible Scheduling in Hard Real-Time Systems”. Department of Computer Science, University of York, UK. (D.Phil. Thesis) YCST 9307.

  Google Scholar 

• Audsley, N. C., Burns, A., Richardson, M. F. and Wellings, A. J. 1991. “Hard Real-Time Scheduling: The Deadline Monotonic Approach”.Proceedings 8th IEEE Workshop on Real-Time Operating Systems and Software, Atlanta, GA, USA, pp. 127–132.

• Audsley, N. C., Burns, A., Richardson, M. F. and Wellings, A. J. 1992. “Deadline Monotonic Scheduling Theory”.Proceedings IFAC/IFIP International Workshop on Real-time Programming, Bruges, Belgium, pp. 55–60.

• Audsley, N. C., Burns, A., Richardson, M. F. and Wellings, A. J. 1993. “Incorporating Unbounded Algorithms Into Predictable Real-Time Systems”.Computer Systems Science and Engineering. 8(3): 80–89.

  Google Scholar 

• Audsley, N. C., Burns, A., Richardson, M. F. and Wellings, A. J. 1994. “STRESS: A Simulator for Hard Real-Time Systems”.Software, Practice and Experience.

• Audsley, N. C., Burns, A., Richardson, M. F., Tindell, K. W. and Wellings, A.J. 1993. “Applying New Scheduling Theory to Static Priority Pre-emptive Scheduling”.Software Engineering Journal. 8(5): 284–292.

  Google Scholar 

• Audsley, N. C., Burns, A. and Wellings, A. J. 1993. “Deadline Monotonic Scheduling Theory and Application”.Control Engineering Practice. 1(1): 71–78.

  Google Scholar 

• Audsley, N. C., Tindell, K. W. and Burns, A. 1993. “The End of the Road for Static Cyclic Scheduling”.Proceedings of 5th Euromicro Workshop on Real-Time Systems, Oulu, Finland, pp. 36–41.

• Bailey, C. M., Fyfe, E., Vardanega, A. T. and Wellings, A. J. 1993. “The Use of Preemptive Priority- Based Scheduling in Space Applications”.Proceedings IEEE Real Time Systems Symposium, pp. 253–257.

• Baker, T. P. 1990. “A Stack-Based Resource Allocation Policy for Real-time Processees”.Proceedings IEEE Real-Time Systems Symposium, pp. 191–200.

• Blazewicz, J. 1976. “Deadline Scheduling of Tasks — A Survey”.Foundations of Control Engineering. 1(4): 203–216.

  Google Scholar 

• Burns, A. 1991. “Scheduling Hard Real-Time Systems — A Review”.Software Engineering Journal. 6(3): 116–128.

  Google Scholar 

• Burns, A. 1993. “Fixed Priority Scheduling with Deadlines Prior to Completion”. Department of Computer Science, University of York, UK. YCS 212.

  Google Scholar 

• Burns, A., Lister, A. M. and Wellings, A. J. 1987.A Review of Ada Tasking. Springer-Verlag.

• Burns, A. and Wellings, A. J. 1990.Real-Time Systems and their Programming Languages. Addison- Wesley.

• Burns, A., Wellings, A. J. and Hutcheon, A. D. 1993. “The Impact of an Ada Run-time System's Performance Characteristics on Scheduling Models”.Ada sans frontieres Proceedings of the 12th Ada-Europe Conference, pp. 240–248.

• Clements, P. C., Heitmeyer, C. L., Labaw, B. G. and Rose, A. T. 1993. “MT: A Toolset for Specifying and Analysing Real-Time Systems”.Proceedings IEEE Real-Time Systems Symposium, pp. 12–22.

• Coffman, E. G. 1976.Computer and Job-Shop Scheduling Theory. John Wiley & Sons.

• Coffman, E. G. and Denning, P. J. 1973.Operating Systems Theory. Prentice-Hall.

• Conway, R. W., Maxwell, W. L. and Miller, L. W. 1967.Theory of Scheduling Addison-Wesley.

• Cornhill, D. T. and Sha, L. 1987. “Priority Inversion in Ada or What Should be the Priority of an Ada Task?”.Ada Letters. 7(7): 30–32.

  Google Scholar 

• Cornhill, D. T., Sha, L., Lehoczky, J. P., Rajkumar, R. and Tokuda, A. 1987. “Limitations of Ada for Real-Time Scheduling”.Ada Letters (Special Issue International Workshop on Ada Issues). 7(6): 33–39.

  Google Scholar 

• Davis, R. I., Tindell, K. W. and Burns, A. 1993. “Scheduling Slack Time in Fixed Priority Pre- emptive Systems”.Proceedings IEEE Real-Time Systems Syposium, pp. 222–231.

• Dhall, S. K. and Liu, C. L. 1978. “On a Real-Time Scheduling Problem”.Operations Research. 26: 127–140.

  Google Scholar 

• Fineberg, M. S. and Serlin, O. 1967. “Multiprogramming for Hybird Computation”.Proceedings AFIPS Fall Joint Computing Conference, pp. 1–13.

• Garey, M. R. and Johnson, D. S. 1979.Computers and Intractability. Freeman.

• Gerber, R. and Hong, S. 1993. “Semantic-Based Compiler Transformations for Enhanced Schedulability”.Proceedings IEEE Real-Time Systems Symposium, pp. 232–242.

• Gonzalez, M. J. 1977. “Determistic Processor Scheduling”.ACM Computing Surveys. 9(3): 173–203.

  Google Scholar 

• Goodenough, J. B. and Sha, L. 1988. “The Priority Ceiling Protocol: A Method for Minimising the Blocking of High Priority Tasks”.Ada Letters. 8(7): 35–38.

  Google Scholar 

• Halang, W. A. and Stoyenko, A. D. 1991.Constructing Predictable Real-Time Systems. Kluwer- Academic.

• Harmon, M. G., Baker, T. P. and Whalley D. B. 1992. “A Retargetable Technique for Predicting Execution Time”.Proceedings IEEE Real-Time Systems Symposium, pp. 68–77.

• Harbour, M. G., Klein, M. H. and Lehoczky, J. P. 1991. “Fixed Priority Scheduling of Periodic Tasks with Varying Execution Priority”.Proceedings IEEE Real-Time Systems Symposium, pp. 116–128.

• Harter, P. K. 1984. “Response Times in Level Structured Systems”. Department of Computer Science, University of Colorado, USA. CU-CS-269-94.

  Google Scholar 

• Harter, P.K. 1987. “Response Times in Level Structured Systems”.ACM Transactions on Computer Systems. 5(3): 232–248.

  Google Scholar 

• Henn, R. 1989. “Feasible Processor Allocation in a Hard Real-Time System”.Real-Time Systems. 1(1): 77–93.

  Google Scholar 

• Henn, R. and Lehnhoff, S. 1973. “Strategien zur pseudo-kollateralen Verarbeitung von Programmen unter Berucksichtigung vorgegebener Antworteiten”. Technical University of Munich, Math. Report 7307.

• Jackson, J. R. 1955. “Scheduling a Production Line to Minimize Maximum Tardiness”. UCLA, USA, Management Sciences Research Project (Research Report 43).

• Jeffay, K. 1989. “Analysis of a Synchronisation and Scheduling Discipline for Real-Time Tasks with Preemption Constraints”.Proceedings 10th IEEE Real-Time Systems Symposium. pp. 295–305.

• Jensen, E. D. 1992. “The Kernel Computational Model of the Alpha Real-Time Distributed OS”. InMission Critical Operating Systems, ed. Agrawala, A. K., Gordon, K. D. and Hwang, P. IOS Press. pp. 179–207.

• Joseph, M. 1985. “On a Problem in Real-Time Computing”.Information Processing Letters. 20(4): 173–177.

  Google Scholar 

• Joseph, M. and Pandya, P. 1986. “Finding Response Times in a Real-Time System”.The Computer Journal (British Computer Society). 29(5): 390–395.

  Google Scholar 

• Katcher, D. I., Arakawa, H. and Strosnider, J. K. 1991. “Bridging the Gap Between Scheduling Theory and Reality”.Proceedings of 1991 Workshop on Architectural Aspects of Real-Time Systems.

• Katcher, D. I., Arakawa, H. and Strosnider, J. K. 1992. “Engineering and Analysis of Real-Time Micro-Kernels”.Proceedings IEEE Workshop on Real-Time Operating Systems and Software, pp. 15–19.

• Katcher, D. I., Arakawa, H. and Strosnider, J. K. 1993. “Engineering and Analysis of Fixed Priority Schedulers”.IEEE Transactions on Software Engineering. 19(9): 920–934.

  Google Scholar 

• Klein, M. H., Ralya, T., Pollak, B., Obenza, R. and Harbour, M. G. 1993.A Practitioner's Guide for Real-Time Analysis. Kluwer Academic Publishers.

• Kligerman, E. and Stoyenko, A. D. 1986. “Real-Time Euclid: A Language for Reliable Real-Time Systems”.IEEE Transactions on Software Engineering. 12(9): 941–949.

  Google Scholar 

• Lampson, B. W. and Redell, D. D. 1980. “Experience with Processes and Monitors in Mesa”.CACM. 23(2): 105–117.

  Google Scholar 

• Lehoczky, J. P., Sha, L. and Strosnider, J. K. 1987. “Enhanced Aperiodic Responsiveness in Hard Real-Time Environments”.Proceedings IEEE Real-Time System Symposium, pp. 261–270.

• Lehoczky, J. P., Sha, L. and Ding, Y. 1989. “The Rate-Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behaviour”.Proceedings IEEE Real-Time Systems Symposium, pp. 166–171.

• Lehoczky, J. P. 1990. “Fixed Priority Scheduling of Periodic Task Sets With Arbitrary Deadlines”.Proceedings IEEE Real-Time Systems Symposium, pp. 201–209.

• Lehoczky, J. P. and Ramos-Thuel, S. 1992. “An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks Fixed-Priority Pre-emptive Systems”.Proceedings IEEE Real-Time Systems Symposium, pp. 110–123.

• Leinbaugh, D. W. 1980. “Guaranteed Response Times in a Hard Real-Time Environment”.IEEE Transactions on Software Engineering. 6(1): 88–91.

  Google Scholar 

• Leinbaugh, D. W. and Yamini, M. R. 1986. “Guaranteed Response Times in a Distributed Hard Real- Time Environment”.IEEE Transactions on Software Engineering. 12(12); 1139–1144.

  Google Scholar 

• Lesser, V. R., Pavlin, J. and Durfee, E. 1988. “Approximate Processing in Real-Time Problem Solving. AI Magazine”. 9(1): 49–61.

  Google Scholar 

• 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.

  Google Scholar 

• Leung, J. Y. T. and Whitehead, J. 1982. “On the Complexity of Fixed-Priority Scheduling of Periodic, Real-Time Tasks”.Performance Evaluation (Netherlands). 2(4): 237–250.

  Google Scholar 

• Levi, S. T. and Agrawala, A. K. 1990.Real-Time System Design. McGraw-Hill.

• Liu, C. L. and Layland, J. W. 1973. “Scheduling Algorithms for Multiprogramming in a Hard Real- Time Environment”.JACM. 20(1): 40–61.

  Google Scholar 

• Liu, J. W. S., Lin, K. J., Shih, W. K., Yu, C. S., Chung, J. Y. and Zhao, W. 1991. “Algorithms for Scheduling Imprecise Computations”.IEEE Computer. May: 58–68.

• Liu, J. W. S., Redondo, J. L., Deng, Z., Tia, T. S., Bettati, R., Silberman, A., Storch, M., Ha, R. and Shih, W. K. “PERTS: A Prototyping Environment for Real-Time Systems”.Proceedings IEEE Real-Time Systems Symposium, pp. 184–188.

• Lizza, C. S., Banks, S. B. and Whelan, M. A. 1991. “Pilot's Associate: Evolution of a Functional Prototype”.AGARD Conference Proceedings 499 (Machine Intelligence for Aerospace Electronic Systems), Lisbon, Portugal, pp. 16.1–16.12.

• Locke, C. D. 1986. “Best-Effort Decision Making for Real-Time Scheduling”. Computer Science Department, CMU, USA. CMU-CS-86-134 (PhD Thesis).

  Google Scholar 

• Locke, C. D. 1992. “Software Architectures for Hard Real-Time Applications: Cyclic Executives vs Fixed Priority Executives”.Real-Time Systems. 4(1): 37–53.

  Google Scholar 

• Locke, C. D. 1994. Private Communication.

• Locke, C. D., Jensen, E. D. and Tokuda, H. 1985. “A time-Driven Scheduling Model for Real-Time Operating Systems”.Proceedings IEEE Real-Time Systems Symposium, pp. 112–122.

• Locke, C. D., Vogel, D. R. and Mesler, T. J. 1991. “Building a Predictable Avionics Platform in Ada: A Case Study”.Proceedings IEEE Real Time Systems Symposium. pp. 181–189.

• Manacher, G. K. 1967. “Production and Stabilisation of Real-Time Task Schedules”.JACM. 14(3):439–465.

  Google Scholar 

• Mok, A. K. L. 1983. “Fundamental Design Problems of Distributed Systems For The Hard Real-Time Environment”. Laboratory of Computer Science, Massachsetts Institute of Technology. MIT/LCS/TR-297 (PhD Thesis).

• Nassor, E. and Bres, G. 1991. “Hard Real-Time Sporadic Task Scheduling for Fixed Priority Schedulers”.Proceedings International Workshop on Responsive Systems, Golfe-Juan, France, pp. 44–47.

• Nirkhe, V. and Pugh, W. 1993. “A Partial Evaluator for the Maruti Hard Real-Time System”.Real- Time Systems. 5(1): 13–30.

  Google Scholar 

• Park, C. Y. 1993. “Predicting Program Execution Times by Analyzing Static and Dynamic Program Paths”.Real-Time Systems. 5(1): 31–62.

  Google Scholar 

• Park, C. Y. and Shaw, A. C. 1989. “A Source-Level Tool for Predicting Deterministic Execution Times of Programs”. Dept. of Computer Science and Engineering, University of Washington, Seattle, USA, Report #89-09-12.

  Google Scholar 

• Pilling, M. J. 1991. “Dangers of Priority as a Structuring Principle for Real-Time Languages”.Australian Computer Science Communications. 13(1).

• Pilling, M. J., Burns, A. and Raymond, K. 1990. “Formal Specifications and Proofs of Inheritance Protocols for Real-Time Scheduling”.Software Engineering Journal. 5(5): 263–279.

  Google Scholar 

• Pleinevaux, P. 1992. “An Improved Hard Real-Time Scheduling for the IEEE 802.5”.Real-Time Systems. 4(2): 99–112.

  Google Scholar 

• POSIX. 1993. “Real-time Extensions for Portable Operating Systems”, Technical Committee of Operating Systems WG15, P1003.4-Draft 14 (March).

• Puschner, P. and Koza, C. 1989. “Calculating The Maximum Execution Time Of Real-Time Programs”.Real-Time Systems. 1(2): 159–176.

  Google Scholar 

• Rajkumar, R. 1990. “Real-Time Synchronisation Protocols for Shared Memory Multiprocessors”.Proceedings 10th IEEE International Conference on Distributed Computing Systems.

• Rajkumar, R. 1991.Synchronisation in Real-Time Systems: A Priority Inheritance Approach, Kluwer Academic Publishers.

• Rajkumar, R., Sha, L. and Lehoczky, J. P. 1987. “On Countering the Effects of Cycle-Stealing in a Hard Real-Time Environment.”Proceedings IEEE Real-Time Systems Symposium, pp.2–11.

• Rajkumar, R., Sha, L. and Lehoczky, J. P. 1988. “Real-Time Synchronisation Protocols for Multiprocessors”.Proceedings IEEE Real-Time Systems Symposium, pp.259–269.

• Rajkumar, R. Sha, L., Lehoczky, J. P. and Ramamritham, K. 1988. “An Optimal Priority Inheritance Protocol for Real-Time Synchronisation”. Department of Computer and Information Science, University of Massachusetts, USA. COINS Technical Report 88-98.

  Google Scholar 

• Ramamritham, K. 1990. “Allocation and Scheduling of Complex Periodic Tasks”.10th International Conference on Distributed Computing Systems, pp. 108–115.

• Roseman, T. 1992. “Rate-Monotonic Analysis”.Proceedings ACM TriAda (Volume I), pp. 355–376.

• Serlin, O. 1972. “Scheduling of Time Critical Processes”.Proceedings AFIPS Spring Computing Conference, pp. 925–932.

• Sha, L., Lehoczky, J. P. and Rajkumar, R. 1986. “Solutions For Some Practical Problems in Prioritised Preemptive Scheduling”.Proceedings IEEE Real-Time Systems Symposium, pp. 181–191.

• Sha, L., Lehoczky, J. P. and Rajkumar, R. 1987. “Priority Inheritance Protocols: An Approach to Real-Time Synchronisation”. Computer Science Department, Carnegie-Mellon University, USA. CMU-CS-87-181.

  Google Scholar 

• Sha, L., Rajkumar, R. Lehoczky, J. P. and Ramamritham, K. 1989. “Mode Change Protocols for Priority-Driven Pre-emptive Scheduling”.Real-Time Systems. 1(3): 244–264.

  Google Scholar 

• Sha, L., Sprunt, B. and Lehoczky, J. P. 1989. “Aperiodic Task Scheduling for Hard Real-Time Systems”.Real-Time Systems. 1(1): 27–69.

  Google Scholar 

• Sha, L., Rajkumar, R. and Lehoczky, J. P. 1990. “Priority Inheritance Protocols: An Approach to Real-Time Synchronisation”. IEEE Transactions on Computers. 39, (9): 1175–1185.

  Google Scholar 

• Simpson, H. 1990. “Four-Slot Fully Asynchronous Communication Mechanism”.IEE Proceedings Part E. 137(1): 17–30.

  Google Scholar 

• Smith, W.E. 1956. “Various Optimisers for Single-Stage Production”.Naval Research and Logistics Quarterly. 3(1).

• Sorenson, P. G. and Hamacher, V. C. 1975. “A Real-Time System Design Methodology”.INFOR- Canada. 13(1): 1–18.

  Google Scholar 

• Sprunt, B., Lehoczky, J. P. and Sha, L. 1988. “Exploiting Unused Periodic Time For Aperiodic Service Using the Extended Priority Exchange Algorithm”.Proceedings IEEE Real-Time Systems Symposium, pp. 251–258.

• Stankovic, J. A. 1988. “Misconceptions About Real-Time Computing: A Serious Problem for Next Generation Systems”.IEEE Computer. 21(10): 10–19.

  Google Scholar 

• Stankovic, J. A. and Ramamritham, K. 1987.Tutorial on Hard Real-Time Systems. IEEE Computer Society Press.

• Stankovic, J. A. and Ramamritham, K. 1993.Advances in Real-Time Systems. IEEE Computer Society Press.

• Stoyenko, A. D. 1987. “A Schedulability Analyzer for Real-Time Euclid”.Proceedings IEEE Real- Time Systems Symposium. pp. 218–227.

• Stoyenko, A. D. and Marlowe, T. J. 1992. “Polynomial-Time Transformations and Schedulability Analysis of Parallel Real-Time Programs with Restricted Resource Contention”.Real-Time Systems. 4(4): 307–330.

  Google Scholar 

• Strosnider, J. K. and Marchok, T. E. (1989). “Responsive, Deterministic IEEE 802.5 Token Ring Scheduling”.Real-Time Systems. 1(2): 133–158.

  Google Scholar 

• Tindell, K. W. 1992. “An Extendible Approach for Analysing Fixed Priority Hard Real-Time Tasks”. Department of Computer Science, University of York, UK. YCS 189.

  Google Scholar 

• Tindell, K. W., Burns, A. and Wellings, A. J. 1992. “Allocating Real-Time Tasks (An NP-Hard Problem made Easy)”.Real Time Systems. 4(2): 145–165.

  Google Scholar 

• Tindell, K. W., Burns, A. and Wellings, A. J. 1992a. “Mode Changes in Priority Pre-emptive Scheduled Systems”.Proceedings IEEE Real Time Systems Symposium, pp. 100–109.

• Tindell, K. W. and Clark, J. 1993. “Holistic Schedulability Analysis for Distributed Hard Real-Time Systems”.Euromicro Journal (Special Issue on Parallel Embedded Real-Time Systems).

• Tokuda, H. and Kotera, M. 1988. “A Real-Time Toolset for the ARTS Kernel”.Proceedings IEEE Real Time Systems Symposium, pp. 289–299.

• US DoD. 1978. “STEELMAN Requirements for High Order Computer Programming Languages”. U. S. Department of Defense.

• US DoD. 1983. “Reference Manual for the Ada Programming Language”. U.S. Department of Defense. ANSI/MIL-STD 1815 A.

• Wyle, H. and Burnett, G. J. 1967. “Management of Periodic Operations in a Real-Time Computation System”.Proceedings AFIPS Fall Joint Computer Conference, pp. 201–208.

• Zhang, N., Burns, A. and Nicholson, M. 1993. “Pipelined Processors and Worst-Case Execution Times”.Real-Times Systems. 5(4): 319–343.

  Google Scholar 

Download references