Design And Implementation Of Lock-free Data Structures Library

In the context of the continuous increasing in the number of computer CPU cores and the widespread popularity of multi-user Internet applications,how to improve the concurrency of computer programs to make full use of the advantages of multi-core CPUs and the waiting time of the network had become an important issue in software development.Data structure is an important part of computer program,in this context,the concurrency safety and performance of data structures had also become an important issue for software developers.Therefore,in order to meet the needs of software developers for the use of lock-free and concurrency-safe data structures in concurrent program development,a program library that provides lock-free data structures and corresponding operations are designed and implemented based on immutable data structures and the Go programming language.The basic design ideas of immutable data structures to achieve efficient performance by sharing most of the content,the basic methods of using immutable data structures to achieve concurrency-safe and lock-free data structures,and the Go runtime that is closely related to the implementation,especially for its memory management module and garbage collection module were firstly introduced.Then in the design process of this library,this paper analyzed and compared some existing data structures,selected the ones that are suitable to transform into immutable data structures,appropriately innovated and optimized them according to the design characteristics of immutable data structure,designed corresponding immutable solutions including immutable stacks,immutable binary search trees and immutable hash sets,and use them to design the corresponding lock-free data structures of the library.Then the Go programming language was used to implement the library according to the design.The test cases of the functional tests and non-functional tests were designed for the library,related tests were performed according to the test cases,and the performance of the implementation was analyzed according to the results of the benchmark tests.Through the analysis of the benchmark tests,this library has nice performance and can meet the requirements of software developers for lock-free data structures well.