Article

An almost non-blocking stack

Author:

Hans-J. BoehmAuthors Info & Claims

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

Pages 40 - 49

https://doi.org/10.1145/1011767.1011774

Published: 25 July 2004 Publication History

Abstract

Non-blocking data structure implementations can be useful for performance and fault-tolerance reasons. And they are far easier to use correctly in a signal- or interrupt-handler context.We describe a weaker class of "almost non-blocking" data structures, which block only if more than some number N of threads attempt to simultaneously access the same data structure. We argue that this gives much of the benefit of fully non-blocking data structures, particularly for signal or interrupt handlers.We present an almost non-blocking linked stack implementation which is efficiently implementable even on hardware providing a single word compare-and-swap operation, while potentially providing the same interface as a well-known fully non-blocking solution, which relies on a double-width compare-and-swap instruction. By making a platform-dependent choice between these, we can implement a signal-handler-safe stack or free-list abstraction that is both portable and exhibits uniformly high performance with any flavor of compare-and-swap instruction.

References

[1]

H.-J. Boehm. The atomic_ops atomic operations package. Included in {3}.]]

[2]

H.-J. Boehm. A garbage collector for C and C++. http://www.hpl.hp.com/personal/Hans_Boehm/gc/.]]

[3]

H.-J. Boehm. The qprof project. http://www.hpl.hp.com/research/linux/qprof.]]

[4]

H. Gao, J. Groote, and W. Hesselink. Efficient almost wait-free parallel accessible dynamic hashtables. http://www.archiv.org/abs/cs.DC/0303011.]]

[5]

M. B. Greenwald. Non-blocking Synchronization and System Design. PhD thesis, Stanford University, August 1999.]]

Digital Library

[6]

T. L. Harris. A pragmatic implementation of non-blocking linked-lists. Lecture Notes in Computer Science, 2180:300--314, 2001.]]

Digital Library

[7]

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

Digital Library

[8]

M. Herlihy. A methodology for implementing highly concurrent data structures. ACM Transactions on Programming Languages and Systems, 15(5):745--770, 1993.]]

Digital Library

[9]

M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Dynamic-sized lockfree data structures. Technical Report TR-2002-110, Sun Microsystems, 2002.]]

Digital Library

[10]

M. Herlihy, V. Luchangco, and M. Moir. Obstruction-free synchronization: Double-ended queues as an example. In Proceedings of the 23rd International Conference on Distributed Computing Systems, pages 522--529, 2003.]]

Digital Library

[11]

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, July 1990.]]

Digital Library

[12]

M. Hohmuth and H. Härtig. Pragmatic nonblocking synchronization for real-time systems. In Proceedings of the 2001 USENIX Annual Technical Conference, 2001.]]

Digital Library

[13]

IEEE and The Open Group. IEEE Standard 1003.1-2001. IEEE, 2001.]]

[14]

Intel Corporation. IA-32 Intel Architecture Software Developer's Manual - Volume 3: System Programming Guide. Intel Corporation, 2004.]]

[15]

P. Jayanti and S. Petrovic. Efficient and practical constructions of LL/SC variables. In Proceedings of the 22nd annual ACM Symposium on Principles of Distributed Computing, pages 285--294, August 2003.]]

Digital Library

[16]

L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Tranactions on Computers, C-28(9):690--691, September 1979.]]

Digital Library

[17]

D. Lea. Concurrency jsr-166 interest site. http://gee.cs.oswego.edu/dl/concurrency-interest.]]

[18]

D. Lea. The JSR-133 cookbook for compiler writers. http://gee.cs.oswego.edu/dl/jmm/cookbook.html.]]

[19]

M. M. Michael. Safe memory reclammation for dynamic lock-free objects using atomic reads and writes. In Proceedings of the 21st annual ACM Symposium on Principles of Distributed Computing, pages 21--30, August 2002.]]

Digital Library

[20]

M. Moir. Practical implementations of nonblocking synchronization primitives. In Proceedings of the 16th annual ACM Symposium on Principles of Distributed Computing, pages 219--228, August 1997.]]

Digital Library

[21]

D. R. Cheriton and K. J. Duda. A caching model of operating system kernel functionality. In Proceedings of First Symposium on Operating System Design and Implementation, pages 179--193, November 1994.]]

Digital Library

[22]

R. Treiber. Systems programming: Coping with parallelism. Technical Report RJ5118, IBM Almaden Research Center, 1986.]]

[23]

J. D. Valois. Lock-free linked lists using compare-and-swap. In Proceedings of the 14th annual ACM Symposium on Principles of Distributed Computing, pages 214--222, August 1995.]]

Digital Library

Cited By

Diep THa PFürlinger K(2023)A general approach for supporting nonblocking data structures on distributed-memory systemsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.11.006173(48-60)Online publication date: Mar-2023
https://doi.org/10.1016/j.jpdc.2022.11.006
Diep TFurlinger K(2021)Nonblocking Data Structures for Distributed-Memory Machines: Stacks as an Example2021 29th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)10.1109/PDP52278.2021.00012(9-17)Online publication date: Mar-2021
https://doi.org/10.1109/PDP52278.2021.00012
Shafiei N(2009)Non-blocking Array-Based Algorithms for Stacks and QueuesProceedings of the 10th International Conference on Distributed Computing and Networking10.1007/978-3-540-92295-7_10(55-66)Online publication date: 26-Mar-2009
https://dl.acm.org/doi/10.1007/978-3-540-92295-7_10
Show More Cited By

Index Terms

An almost non-blocking stack
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Concurrent programming structures
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Concurrency control

Recommendations

Static analysis of atomicity for programs with non-blocking synchronization
PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming

In concurrent programming, non-blocking synchronization is very efficient but difficult to design correctly. This paper presents a static analysis to show that code blocks are atomic, i.e., that every execution of the program is equivalent to one in ...
Nonblocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors

Most multiprocessors are multiprogrammed to achieve acceptable response time and to increase their utilization. Unfortunately, inopportune preemption may significantly degrade the performance of synchronized parallel applications. To address this ...
Grasping the gap between blocking and non-blocking transactional memories

Transactional memory (TM) is an inherently optimistic abstraction: it allows concurrent processes to execute sequences of shared-data accesses (transactions) speculatively, with an option of aborting them in the future. Early TM designs avoided using ...

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

10
Total Citations
View Citations
971
Total Downloads

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

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Diep THa PFürlinger K(2023)A general approach for supporting nonblocking data structures on distributed-memory systemsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.11.006173(48-60)Online publication date: Mar-2023
https://doi.org/10.1016/j.jpdc.2022.11.006
Diep TFurlinger K(2021)Nonblocking Data Structures for Distributed-Memory Machines: Stacks as an Example2021 29th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)10.1109/PDP52278.2021.00012(9-17)Online publication date: Mar-2021
https://doi.org/10.1109/PDP52278.2021.00012
Shafiei N(2009)Non-blocking Array-Based Algorithms for Stacks and QueuesProceedings of the 10th International Conference on Distributed Computing and Networking10.1007/978-3-540-92295-7_10(55-66)Online publication date: 26-Mar-2009
https://dl.acm.org/doi/10.1007/978-3-540-92295-7_10
Hart TMcKenney PBrown AWalpole J(2007)Performance of memory reclamation for lockless synchronizationJournal of Parallel and Distributed Computing10.1016/j.jpdc.2007.04.01067:12(1270-1285)Online publication date: 1-Dec-2007
https://dl.acm.org/doi/10.1016/j.jpdc.2007.04.010
Hart TMcKenney PBrown A(2006)Making lockless synchronization fastProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898953.1898956(21-21)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898953.1898956
Carroll TGrosu D(2006)A strategy proof mechanism for scheduling divisible loads in bus networks without control processorsProceedings 20th IEEE International Parallel & Distributed Processing Symposium10.1109/IPDPS.2006.1639263(8 pp.)Online publication date: 2006
https://doi.org/10.1109/IPDPS.2006.1639263
Hart TMcKenney PBrown A(2006)Making lockless synchronization fast: performance implications of memory reclamationProceedings 20th IEEE International Parallel & Distributed Processing Symposium10.1109/IPDPS.2006.1639261(10 pp.)Online publication date: 2006
https://doi.org/10.1109/IPDPS.2006.1639261
Boehm HSarkar VHall M(2005)Threads cannot be implemented as a libraryProceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation10.1145/1065010.1065042(261-268)Online publication date: 12-Jun-2005
https://dl.acm.org/doi/10.1145/1065010.1065042
Boehm H(2005)Threads cannot be implemented as a libraryACM SIGPLAN Notices10.1145/1064978.106504240:6(261-268)Online publication date: 12-Jun-2005
https://dl.acm.org/doi/10.1145/1064978.1065042
Alon NMerritt MReingold OTaubenfeld GWright R(2005)Tight bounds for shared memory systems accessed by Byzantine processesDistributed Computing10.1007/s00446-005-0125-818:2(99-109)Online publication date: 1-Dec-2005
https://dl.acm.org/doi/10.1007/s00446-005-0125-8

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