Barrier techniques for incremental tracing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Barrier techniques for incremental tracing

Full text

Pdf (708 KB)

Source

International Symposium on Memory Management archive
Proceedings of the 1st international symposium on Memory management table of contents

Vancouver, British Columbia, Canada

Pages: 20 - 25

Year of Publication: 1998

ISBN:1-58113-114-3

Also published in ...

Author

Pekka P. Pirinen

Harlequin Limited, Barrington Hall, Barrington, Cambridge CB2 5RG, UK

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 51, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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/286860.286863 What is a DOI?

ABSTRACT

This paper presents a classification of barrier techniques for interleaving tracing with mutator operation during an incremental garbage collection. The two useful tricolour invariants are derived from more elementary considerations of graph traversal. Barrier techniques for maintaining these invariants are classified according to the action taken at the barrier (such as scanning an object or changing its colour), and it is shown that the algorithms described in the literature cover all the possibilities except one. Unfortunately, the new technique is impractical. Ways of combining barrier techniques are also discussed.

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.

	AEL88	A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, ACM SIGPLAN Notices, v.23 n.7, p.11-20, July 1988
	AP87	Santosh Abraham and J. Patel. Parallel garbage collection on a virtual memory system. In E. Chiricozzi and A. D'Amato, editors, Inter'- national Conference on Parallel Processing and Applications, pages 243--246, L'Aquila, Italy, September 1987. Elsevier-North Holland. Also technical report CSRD 620, University of Illinois at Urbana-Champaign, Center for Supercomputing Research and Development.
	Bak78	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]
	Bar88	Joel F. Bartlett. Compacting garbage collection with ambiguous roots. Technical Report 88/2, DEC Western Research Laboratory, Palo Alto, CA, February 1988. Also in Lisp Pointers 1, 6 (April-June 1988), pp. 2-12.
	BC92	Proceedings of the International Workshop on Memory Management, September 1992
	BDS91	Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, ACM SIGPLAN Notices, v.26 n.6, p.157-164, June 1991
	DLM+76	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]
	Jon96	Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
	NOPH92	Scott Nettles , James O''Toole , David Pierce , Nicholas Haines, Replication-Based Incremental Copying Collection, Carnegie Mellon University, Pittsburgh, PA, 1993
	Ste75	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]
	Wil94	Paul R. Wilson. Uniprocessor garbage collection techniques. Technical report, University of Texas, January 1994. Expanded version of the IWMM92 paper.
	WJ93	Paul R. Wilson and Mark S. Johnstone. Truly real-time non-copying garbage collection. In Eliot Moss, Paul R. Wilson, and Benjamin Zorn, editors, OOPSLA/ECOOP '93 Workshop on Garbage Collection in Object-Oriented Systems, October 1993.
	Yua90	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]

CITED BY 5

	Anthony Savidis, The implementation of generic smart pointers for advanced defensive programming, Software—Practice & Experience, v.34 n.10, p.977-1009, August 2004
	Stephen M. Blackburn , Richard L. Hudson , Ron Morrison , J. Eliot B. Moss , David S. Munro , John Zigman, Starting with termination: a methodology for building distributed garbage collection algorithms, Australian Computer Science Communications, v.23 n.1, p.20-28, January-February 2001
	Filip Pizlo , Antony L. Hosking , Jan Vitek, Hierarchical real-time garbage collection, ACM SIGPLAN Notices, v.42 n.7, July 2007
	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
	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