Flexible task graphs: a unified restricted thread programming model for java

ABSTRACT

The disadvantages of unconstrained shared-memory multi-threading in Java, especially with regard to latency and determinism in realtime systems, have given rise to a variety of language extensions that place restrictions on how threads allocate, share, and communicate memory, leading to order-of-magnitude reductions in latency and jitter. However, each model makes different trade-offs with respect to expressiveness, efficiency, enforcement, and latency, and no one model is best for all applications.

In this paper we present Flexible Task Graphs (Flexotasks), a single system that allows different isolation policies and mechanisms to be combined in an orthogonal manner, subsuming four previously proposed models as well as making it possible to use new combinations best suited to the needs of particular applications. We evaluate our implementation on top of the IBM Web-Sphere Real Time Java virtual machine using both a microbenchmark and a 30 KLOC avionics collision detector. We show that Flexotasks are capable of executing periodic threads at 10 KHz with a standard deviation of 1.2μs and that it achieves significantly better performance than RTSJ's scoped memory constructs while remaining impervious to interference from global garbage collection.

REFERENCES

• 1: AICAS. The Jamaica virtual machine, www.aicas.com.
• 2: Austin Armbruster , Jason Baker , Antonio Cunei , Chapman Flack , David Holmes , Filip Pizlo , Edward Pla , Marek Prochazka , Jan Vitek, A real-time Java virtual machine with applications in avionics, ACM Transactions on Embedded Computing Systems (TECS), v.7 n.1, p.1-49, December 2007 [doi>10.1145/1324969.1324974]
• 3: Joshua Auerbach , David F. Bacon , Bob Blainey , Perry Cheng , Michael Dawson , Mike Fulton , David Grove , Darren Hart , Mark Stoodley, Design and implementation of a comprehensive real-time java virtual machine, Proceedings of the 7th ACM & IEEE international conference on Embedded software, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289927.1289967]
• 4: Joshua Auerbach, David F. Bacon, Florian Bömers, and Perry Cheng. Real-time music synthesis in Java using the Metronome garbage collector. In Proceedings of the International Computer Music Conference, Copenhagen, Denmark, August 2007.
• 5: 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
• 6: 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
• 7: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• 8: BEA. Weblogic real time. www.bea.com, 2006.
• 9: William S. Beebee , Martin C. Rinard, An Implementation of Scoped Memory for Real-Time Java, Proceedings of the First International Workshop on Embedded Software, p.289-305, October 08-10, 2001
• 10: Edward G. Benowitz and Albert F. Niessner. Experiences in adopting real-time java for flight-like software. In Proceedings of the International workshop on Java technologies for real-time and embedded systems (JTRES), pages 490--496, 2003.
• 11: Edward G. Benowitz and Albert F. Niessner. A patterns catalog for RTSJ software designs. In Workshop on Java Technologies for Real-Time and Embedded Systems (JTRES), OTM Workshops, pages 497--507, 2003.
• 12: 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]
• 13: Greg Bollella , Bertrand Delsart , Romain Guider , Christophe Lizzi , Frederic Parain, Mackinac: Making HotSpot" Real-Time, Proceedings of the Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, p.45-54, May 18-20, 2005 [doi>10.1109/ISORC.2005.31]
• 14: James Gosling , Greg Bollella, The Real-Time Specification for Java, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 15: 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
• 16: Mike Fulton , Mark Stoodley, Compilation Techniques for Real-Time Java Programs, Proceedings of the International Symposium on Code Generation and Optimization, p.221-231, March 11-14, 2007 [doi>10.1109/CGO.2007.5]
• 17: Sven Gestegård Robertz , Roger Henriksson , Klas Nilsson , Anders Blomdell , Ivan Tarasov, Using real-time Java for industrial robot control, Proceedings of the 5th international workshop on Java technologies for real-time and embedded systems, September 26-28, 2007, Vienna, Austria [doi>10.1145/1288940.1288955]
• 18: Roger Henriksson. Scheduling Garbage Collection in Embedded Systems. PhD thesis, Lund University, July 1998.
• 19: IBM. DDG1000 Next Generation Navy Destroyers, www.ibm.com/press/us/en/pressrelease/21033.wss, 2007.
• 20: IBM Corporation. IBM Expedited Real Time Task Graphs. www.alphaworks.ibm.com/tech/xrtgs, 2007.
• 21: Nicolas Juillerat, Stefan Müller Arisona, and Simon Schubiger-Banz. Real-time, low latency audio processing in Java. In Proceedings of the International Computer Music Conference, Copenhagen, Denmark, August 2007.
• 22: E.A. Lee. Overview of the Ptolemy project. Technical Report UCB/ERL M03/25, EECS Department, University of California, Berkeley, 2003.
• 23: Ingo Molnar and Thomas Gleixner. The RT-PREEMPT patch set for Linux.
• 24: Albert F. Niessner and Edward G. Benowitz. Rtsj memory areas and their affects on the performance of a flight-like attitude control system. In Proceedings of the International workshop on Java technologies for real-time and embedded systems (JTRES), pages 508--519, 2003.
• 25: Krzysztof Palacz and Jan Vitek. Java subtype tests in real-time. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP), pages 378--404, Darmstadt, Germany, July 2003.
• 26: Filip Pizlo, Jason Fox, David Holmes, and Jan Vitek. Real-time Java scoped memory: design patterns and semantics. In Proceedings of the IEEE International Symposium on Object-oriented Real-Time Distributed Computing (ISORC), Vienna, Austria, May 2004.
• 27: Filip Pizlo , Jan Vitek, An Emprical Evaluation of Memory Management Alternatives for Real-Time Java, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.35-46, December 05-08, 2006 [doi>10.1109/RTSS.2006.9]
• 28: Purdue University. The Ovm virtual machine, www.ovmj.org.
• 29: Fridtjof Siebert. The impact of realtime garbage collection on realtime Java programming. In Seventh IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC'04), pages 33--40, 2004.
• 30: Simulink. www.mathworks.com/products/simulink. 2007.
• 31: Daniel Spoonhower , Joshua Auerbach , David F. Bacon , Perry Cheng , David Grove, Eventrons: a safe programming construct for high-frequency hard real-time applications, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 32: Jesper H. Spring , Jean Privat , Rachid Guerraoui , Jan Vitek, Streamflex: high-throughput stream programming in java, Proceedings of the 22nd annual ACM SIGPLAN conference on Object oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 33: Jesper Honig Spring , Filip Pizlo , Rachid Guerraoui , Jan Vitek, Reflexes: abstractions for highly responsive systems, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA [doi>10.1145/1254810.1254837]
• 34: William Thies , Michal Karczmarek , Saman P. Amarasinghe, StreamIt: A Language for Streaming Applications, Proceedings of the 11th International Conference on Compiler Construction, p.179-196, April 08-12, 2002
• 35: Tian Zhao , James Noble , Jan Vitek, Scoped Types for Real-Time Java, Proceedings of the 25th IEEE International Real-Time Systems Symposium, p.241-251, December 05-08, 2004 [doi>10.1109/REAL.2004.51]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Interpreters

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Classes and objects
      D.3.4 Processors
          Subjects: Run-time environments
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

Keywords:
java virtual machine, memory management, ownership types, real-time systems