High-level real-time programming in Java

ABSTRACT

Real-time systems have reached a level of complexity beyond the scaling capability of the low-level or restricted languages traditionally used for real-time programming.While Metronome garbage collection has made it practical to use Java to implement real-time systems, many challenges remain for the construction of complex real-time systems, some specific to the use of Java and others simply due to the change in scale of such systems.The goal of our current research is the creation of a comprehensive Java-based programming environment and methodology for the creation of complex real-time systems. Our goals include construction of a provably correct real-time garbage collector capable of providing worst case latencies of 100 μs, capable of scaling from sensor nodes up to large multiprocessors; specialized programming constructs that retain the safety and simplicity of Java, and yet provide sub-microsecond latencies; the extension of Java's "write once, run anywhere" principle from functional correctness to timing behavior; on-line analysis and visualization that aids in the understanding of complex behaviors; and a principled probabilistic analysis methodology for bounding the behavior of the resulting systems.While much remains to be done, this paper describes the progress we have made towards these goals.

REFERENCES

• 1: David F. Bacon , Perry Cheng , V. T. Rajan, Controlling fragmentation and space consumption in the metronome, a real-time garbage collector for Java, ACM SIGPLAN Notices, v.38 n.7, July 2003
• 2: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, ACM SIGPLAN Notices, v.38 n.1, p.285-298, January 2003
• 3: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 4: Mordechai Ben-Ari, Algorithms for on-the-fly garbage collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.333-344, July 1984 [doi>10.1145/579.587]
• 5: Guillem Bernat , Antoine Colin , Stefan M. Petters, WCET Analysis of Probabilistic Hard Real-Time Systems, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.279, December 03-05, 2002
• 6: Guy E. Blelloch , Perry Cheng, On bounding time and space for multiprocessor garbage collection, ACM SIGPLAN Notices, v.34 n.5, p.104-117, May 1999
• 7: James Gosling , Greg Bollella, The Real-Time Specification for Java, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 8: Rodney A. Brooks, Trading data space for reduced time and code space in real-time garbage collection on stock hardware, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.256-262, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802042]
• 9: Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, ACM SIGPLAN Notices, v.36 n.5, p.125-136, May 2001
• 10: Dembo, A., and Zeitouni, O. Large Deviations: Techniques and Applications, second ed., vol. 38 of Stochastic Modelling and Applied Probability. Springer-Verlag, 1998.
• 11: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 12: 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
• 13: Henzinger, T. A., Kirsch, C. M., and Horowitz, B. Giotto: A time-triggered language for embedded programming. Proceedings of the IEEE 91, 1 (Jan. 2003), 84--99.
• 14: Henzinger, T. A., Kirsch, C. M., and Matic, S. Schedule-carrying code. In Proc. of the Third International Conference on Embedded Software (Philadelphia, Pennsylvania, Oct. 2003), R. Alur and I. Lee, Eds., vol. 2855 of Lecture Notes in Computer Science, pp. 241--256.
• 15: IBM Corporation. Enterprise Systems Architecture/390 Principles of Operation, ninth ed., June 2003.
• 16: Jikes Research Virtual Machine (RVM). http://jikesrvm.sourceforge.net.
• 17: Lamport, L. Garbage collection with multiple processes: an exercise in parallelism. In Proc. of the 1976 International Conference on Parallel Processing (1976), pp. 50--54.
• 18: Edward A. Lee, What's Ahead for Embedded Software?, Computer, v.33 n.9, p.18-26, September 2000
• 19: Tobias Mann , Morgan Deters , Rob LeGrand , Ron K. Cytron, Static determination of allocation rates to support real-time garbage collection, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 20: Pixley, C. An incremental garbage collection algorithm for multi-mutator systems. Distributed Computing 6, 3 (Dec. 1988), 41--49.
• 21: Tony Printezis , Richard Jones, GCspy: an adaptable heap visualisation framework, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 22: Konstantinos Sagonas , Jesper Wilhelmsson, Message analysis-guided allocation and low-pause incremental garbage collection in a concurrent language, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029875]
• 23: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
• 24: Steele, G. L. Corrigendum: Multiprocessing compactifying garbage collection. Commun. ACM 19, 6 (June 1976), 354.
• 25: Vechev, M. T., Bacon, D. F., Cheng, P., and Grove, D. Derivation and evaluation of concurrent collectors. In Proceedings of the Nineteenth European Conference on Object-Oriented Programming (Glasgow, Scotland, July 2005), A. Black, Ed., Lecture Notes in Computer Science, Springer-Verlag.
• 26: Vechev, M. T., Yahav, E., and Bacon, D. F. Parametric generation of concurrent collection algorithms. Submitted for publication, July 2005.
• 27: T. Yuasa, Real-time garbage collection on general-purpose machines, Journal of Systems and Software, v.11 n.3, p.181-198, Mar. 1990 [doi>10.1016/0164-1212(90)90084-Y]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management
      D.3.4 Processors
          Subjects: Memory management (garbage collection)
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Experimentation, Languages, Measurement, Performance

Keywords:
WCET, allocation, scheduling, tasks, visualization