Research On Non-blocking Unordered Lists

With the rapid development of computer hardware, multicore processors have come into wide use. So the application of concurrent programming techniques can greatly improve performance. Although it can ensure the mutual exclusion of resources and the correctness of concurrent programs to use lock, the increase in the number of threads and intense competition may cause several threads waiting and even deadlocks. Of course, the non-blocking algorithms can avoid deadlocks and provide better scalability. However, it should be remembered a non-blocking algorithms may mean a more complex programming and the difficulty to maintain. What's more, in case of less competition, the complexity of structure may result in a performance lower than a blocking algorithm. Nonetheless, the ability to create low-latency non-blocking data structures is valuable.This paper made a research into achievement of the non-blocking unordered lists which is the basic data structure, including a concurrent lock-free lists algorithm, two wait-free lists and a compatibility adaptive algorithm which can keep the wait-free character and a good performance. The abstract collection corresponding these lists is a unorder set without duplicate values. The main idea is a node consists of the information of the key and the operation. Threads executing related operations can communication with each other through shared nodes, and the lists can be achieved non-blocking by helping each other threads. In addition, the Contains method is designed a read-only operation in order to improve the overall performance.In the experiment, we change variable parameters that include the number of threads, the ratio of operations and the key range and compare with some classical algorithms to analysis and evaluation for performance. The experiment results show that when the number of threads is more, the ratio of lookup is high and the length of the lists is long, the performance of the proposed algorithms is outstanding.