Exact roots for a real-time garbage collector

ABSTRACT

Garbage collection is traditionally not used in real-time systems due to the unpredictable temporal behavior of current implementations of a garbage collector. However, without garbage collection the programming model is very different from standard Java. It is the opinion of the authors that garbage collection algorithms can be adapted to meet even the requirements for hard real-time systems.One important property of a real-time garbage collector is to identify only the real roots on the root scan. Misinterpreting primitive values as false root pointers can result in an unpredictable worst case memory consumption. In this paper we propose a method to add information on the stack layout to the runtime data structure in order to find the roots exactly. Furthermore, interpreting this information during the collection process is implemented to be worst-case execution time analyzable.

References

1. O. Agesen, D. Detlefs, and J. E. Moss. Garbage collection and local variable type-precision and liveness in java virtual machines. In PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, pages 269--279, New York, NY, USA, 1998. ACM Press.
2. Altera. Cyclone FPGA Family Data Sheet, ver. 1.2, April 2003.
3. C. Artho and A. Biere. Subroutine inlining and bytecode abstraction to simplify static and dynamic analysis. Electronic Notes in Theoretical Computer Science, 141(1):109--128, December 2005.
4. H. G. Baker. List processing in real time on a serial computer. Commun. ACM, 21(4):280--294, 1978.
5. H. G. Baker. The treadmill: real-time garbage collection without motion sickness. SIGPLAN Not., 27(3):66--70, 1992.
6. G. Bollella, J. Gosling, B. Brosgol, P. Dibble, S. Furr, and M. Turnbull. The Real-Time Specification for Java. Java Series. Addison-Wesley, June 2000.
7. C. J. Cheney. A nonrecursive list compacting algorithm. Commun. ACM, 13(11):677--678, 1970.
8. J. Cohen and A. Nicolau. Comparison of compacting algorithms for garbage collection. ACM Trans. Program. Lang. Syst., 5(4):532--553, 1983.
9. M. Dahm. Byte code engineering with the BCEL API. Technical report, Freie Universitat Berlin, April 2001.
10. E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: an exercise in cooperation. Commun. ACM, 21(11):966--975, 1978.
11. A. Diwan, E. Moss, and R. Hudson. Compiler support for garbage collection in a statically typed language. In Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, volume 27, pages 273--282, San Francisco, CA, June 1992.
12. J. Gosling, B. Joy, and G. Steele. The Java Language Specification. The Java Series. Addison-Wesley, 1997.
13. F. Gruian and Z. Salcic. Designing a concurrent hardware garbage collector for small embedded systems. In Proceedings of Advances in Computer Systems Architecture: 10th Asia-Pacific Conference, ACSAC 2005, pages 281--294. Springer-Verlag GmbH, October 2005.
14. T. Higuera, V. Issarny, M. Banatre, G. Cabillic, J.-P. Lesot, and F. Parain. Memory management for real-time Java: an efficient solution using hardware support. Real-Time Systems Journal, 2002.
15. A. Ive. Towards an embedded real-time java virtual machine. Licentiate thesis, Lund Institute of Technology, 2003.
16. R. E. Jones and R. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, Chichester, July 1996. With a chapter on Distributed Garbage Collection by R. Lins.
17. N. K., C. L., and R. M. Requirements for real-time extensions for the Java platform. Available at http://www.nist.gov/rt-java/, September 1999.
18. T. Lindholm and F. Yellin. The Java Virtual Machine Specification. Addison-Wesley, Reading, MA, USA, second edition, 1999.
19. J. L. McCarthy. Recursive functions of symbolic expressions and their computation by machine, part i. Communications of the ACM, 3(4):184--195, 1960.
20. A. F. Niessner and E. G. Benowitz. RTSJ memory areas and their affects on the performance of a flight-like attitude control system. In Workshop on Java Technologies for Real-Time and Embedded Systems (JTRES), LNCS, 2003.
21. K. D. Nilsen, S. Mitra, and S. J. Lee. Method for efficient soft real-time execution of portable byte code computer programs. United States Patent 6081665, 2000.
22. A. Nilsson. Compiling java for real-time systems. Licentiate thesis, Dept. of Computer Science, Lund University, May 2004.
23. A. Nilsson and S. G. Robertz. On real-time performance of ahead-of-time compiled java. In ISORC, pages 372--381, 2005.
24. J. M. O'Connor and M. Tremblay. picoJava-I: The Java virtual machine in hardware. IEEE Micro, 17(2):45--53, 1997.
25. M. Pfeffer, T. Ungerer, S. Fuhrmann, J. Kreuzinger, and U. Brinkschulte. Real-time garbage collection for a multithreaded java microcontroller. Real-Time Systems, 26(1):89--106, 2004.
26. F. Pizlo, J. M. Fox, D. Holmes, and J. Vitek. Real-time java scoped memory: Design patterns and semantics. In ISORC, pages 101--110, 2004.
27. P. Puschner and A. Burns. A review of worst-case execution-time analysis. Journal of Real-Time Systems, 18(2/3):115--128, May 2000.
28. S. G. Robertz and R. Henriksson. Time-triggered garbage collection: robust and adaptive real-time GC scheduling for embedded systems. In LCTES '03: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, pages 93--102, New York, NY, USA, 2003. ACM Press.
29. W. J. Schmidt and K. D. Nilsen. Performance of a hardware-assisted real-time garbage collector. In ASPLOS-VI: Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, pages 76--85, New York, NY, USA, 1994. ACM Press.
30. M. Schoeberl. Design and implementation of an efficient stack machine. In Proceedings of the 12th IEEE Reconfigurable Architecture Workshop (RAW2005), Denver, Colorado, USA, April 2005. IEEE.
31. M. Schoeberl. JOP: A Java Optimized Processor for Embedded Real-Time Systems. PhD thesis, Vienna University of Technology, 2005.
32. M. Schoeberl. Real-time garbage collection for Java. In Proceedings of the 9th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC 2006), pages 424--432, Gyeongju, Korea, April 2006.
33. M. Schoeberl and R. Pedersen. Submitted to jtres 2006: Wcet analysis for a java processor. 2006.
34. F. Siebert. Real-time garbage collection in multi-threaded systems on a single processor. In 20th IEEE Real-Time Systems Symposium (RTSS'99), Phoenix, Arizona, 1999.
35. G. L. Steele. Multiprocessing compactifying garbage collection. Commun. ACM, 18(9):495--508, 1975.
36. P. R. Wilson. Uniprocessor garbage collection techniques. Technical report, University of Texas, Jan. 1994. Expanded version of the IWMM92 paper.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

  • Real-time systems

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Garbage collection