Practical implementations of non-blocking synchronization primitives

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Practical implementations of non-blocking synchronization primitives

Full text

Pdf (1.04 MB)

Source

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

Santa Barbara, California, United States

Pages: 219 - 228

Year of Publication: 1997

ISBN:0-89791-952-1

Author

Mark Moir

Department of Computer Science, The University of Pittsburgh, Pittsburgh, PA

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): 47, Citation Count: 36

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/259380.259442 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	Alpha Architecture Handbook, Digital Equipment Corporation, 1992.
	2	James H. Anderson , Mark Moir, Universal constructions for multi-object operations, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.184-193, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224985]
	3	James H. Anderson , Mark Moir, Universal Constructions for Large Objects, Proceedings of the 9th International Workshop on Distributed Algorithms, p.168-182, September 13-15, 1995
	4	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]
	5	Michael Greenwald , David Cheriton, The synergy between non-blocking synchronization and operating system structure, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.123-136, October 29-November 01, 1996, Seattle, Washington, United States
	6	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]
	7	Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.745-770, Nov. 1993 [doi>10.1145/161468.161469]
	8	Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
	9	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]
	10	Amos Israeli , Lihu Rappoport, Disjoint-access-parallel implementations of strong shared memory primitives, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.151-160, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198079]
	11	M. Michael and M. Scott, "Implementation of Atomic Primitives on Distributed Shared Memory Multiprocessors", Proceedings of the 1st Annual Symposium on High Performance Computer A rchitecture, 1995, pp. 221-231.
	12	MIPS RdO00 Microprocessor User's Monual, MIPS Computer Systems, Inc., 1991.
	13	PowerPC 601 RISC Microprocessor l'ser's Manual, Motorola, Inc., 1993.
	14	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 [doi>10.1145/224964.224987]
	15	J. Valois, "Space Bounds for Transactional Synchronization", unpublished manuscript, January 1997.

CITED BY 36

	Dave Dice , Alex Garthwaite, Mostly lock-free malloc, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Patrick Keane , Mark Moir, A Simple Local-Spin Group Mutual Exclusion Algorithm, IEEE Transactions on Parallel and Distributed Systems, v.12 n.7, p.673-685, July 2001
	Mark Moir, Correction: practical implementations of non-blocking synchronization primitives, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.323, August 2001, Newport, Rhode Island, United States
	Tushar Deepak Chandra , Prasad Jayanti , King Tan, A polylog time wait-free construction for closed objects, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.287-296, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Maged M. Michael, High performance dynamic lock-free hash tables and list-based sets, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Prasad Jayanti, A lower bound on the local time complexity of universal constructions, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.183-192, June 28-July 02, 1998, Puerto Vallarta, Mexico
	James H. Anderson , Mark Moir, Universal Constructions for Large Objects, IEEE Transactions on Parallel and Distributed Systems, v.10 n.12, p.1317-1332, December 1999
	Danny Hendler , Nir Shavit, Non-blocking steal-half work queues, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Prasad Jayanti, A time complexity lower bound for randomized implementations of some shared objects, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.201-210, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Mark Moir, Laziness pays! using lazy synchronization mechanisms to improve non-blocking constructions, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.61-70, July 16-19, 2000, Portland, Oregon, United States
	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
	Nimar S. Arora , Robert D. Blumofe , C. Greg Plaxton, Thread scheduling for multiprogrammed multiprocessors, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.119-129, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Ori Shalev , Nir Shavit, Split-ordered lists: lock-free extensible hash tables, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.102-111, July 13-16, 2003, Boston, Massachusetts
	Victor Luchangco , Mark Moir , Nir Shavit, Nonblocking k-compare-single-swap, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Hans-J. Boehm, An almost non-blocking stack, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Simon Doherty , Maurice Herlihy , Victor Luchangco , Mark Moir, Bringing practical lock-free synchronization to 64-bit applications, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Prasad Jayanti , Srdjan Petrovic, Efficient and practical constructions of LL/SC variables, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.285-294, July 13-16, 2003, Boston, Massachusetts
	Prasad Jayanti, f-arrays: implementation and applications, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Maurice Herlihy , Victor Luchangco , Paul Martin , Mark Moir, Nonblocking memory management support for dynamic-sized data structures, ACM Transactions on Computer Systems (TOCS), v.23 n.2, p.146-196, May 2005
	Tim Harris , Keir Fraser, Revocable locks for non-blocking programming, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA
	Mark Moir , Daniel Nussbaum , Ori Shalev , Nir Shavit, Using elimination to implement scalable and lock-free FIFO queues, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Rachid Guerraoui , Maurice Herlihy , Bastian Pochon, Toward a theory of transactional contention managers, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Prasad Jayanti, An optimal multi-writer snapshot algorithm, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Ori Shalev , Nir Shavit, Split-ordered lists: Lock-free extensible hash tables, Journal of the ACM (JACM), v.53 n.3, p.379-405, May 2006
	Maurice Herlihy , Victor Luchangco , Mark Moir, A flexible framework for implementing software transactional memory, ACM SIGPLAN Notices, v.41 n.10, October 2006
	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
	H. Gao , W. H. Hesselink, A general lock-free algorithm using compare-and-swap, Information and Computation, v.205 n.2, p.225-241, February, 2007
	Sebastian Burckhardt , Rajeev Alur , Milo M. K. Martin, CheckFence: checking consistency of concurrent data types on relaxed memory models, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Anders Gidenstam , Marina Papatriantafilou, LFTHREADS: a lock-free thread library, ACM SIGARCH Computer Architecture News, v.36 n.5, December 2008
	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
	Lindsay Groves , Robert Colvin, Derivation of a Scalable Lock-Free Stack Algorithm, Electronic Notes in Theoretical Computer Science (ENTCS), 187, p.55-74, July, 2007
	Cesare Ferri , Tali Moreshet , R. Iris Bahar , Luca Benini , Maurice Herlihy, A hardware/software framework for supporting transactional memory in a MPSoC environment, ACM SIGARCH Computer Architecture News, v.35 n.1, March 2007
	Håkan Sundell , Philippas Tsigas, Lock-free deques and doubly linked lists, Journal of Parallel and Distributed Computing, v.68 n.7, p.1008-1020, July, 2008
	Wojciech Golab , Vassos Hadzilacos , Danny Hendler , Philipp Woelfel, Constant-RMR implementations of CAS and other synchronization primitives using read and write operations, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Maurice Herlihy , Victor Luchangco, Distributed computing and the multicore revolution, ACM SIGACT News, v.39 n.1, March 2008
	Hakan Sundell , Philippas Tsigas, NOBLE: non-blocking programming support via lock-free shared abstract data types, ACM SIGARCH Computer Architecture News, v.36 n.5, December 2008