Mikhail Fomitchev
ABSTRACT
Lock-free shared data structures implement distributed objects without the use of mutual exclusion, thus providing robustness and reliability. We present a new lock-free implementation of singly-linked lists. We prove that the worst-case amortized cost of the operations on our linked lists is linear in the length of the list plus the contention, which is better than in previous lock-free implementations of this data structure. Our implementation uses backlinks that are set when a node is deleted so that concurrent operations visiting the deleted node can recover. To avoid performance problems that would arise from traversing long chains of backlink pointers, we introduce flag bits, which indicate that a deletion of the next node is underway. We then give a lock-free implementation of a skip list dictionary data structure that uses the new linked list algorithms to implement individual levels. Our algorithms use the single-word C&S synchronization primitive.
- M. Fomitchev. Lock-free linked lists and skip lists. Master's thesis, York University, October 2003. http://www.cs.yorku.ca/?mikhail.Google Scholar
- K. A. Fraser. Practical lock-freedom PhD Thesis, University of Cambridge, December 2003. Technical Report UCAM-CL-TR-579.Google Scholar
- T. L. Harris. A pragmatic implementation of non-blocking linked-lists. In Proceedings of the 15th International Symposium on Distributed Computing, pages 300--314, 2001. Google ScholarDigital Library
- M. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems 13(1):124--149, 1991. Google ScholarDigital Library
- M. Herlihy. A methodology for implementing highly concurrent data objects. ACM Transactions on Programming Languages and Systems 15(5):745--770, 1993. Google ScholarDigital Library
- M. Herlihy and J. Wing. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems 12(3):463--492, 1990. Google ScholarDigital Library
- IBM System/370 extended architecture, principles of operation., 1983. IBM Publication No. SA22-7085.Google Scholar
- M. M. Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the 14th annual ACM Symposium on Parallel Algorithms and Architectures, pages 73--82, 2002. Google ScholarDigital Library
- M. M. Michael. Safe memory reclamation for dynamic lock-free objects using atomic reads and writes. In Proceedings of the 21st Annual Symposium on Principles of Distributed Computing, 2002. Google ScholarDigital Library
- M. M. Michael and M. L. Scott. Correction of a memory managemen method for lock-free data structures. Technical Report TR599, Computer Science Department, University of Rochester, 1995. Google ScholarDigital Library
- W. Pugh. Concurrent maintenance of skip lists. Technical Report CS-TR-2222, Computer Science Department, University of Maryland, 1990. Google ScholarDigital Library
- W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Communications of ACM, 33(6):668--676, 1990. Google ScholarDigital Library
- N. Shavi and I. Lotan. Skiplist-based concurrent priority queues. In Proc. 14th IEEE/ACM International Parallel and Distributed Processing Symposium, pages 263--268, 2000. Google ScholarDigital Library
- H. Sundell and P. Tsigas. Fast and lock-free concurrent priority queues for multi-thread systems. In Proceedings of the 17th IEEE/ACM International Parallel and Distributed Processing Symposium, pages 84--94, April 2003. Google ScholarDigital Library
- H. Sundell and P. Tsigas. Scalable and lock-free concurrent dictionaries. In Proceedings of the 19th ACM Symposium on Applied Computing, pages 1438--1445, March 2004. Google ScholarDigital Library
- R. K. Treiber. Systems programming: Coping with parallelism. Research report RJ 5118, IBM Almaden Research Center, 1986.Google Scholar
- J. D. Valois. Lock-free linked lists using compare-and-swap. In Proceedings of the 14th ACM Symposium on Principles of Distributed Computing, pages 214--222, 1995. Google ScholarDigital Library
Index Terms
- Lock-free linked lists and skip lists
Recommendations
Lock-free deques and doubly linked lists
We present a practical lock-free shared data structure that efficiently implements the operations of a concurrent deque as well as a general doubly linked list. The implementation supports parallelism for disjoint accesses and uses atomic primitives ...
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. ...
Fast and lock-free concurrent priority queues for multi-thread systems
We present an efficient and practical lock-free implementation of a concurrent priority queue that is suitable for both fully concurrent (large multi-processor) systems as well as pre-emptive (multi-process) systems. Many algorithms for concurrent ...
Comments