Abstract
We apply the classic theory of linearizability to operations that must wait for some other thread to establish a precondition. We model such an operation as a request and a follow-up, each with its own linearization point. Linearization of the request marks the point at which a thread’s wishes become visible to its peers; linearization of the follow-up marks the point at which the request is fulfilled and the operation takes effect. By placing both linearization points within the purview of object semantics, we can specify not only the effects of operations, but also the order in which pending requests should be fulfilled.
We use the term dual data structure to describe a concurrent object implementation that may hold both data and reservations (registered requests). By reasoning separately about a request, its successful follow-up, and the period in-between, we obtain meaningful definitions of nonblocking dual data structures. As concrete examples, we present lock-free dualstacks and dualqueues, and experimentally compare their performance with that of lock-based and nonblocking alternatives.
This work was supported in part by NSF grants numbers EIA-0080124, CCR-9988361, and CCR-0204344, by DARPA/AFRL contract number F29601-00-K-0182, and by Sun Microsystems Laboratories.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
BBN Laboratories. Butterfly Parallel Processor Overview. BBN Report #6148, Version 1, Cambridge, MA (March 1986)
Herlihy, M., Luchangco, V., Moir, M.: Obstruction-Free Synchronization: Double-Ended Queues as an Example. In: Proceedings of the Twenty-Third International Conference on Distributed Computing Systems, Providence, RI (May 2003)
Herlihy, M.P., Wing, J.M.: Linearizability: A Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems 12(3), 463–492 (1990)
Herlihy, M.: Wait-Free Synchronization. ACM Transactions on Programming Languages and Systems 13(1), 124–149 (1991)
System/370 Principles of Operation. IBM Corporation (1983)
Lamport, L.: A New Solution of Dijkstra’s Concurrent Programming Problem. Communications of the ACM 17(8), 453–455 (1974)
Lamport, L.: Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM 21(7), 558–565 (1978)
Mellor-Crummey, J.M., Scott, M.L.: Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM Transactions on Computer Systems 9(1), 21–65 (1991)
Michael, M.M., Scott, M.L.: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. In: Proceedings of the Fifteenth ACM Symposium on Principles of Distributed Computing, Philadelphia, PA, May 1996, pp. 267–275 (1996)
Papadimitriou, C.H.: The Serializability of Concurrent Database Updates. Journal of the ACM 26(4), 631–653 (1979)
Radovic, Z., Hagersten, E.: Hierarchical Backoff Locks for Nonuniform Communication Architectures. In: Proc of the Ninth International Symposium on High Performance Computer Architecture, Anaheim, CA, February 2003, pp. 241–252 (2003)
Scott, M.L.: Non-blocking Timeout in Scalable Queue-based Spin Locks. In: Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, Monterey, CA, July 2002, pp. 31–40 (2002)
Treiber, R.K.: Systems Programming: Coping with Parallelism. RJ 5118, IBM Almaden Research Center (April 1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Scherer, W.N., Scott, M.L. (2004). Nonblocking Concurrent Data Structures with Condition Synchronization. In: Guerraoui, R. (eds) Distributed Computing. DISC 2004. Lecture Notes in Computer Science, vol 3274. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30186-8_13
Download citation
DOI: https://doi.org/10.1007/978-3-540-30186-8_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23306-0
Online ISBN: 978-3-540-30186-8
eBook Packages: Springer Book Archive