A more pragmatic implementation of the lock-free, ordered, linked list
Pages 457 - 459
Abstract
The lock-free, ordered, singly linked list as proposed in [5, 8] is a textbook example of a concurrent data structure [6, 10]. The data structure supports lock-free insertion and deletion, and wait-free contains operations on items identified by a unique key. The lock-free implementation is actually quite subtle. The ordering condition and a relaxed invariant makes it possible to do with a single-word Compare-And-Swap operation (CAS), and all operations can be shown to be linearizable even though linearization does not always happen at fixed points in the code. The lock-free data structure has many direct and indirect applications, notably in the implementation of concurrent skiplists and hash tables [8, 9, 11, 12].
References
[1]
Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. 2015. Asynchronized Concurrency: The Secret to Scaling Concurrent Search Da ta Structures. In 20th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). 631--644.
[2]
Mikhail Fomitchev and Eric Ruppert. 2004. Lock-free linked lists and skip lists. In Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing (PODC). 50--59.
[3]
Vincent Gramoli. 2015. More than you ever wanted to know about synchronization: synchrobench, measuring the impact of the synchronization on concurrent algorithms. In 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 1--10.
[4]
Rachid Guerraoui and Vasileios Trigonakis. 2016. Optimistic Concurrency with OPTIK. In 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP). 8:1--18:12.
[5]
Timothy L. Harris. 2001. A Pragmatic Implementation of Non-blocking Linked-Lists. In 15th International Conference on Distributed Computing (DISC). 300--314.
[6]
Maurice Herlihy and Nir Shavit. 2012. The Art of Multiprocessor Programming (revised 1st ed.). Morgan Kaufmann Publishers.
[7]
Maxim Khizhinsky. 2020. CDS C++ library. (2020). Retrieved from https://github.com/khizmax/libcds.
[8]
Maged M. Michael. 2002. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). 73--82.
[9]
William Pugh. 1990. Skip Lists: A Probabilistic Alternative to Balanced Trees. Commun. ACM 33, 6 (1990), 668--676.
[10]
Michael L. Scott. 2013. Shared-Memory Synnchronization. Morgan & Claypool Publisher.
[11]
Ori Shalev and Nir Shavit. 2006. Split-ordered lists: Lock-free extensible hash tables. Journal of the ACM 53, 3 (2006), 379--405.
[12]
Håkan Sundell and Philippas Tsigas. 2005. Fast and lock-free concurrent priority queues for multi-thread systems. Journal of Parallel and Distributed Computing 65, 5 (2005), 609--627.
[13]
Jesper Larsson Träff and Manuel Pöter. 2020. A more Pragmatic Implementation of the Lock-free, Ordered, Linked List. arXiv:2010.15755. (2020).
Index Terms
- A more pragmatic implementation of the lock-free, ordered, linked list
Recommendations
Lock-Free Transactional Transformation for Linked Data Structures
Special Issue on SPAA 2016Nonblocking data structures allow scalable and thread-safe access to shared data. They provide individual operations that appear to execute atomically. However, it is often desirable to execute multiple operations atomically in a transactional manner. ...
Transactional lock-free execution of lock-based programs
Special Issue: Proceedings of the 10th annual conference on Architectural Support for Programming Languages and Operating SystemsThis paper is motivated by the difficulty in writing correct high-performance programs. Writing shared-memory multi-threaded programs imposes a complex trade-off between programming ease and performance, largely due to subtleties in coordinating access ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2021
507 pages
Copyright © 2021 Owner/Author.
Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 17 February 2021
Check for updates
Badges
Qualifiers
- Poster
Conference
PPoPP '21: 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
February 27, 2021
Virtual Event, Republic of Korea
Acceptance Rates
PPoPP '21 Paper Acceptance Rate 31 of 150 submissions, 21%;
Overall Acceptance Rate 230 of 1,014 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 327Total Downloads
- Downloads (Last 12 months)50
- Downloads (Last 6 weeks)9
Reflects downloads up to 10 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in