Schedule validation for embedded reactive real-time systems

ABSTRACT

Task scheduling for reactive real time systems is adifficult problem due to tight constraints that theschedule must satisfy.A static priority schemeis proposed here that can be formally validated.The method is applicable both for preemptiveand non-preemptive schedules and is conservativein the sense that a valid schedule may bedeclared invalid, but no invalid schedule may bedeclared valid.Experimental results show thatthe run time of our validation method is negligiblewith respect to other steps in system designprocess, and compares favorably with othermethods of schedule validation.

REFERENCES

• 1: Neil C. Audsley, Alan Burns, M. Richardson, Ken W. Tindell, and Andy J. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, pages 284-292, September 1993.
• 2: Felice Balarin , Harry Hsieh , Attila Jurecska , Luciano Lavagno , Alberto Sangiovanni-Vincentelli, Formal verification of embedded systems based on CFSM networks, Proceedings of the 33rd annual conference on Design automation, p.568-571, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240626]
• 3: Felice Balarin, Karl Petty, Alberto L. Sangiovanni- Vincentelli, and Pravin Varaiya. Formal verification of the PATHO real-time operating system. In Proceedings of 33rd Conference on Decision and Control, CDC'94, December 1994.
• 4: Felice Balarin and Alberto Sangiovanni-Vincentelli. Schedule validation for embedded reactive real-time systems. Technical report, Cadence Berkeley Laboratories, October 1996.
• 5: Massimilano Chiodo , Paolo Giusto , Attila Jurecska , Harry C. Hsieh , Alberto Sangiovanni-Vincentelli , Luciano Lavagno, Hardware-Software Codesign of Embedded Systems, IEEE Micro, v.14 n.4, p.26-36, August 1994 [doi>10.1109/40.296155]
• 6: M. G. Harbour , M. H. Klein , J. P. Lehoczky, Timing Analysis for Fixed-Priority Scheduling of Hard Real-Time Systems, IEEE Transactions on Software Engineering, v.20 n.1, p.13-28, January 1994 [doi>10.1109/32.263752]
• 7: 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]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Design, Experimentation, Measurement, Performance, Theory, Verification