Seminal papers

Principles of real-time systems

  • J. A. Stankovic: Misconceptions About Real-Time Computing: A Serious Problem for Next-Generation Systems, IEEE Computer, Vol. 21, Issue 10, October 1988.

Periodic task scheduling

Surveys

  • N. C. Audsley, A. Burns, R. I. Davis, K. W. Tindell and A. J. Wellings: “Fixed Priority Scheduling: A Historical Perspective”, Real-Time Systems, Vol. 8, No. 3, pp. 173-198, 1995.
  • L. Sha, T. Abdelzaher, K.-E. Arzen, A. Cervin, T. Baker, A. Burns, G. Buttazzo, M. Caccamo, J. Lehoczky and A. Mok: “Real-Time Scheduling Theory: A Historical Perspective,” Real-Time Systems, Vol. 28, No. 2-3, pp. 101-155, November-December 2004.

Rate Monotonic

  • C. L. Liu and J. W. Layland: Scheduling Algoritms for Multiprogramming in a Hard-Real-Time Environment, Journal of ACM, Vol. 20, No. 1, January 1973.

Deadline Monotonic

  • J. Leung and J. Whitehead: “On the Complexity of Fixed-Priority Scheduling of Periodic Real-Time Tasks”, Performance Evaluation, Vol. 2, No. 4, pp. 237—250, December 1982.

Earliest Deadline First

  • C. L. Liu and J. W. Layland: Scheduling Algoritms for Multiprogramming in a Hard-Real-Time Environment, Journal of ACM, Vol. 20, No. 1, January 1973.
  • M. L. Dertouzos: Control Robotics: the Procedural Control of Physical Processes, Information Processing, Vol. 74, pp. 807–813, 1974.

Analysis of fixed priority preemptive scheduling algorithms

  • N.C. Audsley, A. Burns, M.F. Richardson, K. Tindell, and A. J. Wellings: Applying new scheduling theory to static priority pre-emptive scheduling, Software Engineering Journal, 8(5):284–292, September 1993.
  • E. Bini and G. Buttazzo: Schedulability Analysis of Periodic Fixed Priority Systems, IEEE Transactions on Computers, Vol. 53, Issue 11, pp. 1462-1473, November 2004.

Analysis of deadline-based scheduling algorithms

  • S. K. Baruah, R. R. Howell, and L. E. Rosier:  Algorithms and Complexity Concerning the Preemptive Scheduling of Periodic Real-Time Tasks on One Processor, Real-Time Systems, Vol. 2, 1990.

Offset analysis

  • J.Y. Leung and M.L. Merrill: A Note on Preemptive Scheduling of Periodic, Real-Time Tasks, Information Processing Letters, Vol. 11, No. 3, pp. 115-118, 1980.
  • J. Goossens and R. Devillers: The Non-Optimality of the Monotonic Priority Assignments for Hard Real-Time Offset Free Systems, Real-Time Systems, Vol. 13, No. 2, pp. 107-126, 1997.
  • J. Goossens: Scheduling of Offset Free Systems, Real-Time Systems, Vol. 24, No. 2, pp. 239-258, 2003.
  • R. Pellizzoni and G. Lipari: Feasibility Analysis of Real-Time Periodic Tasks with Offsets, Real-Time Systems, Vol. 30, No. 1, pp. 105-128, 2005.

Interrupt analysis

  • K. Jeffay and D. L. Stone: Accounting for interrupt handling costs in dynamic priority task systems, Proceedings of the IEEE Real-Time Systems Symposium, pages 212–221, December 1993.

Limited preemption scheduling

  • K. Jeffay, D. F. Stanat, and C. U. Martel: On non-preemptive scheduling of periodic and sporadic tasks with varying execution priority, Proceedings of the IEEE Real-Time Systems Symposium, pages 129–139, December 1991.
  • A. Burns: Preemptive priority based scheduling: An appropriate engineering approach, Advances in Real-Time Systems (S. Son, editor), pp. 225–248, 1994.
  • Y. Wang and M. Saksena: Scheduling fixed-priority tasks with preemption threshold, Proceedings of the IEEE Int. Conference on Real-Time Computing Systems and Applications, pages 328–335, December 1999.
  • S. K. Baruah: The limited-preemption uniprocessor scheduling of sporadic task systems, Proceedings of the Euromicro Conference on Real-Time Systems, pp. 137–144, July 2005.
  • R. J. Bril, J. J. Lukkien, andW. F. J. Verhaegh: Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption, Real-Time Systems, Vol. 42, No. 1-3, pp. 63–119, 2009.
  • G. Yao, G. Buttazzo and M. Bertogna: Feasibility Analysis under Fixed Priority Scheduling with Limited Preemptions, Real-Time Systems, Vol. 47, No. 3, pp. 198-223, May 2011.

Shared resource protocols

Priority Inheritance and Priority Ceiling

  • L. Sha, R. Rajkumar, and J. P. Lehoczky: Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, Vol. 39, No. 9, September 1990.

Stack Resource Policy

  • T.P. Baker: Stack-Based Scheduling of Real-Time Processes, Real-Time Systems, Vol. 3, No. 1, pp. 67-100, 1991.

Aperiodic task scheduling

  • J. P. Lehoczky, L. Sha, and J. K. Strosnider: Enhanced Aperiodic Responsiveness in Hard Real-Time Environments, Proceedings of the IEEE Real-Time Systems Symposium, pp. 261-270, December 1987.
  • J. K. Strosnider, J. P. Lehoczky and L. Sha: The Deferrable Server Algorithm for Enhanced Aperiodic Responsiveness in Hard Real-Time Environments, IEEE Transactions on Computers, Vol. 44, No. 1, pp. 73-91, January 1995.
  • B. Sprunt, L. Sha, and J. Lehoczky: Aperiodic Task Scheduling for Hard Real-Time System, Real-Time Systems, Vol. 1, pp. 27-60, June 1989.
  • T. M. Ghazalie and T. P. Baker: Aperiodic Servers in a Deadline Scheduling Environment, Real-Time Systems, Vol. 9, No. 1, July 1995.
  • M. Spuri and G. Buttazzo: Scheduling Aperiodic Tasks in Dynamic Priority Systems, Real-Time Systems, Vol. 10, No. 2, pp. 179-210, March 1996.

Resource reservation

  • C. W. Mercer, S. Savage, and H. Tokuda: Processor capacity reserves for multimedia operating systems, Proceedings of IEEE International Conference on Multimedia Computing and System, May 1994.
  • C. W. Mercer, S. Savage, and H. Tokuda: Temporal protection in realtime operating systems, Proceedings of the IEEE workshop on Real-Time Operating System and Software, pp. 79–83. IEEE, May 1994.
  • L. Abeni and G. C. Buttazzo: Resource Reservation in Dynamic Real-Time Systems, Real-Time Systems, Vol. 27, No. 2, pp. 123-167, July 2004.

Energy-aware scheduling

  • H. Aydin, R. Melhem, D. Mosse, and P.M. Alvarez: Power-aware Scheduling for Periodic Real-time Tasks, IEEE Transactions on Computers, vol. 53, no. 5, pp. 584 – 600, May 2004.

Overload handling

  • S. K. Baruah, G. Koren, D. Mao, A. R. B. Mishra, L. Rosier, D. Shasha, and F. Wang: On the competitiveness of on-line real-time task scheduling, Real-Time Systems, Vol. 4, 1992.
  • S. K. Baruah and L. E. Rosier: Limitations concerning on-line scheduling algorithms for overloaded real-time systems, IEEE Workshop on Real-Time Operating Systems and Software, 1991.
  • G. Koren and D. Shasha: Dover: An optimal on-line scheduling algorithm for overloaded real-time systems, Proceedings of the IEEE Real-Time Systems Symposium, 1992.
  • G. Koren and D. Shasha: SkipOver: Algorithms and complexity for overloaded systems that allow skips, Proceedings of the IEEE Real-Time Systems Symposium, December 1995.
  • G. Buttazzo, G. Lipari, M. Caccamo, and L. Abeni: Elastic Scheduling for Flexible Workload Management, IEEE Transactions on Computers, Vol. 51, No. 3, pp. 289-302, March 2002.

Mixed Criticality Systems

  • S. Vestal: Preemptive Scheduling of Multi-Criticality Systems with Varying Degrees of Execution Time Assurance, Proceedings of the IEEE Real-Time Systems Symposium, Tucson, Arizona, USA, December 3-6, 2007.
  • S. K. Baruah, A. Burns, and R. I. Davis: Response-Time Analysis for Mixed Criticality Systems, Proceedings of the IEEE Real-Time Systems Symposium, Vienna, Austria, Nov. 29 – Dec. 2, 2011.
  • S. K. Baruah, V. Bonifaci, G. D’Angelo, H. Li, A. Marchetti-Spaccamela, N. Megow, and L. Stougie: Scheduling Real-Time Mixed-Criticality Jobs, IEEE Transactions on Computers, Vol. 61, No. 8, pp. 1140-1152, August 2012.
  • P. Ekberg and W. Yi: Bounding and Shaping the Demand of Mixed-Criticality Sporadic Tasks. IEEE Proceedings of the 24th Euromicro Conference on Real-Time Systems (ECRTS 2012), Pisa, Italy, July 10-13, 2012.

The time-triggered paradigm

  • H. Kopetz: The time-triggered model of computation, Proceedings of the IEEE Real-Time Systems Symposium, pp 168-177, December 1995.
  • D. Isovic, G. Fohler: Handling Mixed Sets of Tasks in Combined Offline and Online Scheduled Real-Time Systems, Real-Time Systems, Vol. 43, No. 3,
    pp. 296-325, January 2009.

Synthetic task generation algorithms

  • E. Bini and G. Buttazzo: Measuring the Performance of Schedulability Tests, Real-Time Systems, Vol. 30, No. 1/2, pp. 129-154, May 2005.
  • R. Davis and A. Burns: Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems, Real-Time Systems, Vol. 47, No. 1, pp. 1–40, January 2011.

Multiprocessor scheduling

Surveys

  • R.I. Davis and A. Burns, A Survey of Hard Real-Time Scheduling for Multiprocessor Systems, ACM Computing Surveys, 43 (4), Article 35, October 2011.

Partitioning upon identical multiprocessors

  • D. S. Hochbaum and D. B. Shmoys: Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results, Journal of the ACM, Vol. 34, No. 1, 1987
  • D. Oh and T. Baker: Utilization bounds for N-processor rate monotone scheduling with static priority assignment, Real-Time Systems, Vol. 15, pp. 183-192, 1998
  • J. M. Lopez, J. L. Diaz and D. F. Garcia: Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems, Real-Time Systems, Vol. 28, No. 1, pp. 39-68, 2004

Partitioning upon unrelated multiprocessors

  • J. K. Lenstra, D. B. Shmoys and E. Tardos: Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming, Vol. 46, pp. 259-271, 1990.

Global scheduling upon identical multiprocessors

  • C. Phillips, C. Stein, E. Torng, and J. Wein: Optimal time-critical scheduling via resource augmentation, Algorithmica, Vol. 32, No. 2, pp. 163–200, 2002.
  • T. Baker: Multiprocessor EDF and Deadline-Monotonic schedulablity analysis, Proceedings of the IEEE Real-Time Systems Symposium, pp 120-129, December 2003
  • M Bertogna, M. Cirinei, and G. Lipari: New Schedulability Tests for Real-Time Tasks Sets Scheduled  by Deadline Monotonic on Multiprocessors, Proceedings of the International  Conference on Principles of Distributed Systems, Dec 2005.

Global scheduling upon unrelated (heterogeneous) multiprocessors

  • E. Lawler and J. Labetoulle: On preemptive scheduling of unrelated parallel processors by linear programming, Journal of the ACM, Vol. 25, No. 4, 1978

Resource sharing

  • B. Brandenburg and J. Anderson: Optimality Results for Multiprocessor Real-Time Locking, Proceedings of the IEEE Real-Time Systems Symposium, pp. 49-60, December 2010.
  • R. Rajkumar, L. Sha, and J. Lehoczky: Real-time synchronization protocols for multiprocessors. Proceedings of the IEEE Real-Time Systems Symposium, pp. 259–269, 1988.

Real-time networks

  • R.L. Cruz: A calculus for network delay (Parts I and II), IEEE Transactions on Information Theory, Vol. 37, No. 1, January 1991.
  • J. Stankovic, T. Abdelzaher, C. Lu, L. Sha, and J. Hou: Real-time communication and coordination in embedded sensor networks, Proceedings of the IEEE, vol. 91, pp. 1002-1022, July 2003.
  • H. Kopetz: Should Responsive Systems Be Event-triggered or Time-triggered?, IEICE Transactions on Information and Systems, Vol. E76-D, No. 11, November 1993.
  • K. Tindell, A. Burns, and A. Wellings: Analysis of Hard Real-Time Communication, Real-Time Systems, Vol. 9, pp. 147-171, 1995.
  • D. Ferrari: A New Admission Control Method for Real-Time Communication in an Internetwork, Advances in Real-Time Systems (S. Son, editor), Prentice Hall, 1995.

Real-Time and Control

  • T. Abdelzaher, J. Stankovic, C. Lu, R. Zhang, and Y. Lu: Feedback Performance Control in Software Systems, IEEE Control Systems, Vol. 23, No. 3, pp. 74-90, June 2003.
  • D. Seto, J. P. Lehoczky, L. Sha, and K. G. Shin: On Task Schedulability in Real-Time Control Systems, Proceedings of the IEEE Real-Time Systems Symposium, December 1996.

Timing analysis

  • R. Wilhelm et al., The Worst-Case Execution Time Problem— Overview of Methods and Survey of Tools, ACM Transactions on Embedded Computing Systems, Vol. 7, No. 3, April 2008.

Timed automata

  • J. Bengtsson and W. Yi: Timed Automata: Semantics, Algorithms and Tools, Lecture Notes on Concurrency and Petri Nets (W. Reisig and G. Rozenberg, editors), Lecture Notes in Computer Science, Vol. 3098, pp. 87-124, 2003.
  • R. Alur and D. Dill: A Theory of Timed Automata, Theoretical Computer Science, Vol. 126, No. 2, pp. 183-235, 1994
  • E. Fersman, P. Krcal, P. Pettersson and W. Yi: Task Automata: Schedulability, Decidability and Undecidability, Information and Computation, Vol. 205, No. 8, 2007.

Hybrid systems

  • R Alur, T Henzinger, and P. Ho: Automatic symbolic verification of embedded systems, IEEE Transactions on Software Engineering, Vol. 22, pp. 181-201, 1996.

Formal Methods

  • D. Harel: Statecharts: a visual formalism for complex systems, Science of Computer Programming, Vol. 8, pp. 231-274, 1987.
  • F. Jahanian, A. K. Mok, Safety Analysis of Timing Properties in Real-Time Systems, IEEE Transactions on Software Engineering, Vol. 12, No. 9, pp. 890-904, 1986.

Synchronous Languages

  • N. Halbwachs, P. Caspi, P. Raymond, D. Pilaud: The Synchronous Data Flow Programming Language LUSTRE, Proceedings of the IEEE, September 1991.
  • G Berry, S. Moisain and J. -P Rigault: ESTEREL: Towards a synchronous and semantically sound high-level language for real-time applications, Proceedings of the IEEE Real-Time Systems Symposium, pp. 30-37, 1983.