Eventrons: a safe programming construct for high-frequency hard real-time applications

ABSTRACT

While real-time garbage collection has achieved worst-case latencies on the order of a millisecond, this technology is approaching its practical limits. For tasks requiring extremely low latency, and especially periodic tasks with frequencies above 1 KHz, Java programmers must currently resort to the NoHeapRealtimeThread construct of the Real-Time Specification for Java. This technique requires expensive run-time checks, can result in unpredictable low-level exceptions, and inhibits communication with the rest of the garbage-collected application. We present Eventrons, a programming construct that can arbitrarily preempt the garbage collector, yet guarantees safety and allows its data to be visible to the garbage-collected heap. Eventrons are a strict subset of Java, and require no run-time memory access checks. Safety is enforced using a data-sensitive analysis and simple run-time support with extremely low overhead. We have implemented Eventrons in IBM's J9 Java virtual machine, and present experimental results in which we ran Eventrons at frequencies up to 22 KHz (a 45 μs period). Across 10 million periods, 99.997% of the executions ran within 10 μss of their deadline, compared to 99.999% of the executions of the equivalent program written in C.

REFERENCES

• 1: ARNOLD, M., FINK, S. J., GROVE, D., HIND, M., AND SWEENEY, P. F. A survey of adaptive optimization in virtual machines. Proceedings of the IEEE 93, 2 (2005). Special issue on Program Generation, Optimization, and Adaptation.
• 2: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-298, January 15-17, 2003, New Orleans, Louisiana, USA
• 3: Daniel G. Bobrow , Daniel L. Murphy, Structure of a LISP system using two-level storage, Communications of the ACM, v.10 n.3, p.155-159, March 1967 [doi>10.1145/363162.363185]
• 4: BOLLELLA, G., ET AL. The Real-Time Specification for Java. The Java Series. Addison-Wesley, 2000.
• 5: Greg Bollella , Tim Canham , Vanessa Carson , Virgil Champlin , Daniel Dvorak , Brian Giovannoni , Mark Indictor , Kenny Meyer , Alex Murray , Kirk Reinholtz, Programming with non-heap memory in the real time specification for Java, Companion of the 18th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 26-30, 2003, Anaheim, CA, USA [doi>10.1145/949344.949443]
• 6: Chandrasekhar Boyapati , Alexandru Salcianu , William Beebee, Jr. , Martin Rinard, Ownership types for safe region-based memory management in real-time Java, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 7: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 8: Angelo Corsaro , Ron K. Cytron, Efficient memory-reference checks for real-time java, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 9: Angelo Corsaro , Douglas C. Schmidt, Evaluating Real-Time Java Features and Performance for Real-Time Embedded Systems, Proceedings of the Eighth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'02), p.90, September 25-27, 2002
• 10: Morgan Deters , Ron K. Cytron, Automated discovery of scoped memory regions for real-time Java, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 11: FINK, S., DOLBY, J., AND COLBY, L. Semi-automatic J2EE transaction configuration. Tech. Rep. RC23326, IBM Thomas J. Watson Research Center, Apr. 2004.
• 12: Dan Grossman , Greg Morrisett , Trevor Jim , Michael Hicks , Yanling Wang , James Cheney, Region-based memory management in cyclone, ACM SIGPLAN Notices, v.37 n.5, May 2002
• 13: David Grove , Craig Chambers, A framework for call graph construction algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.6, p.685-746, November 2001 [doi>10.1145/506315.506316]
• 14: The Haskell 98 foreign function interface. www.cse.unsw.edu.au/-chak/haskell/ffi/.
• 15: Analyzing the Performance of Memory Management in RTSJ, Proceedings of the Fifth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, p.26, April 29-May 01, 2002
• 16: HIRZEL, M., DIWAN, A., AND HIND, M. Pointer analysis in the pressence of dynamic class loading. In 18th European Conference on Object-Oriented Programming (ECOOP) (June 2004), vol. 3086 of LNCS, pp. 96--122.
• 17: High-Res Timer Kernel Patches. i386-hrt-2.6.10.patch and hrt-common-2.6.10.patch at http://easynews.dl.sourceforge.net/-sourceforge/high-res-timers.
• 18: Sheng Liang, Java Native Interface: Programmer's Guide and Reference, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 19: Jim S. Miller , Susann Ragsdale, The Common Language Infrastructure Annotated Standard, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2003
• 20: PIZLO, F., FOX, J. M., HOLMES, D., AND VITEK, J. Real-time Java scoped memory: Design patterns and semantics. In Proceedings of the 7th IEEE International Symposium on Object-oriented Real-time distributed Computing (May 2004).
• 21: QIAN, F., AND HENDREN, L. Towards dynamic interprocedural analysis in JVMs. In 3rd Virtual Machine Research and Technology Symposium (VM) (May 2004), pp. 139--150.
• 22: Mads Tofte , Jean-Pierre Talpin, Implementation of the typed call-by-value λ-calculus using a stack of regions, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.188-201, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177855]
• 23: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984
• 24: Tian Zhao , James Noble , Jan Vitek, Scoped Types for Real-Time Java, Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS'04), p.241-251, December 05-08, 2004 [doi>10.1109/REAL.2004.51]

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.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:
allocation, real-time, scheduling