Schedulability-driven performance analysis of multiple mode embedded real-time systems

ABSTRACT

Providing multiple modes to support dynamically changing environments, standards, and new services is prevalent in embedded systems, especially in mobile radio systems. Because such a system frequently contains time-constrained tasks, it is important to analyze the temporal requirements as well as the functional correctness. This paper presents a method to analyze temporal requirements imposed on an embedded real-time system supporting multiple modes. While most performance analysis methods focus only on testing the feasibility of a task or a system, our method goes further by addressing the problem of locating hot spots of a system thereby helping the designer to choose among alternative designs or architectures. We formally define the analysis problem and show that it is very unlikely to be solved efficiently. We present a heuristic algorithm, which is accurate and fast enough to be used in iterative processes in system-level analysis and design. The analysis problem is extended to accommodate probabilistic behavior exhibited by soft real-time tasks.

REFERENCES

• 1: J. Mitola, "The software radio architecture," IEEE Communications Magizine, pp. 26-38, May 1995.
• 2: W. Tuttlebee, "The impact of software radio," in Proc. Software Radio Workshop, May 1997.
• 3: C. Douglass Locke, Software architecture for hard real-time applications: cyclic executives vs. fixed priority executives, Real-Time Systems, v.4 n.1, p.37-53, March 1992 [doi>10.1007/BF00365463]
• 4: Hassan Gomaa, Software Design Methods for Concurrent and Real-Time Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 5: R. Gerber and S. Hong, "Semantics-based compiler transformations for enhanced schedulability," in Proc. IEEE Real-Time Systems Symposium, Dec. 1993.
• 6: G. Arora and D. Stewart, "AFTER: A CASE tool to assist in fine-tuning of embedded real-time systems," in Proc. IEEE Real-Time Systems Symposium, Dec. 1996.
• 7: P. Pedro and A. Burns, "Schedulability analysis for mode changes in flexible real-time systems," in P~vc. Eu~vmic~v Workshop on Real-Time Systems, pp. 17- 19, June 1998.
• 8: Asawaree Kalavade , Pratyush Moghé, A tool for performance estimation of networked embedded end-systems, Proceedings of the 35th annual conference on Design automation, p.257-262, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277116]
• 9: Tao Zhou , Xiaobo (Sharon) Hu , Edwin H.-M. Sha, A probabilistic performance metric for real-time system design, Proceedings of the seventh international workshop on Hardware/software codesign, p.90-94, March 1999, Rome, Italy [doi>10.1145/301177.301494]
• 10: 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]
• 11: A. Atlas , A. Bestavros, Statistical Rate Monotonic Scheduling, Proceedings of the IEEE Real-Time Systems Symposium, p.123, December 02-04, 1998
• 12: D. I. Katcher , H. Arakawa , J. K. Strosnider, Engineering and Analysis of Fixed Priority Schedulers, IEEE Transactions on Software Engineering, v.19 n.9, p.920-934, September 1993 [doi>10.1109/32.241774]
• 13: 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]
• 14: Youngsoo Shin , Kiyoung Choi, Enforcing Schedulability of Multi-Task Systems by Hardware-Software Codesign, Proceedings of the 5th International Workshop on Hardware/Software Co-Design, p.3, March 24-26, 1997
• 15: J. Lehoczky, L. Sha, and Y. Ding, "The rate monotonic scheduling algorithm: Exact characterization and average case behavior," in P~vc. IEEE Real-Time Systems Symposium, pp. 166-171, Dec. 1989.
• 16: L. Abeni , G. Buttazzo, Integrating Multimedia Applications in Hard Real-Time Systems, Proceedings of the IEEE Real-Time Systems Symposium, p.4, December 02-04, 1998
• 17: T.-S. Tia , Z. Deng , M. Shankar , M. Storch , J. Sun , L.-C. Wu , J. W.-S. Liu, Probabilistic performance guarantee for real-time tasks with varying computation times, Proceedings of the Real-Time Technology and Applications Symposium, p.164, May 15-17, 1995
• 18: Frank Slomka , Jürgen Zant , Lennard Lambert, Schedulability analysis of heterogeneous systems for performance message sequence chart, Proceedings of the 6th international workshop on Hardware/software codesign, p.91-95, March 15-18, 1998, Seattle, Washington, United States

INDEX TERMS

Primary Classification:
  J. Computer Applications

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

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods; Scheduling

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