Lock-free garbage collection for multiprocessors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lock-free garbage collection for multiprocessors

Full text

Pdf (802 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the third annual ACM symposium on Parallel algorithms and architectures table of contents

Hilton Head, South Carolina, United States

Pages: 229 - 236

Year of Publication: 1991

ISBN:0-89791-438-4

Authors

Maurice P. Herlihy	Digital Equipment Corporation, Cambridge Research Laboratory, One Kendall Square, Cambridge, MA
J. E. B. Moss	Dept. of Comp. and Info. Sci., University of Massachusetts, Amherst, MA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 33, Citation Count: 8

Additional Information:

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/113379.113400 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.

	Afek et al., 1990	Yehuda Afek , Danny Dolev , Hagit Attiya , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.1-13, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93394]
	Baker, 1978	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]
	BBN, 1985	BBN. The uniform system approach to programming the Butterfly parallel processor. Tech. Rep. 6149, Bolt, Beranek, and Newman Adv. Computers, Inc., Cambridge, MA, Oct. 1985.
	Ben-Ari, 1984	Mordechai Ben-Ari, Algorithms for on-the-fly garbage collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.333-344, July 1984 [doi>10.1145/579.587]
	Dijkstra et al., 1978	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]
	Ellis et al., 1988	John R. Ellis, Kai Li, and Andrew W. Appel. Real-time concurrent collection on stock multiprocessors. Tech. Rep. 25, Digital Systems Research Center, 130 Lytton Avenue, Palo Alto, CA 94301, Feb. 1988.
	Halstead, 1985	Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
	Herlihy, 1988	Maurice P. Herlihy, Impossibility and universality results for wait-free synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.276-290, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62593]
	Herlihy, 1990	M. Herlihy, A methodology for implementing highly concurrent data structures, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.197-206, March 14-16, 1990, Seattle, Washington, United States
	Herlihy, 1991	Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
	Herlihy and Moss, 1992	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 [doi>10.1109/71.139204]
	Herlihy and Wing, 1990	Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
	IBM	IBM. System/370 Principles of Operation. Order Number GA22-7000.
	Kilian, 1991	Earl Kilian, Apr. 1991. Personal communication.
	Kung and Song, 1977	H. T. Kung and S. W. Song. An efficient parallel garbage collection system and its correctness proof. In 18th Symposium on Foundations of Computer Science (Oct. 1977), pp. 120-131.
	Lamport, 1983	Leslie Lamport, Specifying Concurrent Program Modules, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.190-222, April 1983 [doi>10.1145/69624.357207]
	Lamport, 1986	Leslie Lamport. On interprocess communication, parts I and II. Distributed Computing i (1986), 77-101.
	Li, 1986	Kai Li, Shared virtual memory on loosely coupled multiprocessors, 1986
	Massalin and Pu, 1991	Henry Massalin and Calton Pu. A lock-free multiprocessor OS kernel. Technical Report CUCS-005-91, Columbia University, Department of Computer Science, New York, NY, Mar. 1991.
	Motorola, Inc., 1989	CORPORATE Motorola, Inc., M68000 family programmer's reference manual, Motorola Inc., Phoenix, AZ, 1991
	Peterson, 1983	Gary L. Peterson, Concurrent Reading While Writing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.46-55, Jan. 1983 [doi>10.1145/357195.357198]
	Pfister et al., 1985	Greg H. Pfister et at. The IBM Research Parallel Processor Prototype (Pal:'3): Introduction and architecture. In International Conference on Parallel Processing (1985).
	Pixley, 1988	C. Pixley. An incremental garbage collection algorithm for multi-mutator systems. Distributed Computing 3, 1 (Dec. 1988), 41-49.

CITED BY 8

	Guy E. Blelloch , Perry Cheng , Phillip B. Gibbons, Room synchronizations, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.122-133, July 2001, Crete Island, Greece
	John D. Valois, Lock-free linked lists using compare-and-swap, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.214-222, August 20-23, 1995, Ottowa, Ontario, Canada
	Maged M. Michael, Safe memory reclamation for dynamic lock-free objects using atomic reads and writes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Theodore Johnson, Characterizing the Performance of Algorithms for Lock-Free Objects, IEEE Transactions on Computers, v.44 n.10, p.1194-1207, October 1995
	Hai Huang , Padmanabhan Pillai , Kang G. Shin, Improving Wait-Free Algorithms for Interprocess Communication in Embedded Real-Time Systems, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.303-316, June 10-15, 2002
	Nandakumar Sankaran, A bibliography on garbage collection and related topics, ACM SIGPLAN Notices, v.29 n.9, p.149-158, Sept. 1994
	Nandakumar Sankaran, A bibliography on garbage collection and related topics, ACM SIGPLAN Notices, v.29 n.9, p.149-158, Sept. 1994
	Phil McGachey , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Vijay Menon , Bratin Saha , Tatiana Shpeisman, Concurrent GC leveraging transactional memory, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA