Implementing analysable hard real-time sporadic tasks in Ada 9X

ABSTRACT

In this paper we illustrate how systems containing hard real-time sporadic tasks can be analysed for their worst case behaviour. In order to undertake this schedulability analysis, it is necessary to define the minimum inter-arrival time and/or maximum arrival frequency of sporadic tasks. Furthermore, at run-time it is essential to ensure that sporadic tasks are not invoked more often than has been guaranteed by the analysis. We assume that sporadics are invoked by interrupts and that interrupts can be masked under software control.Sporadic tasks are often analysed using the notion of bandwidth preserving sporadic servers within the Rate Monotonic Scheduling Analysis scheme. At run-time this requires the underlying kernel to support complex execution time monitoring mechanisms. Unfortunately such mechanisms are not generally supported by Ada 9X. This paper shows that by using Deadline Monotonic Scheduling Analysis there is no need to resort to bandwidth preserving sporadic servers, and the facilities available in Ada 9X can be used.

REFERENCES

• 1: 1. Ada 9X Mapping/Revision Team, Intermetrics, "Ada 9X Reference Manual, Draft Version 3.0", Ada 9X Project Report (June 1993).
• 2: 2. N. Audsley, A. Burns, M. Richardson, K. Tindell and A. Wellings, "Applying New Scheduling Theory to Static Priority Pre-emptive Scheduling", Software Engineering Journal (to appear).
• 3: 3. N. C. Audsley, A. Burns, M. F. Richardson and A. J. Wellings, "Hard Real-Time Scheduling: The Deadline Monotonic Approach", Proceedings 8th IEEE Workshop on Real-Time Operating Systems and Software, Atlanta, GA, USA (15-17 May 1991).
• 4: Alan Burns , Andy J. Wellings , A. D. Hutcheon, The Impact of an Ada Run-Time System's Performance Characteristics on Scheduling Models, Proceedings of the 12th Ada-Europe International Conference, p.240-248, June 14-18, 1993
• 5: 5. J. P. Lehoczky, L. Sha and J. K. Strosnider, Enhancing Aperiodic Responsiveness in Hard Real-Time Environment, Proc. 8th IEEE Real-Time Systems Symposium, San Jose, California, December 1987.
• 6: 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]
• 7: Michael Pilling , Alan Burns , Kerry Raymond, Formal specifications and proofs of inheritance protocols for real-time scheduling, Software Engineering Journal, v.5 n.5, p.263-279, Sep. 1990
• 8: 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]
• 9: 9. B. Sprunt, J. Lehoczky and L. Sha, "Exploiting Unused Periodic Time For Aperiodic Service Using the Extended Priority Exchange Algorithm", Proceedings IEEE Real-Time Systems Symposium, pp. 251-258 (December 1988).
• 10: 10. B. Sprunt, L. Sha and J. P. Lehoczky, "Aperiodic Task Scheduling for Hard Real-Time Systems", Real-Time Systems 1, pp. 27-69 (1989).

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Ada

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

  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:
Design, Languages, Theory