Garbage collection for safety critical Java

ABSTRACT

The Real-time Specification for Java and the upcoming, and more restricted, Safety Critical Java standard have been designed to allow programmers to avoid pauses caused by automatic memory management algorithms. Dynamic memory is user-managed using a region-based allocation scheme known as scoped memory areas. However, usage of those scoped memories is cumbersome and often leads to runtime errors. In this paper we focus on the safety critical subset of the Real-time Specification for Java and propose a real-time garbage collector that can be scheduled like a normal real-time thread with a deadline monotonic assigned priority. The restricted programming model offered by Safety Critical Java allows us to substantially simplify the collector. Our proposal has been implemented and evaluated in the context of the JOP project. JOP is a Java processor especially designed for embedded real-time systems. The architecture is optimized for worst-case execution time (WCET) instead of the usual optimization for average case execution time. Execution time of bytecodes is known cycle accurate.

REFERENCES

• 1: Chris Andreae, Yvonne Coady, Celina Gibbs, James Noble, Jan Vitek, and Tian Zhao. Scoped Types and Aspects for Real-Time Java. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP 2006), pages 124--147, Nantes, France, July 2006. Springer.
• 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: N. C. Audsley, A. Burns, M. F. Richardson, and A. J. Wellings. Hard real-time scheduling: The deadline monotonic approach. In Proceedings 8th IEEE Workshop on Real-Time Operating Systems and Software, Atalanta, 1991.
• 4: 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
• 5: 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]
• 6: Jason Baker, Antonio Cunei, Filip Pizlo, and Jan Vitek. Accurate garbage collection in uncooperative environments with lazy pointer stacks. In International Conference on Compiler Construction (CC), 2007.
• 7: Greg Bollella, James Gosling, Benjamin Brosgol, Peter Dibble, Steve Furr, and Mark Turnbull. The Real-Time Specification for Java. Java Series. Addison-Wesley, June 2000.
• 8: Alan Burns , Brian Dobbing , G. Romanski, The Ravenscar Tasking Profile for High Integrity Real-Time Programs, Proceedings of the 1998 Ada-Europe International Conference on Reliable Software Technologies, p.263-275, June 08-12, 1998
• 9: 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]
• 10: 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]
• 11: Chris Hawblitzel , Heng Huang , Lea Wittie , Juan Chen, A garbage-collecting typed assembly language, Proceedings of the 2007 ACM SIGPLAN international workshop on Types in languages design and implementation, January 16-16, 2007, Nice, Nice, France [doi>10.1145/1190315.1190323]
• 12: Roger Henriksson. Scheduling Garbage Colection in Embedded Systems. PhD thesis, Lund University, July 1998.
• 13: Java Expert Group. Java specification request JSR 302: Safety critical java technology. Available at http://jcp.org/en/jsr/detail?id=302.
• 14: 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]
• 15: Filip Pizlo, J. M. Fox, David Holmes, and Jan Vitek. Real-time java scoped memory: Design patterns and semantics. In Proceedings of the 7th IEEE International Symposium on, Object-Oriented Real-Time Distributed Computing (ISORC 2004), pages 101--110, 2004.
• 16: 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
• 17: A Profile for High-Integrity Real-Time Java Programs, Proceedings of the Fourth International Symposium on Object-Oriented Real-Time Distributed Computing, p.15, May 02-04, 2001
• 18: Sven Gestegard Robertz , Roger Henriksson, Time-triggered garbage collection: robust and adaptive real-time GC scheduling for embedded systems, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 19: RTCA/DO-178B. Software considerations in airborne systems and equipment certification. December 1992.
• 20: Martin Schoeberl. JOP: A Java Optimized Processor for Embedded Real-Time Systems. PhD thesis, Vienna University of Technology, 2005.
• 21: Martin Schoeberl, Real-Time Garbage Collection for Java, Proceedings of the Ninth IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing, p.424-432, April 24-26, 2006 [doi>10.1109/ISORC.2006.66]
• 22: Martin Schoeberl, Architecture for object-oriented programming languages, 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.1288949]
• 23: Martin Schoeberl, A Java processor architecture for embedded real-time systems, Journal of Systems Architecture: the EUROMICRO Journal, v.54 n.1-2, p.265-286, January, 2008 [doi>10.1016/j.sysarc.2007.06.001]
• 24: Martin Schoeberl , Hans Sondergaard , Bent Thomsen , Anders P. Ravn, A Profile for Safety Critical Java, Proceedings of the 10th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing, p.94-101, May 07-09, 2007 [doi>10.1109/ISORC.2007.9]
• 25: Fridtjof Siebert. Hard Realtime Garbage Collection in Modern Object Oriented Programming Languages. Number ISBN: 3-8311-3893-1. aicas Books, 2002.
• 26: 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]
• 27: Martin T. Vechev , Eran Yahav , David F. Bacon , Noam Rinetzky, CGCExplorer: a semi-automated search procedure for provably correct concurrent collectors, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 28: 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:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management

Keywords:
garbage collection, real-time system