A typed assembly language for real-time programs

ABSTRACT

We present a type system for E code, which is an assembly language that manages the release, interaction, and termination of real-time tasks. E code specifies a deadline for each task, and the type system ensures that the deadlines are path-insensitive. We show that typed E programs allow, for given worst-case execution times of tasks, a simple schedulability analysis. Moreover, the real-time programming language Giotto can be compiled into typed E~code. This shows that typed E~code identifies an easily schedulable yet expressive class of real-time programs. We have extended the Giotto compiler to generate typed E code, and enabled the run-time system for E code to perform a type and schedulability check before executing the code.

REFERENCES

• 1: Christian Ferdinand , Reinhold Heckmann , Marc Langenbach , Florian Martin , Michael Schmidt , Henrik Theiling , Stephan Thesing , Reinhard Wilhelm, Reliable and Precise WCET Determination for a Real-Life Processor, Proceedings of the First International Workshop on Embedded Software, p.469-485, October 08-10, 2001
• 2: T.A. Henzinger, B. Horowitz, C.M. Kirsch. Giotto: A time-triggered language for embedded programming. In Proc. IEEE 91(1):84--99, 2003.
• 3: 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
• 4: 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
• 5: T.A. Henzinger, C.M. Kirsch, S. Matic. Schedule-carrying code. In Proc. EMSOFT, LNCS 2855, pp. 241--256. Springer, 2003.
• 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: S. Mork, K. Larsen, H.R. Andersen, P. Sestoft. PMC: A programming language for embedded systems. In Proc. Int. Workshop Formal Methods for Industrial Critical Systems, July 1999.
• 8: Greg Morrisett , David Walker , Karl Crary , Neal Glew, From system F to typed assembly language, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.3, p.527-568, May 1999 [doi>10.1145/319301.319345]

INDEX TERMS

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

General Terms:
Languages

Keywords:
real time, typed assembly language, virtual machine