Abstract
We present a new non-blocking implementation of concurrent linked-lists supporting linearizable insertion and deletion operations. The new algorithm provides substantial benefits over previous schemes: it is conceptually simpler and our prototype operates substantially faster.
Acknowledgments
The work described in this paper was carried out during an internship with the Java Technology Research Group at Sun Labs. The design presented here is the result of much fruitful discussion with Dave Detlefs, Christine Flood,Alex Garthwaite,Stev e Heller,Nir Shavit and Guy Steele. The implementation and evaluation have similarly benefitted from feedback from Mike Burrows,Keir Fraser,Stev en Hand,Mark Moir and John Valois.
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
Nimar S. Arora, Robert D. Blumofe, and C. Greg Plaxton. Thread scheduling for multiprogrammed multiprocessors. In Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 119–129, Puerto Vallarta, Mexico, June 28-July 2, 1998. SIGACT/SIGARCH.
Michael Greenwald and David Cheriton. The synergy between non-blocking synchronization and operating system structure. In USENIX, editor, 2nd Symposium on Operating Systems Design and Implementation (OSDI’ 96), October 28-31, 1996. Seattle, WA, pages 123–136, Berkeley, CA, USA, October 1996. USENIX.
M Greenwald. Non-blocking synchronization and system design. PhD thesis, Stanford University, August 1999. Technical report STAN-CS-TR-99-1624.
Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124–149, January 1991.
Maurice Herlihy. A methodology for implementing highly concurrent data objects. ACM Transactions on Programming Languages and Systems, 15(5):745–770, November 1993.
Gerard J Holzmann. The moel checker SPIN. IEEE Transactions on Software Engineering, 23(5):279–295, May 1997.
Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463–492, July 1990.
Radu Iosif and Riccardo Sisto. dSPIN: A dynamic extension of SPIN. In Proc. of the 6th International SPIN Workshop, volume 1680 of LNCS, pages 261–276. Springer-Verlag, September 1999.
Richard Jones and Rafael Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley and Sons, July 1996.
Anthony LaMarca. A performance evaluation of lock-free synchronization protocols. In Proceedings of the Thirteenth Symposium on Principles of Distributed Computing, pages 130–140, 1994.
Henry Massalin and Calton Pu. A lock-free multiprocessor OS kernel. Technical Report CUCS-005-91, Columbia University, 1991.
Maged M. Michael and Michael L. Scott. Correction of a memory management method for lock-free data structures. Technical Report TR599, University of Rochester, Computer Science Department, December 1995.
Pentium Pro Family Developer’s Manual, volume 2, programmer’s reference manual. Intel Corporation, 1996. Reference number 242691-001.
John D. Valois. Lock-free linked lists using compare-and-swap. In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, pages 214–222, Ottawa, Ontario, Canada, 2-23 August 1995.
John D Valois. Personal communication. March 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Harris, T.L. (2001). A Pragmatic Implementation of Non-blocking Linked-lists. In: Welch, J. (eds) Distributed Computing. DISC 2001. Lecture Notes in Computer Science, vol 2180. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45414-4_21
Download citation
DOI: https://doi.org/10.1007/3-540-45414-4_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42605-9
Online ISBN: 978-3-540-45414-4
eBook Packages: Springer Book Archive