A Copy-based Non-blocking Self-organized Linked-list

Self-organized linked list is data structure, which has edification significance andpractical value. It can respond to changes in access mode, and adjust its structure toimprove performance. And it has been successfully applied to data compressionalgorithm, the convex hull algorithm and calculate the maximum point. As thedevelopment of computer multi-core technology, in order to utilize the computingpower of the multi-cores efficiently, we need to design an efficient concurrencyself-organized linked list.Non-blocking data structure do not use mutual exclusion to achieve concurrent,making the exclusive resource can be accessed by multiple threads simultaneously.And it can void the problems cause by mutual exclusion such as dead lock, priorityinversion and convoy. Non-blocking data structure guarantees that some threads willcomplete within in finite number of steps regardless of other threads’ actions, andoffers better robustness, reliable, and performance. So we propose to achievenon-blocking self-organized linked list.This paper presents a copy-based non-blocking self-organized linked-list. Wemaintain a copy node for the nodes in the list, and by moving the copy node toachieve self-organization of the linked list. The list is divided into two parts:disorderly copy nodes and orderly data nodes, the data node can be quickly accessedthrough the corresponding copy node. And data nodes apply Michael’s algorithm,copy nodes apply MTF rule. The linked list structure is simple, and can guaranteelinearizable and non-blocking.Our experimental results show that our algorithm performs well for long linkedlists with high percentages of search operations. And our algorithm provides the bestperformance in our sequence of experimental data, with90percentages of search andthe range of key values is4096.