Algorithms for on-the-fly garbage collection

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for on-the-fly garbage collection

Full text

Pdf (679 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 6 , Issue 3 (July 1984) table of contents

Pages: 333 - 344

Year of Publication: 1984

ISSN:0164-0925

Author

Mordechai Ben-Ari

Tel Aviv University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 62, Citation Count: 35

Additional Information:

references cited by index terms review 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/579.587 What is a DOI?

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	Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981 [doi>10.1145/356850.356854]
	2	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]
	3	FRANCEZ, N. An application of a method for analysis of cyclic programs. IEEE Trans. $ofiw. Eng. SE-4(5), (1978), 371-378.
	4	FRANCEZ, N. AND PNUELI, A. A proof method for cyclic programs. Acta In{. 9 (1978), 133-157.
	5	David Gries, An exercise in proving parallel programs correct, Communications of the ACM, v.20 n.12, p.921-930, Dec. 1977 [doi>10.1145/359897.359903]
	6	KuNO, H.T. AND SONG, S.W. An efficient parallel garbage collection system and its correctness proof. In Proceedings o{ the IEEE Symposium on Foundations of Computer Science (Providence, R.I.). IEEE, New York, 1977, pp. 120-131.
	7	LAMPORT, L. Proving the correctness of multiprocess programs. IEEE Trans. So{tw. Eng. SE- 3, (1977), 125-143.
	8	OWlCKI, S. ANO GRIE$, D. An axiomatic proof technique for parallel programs I. Acta in{. 6 (1976), 319-340.
	9	Fred J. Pollack , George W. Cox , Dan W. Hammerstrom , Kevin C. Kahn , Konrad K. Lai , Justin R. Rattner, Supporting ada memory management in the iAPX-432, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.117-131, March 01-03, 1982, Palo Alto, California, United States
	10	PNEULI, A. The temporal semantics of concurrent programs. Theor. Comput. Sci. 13 (1981), 45-60.

CITED BY 35

	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
	José M. Piquer, Indirect distributed garbage collection: handling object migration, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.5, p.615-647, Sept. 1996
	Farokh Bastani , Wael Hilal , Ing-Ray Chen, Performance analysis of concurrent maintenance policies for servers in a distributed environment, Proceedings of 1986 ACM Fall joint computer conference, p.611-619, November 1986, Dallas, Texas, United States
	B. Goldberg, Generational reference counting: a reduced-communication distributed storage reclamation scheme, ACM SIGPLAN Notices, v.24 n.7, p.313-321, July 1989
	Damien Doligez , Georges Gonthier, Portable, unobtrusive garbage collection for multiprocessor systems, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.70-83, January 16-19, 1994, Portland, Oregon, United States
	Ravi Sharma , Mary Lou Soffa, Parallel generational garbage collection, ACM SIGPLAN Notices, v.26 n.11, p.16-32, Nov. 1991
	Christian Ungureanu , Benjamin Goldberg, Formal models of distributed memory management, ACM SIGPLAN Notices, v.32 n.8, p.280-291, Aug. 1997
	Ing-Ray Chen , Sayed A. Banawan, A uniform approach to the stability and performance analysis of concurrent data structure maintenance policies, Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing: technological challenges of the 1990's, p.160-168, April 1992, Kansas City, Missouri, United States
	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
	Damien Doligez , Xavier Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.113-123, March 1993, Charleston, South Carolina, United States
	Maurice P. Herlihy , J. E. B. Moss, Lock-free garbage collection for multiprocessors, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.229-236, July 21-24, 1991, Hilton Head, South Carolina, United States
	Katherine Barabash , Yoav Ossia , Erez Petrank, Mostly concurrent garbage collection revisited, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Hezi Azatchi , Yossi Levanoni , Harel Paz , Erez Petrank, An on-the-fly mark and sweep garbage collector based on sliding views, ACM SIGPLAN Notices, v.38 n.11, November 2003
	A. Gupta , W. K. Fuchs, Garbage Collection in a Distributed Object-Oriented System, IEEE Transactions on Knowledge and Data Engineering, v.5 n.2, p.257-265, April 1993
	M. P. Herlihy , J. E. B. Moss, Lock-Free Garbage Collection for Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.3, p.304-311, May 1992
	N. Bagherzadeh , S. -l. Heng , C. -l. Wu, A Parallel Asynchronous Garbage Collection Algorithm for Distributed Systems, IEEE Transactions on Knowledge and Data Engineering, v.3 n.1, p.100-107, March 1991
	Ing-Ray Chen , S. A. Banawan, Modeling and Analysis of Concurrent Maintenance Policies for Data Structures Using Pointers, IEEE Transactions on Software Engineering, v.19 n.9, p.902-911, September 1993
	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
	Lars Birkedal , Noah Torp-Smith , John C. Reynolds, Local reasoning about a copying garbage collector, ACM SIGPLAN Notices, v.39 n.1, p.220-231, January 2004
	Luc Moreau , Peter Dickman , Richard Jones, Birrell's distributed reference listing revisited, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1344-1395, November 2005
	Jan E. Jonker, On-the-fly garbage collection for several mutators, Distributed Computing, v.5 n.4, p.187-199, April 1992
	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
	Noah Torp-Smith , Lars Birkedal , John C. Reynolds, Local reasoning about a copying garbage collector, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.4, p.1-58, July 2008
	Gerard Tel , Friedemann Mattern, The derivation of distributed termination detection algorithms from garbage collection schemes, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.1, p.1-35, Jan. 1993
	H. Gao , J. F. Groote , W. H. Hesselink, Lock-free parallel and concurrent garbage collection by mark&sweep, Science of Computer Programming, v.64 n.3, p.341-374, February, 2007
	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
	Andrew McCreight , Zhong Shao , Chunxiao Lin , Long Li, A general framework for certifying garbage collectors and their mutators, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Martin T. Vechev , Eran Yahav , David F. Bacon , Noam Rinetzky, CGCExplorer: a semi-automated search procedure for provably correct concurrent collectors, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Chun-Xiao Lin , Yi-Yun Chen , Long Li , Bei Hua, Garbage collector verification for proof-carrying code, Journal of Computer Science and Technology, v.22 n.3, p.426-437, May 2007
	J. D. Eckart , R. J. LeBlanc, Distributed garbage collection, ACM SIGPLAN Notices, v.22 n.7, p.264-273, July 1987
	Nandakumar Sankaran, A bibliography on garbage collection and related topics, ACM SIGPLAN Notices, v.29 n.9, p.149-158, Sept. 1994
	B. Lang , F. Dupont, Incremental incrementally compacting garbage collection, ACM SIGPLAN Notices, v.22 n.7, p.253-263, July 1987
	David M. Goldschlag, A Mechanization of Unity in PC-NQTHM-92, Journal of Automated Reasoning, v.23 n.3, p.445-498, November 1999
	Martin Kero , Johan Nordlander , Per Lindgren, A correct and useful incremental copying garbage collector, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada
	Harel Paz , David F. Bacon , Elliot K. Kolodner , Erez Petrank , V. T. Rajan, An efficient on-the-fly cycle collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.4, p.20-es, August 2007

INDEX TERMS

Primary Classification:
D. Software
D.4 OPERATING SYSTEMS
D.4.2 Storage Management
Subjects: Garbage collection

Additional Classification:
D. Software
D.1 PROGRAMMING TECHNIQUES
D.2 SOFTWARE ENGINEERING
D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Design, Languages, Performance, Theory, Verification

REVIEW

"John Gauntlett Benedict Heal : Reviewer"

On-the-fly garbage collectors provide an interesting class of concurrent algorithms for study, as they are quintessentially concurrent, rather than sequential algorithms which manage to work despite the concurrency. Dijstra et al. [1] present a more...

Collaborative Colleagues:

Mordechai Ben-Ari: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player