Research On Wait-free Self-organizing Linked-lists

Self-organizing linked-list is a practical data structure,which can adjust the list structure dynamically according to the access sequence,and adapt to the access pattern.The aim is reducing the average access time and improving the performance of the linked list.If the data being accessed has locality,the self-organizing lists have stronger performance advantage than lists that are not self-organizing.Applying the selforganizing linked-lists into concurrent environments can take full advantage of multicore processors to achieve higher performance.The non-blocking implementation of concurrent self-organizing lists are more reliable and robust than lock-based lists.This paper proposes a novel wait-free self-organizing linked-list.In order to acquire it,a lock-free version is developed.Experiments show that the new wait-free list is pragmatic.The contributions of this paper are as follows:(1)Summarize the existing concurrent self-organizing lists,including lock-free self-organizing lists based on Move-To-Front and Transpose rules.(2)Propose a correct lock-free algorithm based on Move-To-Front rule,and then propose a wait-free self-organizing list which guarantees every process makes progress in bounded steps.(3)Give the correctness proof of the new algorithm on linearizablity,lock-freedom,wait-freedom,and self-organizing property.(4)Analyze the performance of the existing wait-free linked-lists.The experimental results show that the new algorithm outperforms others when the input sequence has locality.