Article

Bringing practical lock-free synchronization to 64-bit applications

Authors:

Maurice Herlihy,

Victor Luchangco,

Mark MoirAuthors Info & Claims

PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

Pages 31 - 39

https://doi.org/10.1145/1011767.1011773

Published: 25 July 2004 Publication History

Abstract

Many lock-free data structures in the literature exploit techniques that are possible only because state-of-the-art 64-bit processors are still running 32-bit operating systems and applications. As software catches up to hardware, "64-bit-clean" lock-free data structures, which cannot use such techniques, are needed.We present several 64-bit-clean lock-free implementations: load-linked/store-conditional variables of arbitrary size, a FIFO queue, and a freelist. In addition to being portable to 64-bit software, our implementations also improve on previous ones in that they are space-adaptive and do not require knowledge of the number of threads that will access them.

References

[1]

Java Specification Request for Concurrent Utilities (JSR166). http://jcp.org.

[2]

J. Anderson and M. Moir. Universal constructions for large objects. IEEE Transactions on Parallel and Distributed Systems, 10(12):1317--1332, 1999.

Digital Library

[3]

J. Chase, M. Baker-Harvey, H. Levy, and E. Lazowska. Opal: A single address space system for 64-bit architectures (abstract). Operating Systems Review, 26(2):9, 1992.

Digital Library

[4]

D. Dice and A. Garthwaite. Mostly lock-free malloc. In Proceedings of the ACM SIGPLAN International Symposium on Memory Management, 2002.

Digital Library

[5]

M. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124--149, 1991.

Digital Library

[6]

M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Dynamic-sized lock-free data structures. In Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing, page 131, July 2002.

Digital Library

[7]

M. Herlihy, V. Luchangco, and M. Moir. The repeat offender problem: A mechanism for supporting dynamic-sized, lock-free data structures. In Proceedings of 16th International Symposium on Distributed Computing, Oct. 2002.

Digital Library

[8]

M. Herlihy, V. Luchangco, and M. Moir. Space- and time-adaptive nonblocking algorithms. In Proceedings of Computing: The Australasian Theory Symposium, 2003.

[9]

M. Herlihy and J. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463--492, Nov. 1990.

Digital Library

[10]

P. Jayanti and S. Petrovic. Efficient and practical constructions of LL/SC variables. In Proceedings of the 22nd Annual ACM Symposium on the Principles of Distributed Computing, July 2003.

Digital Library

[11]

M. Michael. Hazard pointers: Safe memory reclamation for lock-free objects. IEEE Transactions on Parallel and Distributed Systems, 15(8), Aug. 2004. A preliminary version appeared in Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing, 2002.

Digital Library

[12]

M. Michael. Scalable lock-free dynamic memory allocation. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, June 2004.

Digital Library

[13]

M. Michael and M. Scott. Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors. Journal of Parallel and Distributed Computing, 51(10):1--26, 1998.

Digital Library

[14]

MIPS R4000 Microprocessor User's Manual. MIPS Computer Systems, Inc., 1991.

[15]

M. Moir. Practical implementations of non-blocking synchronization primitives. In Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, pages 219--228, 1997.

Digital Library

[16]

PowerPC 601 RISC Microprocessor User's Manual. Motorola, Inc., 1993.

[17]

S. Prakash, Y. Lee, and T. Johnson. A non-blocking algorithm for shared queues using compare-and-swap. IEEE Transactions on Computers, 43(5):548--559, 1994.

Digital Library

[18]

R. L. Sites. Alpha Architecture Reference Manual. Digital Press and Prentice-Hall, 1992.

Digital Library

[19]

R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, 1986.

[20]

J. Valois. Implementing lock-free queues. In Proceedings of the 7th International Conference on Parallel and Distributed Computing Systems, Oct. 1994.

[21]

D. Weaver and T. Germond. The SPARC Architecture Manual Version 9. PTR Prentice Hall, 1994.

Digital Library

Cited By

Naderi-Semiromi FWoelfel PKuznetsov PGelles ROlivetti D(2024)Strongly Linearizable LL/SC from CASProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662800(443-453)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662800
Aghazadeh ZWoelfel PGeorgiou CSpirakis P(2015)On the Time and Space Complexity of ABA Prevention and DetectionProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767403(193-202)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1145/2767386.2767403
Cederman DTsigas P(2013)Supporting Lock-Free Composition of Concurrent Data ObjectsIEEE Transactions on Computers10.1109/TC.2012.24862:9(1866-1878)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1109/TC.2012.248
Show More Cited By

Index Terms

Recommendations

Practical, Fast and Simple Concurrent FIFO Queues Using Single Word Synchronization Primitives
Ada-Europe '08: Proceedings of the 13th Ada-Europe international conference on Reliable Software Technologies

We present an efficient and practical non-blocking implementation of a concurrent array-based FIFO queue that is suitable for preemptive multi threaded systems. It is well known that concurrent FIFO queues relying on mutual exclusion cause blocking, ...
DCAS is not a silver bullet for nonblocking algorithm design
SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures

Despite years of research, the design of efficient nonblocking algorithms remains difficult. A key reason is that current shared-memory multiprocessor architectures support only single-location synchronisation primitives such as compare-and-swap (CAS) ...
SnapQueue: lock-free queue with constant time snapshots
SCALA 2015: Proceedings of the 6th ACM SIGPLAN Symposium on Scala

We introduce SnapQueues - concurrent, lock-free queues with a linearizable, lock-free global-state transition operation. This transition operation can atomically switch between arbitrary SnapQueue states, and is used by enqueue, dequeue, snapshot and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

July 2004

422 pages

ISBN:1581138024

DOI:10.1145/1011767

General Chair:
Soma Chaudhuri
Iowa State University
,
Program Chair:
Shay Kutten
Technion

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC04

Sponsor:

PODC04: Principles of Distributed Computing 2004

July 25 - 28, 2004

Newfoundland, St. John's, Canada

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
872
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Naderi-Semiromi FWoelfel PKuznetsov PGelles ROlivetti D(2024)Strongly Linearizable LL/SC from CASProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662800(443-453)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662800
Aghazadeh ZWoelfel PGeorgiou CSpirakis P(2015)On the Time and Space Complexity of ABA Prevention and DetectionProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767403(193-202)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1145/2767386.2767403
Cederman DTsigas P(2013)Supporting Lock-Free Composition of Concurrent Data ObjectsIEEE Transactions on Computers10.1109/TC.2012.24862:9(1866-1878)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1109/TC.2012.248
Hesselink W(2013)Verifying a simplification of mutual exclusion by Lycklama---HadzilacosActa Informatica10.1007/s00236-013-0178-250:3(199-228)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1007/s00236-013-0178-2
Junchang Wang Kai Zhang Bei Hua (2012)Parallelizing sequential network applications with customized lock-free data structures7th International Conference on Communications and Networking in China10.1109/ChinaCom.2012.6417441(18-23)Online publication date: Aug-2012
https://doi.org/10.1109/ChinaCom.2012.6417441
Cederman DTsigas PAmato NFranke HKelly P(2010)Supporting lock-free composition of concurrent data objectsProceedings of the 7th ACM international conference on Computing frontiers10.1145/1787275.1787286(53-62)Online publication date: 17-May-2010
https://dl.acm.org/doi/10.1145/1787275.1787286
Li ZYu NHao Z(2010)A Novel Parallel Traffic Control Mechanism for Cloud ComputingProceedings of the 2010 IEEE Second International Conference on Cloud Computing Technology and Science10.1109/CloudCom.2010.9(376-382)Online publication date: 30-Nov-2010
https://dl.acm.org/doi/10.1109/CloudCom.2010.9
Gao HFu YHesselink W(2009)Practical Lock-Free Implementation of LL/SC Using Only Pointer-Size CASProceedings of the 2009 First IEEE International Conference on Information Science and Engineering10.1109/ICISE.2009.841(320-323)Online publication date: 26-Dec-2009
https://dl.acm.org/doi/10.1109/ICISE.2009.841
Lei GMingche LZhenghu G(2009)A Practical Non-blocking Route Propagation Technology for Threaded BGPProceedings of the 2009 International Conference on Scalable Computing and Communications; Eighth International Conference on Embedded Computing10.1109/EmbeddedCom-ScalCom.2009.45(206-211)Online publication date: 25-Sep-2009
https://dl.acm.org/doi/10.1109/EmbeddedCom-ScalCom.2009.45
Gao HFu YHesselink W(2009)Verification of a Lock-Free Implementation of Multiword LL/SC ObjectProceedings of the 2009 Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing10.1109/DASC.2009.25(31-36)Online publication date: 12-Dec-2009
https://dl.acm.org/doi/10.1109/DASC.2009.25
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents