Transpose-based Non-blocking Self-organized Linked-lists

Self-organized linked-lists can be adjusted dynamically according to the access sequence,thereby reducing the average access time and improving its performance.If the accessed data exhibits strong locality of reference,self-organized linked-lists outperform traditional linked-lists.With the increasing popularity of multi-core processors,in order to take full advantage of multi-core,the study of concurrent data structures is more compelling.There have been many practical concurrent linked-list algorithms which have been applied in real world.However,the study of self-organized linked-list is still naive.On the basis of existing researches,this thesis has done the following work.1)We propose the first lock-free and wait-free self-organized linked-list algorithm based on the transpose rule.The basic idea of our algorithms is that the lookup method tries to mark the found node,and then tries to swap its predecessor.Besides,the other method would try to help the unfinished exchange if it noticed.2)We implement the first wait-free self-organized linked-list algorithm based on the move-to-front rule,where we use the wait-free enlist method to ensure that the whole algorithm is wait-freedom.3)Based on our research,we point out some weaknesses of the fast-path-slow-path method,i.e.,if the lock-free version of the algorithm is not compatible with the wait-free version,the fast-path-slow-path method does not work.We experimentally investigate our algorithms on CAIDA's data set which exhibits locality of reference.Experimental results show that: 1)the performance of the self-organized linked-lists is better than traditional lists.Specifically,the lock-free self-organized linked-list algorithm achieves higher throughput than the algorithm based on coarse-grained lock.2)Performances of MTF rule based self-organized algorithms outperform transpose rule based algorithms,which is consistent with the analysis of the sequential algorithm.3)The average performance of the wait-free MTF self-organized Linked-list algorithm is better than that of Harris algorithm,and it is more robust and more scalable.