research-article

Supporting lock-free composition of concurrent data objects

Authors:

Daniel Cederman,

Philippas TsigasAuthors Info & Claims

CF '10: Proceedings of the 7th ACM international conference on Computing frontiers

Pages 53 - 62

https://doi.org/10.1145/1787275.1787286

Published: 17 May 2010 Publication History

Abstract

Lock-free data objects offer several advantages over their blocking counterparts, such as being immune to deadlocks and convoying and, more importantly, being highly concurrent. However, composing the operations they provide into larger atomic operations, while still guaranteeing efficiency and lock-freedom, is a challenging algorithmic task.

We present a lock-free methodology for composing highly concurrent linearizable objects together by unifying their linearization points. This makes it possible to relatively easily introduce atomic lock-free move operations to a wide range of concurrent objects. Experimental evaluation has shown that the operations originally supported by the data objects keep their performance behavior under our methodology.

References

[1]

J. H. Anderson and M. Moir. Universal Constructions for Multi-Object Operations. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, pages 184--193, 1995.

Digital Library

[2]

J. H. Anderson, S. Ramamurthy, and R. Jain. Implementing Wait-Free Objects on Priority-Based Systems. In PODC '97: Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, pages 229--238, 1997.

Digital Library

[3]

C. Cascaval, C. Blundell, M. Michael, H. W. Cain, P. Wu, S. Chiras, and S. Chatterjee. Software Transactional Memory: Why Is It Only a Research Toy? Queue, 6(5):46--58, 2008.

Digital Library

[4]

D. Cederman and P. Tsigas. Supporting Lock-Free Composition of Concurrent Data Objects. Computing Research Repository, abs/0910.0366, 2009.

[5]

S. Doherty, D. L. Detlefs, L. Groves, C. H. Flood, V. Luchangco, P. A. Martin, M. Moir, N. Shavit, and G. L. Steele, Jr. DCAS is not a Silver Bullet for Nonblocking Algorithm Design. In SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, pages 216--224, 2004.

Digital Library

[6]

S. Doherty, M. Herlihy, V. Luchangco, and M. Moir. Bringing Practical Lock-Free Synchronization to 64-bit Applications. In PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pages 31--39, 2004.

Digital Library

[7]

M. Fomitchev and E. Ruppert. Lock-free linked lists and skip lists. In PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pages 50--59, 2004.

Digital Library

[8]

A. Gidenstam, M. Papatriantafilou, and P. Tsigas. Allocating Memory in a Lock-Free Manner. In ESA '05: Proceedings of the 13th Annual European Symposium on Algorithms, pages 329--342, 2005.

Digital Library

[9]

A. Gidenstam, M. Papatriantafilou, and P. Tsigas. NBmalloc: Allocating Memory in a Lock-Free Manner. Algorithmica, 2009.

[10]

P. H. Ha and P. Tsigas. Reactive Multi-Word Synchronization for Multiprocessors. In Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, pages 184--193, 2003.

Digital Library

[11]

T. Harris. A Pragmatic Implementation of Non-blocking Linked-Lists. In DISC '01: Proceedings of the 15th International Conference on Distributed Computing, pages 300--314, 2001.

Digital Library

[12]

T. Harris, K. Fraser, and I. A. Pratt. A Practical Multi-word Compare-and-Swap Operation. In DISC '02: Proceedings of the 16th International Conference on Distributed Computing, pages 265--279, 2002.

Digital Library

[13]

T. Harris, S. Marlow, S. Peyton-Jones, and M. P. Herlihy. Composable Memory Transactions. In PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 48--60, 2005.

Digital Library

[14]

T. L. Harris. A pragmatic implementation of non-blocking linked-lists. In DISC '01: Proceedings of the 15th International Conference on Distributed Computing, pages 300--314, 2001.

Digital Library

[15]

M. P. Herlihy. A Methodology for Implementing Highly Concurrent Data Objects. ACM Transactions on Programming Languages and Systems, 15(5):745--770, 1993.

Digital Library

[16]

M. P. Herlihy and J. M. Wing. Linearizability: a Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems, 12(3):463--492, 1990.

Digital Library

[17]

Intel. Threading Building Blocks, 2009.

[18]

A. Israeli and L. Rappoport. Disjoint-Access-Parallel Implementations of Strong Shared Memory Primitives. In PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, pages 151--160, 1994.

Digital Library

[19]

J. Larus and C. Kozyrakis. Transactional Memory. Communications of the ACM, 51(7):80--88, 2008.

Digital Library

[20]

D. Lea. The Java Concurrency Package (JSR-166), 2009.

[21]

M. M. Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of fourteenth annual ACM symposium on Parallel algorithms and architectures, pages 73--82, 2002.

Digital Library

[22]

M. M. Michael. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE Transactions on Parallel and Distributed Systems, 15(6):491--504, 2004.

Digital Library

[23]

M. M. Michael and M. L. Scott. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. In PODC '96: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, pages 267--275, 1996.

Digital Library

[24]

Microsoft. Parallel Computing Developer Center, 2009.

[25]

M. Moir. Transparent Support for Wait-Free Transactions. In WDAG '97: Proceedings of the 11th International Workshop on Distributed Algorithms, pages 305--319, 1997.

Digital Library

[26]

N. Shavit and D. Touitou. Software Transactional Memory. In PODC '95: Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, pages 204--213, 1995.

Digital Library

[27]

H. Sundell and P. Tsigas. NOBLE: A Non-Blocking Inter-Process Communication Library. In Proceedings of the 6th Workshop on Languages, Compilers and Run-time Systems for Scalable Computers, Lecture Notes in Computer Science, 2002.

[28]

H. Sundell and P. Tsigas. Scalable and lock-free concurrent dictionaries. In SAC '04: Proceedings of the 2004 ACM symposium on Applied computing, pages 1438--1445, 2004.

Digital Library

[29]

H. Sundell and P. Tsigas. Fast and lock-free concurrent priority queues for multi-thread systems. Journal of Parallel and Distributed Computing, 65(5):609--627, 2005.

Digital Library

[30]

R. K. Treiber. Systems programming: Coping with parallelism. In Technical Report RJ 5118, April 1986.

[31]

P. Tsigas and Y. Zhang. Evaluating the Performance of Non-Blocking Synchronization on Shared-Memory Multiprocessors. ACM SIGMETRICS Performance Evaluation Review, 29(1):320--321, 2001.

Digital Library

[32]

P. Tsigas and Y. Zhang. Integrating Non-Blocking Synchronisation in Parallel Applications: Performance Advantages and Methodologies. In WOSP '02: Proceedings of the 3rd international workshop on Software and performance, pages 55--67, 2002.

Digital Library

[33]

V. Vafeiadis. Shape-Value Abstraction for Verifying Linearizability. In Proceedings of the 10th International Conference on Verification, Model Checking, and Abstract Interpretation, pages 335--348, 2009.

Digital Library

[34]

J. D. Valois. Lock-free linked lists using compare-and-swap. In PODC '95: Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, pages 214--222, 1995.

Digital Library

Cited By

Ziv OAiken AGolan-Gueta GRamalingam GSagiv M(2015)Composing concurrency controlACM SIGPLAN Notices10.1145/2813885.273797050:6(240-249)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2813885.2737970
Ziv OAiken AGolan-Gueta GRamalingam GSagiv MGrove DBlackburn S(2015)Composing concurrency controlProceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2737924.2737970(240-249)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2737924.2737970
Shafiei N(2013)Non-blocking Patricia Tries with Replace OperationsProceedings of the 2013 IEEE 33rd International Conference on Distributed Computing Systems10.1109/ICDCS.2013.43(216-225)Online publication date: 8-Jul-2013
https://dl.acm.org/doi/10.1109/ICDCS.2013.43
Show More Cited By

Index Terms

Supporting lock-free composition of concurrent data objects
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages

Recommendations

Supporting lock-free composition of concurrent data objects
PPoPP '10

Lock-free data objects offer several advantages over their blocking counterparts, such as being immune to deadlocks and convoying and, more importantly, being highly concurrent. But they share a common disadvantage in that the operations they provide ...
Supporting lock-free composition of concurrent data objects
PPoPP '10: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Lock-free data objects offer several advantages over their blocking counterparts, such as being immune to deadlocks and convoying and, more importantly, being highly concurrent. But they share a common disadvantage in that the operations they provide ...
Supporting Lock-Free Composition of Concurrent Data Objects: Moving Data between Containers

Lock-free data objects offer several advantages over their blocking counterparts, such as being immune to deadlocks, priority inversion, and convoying. They have also been shown to work well in practice. However, composing the operations they provide ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CF '10: Proceedings of the 7th ACM international conference on Computing frontiers

May 2010

370 pages

ISBN:9781450300445

DOI:10.1145/1787275

General Chair:
Nancy M. Amato
Texas A&M University, USA
,
Program Chairs:
Hubertus Franke
IBM Research, USA
,
Paul H.J. Kelly
Imperial College London, UK

Copyright © 2010 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

SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 May 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CF'10

Sponsor:

SIGMICRO

CF'10: Computing Frontiers Conference

May 17 - 19, 2010

Bertinoro, Italy

Acceptance Rates

CF '10 Paper Acceptance Rate 30 of 113 submissions, 27%;

Overall Acceptance Rate 273 of 785 submissions, 35%

Upcoming Conference

CF '25

Sponsor:
sigmicro

22nd ACM International Conference on Computing Frontiers

May 28 - 30, 2025

Cagliari , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
268
Total Downloads

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

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ziv OAiken AGolan-Gueta GRamalingam GSagiv M(2015)Composing concurrency controlACM SIGPLAN Notices10.1145/2813885.273797050:6(240-249)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2813885.2737970
Ziv OAiken AGolan-Gueta GRamalingam GSagiv MGrove DBlackburn S(2015)Composing concurrency controlProceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2737924.2737970(240-249)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2737924.2737970
Shafiei N(2013)Non-blocking Patricia Tries with Replace OperationsProceedings of the 2013 IEEE 33rd International Conference on Distributed Computing Systems10.1109/ICDCS.2013.43(216-225)Online publication date: 8-Jul-2013
https://dl.acm.org/doi/10.1109/ICDCS.2013.43
Turon A(2012)ReagentsACM SIGPLAN Notices10.1145/2345156.225408447:6(157-168)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2345156.2254084
Turon AVitek JLin HTip F(2012)ReagentsProceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2254064.2254084(157-168)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2254064.2254084
Dang NTsigas P(2011)Progress guarantees when composing lock-free objectsProceedings of the 17th international conference on Parallel processing - Volume Part II10.5555/2033408.2033426(148-159)Online publication date: 29-Aug-2011
https://dl.acm.org/doi/10.5555/2033408.2033426

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