Scalable and lock-free concurrent dictionaries

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.

REFERENCES

• 1: J. Aspnes , M. Herlihy, Wait-free data structures in the asynchronous PRAM model, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.340-349, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97701]
• 2: L. Boug, J. Gabarr, and X. Messeguer. Concurrent AVL revisited: Self-balancing distributed search trees. Research Report RR95--45, LIP, ENS Lyon, 1995.
• 3: Timothy L. Harris, A Pragmatic Implementation of Non-blocking Linked-Lists, Proceedings of the 15th International Conference on Distributed Computing, p.300-314, October 03-05, 2001
• 4: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 5: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 6: Maged M. Michael, High performance dynamic lock-free hash tables and list-based sets, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564881]
• 7: Maged M. Michael, Safe memory reclamation for dynamic lock-free objects using atomic reads and writes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571829]
• 8: Maged M. Michael , Michael L. Scott, Correction of a Memory Management Method for Lock-Free Data Structures, University of Rochester, Rochester, NY, 1995
• 9: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 10: 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.
• 11: L. Sha , R. Rajkumar , J. P. Lehoczky, Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, v.39 n.9, p.1175-1185, September 1990 [doi>10.1109/12.57058]
• 12: Abraham Siberschatz , Peter B. Galvin, Operating System Concepts, 4th Ed., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 13: 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.
• 14: Håkan Sundell , Philippas Tsigas, Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.84.2, April 22-26, 2003
• 15: H. Sundell and P. Tsigas. Scalable and lock-free concurrent dictionaries, extended version. Technical report, Computing Science, Chalmers University of Technology, Dec. 2003.
• 16: Philippas Tsigas , Yi Zhang, Integrating non-blocking synchronisation in parallel applications: performance advantages and methodologies, Proceedings of the 3rd international workshop on Software and performance, July 24-26, 2002, Rome, Italy [doi>10.1145/584369.584378]
• 17: John David Valois, Lock-free data structures, Rensselaer Polytechnic Institute, Troy, NY, 1996

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Experimentation, Performance, Reliability

Keywords:
concurrent, dictionary, non-blocking, shared memory