Non-blocking object copy for real-time garbage collection

ABSTRACT

A real-time garbage collector has to fulfill two conflicting properties: avoid heap fragmentation and provide short blocking time. The heap needs to be compacted to avoid probably unbounded fragmentation. During compaction all objects are copied; copying is usually performed atomically to avoid interference with mutator threads. Copying of large objects and especially large arrays introduces long blocking times that are unacceptable for real-time systems.

In this paper an interruptible copy unit is presented that implements non-blocking object copy. The unit intercepts object and array field access and redirects the access either to the source or destination part of the moving object. The unit can be interrupted after a single word move. The resulting maximum blocking time is the time for a memory word read and write. We have implemented the proposed non-blocking copy unit in the Java processor JOP and are able to run high priority real-time tasks at 10 kHz parallel to the garbage collection task on a 100 MHz system.

REFERENCES

• 1: 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
• 2: 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]
• 3: James Gosling , Greg Bollella, The Real-Time Specification for Java, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 4: Rodney A. Brooks, Trading data space for reduced time and code space in real-time garbage collection on stock hardware, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.256-262, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802042]
• 5: 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]
• 6: Lorenz Huelsbergen , James R. Larus, A concurrent copying garbage collector for languages that distinguish (im)mutable data, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.73-82, May 19-22, 1993, San Diego, California, United States
• 7: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 8: Matthias Meyer, A true hardware read barrier, Proceedings of the 5th international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada [doi>10.1145/1133956.1133959]
• 9: Scott Nettles , James O'Toole, Real-time replication garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.217-226, June 21-25, 1993, Albuquerque, New Mexico, United States
• 10: Kelvin D. Nilsen , William J. Schmidt, Cost-effective object space management for hardware-assisted real-time garbage collection, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.338-354, Dec. 1992 [doi>10.1145/161494.161508]
• 11: S. C. North , J. H. Reppy, Concurrent garbage collection on stock hardware, Proc. of a conference on Functional programming languages and computer architecture, p.113-133, October 1987, Portland, Oregon, United States
• 12: C. Pitter and M. Schoeberl. Performance evaluation of a Java chip-multiprocessor. In Proceedings of the 3rd IEEE Symposium on Industrial Embedded Systems (SIES 2008), Jun. 2008.
• 13: Filip Pizlo , Daniel Frampton , Erez Petrank , Bjarne Steensgaard, Stopless: a real-time garbage collector for multiprocessors, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296927]
• 14: Wolfgang Puffitsch , Martin Schoeberl, Non-blocking root scanning for real-time garbage collection, Proceedings of the 6th international workshop on Java technologies for real-time and embedded systems, September 24-26, 2008, Santa Clara, California [doi>10.1145/1434790.1434801]
• 15: 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]
• 16: Martin Schoeberl, A time predictable Java processor, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 17: 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]
• 18: 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]
• 19: Martin Schoeberl , Rasmus Pedersen, WCET analysis for a Java processor, Proceedings of the 4th international workshop on Java technologies for real-time and embedded systems, October 11-13, 2006, Paris, France [doi>10.1145/1167999.1168033]
• 20: Martin Schoeberl , Jan Vitek, Garbage collection for safety critical Java, 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.1288953]
• 21: Fridtjof Siebert, Eliminating external fragmentation in a non-moving garbage collector for Java, Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systems, p.9-17, November 17-19, 2000, San Jose, California, United States [doi>10.1145/354880.354883]
• 22: F. Siebert. Hard Real-time Garbage Collection in Modern Object Oriented Programming Languages. Number ISBN: 3-8311-3893-1. aicas Books, 2002.
• 23: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
• 24: P. R. Wilson. Uniprocessor garbage collection techniques. Technical report, University of Texas, Jan. 1994. Expanded version of the IWMM92 paper.
• 25: 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]
• 26: Martin Zabel , Thomas B. Preuber , Peter Reichel , Rainer G. Spallek, Secure, Real-Time and Multi-Threaded General-Purpose Embedded Java Microarchitecture, Proceedings of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools, p.59-62, August 29-31, 2007 [doi>10.1109/DSD.2007.97]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Java
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Design, Experimentation, Languages, Measurement, Performance