Low-latency time-portable real-time programming with Exotasks

ABSTRACT

Exotasks are a novel Java programming construct that achieve three important goals. They achieve low latency while allowing the fullest use of Java language features, compared to previous attempts to restrict the Java language for use in the submillisecond domain. They support pluggable schedulers, allowing easy implementation of new scheduling paradigms in a real-time Java system. They can achieve deterministic timing, even in the presence of other Java threads, and across changes of hardware and software platform. To achieve these goals, the program is divided into tasks with private heaps. Tasks may be strongly isolated, communicating only with each other and guaranteeing determinism, or weakly isolated, allowing some communication with the rest of the Java application. Scheduling of the tasks' execution, garbage collection, and value passing is accomplished by the pluggable scheduler. Schedulers that we have written employ logical execution time (LET) in association with strong isolation to achieve time portability. We have also built a quad-rotor model helicopter, the JAviator, which we use to evaluate our implementation of Exotasks in an experimental embedded version of IBM's J9 real-time virtual machine. Our experiments show that we are able to maintain very low scheduling jitter and deterministic behavior in the face of variations in both software load and hardware platform. We also show that Exotasks perform nearly as well as Eventrons on a benchmark audio application.

REFERENCES

• 1: AICAS. The Jamaica virtual machine. http://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: Joe Armstrong , Robert Virding , Claes Wikström , Mike Williams, Concurrent programming in ERLANG (2nd ed.), Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1996
• 4: 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]
• 5: Auerbach, J., Bacon, D. F., BO Mers, F., and Cheng, P. 2007. Real-time music synthesis in Java using the Metronome garbage collector. In Proceedings of the International Computer Music Conference.
• 6: 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
• 7: David F. Bacon , Perry Cheng , David Grove, Garbage collection for embedded systems, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy [doi>10.1145/1017753.1017776]
• 8: 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
• 9: 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
• 10: 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]
• 11: James Gosling , Greg Bollella, The Real-Time Specification for Java, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 12: Alan Burns , Andy Wellings, Concurrency in Ada (2nd ed.), Cambridge University Press, New York, NY, 1998
• 13: Eclipse Foundation. 2007. The Eclipse open development platform. http://www.eclipse.org.
• 14: 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]
• 15: 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]
• 16: Arkadeb Ghosal , Alberto Sangiovanni-Vincentelli , Christoph M. Kirsch , Thomas A. Henzinger , Daniel Iercan, A hierarchical coordination language for interacting real-time tasks, Proceedings of the 6th ACM & IEEE International conference on Embedded software, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176887.1176907]
• 17: Ghosal, A., Iercan, D., Kirsch, C., Henzinger, T., and Sangiovanni-Vincentelli, A. 2007. Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code. In Proceedings of the APGES Workshop.
• 18: Nicolas Halbwachs, Synchronous Programming of Reactive Systems, Kluwer Academic Publishers, Norwell, MA, 1992
• 19: Fergus Henderson, Accurate garbage collection in an uncooperative environment, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
• 20: Thomas A. Henzinger , Christoph M. Kirsch, The embedded machine: Predictable, portable real-time code, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.6, p.33-es, October 2007 [doi>10.1145/1286821.1286824]
• 21: Henzinger, T., Kirsch, C., And Horowitz, B. 2003. Giotto: A time-triggered language for embedded programming. Proc. IEEE 91, 1, 84--99.
• 22: IBM. 2007. DDG1000 next generation Navy destroyers. http://www.ibm.com/press/us/en/pressrelease/21033.wss.
• 23: IBM Corp. 2006. WebSphere Real-Time User's Guide, 1st Ed.
• 24: IBM Corporation. 2007. IBM expedited real time task graphs. www.alphaworks.ibm.com/tech/xrtgs.
• 25: Java Community Process. JSR-121 application isolation API. http://www.jcp.org/aboutJava/communityprocess/final/jsr121.
• 26: Juillerat, N., Müller Arisona, S., And Schubiger-Banz, S. 2007. Real-time, low latency audio processing in java. In Proceedings of the International Computer Music Conference.
• 27: Lee, E. 2003. Overview of the Ptolemy project. Tech. rep. UCB/ERL M03/25, EECS Department, University of California, Berkeley.
• 28: Katsuhiko Ogata, Modern control engineering (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 29: Padmanabhan Pillai , Kang G. Shin, Real-time dynamic voltage scaling for low-power embedded operating systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 30: Filip Pizlo , Antony L. Hosking , Jan Vitek, Hierarchical real-time garbage collection, Proceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 13-15, 2007, San Diego, California, USA
• 31: Purdue. The OVM virtual machine. http://www.ovmj.org.
• 32: Real-Time-Workshop. 2007. http://www.mathworks.com/products/rtw.
• 33: Siebert, F. 2004. The impact of realtime garbage collection on realtime Java programming. In Proceedings of the 7th Annual IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC'04). IEEE, Los Alamitos, CA, 33--40.
• 34: Simulink. 2007. http://www.mathworks.com/products/simulink.
• 35: 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
• 36: 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]
• 37: 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
• 38: David B. Stewart , Richard A. Volpe , Pradeep K. Khosla, Design of Dynamically Reconfigurable Real-Time Software Using Port-Based Objects, IEEE Transactions on Software Engineering, v.23 n.12, p.759-776, December 1997 [doi>10.1109/32.637390]
• 39: University of Salzburg. 2007. Exotask htl scheduler. htl.cs.uni-salzburg.at/exotask-htl.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

General Terms:
Algorithms, Languages, Measurement, Performance

Keywords:
Real-time scheduling, UAVs, time portability, virtual machine