Research On Non-blocking Self-organized Linked-lists

Self-organized linked list is proposed for the search problem, it has a rule or algorithm for changing the position of nodes when responding to an unknown input request sequence. The rule or algorithm can get the structure of the linked list into a state that will take advantage of the properties of the input requeset sequence, and reduce the overall cost of operations, improve the performance of the linked list. As the development of computer hardware technology, in order to utilize the computing power of multi-processors efficiently, we need to design a concurrent and shared self-organized linked list.Non-blocking data structure do not use mutual exclusion. It can be accessed by multiple threads simultaneously, and can avoid performance problems due to unpredictable delays while threads are within cirtical sections. Non-blocking data structure guarantees that infinitely often some thread can finish its method calls in a finite number of steps. It's more robust and reliable.This paper presents two non-blocking self-organized linked lists, the read-only non-blocking self-organized linked list and the read-write non-blocking self-organized linked list. The two linked lists are all linearizable. The read-write non-blocking self-organized linked list uses MTF rule, and it's the first known non-blocking self-organized linked list supporting all common operations on a dictionary.The read-only non-blocking self-organized linked list introduces the concept of"hot"elements. Each thread has a hot array, the hot array can be used to guide the self-organized behaviors. In addition, the hot arrays can improve the search performance of hot elements and may make efficient use of cache.The read-write non-blocking self-organized linked list is composed of data nodes and operation nodes. Threads executing related operations can communicate with each other through operation nodes. They can get others'results and tell others their result. These guarantee the non-blocking property and the correctness of the operations. The operation nodes can also act as data nodes, making MTF operations accurate and timely.Our experimental results show that when the input request sequence has local property , the two new linked list outperform the known non-blocking linked lists without self-organized behaviors and the coarse-grained blocking self-organized linked list.