Håkan Sundell
ABSTRACT
We present an efficient and practical lock-free implementation of a concurrent dictionary that is suitable for both fully concurrent (large multi-processor) systems as well as pre-emptive (multi-process) systems. Many algorithms for concurrent dictionaries are based on mutual exclusion. However, mutual exclusion causes blocking which has several drawbacks and degrades the system's overall performance. Non-blocking algorithms avoid blocking, and are either lockfree or wait-free. Our algorithm is based on the randomized sequential list structure called Skiplist, and implements the full set of operations on a dictionary that is suitable for practical settings. In our performance evaluation we compare our algorithm with the most efficient non-blocking implementation of dictionaries known. The experimental results clearly show that our algorithm outperforms the other lockfree algorithm for dictionaries with realistic sizes, both on fully concurrent as well as pre-emptive systems.
- J. Aspnes and M. Herlihy. Wait-free data structures in the asynchronous PRAM model. In ACM Symposium on Parallel Algorithms and Architectures, pages 340--349, 2000. Google Scholar
Digital Library
- L. Boug, J. Gabarr, and X. Messeguer. Concurrent AVL revisited: Self-balancing distributed search trees. Research Report RR95--45, LIP, ENS Lyon, 1995.Google Scholar
- T. L. Harris. A pragmatic implementation of non-blocking linked lists. In Proceedings of the 15th International Symposium of Distributed Computing, pages 300-314, Oct. 2001. Google ScholarDigital Library
- M. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 11(1):124--149, Jan. 1991. 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
- M. M. Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the 14th 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 ACM Symposium on Principles of Distributed Computing, pages 21--30, 2002. Google ScholarDigital Library
- M. M. Michael and M. L. Scott. Correction of a memory management method for lock-free data structures. Technical report, Computer Science Department, University of Rochester, 1995. Google ScholarDigital Library
- W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33(6):668--676, 1990. Google ScholarDigital Library
- R. Rajkumar. Real-time synchronization protocols for shared memory multiprocessors. In Proceedings of the 10th International Conference on Distributed Computing Systems, pages 116--123, 1990.Google ScholarCross Ref
- L. Sha, R. Rajkumar, and J. Lehoczky. Priority inheritance protocols: An approach to real-time synchronization. IEEE Transactions on Computers, 39(9):1175--1185, Sept. 1990. Google ScholarDigital Library
- A. Silberschatz and P. Galvin. Operating System Concepts. Addison Wesley, 1994. Google ScholarDigital Library
- H. Sundell and P. Tsigas. NOBLE: A non-blocking inter-process communication library. In Proceedings of the 6th Workshop on Languages, Compilers and Run-time Systems for Scalable Computers, Lecture Notes in Computer Science. Springer Verlag, 2002.Google Scholar
- H. Sundell and P. Tsigas. Fast and lock-free concurrent priority queues for multi-thread systems. In Proceedings of the 17th International Parallel and Distributed Processing Symposium. IEEE press, 2003. Google ScholarDigital Library
- H. Sundell and P. Tsigas. Scalable and lock-free concurrent dictionaries, extended version. Technical report, Computing Science, Chalmers University of Technology, Dec. 2003.Google Scholar
- P. Tsigas and Y. Zhang. Integrating non-blocking synchronisation in parallel applications: Performance advantages and methodologies. In Proceedings of the 3rd ACM Workshop on Software and Performance, pages 55--67, ACM Press, 2002. Google ScholarDigital Library
- J. D. Valois. Lock-Free Data Structures. PhD thesis, Rensselaer Polytechnic Institute, Troy, New York, 1995. Google ScholarDigital Library
Index Terms
- Scalable and lock-free concurrent dictionaries
Recommendations
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 ...
Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems
IPDPS '03: Proceedings of the 17th International Symposium on Parallel and Distributed ProcessingWe 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 ...
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 ...
Comments