A real-time garbage collector with low overhead and consistent utilization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A real-time garbage collector with low overhead and consistent utilization

Full text

Pdf (517 KB)

Source

ACM SIGPLAN Notices archive
Volume 38 , Issue 1 (January 2003) table of contents

Pages: 285 - 298

Year of Publication: 2003

ISSN:0362-1340

Also published in ...

Authors

David F. Bacon	IBM T.J. Watson Research Center, Yorktown Heights, NY
Perry Cheng	IBM T.J. Watson Research Center, Yorktown Heights, NY
V. T. Rajan	IBM T.J. Watson Research Center, Yorktown Heights, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 20, Downloads (12 Months): 220, Citation Count: 71

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/640128.604155 What is a DOI?

ABSTRACT

Now that the use of garbage collection in languages like Java is becoming widely accepted due to the safety and software engineering benefits it provides, there is significant interest in applying garbage collection to hard real-time systems. Past approaches have generally suffered from one of two major flaws: either they were not provably real-time, or they imposed large space overheads to meet the real-time bounds. We present a mostly non-moving, dynamically defragmenting collector that overcomes both of these limitations: by avoiding copying in most cases, space requirements are kept low; and by fully incrementalizing the collector we are able to meet real-time bounds. We implemented our algorithm in the Jikes RVM and show that at real-time resolution we are able to obtain mutator utilization rates of 45% with only 1.6--2.5 times the actual space required by the application, a factor of 4 improvement in utilization over the best previously published results. Defragmentation causes no more than 4% of the traced data to be copied.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
	2	A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.11-20, June 20-24, 1988, Atlanta, Georgia, United States
	3	Matthew Arnold , Barbara G. Ryder, Thin Guards: A Simple and Effective Technique for Reducing the Penalty of Dynamic Class Loading, Proceedings of the 16th European Conference on Object-Oriented Programming, p.498-524, June 10-14, 2002
	4	David F. Bacon , Stephen J. Fink , David Grove, Space- and Time-Efficient Implementation of the Java Object Model, Proceedings of the 16th European Conference on Object-Oriented Programming, p.111-132, June 10-14, 2002
	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	Henry G. Baker, The treadmill: real-time garbage collection without motion sickness, ACM SIGPLAN Notices, v.27 n.3, p.66-70, March 1992 [doi>10.1145/130854.130862]
	7	Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Kean Kuiper , Victor Leikehman, An algorithm for parallel incremental compaction, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
	8	Stephen M Blackburn , Richard Jones , Kathryn S. McKinley , J Eliot B Moss, Beltway: getting around garbage collection gridlock, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
	9	James Gosling , Greg Bollella, The Real-Time Specification for Java, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
	10	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]
	11	A. M. Cheadle , A. J. Field , S. Marlow , S. L. Peyton Jones , R. L. While, Non-stop Haskell, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.257-267, September 2000
	12	Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.125-136, June 2001, Snowbird, Utah, United States
	13	Perry Cheng , Robert Harper , Peter Lee, Generational stack collection and profile-driven pretenuring, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.162-173, June 17-19, 1998, Montreal, Quebec, Canada
	14	R. Dimpsey , R. Arora , K. Kuiper, Java server performance: a case study of building efficient, scalable Jvms, IBM Systems Journal, v.39 n.1, p.151-174, January 2000
	15	Henriksson, R. Scheduling Garbage Collection in Embedded Systems. PhD thesis, Lund Institute of Technology, July 1998.
	16	Richard L. Hudson , J. Eliot B. Moss, Incremental Collection of Mature Objects, Proceedings of the International Workshop on Memory Management, p.388-403, September 17-19, 1992
	17	Mark Stuart Johnstone , Paul R. Wilson, Non-compacting memory allocation and real-time garbage collection, 1997
	18	Joseph, M., and Pandya, P. K. Finding response times in a real-time system. Computer Journal 29, 5 (1986), 390--395.
	19	Martin Larose , Marc Feeley, A compacting incremental collector and its performance in a production quality compiler, ACM SIGPLAN Notices, v.34 n.3, p.1-9, March 1999
	20	David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
	21	Scott Nettles , James O'Toole, Real-time replication garbage collection, ACM SIGPLAN Notices, v.28 n.6, p.217-226, June 1993
	22	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
	23	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]
	24	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]
	25	Zorn, B. Barrier methods for garbage collection. Tech. Rep. CU-CS-494-90, University of Colorado at Boulder, 1990.

CITED BY 71

	Angelo Corsaro , Ron K. Cytron, Efficient memory-reference checks for real-time java, ACM SIGPLAN Notices, v.38 n.7, July 2003
	Tobias Mann , Morgan Deters , Rob LeGrand , Ron K. Cytron, Static determination of allocation rates to support real-time garbage collection, ACM SIGPLAN Notices, v.40 n.7, July 2005
	Matthias Meyer, A true hardware read barrier, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Dinakar Dhurjati , Sumant Kowshik , Vikram Adve , Chris Lattner, Memory safety without runtime checks or garbage collection, ACM SIGPLAN Notices, v.38 n.7, July 2003
	Sven Gestegard Robertz , Roger Henriksson, Time-triggered garbage collection: robust and adaptive real-time GC scheduling for embedded systems, ACM SIGPLAN Notices, v.38 n.7, July 2003
	David F. Bacon , Perry Cheng , V. T. Rajan, Controlling fragmentation and space consumption in the metronome, a real-time garbage collector for Java, ACM SIGPLAN Notices, v.38 n.7, July 2003
	Chandrasekhar Boyapati , Alexandru Salcianu , William Beebee, Jr. , Martin Rinard, Ownership types for safe region-based memory management in real-time Java, ACM SIGPLAN Notices, v.38 n.5, May 2003
	Stephen M. Blackburn , Kathryn S. McKinley, Ulterior reference counting: fast garbage collection without a long wait, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Diab Abuaiadh , Yoav Ossia , Erez Petrank , Uri Silbershtein, An efficient parallel heap compaction algorithm, ACM SIGPLAN Notices, v.39 n.10, October 2004
	Hans-J. Boehm, The space cost of lazy reference counting, ACM SIGPLAN Notices, v.39 n.1, p.210-219, January 2004
	Narendran Sachindran , J. Eliot B. Moss , Emery D. Berger, MC²: high-performance garbage collection for memory-constrained environments, ACM SIGPLAN Notices, v.39 n.10, October 2004
	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
	Stephen M. Blackburn , Antony L. Hosking, Barriers: friend or foe?, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	A. M. Cheadle , A. J. Field , S. Marlow , S. L. Peyton Jones , R. L. While, Exploring the barrier to entry: incremental generational garbage collection for Haskell, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	David Detlefs , Christine Flood , Steve Heller , Tony Printezis, Garbage-first garbage collection, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	David F. Bacon , Perry Cheng , V. T. Rajan, A unified theory of garbage collection, ACM SIGPLAN Notices, v.39 n.10, October 2004
	Konstantinos Sagonas , Jesper Wilhelmsson, Message analysis-guided allocation and low-pause incremental garbage collection in a concurrent language, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	Yoav Ossia , Ori Ben-Yitzhak , Marc Segal, Mostly concurrent compaction for mark-sweep GC, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	David F. Bacon , Perry Cheng , David Grove , Michael Hind , V. T. Rajan , Eran Yahav , Matthias Hauswirth , Christoph M. Kirsch , Daniel Spoonhower , Martin T. Vechev, High-level real-time programming in Java, Proceedings of the 5th ACM international conference on Embedded software, September 18-22, 2005, Jersey City, NJ, USA
	Martin T. Vechev , David F. Bacon, Write barrier elision for concurrent garbage collectors, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	Dinakar Dhurjati , Sumant Kowshik , Vikram Adve , Chris Lattner, Memory safety without garbage collection for embedded applications, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.1, p.73-111, February 2005
	Lothar Thiele , Reinhard Wilhelm, Design for Timing Predictability, Real-Time Systems, v.28 n.2-3, p.157-177, November-December 2004
	Yuqiang Xian , Guangze Xiong, Minimizing memory requirement of real-time systems with concurrent garbage collector, ACM SIGPLAN Notices, v.40 n.3, p.40-48, March 2005
	Matthew Hertz , Yi Feng , Emery D. Berger, Garbage collection without paging, ACM SIGPLAN Notices, v.40 n.6, June 2005
	David F. Bacon , Perry Cheng , David Grove , Martin T. Vechev, Syncopation: generational real-time garbage collection in the metronome, ACM SIGPLAN Notices, v.40 n.7, July 2005
	G. Chen , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , B. Mathiske , M. Wolczko, Heap compression for memory-constrained Java environments, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Daniel Spoonhower , Guy Blelloch , Robert Harper, Using page residency to balance tradeoffs in tracing garbage collection, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA
	Danny Dubé , Marc Feeley, BIT: A Very Compact Scheme System for Microcontrollers, Higher-Order and Symbolic Computation, v.18 n.3-4, p.271-298, December 2005
	Daniel Spoonhower , Joshua Auerbach , David F. Bacon , Perry Cheng , David Grove, Eventrons: a safe programming construct for high-frequency hard real-time applications, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Zhang Ning , Guangze Xiong, Minimizing GC work by analysis of live objects, ACM SIGPLAN Notices, v.41 n.3, March 2006
	David Atienza , Jose M. Mendias , Stylianos Mamagkakis , Dimitrios Soudris , Francky Catthoor, Systematic dynamic memory management design methodology for reduced memory footprint, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.2, p.465-489, April 2006
	Antony L. Hosking, Portable, mostly-concurrent, mostly-copying garbage collection for multi-processors, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Stylianos Mamagkakis , David Atienza , Christophe Poucet , Francky Catthoor , Dimitrios Soudris, Energy-efficient dynamic memory allocators at the middleware level of embedded systems, Proceedings of the 6th ACM & IEEE International conference on Embedded software, October 22-25, 2006, Seoul, Korea
	Michael D. Bond , Kathryn S. McKinley, Bell: bit-encoding online memory leak detection, ACM SIGPLAN Notices, v.41 n.11, November 2006
	Tony Printezis, On measuring garbage collection responsiveness, Science of Computer Programming, v.62 n.2, p.164-183, 1 October 2006
	Yang Chang , Andy Wellings, Low memory overhead real-time garbage collection for Java, Proceedings of the 4th international workshop on Java technologies for real-time and embedded systems, October 11-13, 2006, Paris, France
	Konstantinos Sagonas , Jesper Wilhelmsson, Efficient memory management for concurrent programs that use message passing, Science of Computer Programming, v.62 n.2, p.98-121, 1 October 2006
	Wen-ke Chen , Sanjay Bhansali , Trishul Chilimbi , Xiaofeng Gao , Weihaw Chuang, Profile-guided proactive garbage collection for locality optimization, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Wei Fu , Carl Hauser, A real-time garbage collection framework for embedded systems, Proceedings of the 2005 workshop on Software and compilers for embedded systems, p.20-26, September 29-October 01, 2005, Dallas, Texas
	Chengliang Zhang , Kirk Kelsey , Xipeng Shen , Chen Ding , Matthew Hertz , Mitsunori Ogihara, Program-level adaptive memory management, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Martin T. Vechev , Eran Yahav , David F. Bacon, Correctness-preserving derivation of concurrent garbage collection algorithms, ACM SIGPLAN Notices, v.41 n.6, June 2006
	A. M. Cheadle , A. J. Field , J. W. Ayres , N. Dunn , R. A. Hayden , J. Nystrom-Persson, Visualising dynamic memory allocators, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	David F. Bacon, Realtime garbage collection, Queue, v.5 n.1, February 2007
	Shahrooz Feizabadi , Godmar Back, Garbage collection-aware utility accrual scheduling, Real-Time Systems, v.36 n.1-2, p.3-22, July 2007
	Hyeonjoong Cho , Chewoo Na , Binoy Ravindran , E. Douglas Jensen, On scheduling garbage collector in dynamic real-time systems with statistical timing assurances, Real-Time Systems, v.36 n.1-2, p.23-46, July 2007
	Okehee Goh , Yann-Hang Lee , Ziad Kaakani , Elliott Rachlin, Schedulable garbage collection in CLI virtual execution system, Real-Time Systems, v.36 n.1-2, p.47-74, July 2007
	Jesper H. Spring , Jean Privat , Rachid Guerraoui , Jan Vitek, Streamflex: high-throughput stream programming in java, ACM SIGPLAN Notices, v.42 n.10, October 2007
	Sylvain Stanchina , Matthias Meyer, Mark-sweep or copying?: a "best of both worlds" algorithm and a hardware-supported real-time implementation, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada
	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
	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
	Glenn Ammons , Jonathan Appavoo , Maria Butrico , Dilma Da Silva , David Grove , Kiyokuni Kawachiya , Orran Krieger , Bryan Rosenburg , Eric Van Hensbergen , Robert W. Wisniewski, Libra: a library operating system for a jvm in a virtualized execution environment, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA
	Stephen M. Blackburn , Kathryn S. McKinley, Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance, ACM SIGPLAN Notices, v.43 n.6, June 2008
	Filip Pizlo , Erez Petrank , Bjarne Steensgaard, A study of concurrent real-time garbage collectors, ACM SIGPLAN Notices, v.43 n.6, June 2008
	Filip Pizlo , Erez Petrank , Bjarne Steensgaard, Path specialization: reducing phased execution overheads, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA
	Filip Pizlo , Antony L. Hosking , Jan Vitek, Hierarchical real-time garbage collection, ACM SIGPLAN Notices, v.42 n.7, July 2007
	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, ACM SIGPLAN Notices, v.42 n.7, July 2007
	Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Oil and Water? High Performance Garbage Collection in Java with MMTk, Proceedings of the 26th International Conference on Software Engineering, p.137-146, May 23-28, 2004
	V. Krishna Nandivada , David Detlefs, Compile-Time Concurrent Marking Write Barrier Removal, Proceedings of the international symposium on Code generation and optimization, p.37-48, March 20-23, 2005
	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
	Chris Andreae , Yvonne Coady , Celina Gibbs , James Noble , Jan Vitek , Tian Zhao, Scoped types and aspects for real-time Java memory management, Real-Time Systems, v.37 n.1, p.1-44, October 2007
	Joshua Auerbach , David F. Bacon , Rachid Guerraoui , Jesper Honig Spring , Jan Vitek, Flexible task graphs: a unified restricted thread programming model for java, ACM SIGPLAN Notices, v.43 n.7, July 2008
	Luc Bläser, A high-performance operating system for structured concurrent programs, Proceedings of the 4th workshop on Programming languages and operating systems, October 18-18, 2007, Stevenson, Washington
	A. M. Cheadle , A. J. Field , J. Nystrom-Persson, A method specialisation and virtualised execution environment for Java, Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, March 05-07, 2008, Seattle, WA, USA
	Jie Hu , Shruti Gorappa , Juan A. Colmenares , Raymond Klefstad, Compadres: a lightweight component middleware framework for composing distributed real-time embedded systems with real-time Java, Proceedings of the ACM/IFIP/USENIX 2007 International Conference on Middleware, November 26-30, 2007, Newport Beach, California
	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
	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
	Wolfgang Puffitsch, Decoupled root scanning in multi-processor systems, Proceedings of the 2008 international conference on Compilers, architectures and synthesis for embedded systems, October 19-24, 2008, Atlanta, GA, USA
	Martin Schoeberl , Wolfgang Puffitsch, Non-blocking object copy 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
	Michael D. Bond , Kathryn S. McKinley, Tolerating memory leaks, ACM SIGPLAN Notices, v.43 n.10, September 2008
	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
	Joshua Auerbach , David F. Bacon , Perry Cheng , David Grove , Ben Biron , Charlie Gracie , Bill McCloskey , Aleksandar Micic , Ryan Sciampacone, Tax-and-spend: democratic scheduling for real-time garbage collection, Proceedings of the 7th ACM international conference on Embedded software, October 19-24, 2008, Atlanta, GA, USA