A hierarchical coordination language for interacting real-time tasks

ABSTRACT

We designed and implemented a new programming language called Hierarchical Timing Language (HTL) for hard realtime systems. Critical timing constraints are specified within the language,and ensured by the compiler. Programs in HTL are extensible in two dimensions without changing their timing behavior: new program modules can be added, and individual program tasks can be refined. The mechanism supporting time invariance under parallel composition is that different program modules communicate at specified instances of time. Time invariance under refinement is achieved by conservative scheduling of the top level. HTL is a coordination language, in that individual tasks can be implemented in "foreign" languages. As a case study, we present a distributed HTL implementation of an automotive steer-by-wire controller.

REFERENCES

• 1: Henzinger, T. A., Horowitz, B., Kirsch, C.M.: Giotto: A time-triggered language for embedded programming. Proceedings of the IEEE 91 (2003) 84--99
• 2: 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
• 3: Ghosal, A., Henzinger, T. A., Iercan, D., Kirsch, C., Sangiovanni-Vincentelli, A.: Hierarchical timing language. Technical report, UC Berkeley (2006)
• 4: Ken Tindell , John Clark, Holistic schedulability analysis for distributed hard real-time systems, Microprocessing and Microprogramming, v.40 n.2-3, p.117-134, April 1994 [doi>10.1016/0165-6074(94)90080-9]
• 5: Christoph M. Kirsch , Marco A. A. Sanvido , Thomas A. Henzinger, A programmable microkernel for real-time systems, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064986]
• 6: Thomas A. Henzinger , Christoph Meyer Kirsch , Rupak Majumdar , Slobodan Matic, Time-Safety Checking for Embedded Programs, Proceedings of the Second International Conference on Embedded Software, p.76-92, October 07-09, 2002
• 7: Giorgio C. Buttazzo , Giorgio Buttanzo, Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 8: Emilia Farcas , Claudiu Farcas , Wolfgang Pree , Josef Templ, Transparent distribution of real-time components based on logical execution time, ACM SIGPLAN Notices, v.40 n.7, July 2005
• 9: Liu, J., Lee, E.A.: Timed multitasking for real-time embedded software. IEEE Control Systems Magazine 23 (2003) 65--75
• 10: Ghosal, A., Henzinger, T. A., Kirsch, C. M., Sanvido, M. A. A.: Event-driven programming with logical execution times. In: Hybrid Systems Computation and Control. Lecture Notes in Computer Science 2993. Springer-Verlag (2004)
• 11: Boussinot, F., de Simone, R.: The ESTEREL language. Proceedings of the IEEE 79 (1991) 1293--1304
• 12: Halbwachs, N., Caspi, P., Raymond, P., Pilaud, D.: The synchronous data-flow programming language LUSTRE. Proceedings of the IEEE 79 (1991) 1305--1320
• 13: Guernic, P. L., Borgne, M. L., Gauthier, T., Maire, C. L.: Programming real time applications with SIGNAL. Proceedings of the IEEE 79 (1991) 1321--1336
• 14: Simulink: (http://www.mathworks.com/products/simulink/)
• 15: Real-Time-Workshop: (http://www.mathworks.com/products/rtw/)
• 16: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 17: Joe Armstrong , Robert Virding , Claes Wikström , Mike Williams, Concurrent programming in ERLANG (2nd ed.), Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1996
• 18: Kevin B. Kenny , Kwei-Jay Lin, Building Flexible Real-Time Systems Using the Flex Language, Computer, v.24 n.5, p.70-78, May 1991 [doi>10.1109/2.76288]

INDEX TERMS

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

General Terms:
Languages

Keywords:
automotive systems, real time