The treadmill

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The treadmill: real-time garbage collection without motion sickness

Full text

Pdf (464 KB)

Source

ACM SIGPLAN Notices archive
Volume 27 , Issue 3 (March 1992) table of contents

Pages: 66 - 70

Year of Publication: 1992

ISSN:0362-1340

Author

Henry G. Baker

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 41, Citation Count: 32

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/130854.130862 What is a DOI?

ABSTRACT

A simple real-time garbage collection algorithm is presented which does not copy, thereby avoiding some of the problems caused by the asynchronous motion of objects. This in-place "treadmill" garbage collection scheme has approximately the same complexity as other non-moving garbage collectors, thus making it usable in a high-level language implementation where some pointers cannot be traced. The treadmill is currently being used in a Lisp system built in Ada.

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	Andre, David L. Paging in Lisp Programs. M.S. Thesis, U. of Maryland, 1986.
	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	Brenda S. Baker , Dan E. Willard, Algorithms for resolving conflicts in dynamic storage allocation, Journal of the ACM (JACM), v.32 n.2, p.327-343, April 1985 [doi>10.1145/3149.335126]
	4	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]
	5	Baker, Henry. "Garbage Collection in Ada". Ada-9X Revision Request#643, Ada Joint Program Office, Oct., 1989.
	6	Henry G. Baker, Unify and conquer, Proceedings of the 1990 ACM conference on LISP and functional programming, p.218-226, June 27-29, 1990, Nice, France [doi>10.1145/91556.91652]
	7	Henry G. Baker, Structured programming with limited private types in Ada: nesting if for the soaring eagles, ACM SIGAda Ada Letters, v.XI n.5, p.79-90, July/August 1991 [doi>10.1145/122215.122219]
	8	Baker Henry. "CONS Should not CONS its Arguments, or, A Lazy Alloc is a Smart Alloc". Submitted to Comm. of the ACM, 1991.
	9	Baker, Henry. "Equal Rights for Functional Objects, or, The More Things Change, The More They Are the Same". Submitted to ACM TOPLAS, 1991.
	10	Beaudoing, B., and Queinnec, C. "Mark-DURING-Sweep: A Real-Time Garbage Collector". Submitted to PARLE '91.
	11	Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
	12	R. P. Brent, Efficient implementation of the first-fit strategy for dynamic storage allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.388-403, July 1989 [doi>10.1145/65979.65981]
	13	David Read Chase , Kenneth W. Kennedy, Garbage collection and other optimizations, Rice University, Houston, TX, 1988
	14	D. R. Chase, Safety consideration for storage allocation optimizations, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.1-10, June 20-24, 1988, Atlanta, Georgia, United States
	15	Hederman, Lucy. Compile Time Garbage Collection. MS Thesis, Rice U. Comp. Sci. Dept., Sept. 1988.
	16	Tim Hickey , Jacques Cohen, Performance analysis of on-the-fly garbage collection, Communications of the ACM, v.27 n.11, p.1143-1154, Nov. 1984 [doi>10.1145/1968.358298]
	17	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	18	Kung, H.T., and Song, S.W. "A Parallel Garbage Collection Algorithm and its Correctness Proof". Tech. Report, Computer Science Dept., Carnegie-Mellon Univ., May 1977, 20 p.
	19	Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
	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	J. E. B. Moss, Managing stack frames in Smalltalk, ACM SIGPLAN Notices, v.22 n.7, p.229-240, July 1987
	22	K. Nilsen, Garbage collection of strings and linked data structures in real time, Software—Practice & Experience, v.18 n.7, p.613-640, July 1988 [doi>10.1002/spe.4380180704]
	23	Christian Queinnec , Barbara Beaudoing , Jean-Pierre Queille, Mark DURING Sweep rather than Mark THEN Sweep, Proceedings of the Parallel Architectures and Languages Europe, Volume I: Parallel Architectures, p.224-237, June 12-16, 1989
	24	J. M. Robson, Bounds for Some Functions Concerning Dynamic Storage Allocation, Journal of the ACM (JACM), v.21 n.3, p.491-499, July 1974 [doi>10.1145/321832.321846]
	25	Robson, J.M. "Storage Allocation is NP-Hard". Info. Proc. Let. 11, 3 (1980), 119-125.
	26	White, Jon L. "Three Issues in Object-Oriented Garbage Collection". Proc. ECOOP/OOPSLA'90 Workshop on Garbage Collection, 1990.
	27	Paul R. Wilson, Some issues and strategies in heap management and memory hierarchies, ACM SIGPLAN Notices, v.26 n.3, p.45-52, March 1991 [doi>10.1145/122167.122173]
	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]
	29	Benjamin Goth Zorn, Comparative performance evaluation of garbage collection algorithms, University of California, Berkeley, 1989

CITED BY 32

	Tamar Domani , Elliot K. Kolodner , Erez Petrank, A generational on-the-fly garbage collector for Java, ACM SIGPLAN Notices, v.35 n.5, p.274-284, May 2000
	Daniel C. Wang , Andrew W. Appel, Type-preserving garbage collectors, ACM SIGPLAN Notices, v.36 n.3, p.166-178, March 2001
	Martin Hirzel , Johannes Henkel , Amer Diwan , Michael Hind, Understanding the connectivity of heap objects, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Saleh E. Abdullahi , Graem A. Ringwood, Garbage collecting the Internet: a survey of distributed garbage collection, ACM Computing Surveys (CSUR), v.30 n.3, p.330-373, Sept. 1998
	Michael Hicks , Luke Hornof , Jonathan T. Moore , Scott M. Nettles, A study of large object spaces, ACM SIGPLAN Notices, v.34 n.3, p.138-145, March 1999
	Julian Dolby , Andrew Chien, An automatic object inlining optimization and its evaluation, ACM SIGPLAN Notices, v.35 n.5, p.345-357, May 2000
	Yoo C. Chung , Soo-Mook Moon , Kemal Ebcioğlu , Dan Sahlin, Reducing sweep time for a nearly empty heap, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.378-389, January 19-21, 2000, Boston, MA, USA
	Ulrik Pagh Schultz , Kim Burgaard , Flemming Gram Christensen , Jørgen Lindskov Knudsen, Compiling java for low-end embedded systems, ACM SIGPLAN Notices, v.38 n.7, July 2003
	David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, ACM SIGPLAN Notices, v.38 n.1, p.285-298, January 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
	Yoo C. Chung , Soo-Mook Moon , Kemal Ebcioğlu , Dan Sahlin, Selective sweeping, Software—Practice & Experience, v.35 n.1, p.15-26, January 2005
	Matthias Pfeffer , Theo Ungerer , Stephan Fuhrmann , Jochen Kreuzinger , Uwe Brinkschulte, Real-Time Garbage Collection for a Multithreaded Java Microcontroller, Real-Time Systems, v.26 n.1, p.89-106, January 2004
	Tian F. Lim , Przemysław Pardyak , Brian N. Bershad, A memory-efficient real-time non-copying garbage collector, ACM SIGPLAN Notices, v.34 n.3, p.118-129, March 1999
	Teresa Higuera , Valérie Issarny , Michel Banâtre , Frédéric Parain, Memory Management for Real-Time Java: An Efficient Solution using Hardware Support, Real-Time Systems, v.26 n.1, p.63-87, January 2004
	Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Myths and realities: the performance impact of garbage collection, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
	David F. Bacon , Perry Cheng , V. T. Rajan, A unified theory of garbage collection, 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
	Phil McGachey , Antony L. Hosking, Reducing generational copy reserve overhead with fallback compaction, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Fridtjof Siebert, Realtime garbage collection in the JamaicaVM 3.0, Proceedings of the 5th international workshop on Java technologies for real-time and embedded systems, September 26-28, 2007, Vienna, Austria
	Rasmus Pedersen , Martin Schoeberl, Exact roots for a real-time garbage collector, Proceedings of the 4th international workshop on Java technologies for real-time and embedded systems, October 11-13, 2006, Paris, France
	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
	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
	Konstantinos Sagonas , Jesper Wilhelmsson, Mark and split, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	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
	Sylvain Stanchina , Matthias Meyer, Exploiting the efficiency of generational algorithms for hardware-supported real-time garbage collection, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
	Sebastien Marion , Richard Jones , Chris Ryder, Decrypting the Java gene pool, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada
	Kelvin Nilsen, High-level dynamic memory management for object-oriented real-time systems, ACM SIGPLAN OOPS Messenger, v.7 n.1, p.86-93, Jan. 1996
	Henry G. Baker, Safe and leakproof resource management using Ada83 limited types, ACM SIGAda Ada Letters, v.XIII n.5, p.32-42, Sept./Oct. 1993
	Henry G. Baker, Minimizing reference count updating with deferred and anchored pointers for functional data structures, ACM SIGPLAN Notices, v.29 n.9, p.38-43, Sept. 1994
	Nandakumar Sankaran, A bibliography on garbage collection and related topics, ACM SIGPLAN Notices, v.29 n.9, p.149-158, Sept. 1994
	Ting Yang , Emery D. Berger , Scott F. Kaplan , J. Eliot B. Moss, CRAMM: virtual memory support for garbage-collected applications, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington