A performance evaluation of lock-free synchronization protocols

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A performance evaluation of lock-free synchronization protocols

Full text

Pdf (1.10 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing table of contents

Los Angeles, California, United States

Pages: 130 - 140

Year of Publication: 1994

ISBN:0-89791-654-9

Author

Anthony LaMarca

Department of Computer Science and Engineering, University of Washington, Seattle, WA

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 31, Citation Count: 7

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/197917.197975 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	Juan Alemany , Edward W. Felten, Performance issues in non-blocking synchronization on shared-memory multiprocessors, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.125-134, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135446]
	2	Richard J. Anderson , Heather Woll, Wait-free parallel algorithms for the union-find problem, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.370-380, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103458]
	3	Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, Scheduler activations: effective kernel support for the user-level management of parallelism, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.95-109, October 13-16, 1991, Pacific Grove, California, United States
	4	T. E. Anderson, The Performance of Spin Lock Alternatives for Shared-Money Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.6-16, January 1990 [doi>10.1109/71.80120]
	5	Greg Barnes, A method for implementing lock-free shared-data structures, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.261-270, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165265]
	6	B. Bershad. Practical Considerations for Non- Blocking Concurrent Objects. In Proceedings of the 13th International Conference on Distributed Computing Systems, pages 264-274, May 1993.
	7	Brian N. Bershad , David D. Redell , John R. Ellis, Fast mutual exclusion for uniprocessors, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.223-233, October 12-15, 1992, Boston, Massachusetts, United States
	8	Brian N. Bershad, Matthew J. Zekauskas, and Wayne A. Sawdon. The Midway Distributed Shared Memory System. In Proceedings of the 38th IEEE Computer Society International Conference (COM- PCON '93), pages 528-537, February 1993.
	9	Eric A. Brewer , Chrysanthos N. Dellarocas , Adrian Colbrook , William E. Weihl, PROTEUS: a high-performance parallel-architecture simulator, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.247-248, June 01-05, 1992, Newport, Rhode Island, United States
	10	John B. Carter , John K. Bennett , Willy Zwaenepoel, Implementation and performance of Munin, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.152-164, October 13-16, 1991, Pacific Grove, California, United States
	11	David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
	12	Digital Equipment Corporation. DECchip 21064- AA Microprocessor, Hardware Reference Manual, 1992. Order Number: EC-N0079-72.
	13	Gary Granunke , Shreekant Thakkar, Synchronization Algorithms for Shared-Memory Multiprocessors, Computer, v.23 n.6, p.60-69, June 1990 [doi>10.1109/2.55501]
	14	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
	15	M. Herlihy. A Methodology for Implementing Highly Concurrent Data Objects., 1991. CRL Technical Report 91/10.
	16	Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, ACM SIGARCH Computer Architecture News, v.21 n.2, p.289-300, May 1993
	17	Daniel Lenoski , James Laudon , Truman Joe , David Nakahira , Luis Stevens , Anoop Gupta , John Hennessy, The DASH prototype: implementation and performance, Proceedings of the 19th annual international symposium on Computer architecture, p.92-103, May 19-21, 1992, Queensland, Australia
	18	H. Massalin , C. Pu, Threads and input/output in the synthesis kernal, Proceedings of the twelfth ACM symposium on Operating systems principles, p.191-201, November 1989
	19	John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
	20	Lawrence Snyder, Type architectures, shared memory, and the corollary of modest potential, Annual review of computer science vol. 1, 1986, Annual Reviews Inc., Palo Alto, CA, 1986
	21	Josep Torrellas , Anoop Gupta , John Hennessy, Characterizing the caching and synchronization performance of a multiprocessor operating system, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.162-174, October 12-15, 1992, Boston, Massachusetts, United States
	22	j. M. Wing and C. Gong. A Library of Concurrent Objects and Their Proofs of Correctness., 1990. Technical Report CMU-CS-90-151, Carnegie Mellon University.
	23	Jeannette M. Wing , Chun Gong, Testing and verifying concurrent objects, Journal of Parallel and Distributed Computing, v.17 n.1-2, p.164-182, Jan./Feb. 1993 [doi>10.1006/jpdc.1993.1015]
	24	J. Zahorjan, E. Lazowska, and D. Eager. Spinning Verses Waiting in Parallel Systems with Uncertainty. In Proceedings of the International Seminar on Distributed and Parallel Systems, pages 455-472, December 1988.

CITED BY 7

	Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada
	Yehuda Afek , Dalia Dauber , Dan Touitou, Wait-free made fast, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.538-547, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Philip Holman , James H. Anderson, Supporting lock-free synchronization in Pfair-scheduled real-time systems, Journal of Parallel and Distributed Computing, v.66 n.1, p.47-67, January 2006
	Hagit Attiya , Rachid Guerraoui , Danny Hendler , Petr Kouznetsov, Synchronizing without locks is inherently expensive, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	H. Gao , J. F. Groote , W. H. Hesselink, Lock-free dynamic hash tables with open addressing, Distributed Computing, v.18 n.1, p.21-42, July 2005
	Guojing Cong , David A. Bader, Designing irregular parallel algorithms with mutual exclusion and lock-free protocols, Journal of Parallel and Distributed Computing, v.66 n.6, p.854-866, June 2006
	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