Research On Wait-free Stack

Concurrent stacks are widely used in parallel applications and operating systems.Concurrent stacks support push and pop operations,and are able to satisfy the LIFO semantics.Concurrent stack algorithms can take full advantage of multicore processors to achieve higher performance.Existing concurrent stack algorithm has two main ways to achieve,including locking and general construction,but its performance is not satisfactory.Lock-based approach is difficult to achieve high parallelism,and delay or stop of some threads will block the operation of other threads.And the implementation of general construction is complex,low efficiency and low usable.So it is imperative to study the practical concurrency stack algorithm.Wait-free feature ensures that all threads will be able to complete in a limited number of steps,and has stronger fault tolerance in engineering practice.Therefore,even if a thread suddenly crashes,it will not affect other threads.On the basis of existing researches,this paper studies the blocking and nonblocking concurrent stacks,does the following work:(1)proposes and implements a wait-free concurrent stack algorithm,the basic idea of this paper is that all the push and pull operations need to insert a new node into the head of the list.After inserting the node,it needs to traverse the linked list to find the matching node and find the correct node.This operation uses the idea of reference counting.At the same time,the algorithm uses the help mechanism to ensure that the insertion of the node is waitfree,so as to ensure that the whole algorithm is wait-free.At present,there is no stack based on the idea of counting,so it has certain practical value in the research of concurrency data structure.(2)this paper summarizes the existing concurrent stack algorithms,and gives a detailed introduction to the realization and advantages and disadvantages of the algorithm.(3)Moreover discusses the necessity of correctness proof of the procedure.The correctness of the wait-free stack algorithm is proved from the aspects of linearizable and wait-free.