The Research Of Binary Search Tree Algorithm Based On Lock-Free Method

With the development of multi-/many-core technology,high concurrency data structure becomes a research hotspot in concurrent programming.The binary search tree is widely used and plays an important role in the concurrent data structure.The design and implementation of highly concurrent lock-free binary search tree algorithm structure will provide strong support for modern concurrent programming.For the research of binary search tree algorithm,an important issue is how to achieve multithreaded synchronization access of shared resources.Synchronization with the locking mechanism is common in traditional solutions to ensure secure access of threads,but it is easy to cause problems such as deadlock and lock competition,which leads to the inefficiency of the algorithm.In view of the problem caused by the use of the lock mechanism for the binary search tree algorithm,this paper proposes a novel lock-free algorithm,which can implement the lock-free operations in the asynchronous shared memory system,such as search,insert and delete operations,using compare and swap(CAS).Using an external(called leaf-facing)search tree,the algorithm of this paper does not require to remove two children with the same position,hence improve the efficiency of the delete operation.Unlike the studies of handling the inside node in a binary search tree,the algorithm of this paper uses the whole idea to handle the insert and delete operations by operating of the subtree.This paper presents the design details of the lock-free binary search tree algorithm,carries out experiment under various conditions(such as different tree sizes,workload distributions and contention degrees)and compares the algorithm of this paper with lock-based algorithm of Bronson et al and lock-free algorithm of Ellen et al by throughput.Experiment results show that the throughput of the algorithm of this paper outperforms that of the other two concurrent BST algorithms when the number of threads is more than 4.It can effectively reduce the contention between the update operations(insert or delete operations).The algorithm of this paper will be competitive when the concurrency is high.