RTComposer: a framework for real-time components with scheduling interfaces

ABSTRACT

We present a framework for component-based design and scheduling of real-time embedded software. Each component has a clearly specified interface that includes the methods used for sensing, computation, and actuation, along with a requirement given as a regular set of macro-schedules. Each macro-schedule is an infinite sequence that specifies, for every time slot, the set of component methods invoked in that slot. The macro-scheduler composes the specifications of all the components, along with the platform specification that constrains which methods can be executed within a single slot, to generate a feasible macro-schedule. Within a slot, we use logical execution time semantics, and this micro-scheduling is implemented on top of a native priority-based scheduler. With this approach, each component can be specified and analyzed in a platform-independent way, and at the same time, the performance can vary with changing load and changing processing speed. We describe an implementation using Real-Time Java. Scheduling specifications can be given as periodic tasks, or using temporal logic, or as omega-automata. Components can be added dynamically, and non-real-time components are allowed. We demonstrate the benefits of the approach using case studies.

REFERENCES

• 1: Rajeev Alur , Aditya Kanade , Gera Weiss, Ranking Automata and Games for Prioritized Requirements, Proceedings of the 20th international conference on Computer Aided Verification, July 07-14, 2008, Princeton, NJ, USA [doi>10.1007/978-3-540-70545-1_23]
• 2: Rajeev Alur , Gera Weiss, Regular Specifications of Resource Requirements for Embedded Control Software, Proceedings of the 2008 IEEE Real-Time and Embedded Technology and Applications Symposium, p.159-168, April 22-24, 2008 [doi>10.1109/RTAS.2008.13]
• 3: Madhukar Anand , Sebastian Fischmeister , Insup Lee, Composition Techniques for Tree Communication Schedules, Proceedings of the 19th Euromicro Conference on Real-Time Systems, p.235-246, July 04-06, 2007 [doi>10.1109/ECRTS.2007.88]
• 4: Joshua Auerbach , David F. Bacon , Daniel T. Iercan , Christoph M. Kirsch , V. T. Rajan , Harald Roeck , Rainer Trummer, Java takes flight: time-portable real-time programming with exotasks, Proceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 13-15, 2007, San Diego, California, USA
• 5: Greg Bollella , James Gosling, The Real-Time Specification for Java, Computer, v.33 n.6, p.47-54, June 2000 [doi>10.1109/2.846318]
• 6: Giorgio C. Buttazzo, Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 7: A. Cervin, D. Henriksson, B. Lincoln, J. Eker, and K.-E. Årzén. How does control timing affect performance? IEEE Control Systems Magazine, 23(3):16--30, June 2003.
• 8: A. Chakrabarti, L. de Alfaro, T. Henzinger, and M. Stoelinga. Resource interfaces. In Embedded Software, 3rd International Conference, LNCS 2855, pages 117--133, 2003.
• 9: Luca de Alfaro , Thomas A. Henzinger, Interface automata, Proceedings of the 8th European software engineering conference held jointly with 9th ACM SIGSOFT international symposium on Foundations of software engineering, September 10-14, 2001, Vienna, Austria
• 10: Z. Deng , J. W.-S. Liu, Scheduling real-time applications in an open environment, Proceedings of the 18th IEEE Real-Time Systems Symposium (RTSS '97), p.308, December 03-05, 1997
• 11: E. A. Emerson. Alternative semantics for temporal logics. Theor. Comput. Sci., 26:121--130, 1983.
• 12: Emilia Farcas , Claudiu Farcas , Wolfgang Pree , Josef Templ, Transparent distribution of real-time components based on logical execution time, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 13: T. Henzinger, B. Horowitz, and C. Kirsch. Giotto: A time-triggered language for embedded programming. Proceedings of the IEEE, 91(1):84--99, 2003.
• 14: Thomas A. Henzinger , Christoph M. Kirsch, The embedded machine: predictable, portable real-time code, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 15: T. Henzinger and J. Sifakis. The embedded systems design challenge. In FM 2006: 14th International Symposium on Formal Methods, LNCS 4085, pages 1--15, 2006.
• 16: T. A. Henzinger, B. Horowitz, and C. M. Kirsch. Giotto: a time-triggered language for embedded programming. Proceedings of the IEEE, 91(1):84--99, 2003.
• 17: Hermann Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 18: H. Kopetz and G. Bauer. The time triggered architecture. Proceedings of the IEEE, 91(1):112--126, 2003.
• 19: Edward A. Lee, What's Ahead for Embedded Software?, Computer, v.33 n.9, p.18-26, September 2000
• 20: 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]
• 21: Nancy Lynch , Roberto Segala , Frits Vaandrager, Hybrid I/O automata, Information and Computation, v.185 n.1, p.105-157, August 25, 2003 [doi>10.1016/S0890-5401(03)00067-1]
• 22: Zohar Manna , Amir Pnueli, The temporal logic of reactive and concurrent systems, Springer-Verlag New York, Inc., New York, NY, 1992
• 23: Aloysius K. Mok , Xiang (Alex) Feng, Towards Compositionality in Real-Time Resource Partitioning Based on Regularity Bounds, Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), p.129, December 03-06, 2001
• 24: John Regehr , John A. Stankovic, HLS: A Framework for Composing Soft Real-Time Schedulers, Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), p.3, December 03-06, 2001
• 25: Alberto Sangiovanni-Vincentelli , Luca Carloni , Fernando De Bernardinis , Marco Sgroi, Benefits and challenges for platform-based design, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996684]
• 26: S. Sastry, J. Sztipanovits, R. Bajcsy, and H. Gill. Modeling and design of embedded software. Proceedings of the IEEE, 91(1), 2003.
• 27: Insik Shin , Insup Lee, Compositional real-time scheduling framework with periodic model, ACM Transactions on Embedded Computing Systems (TECS), v.7 n.3, p.1-39, April 2008 [doi>10.1145/1347375.1347383]
• 28: http://www.mathworks.com/products/simulink/.
• 29: Lothar Thiele , Ernesto Wandeler , Nikolay Stoimenov, Real-time interfaces for composing real-time systems, Proceedings of the 6th ACM & IEEE International conference on Embedded software, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176887.1176894]
• 30: Wolfgang Thomas, Automata on infinite objects, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 31: Y.-K. Tsay, Y.-F. Chen, M.-H. Tsai, K.-N. Wu, and W.-C. Chan. Goal: A graphical tool for manipulating büchi automata and temporal formulae. In Proceedings of the 13th conference on Tools and Algorithms for Construction and Analysis of Systems, pages 466--471, 2007.
• 32: G. Weiss and R. Alur. Automata based interfaces for control and scheduling. In Proceedings of the 10th workshop on Hybrid Systems: Computation and Control, 2007.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS
      Subjects: Process control; Real time

General Terms:
Performance, Reliability

Keywords:
automata based scheduling, real time specification for java (RTSJ)