Abstract
The computer industry is examining the use of strong syn- chronization operations such as double compare-and-swap (DCAS) as a means of supporting non-blocking synchronization on tomorrow’s mul- tiprocessor machines. However, before such a primitive will be incorpo- rated into hardware design, its utility needs to be proven by developing a body of effective non-blocking data structures using DCAS.
In a previous paper, we presented two linearizable non-blocking imple- mentations of concurrent deques (double-ended queues) using the DCAS operation. These improved on previous algorithms by nearly always al- lowing unimpeded concurrent access to both ends of the deque while correctly handling the difficult boundary cases when the deque is empty or full. A remaining open question was whether, using DCAS, one can design a non-blocking implementation of concurrent deques that allows dynamic memory allocation but also uses only a single DCAS per push or pop in the best case.
This paper answers that question in the affirmative. We present a new non-blocking implementation of concurrent deques using the DCAS operation. This algorithm provides the benefits of our previous techniques while overcoming drawbacks. Like our previous approaches, this implementation relies on automatic storage reclamation to ensure that a storage node is not reclaimed and reused until it can be proved that the node is not reachable from any thread of control. This algorithm uses a linked-list representation with dynamic node allocation and therefore does not impose a fixed maximum capacity on the deque. It does not equire the use of a “spare bit” in pointers. In the best case (no interference), it requires only one DCAS per push and one DCAS per pop. We also sketch a proof of correctness.
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
Y. Afek, M. Merritt, G. Taubenfeld, and D. Touitou. Disentangling multi-object operations. In Proc. 16th ACM Symp. Principles of Dist. Computing, pages 111–120, August 1997. Santa Barbara, CA.
O. Agesen, D. Detlefs, C. Flood, A. Garthwaite, P. Martin, N. Shavit, and G. Steele. DCAS-based concurrent deques. In Proc. 12th ACM Symp. Parallel Algorithms and Architectures (to appear), July 2000.
N. S. Arora, R. Blumofe, and C. G. Plaxton. Thread scheduling for multipro-grammed multiprocessors. In Proc. 10th ACM Symp. Parallel Algorithms and Architectures, 1998.
H. Attiya and E. Dagan. Universal operations: Unary versus binary. In Proc. 15th ACM Symp. Principles of Dist. Computing, May 23-26 1996. Philadelphia, PA.
Hagit Attiya, Nancy Lynch, and Nir Shavit. Are wait-free algorithms fast? Journal of the ACM, 41(4):725–763, July 1994.
Hagit Attiya and Ophir Rachman. Atomic snapshots in O(n log n) operations. SIAM Journal on Computing, 27(2):319–340, March 1998.
G. Barnes. A method for implementing lock-free shared data structures. In Proc. 5th ACM Symp. Parallel Algorithms and Architectures, pages 261–270, June 1993.
B. N. Bershad. Practical considerations for non-blocking concurrent objects. In Proc. 13th IEEE International Conf. on Distributed Computing Systems, pages 264–273. IEEE Computer Society Press, May 25-28 1993. Los Alamitos, CA.
M. Greenwald. Non-Blocking Synchronization and System Design. PhD thesis, Stanford University Technical Report STAN-CS-TR-99-1624, Palo Alto, CA, 1999.
M. B. Greenwald and D. R. Cheriton. The synergy between non-blocking synchro-nization and operating system structure. In 2nd Symp. Operating Systems Design and Implementation, pages 123–136, October 28-31 1996. Seattle, WA.
M. Herlihy. A methodology for implementing highly concurrent data structures. ACM Trans. Programming Languages and Systems, 15(5):745–770, November 1993.
M. Herlihy and J. Moss. Transactional memory: Architectural support for lock-free data structures. Technical Report CRL 92/07, Digital Equipment Corporation, Cambridge Research Lab, 1992.
M. P. Herlihy. Wait-free synchronization. ACM Trans. Programming Languages and Systems, 13(1):123–149, January 1991.
M. P. Herlihy and J. M. Wing. Linearizability: A correctness condition for concur-rent objects. ACM Trans. Programming Languages and Systems, 12(3):463–492, July 1990.
D. E. Knuth. The Art of Computer Programming: Fundamental Algorithms. Addison-Wesley, 2nd edition, 1968.
H. Massalin and C. Pu. A lock-free multiprocessor OS kernel. Technical Report TR CUCS-005-9, Columbia University, New York, NY, 1991.1j
M. M. Michael and M. L. Scott. Correction of a memory management method for lock-free data structures. Technical Report TR 599, Computer Science Depart-ment, University of Rochester, 1995.
Motorola. MC68020 32-Bit Microprocessor User’s Manual. Prentice-Hall, 1986.
Motorola. MC68030 User’s Manual. Prentice-Hall, 1989.
Martin C. Rinard. Effective fine-grain synchronization for automatically paral-lelized programs using optimistic synchronization primitives. ACM Trans. Com-puter Systems, 17(4):337–371, November 1999.
N. Shavit and D. Touitou. Software transactional memory. Distributed Computing, 10(2):99–116, February 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Detlefs, D.L., Flood, C.H., Garthwaite, A.T., Martin, P.A., Shavit, N.N., Steele, G.L. (2000). Even Better DCAS-Based Concurrent Deques. In: Herlihy, M. (eds) Distributed Computing. DISC 2000. Lecture Notes in Computer Science, vol 1914. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-40026-5_4
Download citation
DOI: https://doi.org/10.1007/3-540-40026-5_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41143-7
Online ISBN: 978-3-540-40026-4
eBook Packages: Springer Book Archive